Start node determination for tree traversal for shadow rays in graphics processing

2:

• The method of claim 1, wherein rasterizing the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• associating, by the at least one processor, a different one of a plurality of color values with each of the plurality of nodes of the hierarchical data structure;
• and
• for each bounding volume of the plurality of bounding volumes, rasterizing, by the at least one processor, a block of pixels having one of the different color values associated with one of the nodes of the hierarchical data structure that is associated with the respective bounding volume.

3:

• The method of claim 2, wherein determining the non-root node of the hierarchical data structure associated with the bounding volume as the start node to start traversal of the hierarchical data structure further comprises:
• determining, by the at least one processor, one of the nodes of the hierarchical data structure that is associated with the color value of the pixel;
• and
• setting, by the at least one processor, the node of the hierarchical data structure that is associated with the color value of the pixel as the start node to start traversal of the hierarchical data structure.

4:

• The method of claim 2, further comprising:
• determining, by the at least one processor, that a first representation of a first bounding volume of the bounding volumes overlaps a second representation of a second bounding volume of the bounding volumes, wherein the first bounding volume is associated with a first node of the nodes of the hierarchical data structure and the second bounding volume is associated with a second node of the nodes of the hierarchical data structure;
• and
• setting, by the at least one processor, color values of one or more pixels in a region of overlap of the first representation and the second representation to a node color value associated with a lowest common ancestor node of the first node and the second node.

7:

• The method of claim 1, wherein rasterizing the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• rasterizing, by the at least one processor, a plurality of flat-shaded cubes to the off-screen render target as the representations of each of the plurality of bounding volumes;
• and
• scaling and translating, by the at least one processor, each of the plurality of flat-shaded cubes to match a shape of a respective bounding volume.

9:

• An apparatus configured to process graphics data comprising:
• a memory;
• and
• at least one processor configured to:
• organize a plurality of primitives of a scene in a hierarchical data structure, wherein a plurality of bounding volumes are associated with nodes of the hierarchical data structure;
• rasterize representations of each of the plurality of bounding volumes to an off-screen render target in the memory, wherein each representation of the representations of each of the plurality of bounding volumes is associated with a different color value of a plurality of color values;
• determine, based at least in part on a color value of the plurality of color values of a pixel of a representation of a respective one of the bounding volumes in the off-screen render target that maps to a ray in the scene, a non-root node of the hierarchical data structure associated with the respective one of the bounding volumes as a start node to start traversal of the hierarchical data structure;
• and
• traverse a set of nodes of the hierarchical data structure starting from the start node to determine whether the ray in the scene intersects one of the plurality of primitives.

10:

• The apparatus of claim 9, wherein the at least one processor is further configured to:
• associate a different one of a plurality of color values with each of the plurality of nodes of the hierarchical data structure;
• and
• for each bounding volume of the plurality of bounding volumes, rasterize a block of pixels having one of the different color values associated with one of the nodes of the hierarchical data structure that is associated with the respective bounding volume.

11:

• The apparatus of claim 10, wherein the at least one processor is further configured to:
• determine one of the nodes of the hierarchical data structure that is associated with the color value of the pixel;
• and
• set the node of the hierarchical data structure that is associated with the color value of the pixel as the start node to start traversal of the hierarchical data structure.

12:

• The apparatus of claim 10, wherein the at least one processor is further configured to:
• determine that a first representation of a first bounding volume of the bounding volumes overlaps a second representation of a second bounding volume of the bounding volumes, wherein the first bounding volume is associated with a first node of the nodes of the hierarchical data structure and the second bounding volume is associated with a second node of the nodes of the hierarchical data structure;
• and
• set color values of one or more pixels in a region of overlap of the first representation and the second representation to a node color value associated with a lowest common ancestor node of the first node and the second node.

15:

• The apparatus of claim 9, wherein the at least one processor is further configured to:
• rasterize a plurality of flat-shaded cubes to the off-screen render target as the representations of each of the plurality of bounding volumes;
• and
• scale and translate each of the plurality of flat-shaded cubes to match a shape of a respective bounding volume.

17:

• An apparatus comprising:
• means for organizing a plurality of primitives of a scene in a hierarchical data structure, wherein a plurality of bounding volumes are associated with nodes of the hierarchical data structure;
• means for rasterizing representations of each of the plurality of bounding volumes to an off-screen render target, wherein each representation of the representations of each of the plurality of bounding volumes is associated with a different color value of a plurality of color values;
• means for determining, based at least in part on a color value of the plurality of color values of a pixel of a representation of a respective one of the bounding volumes in the off-screen render target maps to a ray in the scene, a non-root node of the hierarchical data structure associated with the respective one of the bounding volumes as a start node to start traversal of the hierarchical data structure;
• and
• means for traversing a set of nodes of the hierarchical data structure starting from the start node to determine whether the ray in the scene intersects one of the plurality of primitives.

18:

• The apparatus of claim 17, wherein the means for rasterizing the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• means for associating a different one of a plurality of color values with each of the plurality of nodes of the hierarchical data structure;
• and
• means for rasterizing, for each bounding volume of the plurality of bounding volumes, a block of pixels having one of the different color values associated with one of the nodes of the hierarchical data structure that is associated with the respective bounding volume.

19:

• The apparatus of claim 18, wherein the means for determining the non-root node of the hierarchical data structure associated with the bounding volume as the start node to start traversal of the hierarchical data structure further comprises:
• means for determining one of the nodes of the hierarchical data structure that is associated with the color value of the pixel;
• and
• means for setting the node of the hierarchical data structure that is associated with the color value of the pixel as the start node to start traversal of the hierarchical data structure.

20:

• The apparatus of claim 18, further comprising:
• means for determining that a first representation of a first bounding volume of the bounding volumes overlaps a second representation of a second bounding volume of the bounding volumes, wherein the first bounding volume is associated with a first node of the nodes of the hierarchical data structure and the second bounding volume is associated with a second node of the nodes of the hierarchical data structure;
• and
• means for setting color values of one or more pixels in a region of overlap of the first representation and the second representation to a node color value associated with a lowest common ancestor node of the first node and the second node.

23:

• The apparatus of claim 17, wherein the means for rasterizing the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• means for rasterizing a plurality of flat-shaded cubes to the off-screen render target as the representations of each of the plurality of bounding volumes;
• and
• means for scaling and translating each of the plurality of flat-shaded cubes to match a shape of a respective bounding

24:

• A non-transitory computer-readable storage medium storing instructions that, when executed, cause one or more programmable processors to:
• organize a plurality of primitives of a scene in a hierarchical data structure, wherein a plurality of bounding volumes are associated with nodes of the hierarchical data structure;
• rasterize representations of each of the plurality of bounding volumes to an off-screen render target in the memory, wherein each representation of the representations of each of the plurality of bounding volumes is associated with a different color value of a plurality of color values;
• determine, based at least in part on a color value of the plurality of color values of a pixel of a representation of a respective one of the bounding volumes in the off-screen render target maps to a ray in the scene, a non-root node of the hierarchical data structure associated with the respective one of the bounding volume as a start node to start traversal of the hierarchical data structure;
• and
• traverse a set of nodes of the hierarchical data structure starting from the start node to determine whether the ray in the scene intersects one of the plurality of primitives.

25:

• The non-transitory computer-readable storage medium of claim 24, wherein rasterize the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• associate a different one of a plurality of color values with each of the plurality of nodes of the hierarchical data structure;
• and
• for each bounding volume of the plurality of bounding volumes, rasterize a block of pixels having one of the different color values associated with one of the nodes of the hierarchical data structure that is associated with the respective bounding volume.

26:

• The non-transitory computer-readable storage medium of claim 25, wherein determine the non-root node of the hierarchical data structure associated with the bounding volume as the start node to start traversal of the hierarchical data structure further comprises:
• determine one of the nodes of the hierarchical data structure that is associated with a color value of the pixel;
• and
• set the node of the hierarchical data structure that is associated with the color value of the pixel as the start node to start traversal of the hierarchical data structure.

27:

• The non-transitory computer-readable storage medium of claim 25, further comprising instructions that, when executed, cause one or more programmable processors to:
• determine that a first representation of a first bounding volume of the bounding volumes overlaps a second representation of a second bounding volume of the bounding volumes, wherein the first bounding volume is associated with a first node of the nodes of the hierarchical data structure and the second bounding volume is associated with a second node of the nodes of the hierarchical data structure;
• and
• set color values of pixels in a region of overlap of the first representation and the second representation to the node color value associated with a lowest common ancestor node of the first node and the second node.

30:

• The non-transitory computer-readable storage medium of claim 24, wherein rasterize the representation of each of the plurality of bounding volumes to the off-screen render target further comprises:
• rasterize a plurality of flat-shaded cubes to the off-screen render target as the representations of each of the plurality of bounding volumes;
• and
• scale and translate each of the plurality of flat-shaded cubes to match a shape of a respective bounding volume.