Method and apparatus for generating acceleration structure

Patent metadata

Field	Value
Publication number	US-10497167-B2
Application number	US-201715625244-A
Country	US
Kind code	B2
Filing date	Jun 16, 2017
Priority date	Dec 15, 2016
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

A method and apparatus for generating an acceleration structure. Primitives corresponding to at least one object on which rendering is to be performed may be aligned. Candidate split points are determined by scanning the aligned primitives. The candidate split points are stored according to a predetermined rule, and the acceleration structure is generated by sequentially reading the stored candidate split points and generating at least one node corresponding to the stored candidate split points.

First claim

What is claimed is:

1. A method of generating an acceleration structure for ray tracing, the method comprising:
aligning primitives corresponding to at least one object on which rendering is to be performed;
generating a bounding box when the aligned primitives are sequentially input;
determining candidate split points based on comprising a ratio of one bounding box with a ratio of another bounding box;
storing the candidate split points according to a predetermined rule;
reading the stored candidate split points including at least one candidate split point from a previous rendering and generating at least one node corresponding to one of the candidate split points; and
generating the acceleration structure by using the generated at least one node.

2. The method of claim 1 , wherein the candidate split points are stored in an internal memory of a graphics processing unit (GPU).

3. The method of claim 1 , wherein the stored candidate split points are sequentially read, and generating the at least one node comprises sequentially generating an upper node and a lower node of the acceleration structure.

4. The method of claim 1 , wherein the aligning of the primitives comprises:
generating a Morton code indicating a respective location of each of the primitives; and
aligning the primitives based on a value of the Morton code for each of the primitives.

5. The method of claim 4 , wherein the location of each of the primitives comprises coordinate information of a center of each of the primitives in a three-dimensional (3D) space.

6. The method of claim 1 , wherein the determining of the candidate split points comprises: determining the candidate split points by scanning the primitives in a direction in which a respective value of one of a plurality of Morton codes corresponding to each primitive increases.

7. The method of claim 1 , wherein the determining of the candidate split points comprises: determining the candidate split points by scanning the primitives in a direction in which a respective value of one of a plurality of Morton codes corresponding to each primitive decreases.

8. The method of claim 1 , wherein the storing of the candidate split points comprises: determining the candidate split points based on a respective value of a plurality of Morton codes corresponding to each of the candidate split points, or determining a size increase ratio of bounding boxes corresponding to the candidate split points.

9. The method of claim 1 , wherein the generating the acceleration structure by generating at least one node comprises generating a plurality of nodes with respect to the stored candidate split points.

10. An apparatus for generating an acceleration structure for ray tracing, the apparatus comprising:
a memory configured to store candidate split points; and
a processor configured to align primitives corresponding to at least one object on which rendering is to be performed, determine the candidate split points by scanning the aligned primitives, control the memory to store the candidate split points according to a predetermined rule, and generate the acceleration structure based on a sequential reading of the candidate split points from the memory and generate at least one node corresponding to the sequentially read candidate split points, wherein the processor is further configured to generate a bounding box when the aligned primitives are sequentially input and determine the candidate split points based on comparing a ratio of one bounding box with a ratio of another bounding box.

11. The apparatus of claim 10 , wherein the processor is further configured to generate a Morton code indicating a location of each of the primitives and align the primitives based on a respective value of the Morton code.

12. The apparatus of claim 11 , wherein the location of each of the primitives comprises coordinate information of a center of each of the primitives in a three-dimensional space.

13. The apparatus of claim 10 , wherein the processor is further configured to determine the candidate split points by scanning the primitives in a direction in which a respective value of one of a plurality of Morton codes corresponding to each primitive increases.

14. The apparatus of claim 10 , wherein the processor is further configured to determine the candidate split points by scanning the primitives in a direction in which a respective value of one of a plurality of Morton codes corresponding to each primitive decreases.

15. The apparatus of claim 10 , wherein the processor is further configured to control the memory to store the candidate split points based on a respective value of a plurality of Morton codes each corresponding to one of the candidate split points or a size increase ratio of bounding boxes corresponding to the candidate split points.

16. An apparatus for generating an acceleration structure for ray tracing, the apparatus comprising:
a memory configured to store a plurality of candidate split points;
an acceleration structure generator connected to the memory, the acceleration structure includes at least one processor configured to align primitives corresponding to at least one object of a three-dimensional image on which rendering is to be performed, generate a bounding box when the aligned primitives are sequentially input, determine the candidate split points based on comparing a ratio of one bounding box with a ratio of another bounding box, control the memory to store the candidate split points according to a predetermined rule, and read the candidate split points from the memory and generate one or more nodes corresponding to one or more candidate split points, and generate the acceleration structure based on the one or more nodes; and
wherein the candidate split points used to generate the acceleration structure were previously stored in a rendering of another object of the three-dimensional image.

17. The apparatus according to claim 16 , wherein the acceleration structure comprises a K-dimensional (KD) tree.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Shin Young-Sam
• Lee Won-Jong

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T17/005

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

• G06T15/80

  Shading · CPC title

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title