Method of generating and traversing acceleration structure

Patent metadata

Field	Value
Publication number	US-10019832-B2
Application number	US-201615197339-A
Country	US
Kind code	B2
Filing date	Jun 29, 2016
Priority date	Aug 31, 2015
Publication date	Jul 10, 2018
Grant date	Jul 10, 2018

Abstract

A method of generating an acceleration structure for ray tracing, the method including, using a processor, dividing a three-dimensional (3D) space including primitives into bounding boxes, obtaining position information of where the bounding boxes overlapping each other, and generating an acceleration structure representing the position information and an inclusion relation between the bounding boxes. Also disclosed is a related method of traversing an acceleration structure.

First claim

What is claimed is:

1. A method of traversing an acceleration structure comprising one or more nodes, the method comprising:
traversing, using a processor, the acceleration structure until the traversing reaches a leaf node;
obtaining, using the processor, a hit point of a primitive intersected by ray data by traversing the leaf node;
traversing, using the processor, a node of the acceleration structure comprising the hit point; and
rendering an image using results of traversing the node of the acceleration structure;
wherein,
each node of the one or more nodes corresponds to one of plural bounding boxes which divide a three-dimension (3D) space, and comprises position information of where the bounding boxes overlap each other, and
the 3D space is divided into grids, the position information comprising grid positions where the bounding boxes overlap each other.

2. The method of claim 1 , wherein the traversing a node comprises:
terminating the traversal if there is no node that comprises the hit point.

3. The method of claim 1 , wherein the traversing a node comprises:
updating the hit point if the primitive intersected by the ray data exists in the node.

4. The method of claim 1 , wherein the hit point is indicated by a grid position where the primitive is located.

5. A device for traversing an acceleration structure comprising one or more nodes, the device comprising:
a processor configured to traverse the acceleration structure until the traversing reaches a leaf node, obtain a hit point of a primitive intersected by ray data by traversing the leaf node, traverse a node of the acceleration structure comprising the hit point, and render an image using results of traversing the node of the acceleration structure; and
a memory configured to store the acceleration structure;
wherein,
each node of the one or more nodes corresponds to one of plural bounding boxes which divide a three-dimensional (3D) space, and comprises position information of where the bounding boxes overlap each other, and
the 3D space is divided into grids, the position information comprising grid positions where the bounding boxes overlap each other.

6. The device of claim 5 , wherein the processor terminates the traversal if there is no node that comprises the hit point.

7. The device of claim 5 , wherein the processor updates the hit point if the primitive intersected by the ray data exists in the node.

8. The device of claim 5 , wherein the hit point is indicated by a grid position where the primitive is located.

9. A non-transitory computer-readable storage medium storing instructions that when executed by computing hardware, implements a method of traversing an acceleration structure comprising one or more nodes, the method comprising:
traversing, using a processor, the acceleration structure until the traversing reaches a leaf node;
obtaining, using the processor, a hit point of a primitive intersected by ray data by traversing the leaf node; and
traversing, using the processor, a node of the acceleration structure comprising the hit point; and
rendering an image using results of traversing the node of the acceleration structure;
wherein,
each node of the one or more nodes corresponds to one of plural bounding boxes which divide a three-dimensional (3D) space, and comprises position information of where the bounding boxes overlap each other, and
the 3D space is divided into grids, the position information comprising grid positions where the bounding boxes overlap each other.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the traversing a node comprises terminating the traversal if there is no node that comprises the hit point.

11. The non-transitory computer-readable storage medium of claim 9 , wherein the traversing a node comprises updating the hit point if a primitive intersected by the ray data exists in the node.

12. The non-transitory computer-readable storage medium of claim 9 , wherein the hit point is indicated by a grid position where the primitive is located.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Park Jeongsoo
• Shin Youngsam
• Woo Sangoak

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title