Apparatus and method for traversing hierarchical acceleration structure

1. An apparatus for traversing a hierarchical acceleration structure, the apparatus comprising:

a determining unit configured to determine whether a current traversal node is a leaf node;

a calculating unit configured to calculate a first distance from the current traversal node to a pop level and a second distance from a root node to the pop level when the current traversal node is the leaf node; and

a control unit configured to determine a hierarchical traversal restarting position by comparing the first distance and the second distance: and

a selecting unit to select, as the pop level, the largest level among levels having a trail value of a first predetermined value when the current traversal node is the leaf node.

2. The apparatus of claim 1 , wherein when the first distance is less than the second distance, the control unit determines the current traversal node as the hierarchical traversal restarting position.

3. The apparatus of claim 1 , wherein when the second distance is less than the first distance, the control unit is further configured to determine the root node as the hierarchical traversal restarting position.

4. The apparatus of claim 1 , wherein when the first distance is less than the second distance, the control unit is further configured to control hierarchical traversal to be performed from the current traversal node toward a pop node positioned at the pop level.

5. The apparatus of claim 1 , wherein when the first distance is less than the second distance, the control unit is further configured to move from the current traversal node up to the pop level and to select, as a subsequent traversal node, a sibling node of a node that is traversed at the pop level.

6. The apparatus of claim 1 , wherein when the second distance is less than the first distance, the control unit is further configured to control hierarchical traversal to be performed from the root node toward a pop node positioned at the pop level.

7. The apparatus of claim 1 , wherein when the second distance is less than the first distance, the control unit is further configured to move from the root node to be before the pop level and to select, as a subsequent traversal node, a node that is not traversed among nodes of the pop level.

8. The apparatus of claim 1 , wherein in the case of determining a restart node, the control unit changes the trail value of the pop level to a second predetermined value and changes all of the trail values of levels greater than the pop level to a first predetermined value.

9. The apparatus of claim 4 , wherein the leaf node and the pop node comprise a parent node pointer.

10. A method of traversing a hierarchical acceleration structure, the method comprising:

determining, by a processor, whether a current traversal node is a leaf node;

calculating a first distance from the current traversal node to a pop level and a second distance from a root node to the pop level when the current traversal node is the leaf node;

determining a hierarchical traversal restarting position by comparing the first distance and the second distance; and

selecting, as the pop level, the largest level among levels having a trail value of a first predetermined value when the current traversal node is the leaf node.

11. The method of claim 10 , further comprising:

determining the current traversal node as the hierarchical traversal restarting position when the first distance is less than the second distance; and

determining the root node as the hierarchical traversal restarting position when the second distance is less than the first distance.

12. The method of claim 10 , further comprising:

controlling hierarchical traversal to be performed from the current traversal node toward a pop node positioned at the pop level when the first distance is less than the second distance; and

controlling hierarchical traversal to be performed from the root node toward the pop node positioned at the pop level when the second distance is less than the first distance.

13. The method of claim 10 , further comprising:

moving from the current traversal node up to the pop level and selecting, as a subsequent traversal node, a sibling node of a node that is traversed at the pop level when the first distance is less than the second distance; and

moving from the root node to be before the pop level and selecting, as the subsequent traversal node, a node that is not traversed among nodes of the pop level when the second distance is less than the first distance.

14. The method of claim 10 , further comprising

changing the trail value of the pop level to a second predetermined value and changing all of the trail values of levels greater than the pop level to the first predetermined value in the case of determining a restart node.

15. The method of claim 12 , wherein each node includes a parent node pointer.

16. A non-transitory computer-readable medium comprising a program for instructing a computer to perform the method of claim 10 .

17. The method of claim 14 , wherein the first predetermined value is “0” and the second predetermined value is “1”.