Method and apparatus generating acceleration structure

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.

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. 
 
 
     
     
       19. The apparatus of  claim 18 , wherein the first primitive comprises a primitive having a smallest Morton code, and
 the second primitive comprises a primitive having a greatest Morton code. 
 
     
     
       20. The apparatus of  claim 18 , 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.