Method and apparatus generating acceleration structure

Patent metadata

Field	Value
Publication number	US-10115224-B2
Application number	US-201615334815-A
Country	US
Kind code	B2
Filing date	Oct 26, 2016
Priority date	Oct 26, 2015
Publication date	Oct 30, 2018
Grant date	Oct 30, 2018

Abstract

A method of generating a ray tracing acceleration structure includes transformatively mapping locations of object primitives in a three dimensional first space into Morton codes indicating respective locations of the primitives along a meandering linear path through the first space; determining a Morton distance indicating a difference between a first Morton code corresponding with a first primitive and a second Morton code corresponding with a second primitive; generating an acceleration structure to include nodes representing portions of the first space and adaptively adjusting a reference level of the acceleration structure, based on the Morton distance between primitives; and dividing the first space using a first division method when a level of a first node of the acceleration structure which corresponds to the first space is lower than the reference level, and dividing the first space using a second division method when the level of the first node exceeds the reference level.

First claim

What is claimed is:

1. A method of generating and using an acceleration structure for ray tracing a three-dimensional scene including primitives, the method comprising:
obtaining Morton codes indicating respective locations of the primitives comprised in a first space;
calculating a Morton distance indicating a difference between a first Morton code corresponding with a first primitive and a second Morton code corresponding with a second primitive;
adjusting a reference level of the acceleration structure, based on the Morton distance; and
dividing the first space using a first division method in response to a level of a first node of the acceleration structure which corresponds to the first space being lower than the reference level, and dividing the first space using a second division method in response to the level of the first node exceeding the reference level;
ray tracing from a viewpoint by casting rays into three-dimensional scene by using the acceleration structure; and
generating respective pixel values on an image plane by using results of the ray tracing.

2. The method of claim 1 , wherein the first division method comprises a surface area heuristic (SAH) method, and
the second division method comprises a division method using the Morton codes.

3. The method of claim 2 , wherein the dividing of the first space comprises dividing spaces respectively corresponding to sub-nodes included in the first node by using the Morton codes in response to the level of the first node exceeding the reference level.

4. The method of claim 2 , further comprising obtaining sub-spaces comprising the first space by dividing a second space by using the SAH method.

5. The method of claim 1 , wherein the first primitive comprises a primitive having a smallest Morton code, and
the second primitive comprises a primitive having a greatest Morton code.

6. The method of claim 1 , wherein the adjusting of the reference level comprises decreasing the reference level when the Morton distance is less than a certain threshold value and increasing the reference level when the Morton distance is equal to or greater than the certain threshold value.

7. The method of claim 1 , wherein the obtaining Morton codes comprises transformatively mapping locations of object primitives in the first space into Morton codes indicating respective locations of the primitives along a meandering linear path through the first space.

8. A non-transitory computer-readable recording medium having embodied thereon a computer program which, when executed by a computer, performs the method of claim 1 .

9. A method of generating an acceleration structure for ray tracing, the method comprising:
obtaining Morton codes indicating locations of primitives comprised in a first space;
calculating a Morton distance indicating a difference between a first Morton code corresponding with a first primitive and a second Morton code corresponding with a second primitive;
dividing the first space into sub-spaces by using a first division method in response to the Morton distance being less than a certain threshold value and dividing the first space into the sub-spaces by using a second division method in response to the Morton distance exceeding the certain threshold value;
generating the acceleration structure by setting each of the sub-spaces as a node comprised in the acceleration structure;
ray tracing rays generated from a viewpoint to intersect a scene object by using the generated acceleration structure; and
using the results from the ray tracing to determine color values of pixels for forming an image.

10. The method of claim 9 , wherein the first primitive comprises a primitive having a smallest Morton code, and
the second primitive comprises a primitive having a greatest Morton code.

11. The method of claim 9 , wherein the first division method comprises a surface area heuristic (SAH) method, and
the second division method comprises a division method using the Morton codes.

12. An apparatus for generating and using an acceleration structure for ray tracing a three-dimensional scene including primitives, the apparatus comprising:
a memory configured to store information about the acceleration structure; and
a processor configured to
obtain Morton codes indicating locations of the primitives comprised in a first space,
calculate a Morton distance indicating a difference between a first Morton code corresponding to a first primitive from among the primitives comprised in the first space and a second Morton code corresponding to a second primitive from among the primitives,
adjust a reference level of the acceleration structure based on the Morton distance,
divide the first space by using a first division method in response to a level of a first node of the acceleration structure that corresponds to the first space being lower than the reference level, or divide the first space by using a second division method in response to the level of the first node exceeding the reference level,
ray tracing from a viewpoint by casting rays into the three-dimensional scene by using the acceleration structure; and
generate respective pixel values on an image plane by using results of the ray tracing.

13. The apparatus of claim 12 , wherein the first division method comprises a surface area heuristic (SAH) method, and
the second division method comprises a division method using the Morton codes.

14. The apparatus of claim 12 , wherein the processor is further configured to divide spaces respectively corresponding to sub-nodes comprised in the first node by using the Morton codes when the level of the first node exceeds the reference level.

15. The apparatus of claim 13 , wherein the processor is further configured to obtain sub-spaces comprising the first space by dividing a second space by using the SAH method.

16. The apparatus of claim 12 , wherein the first primitive comprises a primitive having a smallest Morton code, and
the second primitive comprises a primitive having a greatest Morton code.

17. The apparatus of claim 13 , wherein the processor is further configured to decrease the reference level of the acceleration structure when the Morton distance is less than a certain threshold value and increase the reference level when the Morton distance is equal to or greater than the certain threshold value.

18. An apparatus for generating an acceleration structure for ray tracing, the apparatus comprising:
a memory configured to store information about the acceleration structure; and
a processor configured:
to obtain Morton codes indicating locations of primitives comprised in a first space,
to calculate a Morton distance indicating a difference between a first Morton code corresponding to a first primitive from among the primitives comprised in the first space and a second Morton code corresponding to a second primitive from among the primitives,
to divide the first space into sub-spaces by using a first division method in response to the Morton distance being less than a certain threshold value, or to divide the first space into sub-spaces by using a second division method in response to the Morton distance exceeding the certain threshold value,
to generate the acceleration structure by setting each sub-space as a node in the acceleration structure,
ray tracing rays generated from a viewpoint to intersect a scene object by using the generated acceleration structure; and
using the results from the ray tracing to determine color values of pixels for forming an image.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Shin Youngsam
• Lee Wonjong
• Hwang Seokjoong

Classifications

• G06T15/50

  Lighting effects · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T2210/21

  Collision detection, intersection · CPC title

• G06T17/005

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