Apparatus and method of traversing acceleration structure in ray tracing system

Patent metadata

Field	Value
Publication number	US-10049488-B2
Application number	US-201514722887-A
Country	US
Kind code	B2
Filing date	May 27, 2015
Priority date	May 27, 2014
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

A method of traversing an acceleration structure (AS) in a ray tracing system includes obtaining information about child nodes of a target node included in the AS; determining whether each of the child nodes intersects a ray based on the obtained information; determining a next target node among at least one child node that intersects the ray; and performing an operation corresponding to a type of the determined next target node.

First claim

What is claimed is:

1. A processor-based image rendering method of traversing an acceleration structure (AS) in a ray tracing system, the method comprising:
obtaining, by at least one processor, information from a data structure about child nodes of a target node included in an acceleration structure (AS) in which the obtained information is preset in the data structure, wherein the data structure is generated by an AS generator, is stored in an external memory and includes memory addresses at which the child nodes are stored, indices indicating the child nodes, type information of the child nodes and bounding box information of the child nodes;
determining, simultaneously, by the at least one processor, whether each of the child nodes intersects a ray based on the obtained information;
determining, by the at least one processor, a next target node to be traversed and an operation to be performed thereon among at least one child node that intersects the ray after the determining of whether each of the child nodes intersects the ray; and
performing, by the at least one processor, an operation corresponding to a type of the determined next target node,
wherein the simultaneously determining whether each of the child nodes intersect the ray based on the obtained information from the data structure is performed in one traversal process.

2. The method of claim 1 , wherein the determining of whether each of the child nodes intersects the ray comprises simultaneously performing intersection determinations respectively determining whether each of the child nodes intersect the ray based on the obtained information.

3. The method of claim 1 , wherein the determining of whether each of the child nodes intersects the ray comprises simultaneously performing intersection determinations respectively determining whether a first child node and a second child node intersect the ray based on obtained information about the first child node and the second child node.

4. The method of claim 1 , wherein the determining of the next target node comprises:
in response to there being only one child node that intersects the ray, determining the one child node as the next target node; and
in response to there being two or more child nodes that intersect the ray, determining a child node having a shortest intersection distance to the ray among the two or more child nodes as the next target node.

5. The method of claim 1 , wherein the determining of the next target node comprises, in response to there being no child node that intersects the ray:
extracting from the AS any one node among nodes that are not subordinate to the target node; and
determining the extracted node as the next target node.

6. The method of claim 1 , wherein the performing of the operation corresponding to the type of the determined next target node comprises:
in response to the next target node being an inner node, moving to at least one child node of the next target node; and
in response to the next target node being a leaf node, performing an intersection test to determine whether at least one primitive included in the leaf node intersects the ray.

7. The method of claim 6 , wherein the performing of the operation corresponding to the type of the determined next target node further comprises, based on a result of the intersection test, traversing another child node that intersects the ray.

8. The method of claim 6 , the determining of whether the at least one primitive included in the leaf node intersects the ray comprises determining whether a preset bounding box of the at least one primitive included in the leaf node intersects the ray.

9. The method of claim 1 , further comprising, in response to the target node included in a root node being a leaf node:
dividing at least one primitive included in the target node; and
generating a child node of the target node based on the divided at least one primitive.

10. A non-transitory computer-readable storage medium storing instructions for causing a computer to perform the method of claim 1 .

11. A processor-based image rendering apparatus for traversing an acceleration structure (AS) in a ray tracing system, the apparatus comprising:
at least one processor configured to execute ray tracing operations that include:
obtain information from a data structure about child nodes of a target node included in the AS in which the obtained information is preset in the data structure, wherein the data structure is generated by an AS generator, is stored in an external memory and includes memory addresses at which the child nodes are stored, indices indicating the child nodes, type information of the child nodes and bounding box information of the child nodes;
simultaneously determine whether each of the child nodes intersects a ray based on the obtained information in the data structure;
determine a next target node among at least one child node that intersects the ray, and perform an operation corresponding to a type of the determined next target node, and
render an image for display based on a pixel value of the image generated based on the performed operation,
wherein the simultaneously determining whether each of the child nodes intersect the ray based on the obtained information from the data structure is performed in one traversal process.

12. The apparatus of claim 11 , wherein the at least one processor simultaneously determines whether each of the child nodes intersects the ray by simultaneously performing intersection determinations respectively determining whether each of the child nodes intersect the ray based on the obtained information.

13. The apparatus of claim 11 , wherein the at least one processor simultaneously determines whether each of the child nodes intersects the ray includes by simultaneously performing intersection determinations respectively determining whether a first child node and a second child node intersect the ray based on obtained information about the first child node and the second child node.

14. The apparatus of claim 11 , wherein, to determine the next target node, the at least one processor is further configured to:
in response to there being only one child node that intersects the ray, determine the one child node as the next target node; and
in response to there being two or more child nodes that intersect the ray, determine a child node having a shortest intersection distance to the ray among the two or more child nodes as the next target node.

15. The apparatus of claim 11 , wherein, to determine the next target node, the at least one processor is further configured to, in response to there being no child node that intersects the ray, extract any one node among nodes that are not subordinate to the target node from the AS, and determine the extracted node as the next target node.

16. The apparatus of claim 11 , wherein the at least one processor is further configured to:
in response to the next target node being an inner node, move to at least one child node of the next target node; and
in response to the next target node being a leaf node, perform an intersection test to determine whether at least one primitive included in the leaf node intersects the ray.

17. The apparatus of claim 16 , wherein the at least one processor is further configured to, based on a result of the intersection test, traverse another child node that intersects the ray.

18. The apparatus of claim 16 , wherein the at least one processor is further configured to determine whether the least one primitive included in the leaf node interse

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Jaedon
• Shin Youngsam
• Lee Wonjong
• Hwang Seokjoong

Classifications

• G06T2210/52

  Parallel processing · CPC title

• G06T2210/12

  Bounding box · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title