Efficient hierarchy traversal in ray tracing applications

Patent metadata

Field	Value
Publication number	US-2016292908-A1
Application number	US-201514831726-A
Country	US
Kind code	A1
Filing date	Aug 20, 2015
Priority date	Apr 2, 2015
Publication date	Oct 6, 2016
Grant date	—

Abstract

Methods and systems disclosed improve the efficiency of ray tracing. In one aspect, a method of ray tracing in a digital representation of a scene includes segmenting the scene into a plurality of voxels, associating each of the voxels with a node of a bounding volume hierarchy (BVH) representing one or more object primitives within the scene, determining a set of voxels through which the ray passes, determining a set of nodes associated with the set of voxels, determining a deepest common ancestor node of the set of nodes, traversing the hierarchy starting at the deepest common ancestor node to determine a point of intersection between the ray and one of the one or more object primitives; and updating a digital image of the scene based on the determined point of intersection.

First claim

What is claimed:

1 . A method of tracing a ray in an electronic image of a scene, comprising:
segmenting the scene into a plurality of voxels; associating each of the voxels with a node of a bounding volume hierarchy (BVH) representing one or more object primitives within the scene; determining a set of voxels through which the ray passes; determining a set of nodes associated with the set of voxels; determining a deepest common ancestor node of the set of nodes; traversing the hierarchy starting at the deepest common ancestor node to determine a point of intersection between the ray and one of the one or more object primitives; and updating a digital image of the scene based on the determined point of intersection.

2 . The method of claim 1 , further comprising outputting the updated digital image to an output device.

3 . The method of claim 1 , wherein associating each voxel with a node comprises:
determining a smallest set of bounding volumes for each voxel encompassing primitives also included in the space represented by the voxel; determining nodes in the hierarchy associated with the set of bounding volumes; determining a second deepest common ancestor of the determined nodes; and associating the voxel with the second deepest common ancestor.

4 . The method of claim 1 , wherein traversing the hierarchy comprises performing a depth first traversal of the hierarchy starting with the deepest common ancestor.

5 . The method of claim 3 , further comprising selecting the smallest set of bounding volumes from bounding volumes at a level of the bounding volume hierarchy that is below a threshold.

6 . The method of claim 1 , further comprising:
storing an identification of each voxel and its associated node in a data structure; and determining a plurality of deepest common ancestors for a corresponding plurality of rays based on the data structure.

7 . The method of claim 1 , wherein the ray is a shadow ray following a path from a surface of one of the one or more object primitives toward a light source in the scene.

8 . The method of claim 8 , wherein the surface point is also a point of intersection of a second ray, the path of the shadow ray independent of an origin of the second ray.

9 . An apparatus for tracing a ray in an electronic image of a scene, comprising:
a memory circuit configured to store a representation of a scene; and a processor circuit in communication with the memory unit configured to:
segment the scene into a plurality of voxels;
associate each of the voxels with a node of a bounding volume hierarchy (BVH) representing one or more object primitives within the scene;
determine a set of voxels through which the ray passes;
determine a set of nodes associated with the set of voxels;
determine a deepest common ancestor node of the set of nodes;
traverse the hierarchy starting at the deepest common ancestor node to determine a point of intersection between the ray and one of the one or more object primitives; and
update a digital image of the scene based on the determined point of intersection.

10 . The apparatus of claim 9 , wherein the processor circuit is further configured to output the updated digital image to an output device.

11 . The apparatus of claim 9 , wherein associate each voxel with a node comprises:
determine a smallest set of bounding volumes for each voxel encompassing all primitives also included in the space represented by the voxel; determine nodes in the hierarchy associated with the set of bounding volumes; determine a second deepest common ancestor of the determined nodes; and associate the voxel with the second deepest common ancestor.

12 . The apparatus of claim 9 , wherein traverse the hierarchy comprises perform a depth first traversal of the hierarchy starting with the deepest common ancestor.

13 . The apparatus of claim 11 , wherein the processor circuit is further configured to select the smallest set of bounding volumes from bounding volumes at a level of the bounding volume hierarchy below a threshold.

14 . The apparatus of claim 9 , wherein the processor circuit is further configured to:
store an identification of each voxel and its associated node in a data structure; and determine a plurality of deepest common ancestors for a corresponding plurality of rays based on the data structure.

15 . The apparatus of claim 9 , wherein the ray is a shadow ray following a path from a surface point of one of the one or more object primitives toward a light source in the scene.

16 . The apparatus of claim 9 , wherein the surface point corresponds to the point of intersection of a second ray, the path of the shadow ray independent of an origin of the second ray.

17 . An apparatus for tracing a ray in an electronic image of a scene, comprising:
means for segmenting the scene into a plurality of voxels; means for associating each of the voxels with a node of a bounding volume hierarchy (BVH) representing one or more object primitives within the scene; means for determining a set of voxels through which the ray passes; means for determining a set of nodes associated with the set of voxels; means for determining a deepest common ancestor node of the set of nodes; means for traversing the hierarchy starting at the deepest common ancestor node to determine a point of intersection between the ray and one of the one or more object primitives; and means for updating a digital image of the scene based on the determined point of intersection.

18 . The apparatus of claim 17 , wherein the segmenting means comprises a processing circuit, wherein the associating means comprises the processing circuit, wherein the set of voxel determining means comprises the processing circuit, wherein the set of nodes determining means comprises the processing circuit, wherein the deepest common ancestor determining means comprises the processing circuit, wherein the hierarchy determining means comprises the processing circuit, wherein the traversing means comprises the processing circuit, and wherein the updating means comprises the processing circuit.

19 . The apparatus of claim 17 , further comprising means for outputting the updated digital image to an output device.

20 . The apparatus of claim 17 , wherein the associating means comprises:
means for determining a smallest set of bounding volumes for each voxel encompassing all primitives also included in the space represented by the voxel; means for determining nodes in the hierarchy associated with the set of bounding volumes; means for determining a second deepest common ancestor of the determined nodes; and means for associating the voxel with the second deepest common ancestor.

21 . The apparatus of claim 17 , wherein the traversing means comprises means for performing a depth first traversal of the hierarchy starting with the deepest common ancestor.

22 . The apparatus of claim 19 , further comprising means for selecting the smallest set of bounding volumes from bounding volumes at a level of the bounding volume hierarchy below a threshold.

23 . The apparatus of claim 17 , further comprising:
means for storing an identification of each voxel and its associated node in a data structure; and means for determining a plurality of deepest common ancestors for a corresponding plurality of rays based on the data structure.

24 . The apparatus of claim 17 , wherein the r

Assignees

• Qualcomm Inc

Inventors

• Obert Juraj

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06T15/08

  Volume rendering · CPC title

• G06T17/005

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