Apparatus and method of using acceleration structure in ray tracing

Patent metadata

Field	Value
Publication number	US-9728000-B2
Application number	US-201414260754-A
Country	US
Kind code	B2
Filing date	Apr 24, 2014
Priority date	Oct 22, 2013
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

An apparatus and a method of using an acceleration structure in ray tracing, and a method of ray tracing are provided. The method involves setting a bit stack value of a level of an acceleration structure, moving to a child node among the ray-crossing child nodes and setting a route value of a corresponding level of the acceleration structure, and determining a pop level based on one or more bit stack values.

First claim

What is claimed is:

1. A method of using an acceleration structure for ray tracing, the method comprising:
setting a bit stack value of a level of an acceleration structure based on a number of ray-crossing child nodes;
moving to a child node among the ray-crossing child nodes and setting a route value of a corresponding level of the acceleration structure; and
in response to the child node being a leaf node or a derivative node of the child node not intersecting a ray, determining a pop level based on relative level among levels having one or more bit stack values,
wherein the bit stack value indicates whether there is an untraversed child node among the ray-crossing child nodes at the level, the bit stack value has a first value that indicates there is no untraversed child node and a second value that indicates that there is an untraversed child node among the ray-crossing child nodes,
wherein the determining of the pop level comprises determining a highest level among levels having a bit stack value that corresponds to the second value as the pop level.

2. The method of claim 1 , further comprising:
determining the number of ray-crossing child nodes before setting the bit stack value;
moving from a root node to the pop level based on the route value;
moving from the pop level to an untraversed child node among the ray-crossing child nodes based on the route value of the pop level and changing the route value of the pop level; and
traversing through the acceleration structure from the untraversed child node.

3. The method of claim 2 , wherein the setting of the bit stack value comprises, in response to the number of the ray-crossing child nodes being 1, setting the bit stack value of a level corresponding to a parent node thereof to a first value, and
in response to the number of the ray-crossing child nodes being 2 or greater, setting the bit stack value of a level corresponding to a parent node thereof to a second value.

4. The method of claim 2 , wherein the setting of the route value comprises, in response to moving to a first child node among the ray-crossing child nodes, setting the route value of the level corresponding to a parent node thereof to a first value, and,
in response to moving to a second child node among the ray-crossing child nodes, setting the route value of the level corresponding to a parent node thereof to a second value.

5. The method of claim 2 , wherein the setting of the route value comprises, in response to the number of the ray-crossing child nodes being N, setting the route value by using log N bits.

6. The method of claim 2 , wherein the moving to the pop level comprises moving from the root node of the acceleration structure to the pop level by moving through child nodes according to the route value of the level.

7. The method of claim 2 , wherein the changing of the route value of the pop level comprises moving to a child node corresponding to a second route value different from the route value of the pop level, and the route value of the pop level being changed to a second route value.

8. The method of claim 1 , wherein the bit stack value is set in a one-bit stack.

9. The method of claim 1 , further comprising, in response to the number of untraversed child nodes among the ray-crossing child nodes being 1, changing the bit stack value of the pop level to the first value.

10. A non-transitory computer readable recording medium having recorded thereon a computer readable code to control at least one processing device to implement the method of claim 1 .

11. An acceleration structure traversing apparatus for ray tracing, the apparatus comprising:
a calculation unit configured to determine a number of ray-crossing child nodes;
a storage unit configured to store bit stack values and route values, the bit stack values for a corresponding level of an acceleration structure being based on the number of ray-crossing child nodes, and the route values for a corresponding level being based on a moving route of a ray; and
a control unit configured to determine a pop level based on relative level among levels having the bit stack values,
wherein the calculation unit, the storage unit and the control unit are implemented by one or more processors, and
wherein the bit stack value indicates whether there is an untraversed child node among the ray-crossing child nodes at the level, the bit stack value has a first value that indicates there is no untraversed child node and a second value that indicates that there is an untraversed child node among the ray-crossing child nodes,
wherein the control unit is configured to determine a highest level among levels having a bit stack value that corresponds to the second value as the pop level.

12. The apparatus of claim 11 , wherein the control unit is configured to control the ray to move from the root node of the acceleration structure to the pop level based on the route values, to control the ray to move to an untraversed child node among the ray-crossing child nodes at the pop level based on the route value of the pop level, and to change the route value of the pop level, and
wherein the calculation unit is configured to restart traversal from the untraversed child node.

13. The apparatus of claim 12 , wherein, in response to moving the ray to a first child node among the ray-crossing child nodes, the control unit is configured to set the route value of the level corresponding to a parent node thereof to a first value, and,
in response to moving the ray to a second child node among the ray-crossing child nodes, the control unit is configured to set the route value of the level corresponding to a parent node thereof to a second value.

14. The apparatus of claim 12 , wherein, in response to the number of the ray-crossing child nodes being N, the control unit is configured to set the route value by using log N bits.

15. The apparatus of claim 12 , wherein the control unit is configured to control the ray to move from the root node of the acceleration structure to the pop level by moving through child nodes corresponding to the route value of the level.

16. The apparatus of claim 11 , wherein the bit stack value is stored in a one-bit stack.

17. The apparatus of claim 11 , wherein, in response to the number of the ray-crossing child nodes being 1, the control unit is configured to set the bit stack value of a level corresponding to a parent node thereof to the first value, and
in response to the number of the ray-crossing child nodes being 2 or greater, the control unit is configured to set the bit stack value of a level corresponding to a parent node thereof to the second value.

18. The apparatus of claim 11 , wherein, in response to the number of untraversed child nodes among the ray-crossing child nodes being 1, the control unit is configured to change the bit stack value of the pop level to the first value.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Jae-Don
• Shin Young-Sam
• Lee Won-Jong

Classifications

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title