Method and apparatus for stack management

Patent metadata

Field	Value
Publication number	US-9275494-B2
Application number	US-201313958850-A
Country	US
Kind code	B2
Filing date	Aug 5, 2013
Priority date	Feb 25, 2013
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

A method and apparatus for managing a stack used for a tree traversal (TRV) may include a processing unit that may manage a short stack for a tree TRV, and a storage unit that may store data of the short stack. The processing unit may perform a restart of the tree TRV from an intermediate node of a tree to fill the short stack when the short stack is empty.

First claim

What is claimed is:

1. An electronic apparatus, comprising:
a processor configured to manage a short stack for a tree traversal (TRV); and
a storage configured to store data of the short stack,
wherein the processor restarts the tree TRV from an intermediate node disposed between a root node of the tree and a node popped last in the short stack to fill the short stack in response to the short stack being empty, and
wherein the processor predetermines the intermediate node by storing a link indicating the intermediate node in the storage, and
wherein the processor manages a buffer of a predetermined size,
the storage unit stores data of the buffer, and
the buffer stores the short stack, and stores the link indicating the intermediate node.

2. The electronic apparatus of claim 1 , wherein the tree comprises an acceleration structure (AS) in which partitioned spaces overlap.

3. The electronic apparatus of claim 1 , wherein the tree comprises a bounding volume hierarchy (BVH).

4. The electronic apparatus of claim 1 , wherein the processor stores the link in the storage unit when the short stack is full.

5. The electronic apparatus of claim 1 , wherein the link comprises a plurality of links.

6. The electronic apparatus of claim 5 , wherein the processor variably adjusts a size of a first area in the buffer storing the short stack and a size of a second area in the buffer storing the plurality of links.

7. The electronic apparatus of claim 1 , wherein the processor determines a number of the plurality of links, based on a maximum value of a number of nodes being pushed during the tree TRV.

8. The electronic apparatus of claim 1 , wherein the processor determines a number of the plurality of links, based on the maximum value of the number of nodes being pushed during the tree TRV, and a size of the short stack.

9. A method for a tree traversal (TRV), using a short stack, the method comprising:
popping, by a processor, a node from the short stack;
restarting, by a processor, the tree TRV to fill the short stack from an intermediate node disposed between a root node and the popped node in response to the tree being empty, wherein the intermediate node is predetermined by a link stored in a storage unit; and
managing, by a processor, a buffer of a predetermined size,
wherein data of the buffer is stored in the storage unit, and
the link indicating the short stack and the intermediate node is stored in the buffer.

10. The method of claim 9 , wherein the tree comprises an acceleration structure (AS) in which partitioned spaces overlap.

11. The method of claim 9 , wherein the link is stored in the storage unit when the short stack is full.

12. The method of claim 9 , wherein the link comprises a plurality of links.

13. The method of claim 12 , wherein a size of a first area in the buffer storing the short stack and a size of a second area in the buffer storing the plurality of links are variably adjusted.

14. The method of claim 9 , wherein a number of the plurality of links is determined based on a maximum value of a number of nodes being pushed during the tree TRV.

15. The method of claim 9 , wherein the number of the plurality of links is determined based on the maximum value of the number of nodes being pushed during the tree TRV and a size of the short stack.

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

Assignees

• Samsung Electronics Co Ltd
• Univ Yonsei Iacf

Inventors

• Lee Won Jong
• Kim Jin Woo
• Shin Young Sam
• Lee Jae Don

Classifications

• G06T2200/28

  involving image processing hardware · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T1/60

  Memory management · CPC title