IP Library › Granted Patent US 9,805,495

Granted Patent B2

US 9,805,495 · App. 15/054,717 · Granted Oct 31, 2017

Single pass bounding volume hierarchy rasterization

Inventors: Juraj Obert (Orlando, FL); Tao Wang (Sunnyvale, CA); Vineet Goel (La Jolla, CA)

Assignee: QUALCOMM Incorporated

G06T15/005 G06T15/06 G06T2200/28 G06T2210/21

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 9,805,495
App. No.: 15/054,717
Granted: Oct 31, 2017
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A render output unit running on at least one processor may receive a source pixel value to be written to a pixel location in a render target, wherein the source pixel value is associated with a source node in a hierarchical structure. The render output unit may receive a destination pixel value of the pixel location in the render target, wherein the destination pixel value is associated with a destination node in the hierarchical structure. The render output unit may determine a lowest common ancestor node of the source node and the destination node in the hierarchical structure. The render output unit may output a resulting pixel value associated with the lowest common ancestor node of the source node and the destination node to the pixel location in the render target.

Claims (121)

1. A method for graphics processing, comprising:

receiving, by at least one processor, a source pixel value to be written to a pixel location in a render target, wherein the source pixel value is associated with a source node in a hierarchical structure having a plurality of nodes associated with a plurality of node indices, and wherein the source node is associated with a source node index made up of a first set of bits;

receiving, by the at least one processor, a destination pixel value of the pixel location in the render target, wherein the destination pixel value is associated with a destination node in the hierarchical structure, and wherein the destination node is associated with a destination node index made up of a second set of bits;

determining, by the at least one processor, a lowest common ancestor node of the source node and the destination node in the hierarchical structure, including determining a resulting node index associated with the lowest common ancestor node based at least in part on a common set of bits between the first set of bits and the second set of bits; and

outputting, by the at least one processor, a resulting pixel value associated with the lowest common ancestor node of the source node and the destination node to the pixel location in the render target.

2. The method of claim 1 , wherein the hierarchical structure includes a binary tree, the method further comprising:

determining, by the at least one processor and based at least in part on the source pixel value, the source node index associated with the source node; and

determining, by the at least one processor and based at least in part on the destination pixel value, the destination node index associated with the destination node.

3. The method of claim 2 , wherein determining the resulting node index further comprises:

aligning, by the at least one processor, the first set of bits that make up the source node index and the second set of bits that make up the destination node index under a highest set bit of each of the first set of bits and the second set of bits by right-shifting the greater of the first set of bits and the second set of bits; and

determining, by the at least one processor, the resulting node index as being made up of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set bit, as a third set of bits associated with the lowest common ancestor node.

4. The method of claim 3 , wherein aligning the first set of bits and the second set of bits further comprises:

left-aligning, by the at least one processor, the first set of bits that make up the source node index and a second set of bits that make up the destination node index, by at least left-shifting one or more of the first set of bits and the second set of bits, such that a respective highest bit of the left-aligned first set of bits and the left-aligned second set of bits are each set; and

determining, by the at least one processor, the resulting node index as being made up of at least a portion of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set bit.

5. The method of claim 1 , further comprising:

binding, by the at least one processor, a plurality of primitives of a scene into a plurality of bounding volumes;

organizing, by the at least one processor, the plurality of bounding volumes in the hierarchical structure, wherein a plurality of nodes of the hierarchical structure are associated with the plurality of bounding volumes; and

rasterizing, by the at least one processor, representations of one or more of the bounding volumes to the render target, including:

rasterizing, by the at least one processor, a representation of a first bounding volume to a first set of pixel locations in the render target, and

rasterizing, by the at least one processor, a representation of a second bounding volume to a second set of pixel locations in the render target, wherein first set of pixel locations and the second set of pixel locations both include the pixel location in the render target.

6. The method of claim 5 , further comprising:

mapping, by the at least one processor, a ray to one or more pixels of the render target;

determining, by the at least one processor and based at least in part on the one or more pixels of the render target mapped to the ray, a non-root node of the hierarchical data structure associated with the resulting pixel value of the pixel location as a start node to start traversal of the hierarchical data structure; and

traversing, by the at least one processor, a set of nodes of the hierarchical data structure starting from the start node to determine one or more intersections between the ray and one or more of the plurality of primitives.

7. The method of claim 6 , further comprising:

updating, by the at least one processor, one or more pixel values for one or more locations of the scene based at least in part on determining the one or more intersections between the ray and the one or more of the plurality of primitives; and

rendering, by the at least one processor, the scene based at least in part on the one or more pixel values for the one or more locations of the scene for display by a display device.

8. The method of claim 1 , wherein:

the source pixel value specifies a source color value;

the destination pixel value specifies a destination color value; and

the resulting pixel value specifies a resulting color value.

9. An apparatus for graphics processing, comprising:

a memory configured to store a render target;

at least one processor configured to:

receive a source pixel value to be written to a pixel location in the render target, wherein the source pixel value is associated with a source node in a hierarchical structure having a plurality of nodes associated with a plurality of node indices, and wherein the source node is associated with a source node index made up of a first set of bits;

receive a destination pixel value of the pixel location in the render target, wherein the destination pixel value is associated with a destination node in the hierarchical structure, and wherein the destination node is associated with a destination node index made up of a second set of bits;

determine a lowest common ancestor node of the source node and the destination node in the hierarchical structure, including determining a resulting node index associated with the lowest common ancestor node based at least in part on a common set of bits between the first set of bits and the second set of bits; and

output a resulting pixel value associated with the lowest common ancestor node of the source node and the destination node to the pixel location in the render target.

10. The apparatus of claim 9 , wherein:

the hierarchical structure includes a binary tree;

and

the at least one processor is further configured to:

determine, based at least in part on the source pixel value, the source node index associated with the source node; and

determine, based at least in part on the destination pixel value, the destination node index associated with the destination node.

11. The apparatus of claim 10 , wherein the at least one processor is further configured to:

align the first set of bits that make up the source node index and the second set of bits that make up the destination node index under a highest set bit of each of the first set of bits and the second set of bits by right-shifting the greater of the first set of bits and the second set of bits; and

determine the resulting node index as being made up of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set bit as a third set of bits associated with the lowest common ancestor node.

12. The apparatus of claim 10 , wherein the at least one processor is further configured to:

left-align the first set of bits that make up the source node index and a second set of bits that make up the destination node index, by left-shifting one or more of the first set of bits and the second set of bits, such that a respective highest bit the left-aligned first set of bits and the left-aligned second set of bits are each set; and

determine the resulting node index as being made up of at least a portion of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set.

13. The apparatus of claim 9 , wherein the at least one processor is further configured to:

bind a plurality of primitive of a scene into a plurality of bounding volumes;

organize the plurality of bounding volumes in the hierarchical structure, wherein a plurality of nodes of the hierarchical structure are associated with the plurality of bounding volumes; and

rasterize representations of one or more of the bounding volumes to the render target, including:

rasterize a representation of a first bounding volume to a first set of pixel locations in the render target, and

rasterize a representation of a second bounding volume to a second set of pixel locations in the render target, wherein first set of pixel locations and the second set of pixel locations both include the pixel location in the render target.

14. The apparatus of claim 13 , wherein the at least one processor is further configured to:

map a ray to one or more pixels of the render target;

determine, based at least in part the one or more pixels of the render target mapped to the ray including the pixel location, a non-root node of the hierarchical data structure associated with the resulting pixel value of the pixel location as a start node to start traversal of the hierarchical data structure; and

15. The apparatus of claim 14 , wherein the at least one processor is further configured to:

update one or more pixel values for one or more locations of the scene based at least in part on determining the one or more intersections between the ray and the one or more of the plurality of primitives; and

render the scene based at least in part on the one or more pixel values for the one or more locations of the scene for display by a display device.

16. The apparatus of claim 9 , wherein:

the source pixel value specifies a source color value;

the destination pixel value specifies a destination color value; and

the resulting pixel value specifies a resulting color value.

17. An apparatus for graphics processing, comprising:

means for receiving a source pixel value to be written to a pixel location in a render target, wherein the source pixel value is associated with a source node in a hierarchical structure having a plurality of nodes associated with a plurality of node indices, and wherein the source node is associated with a source node index made up of a first set of bits;

means for receiving a destination pixel value of the pixel location in the render target, wherein the destination pixel value is associated with a destination node in the hierarchical structure, and wherein the destination node is associated with a destination node index made up of a second set of bits;

means for determining a lowest common ancestor node of the source node and the destination node in the hierarchical structure, the means for determining including means for determining a resulting node index associated with the lowest common ancestor node based at least in part on a common set of bits between the first set of bits and the second set of bits; and

means for outputting, by the render output unit of the processor, a resulting pixel value associated with the lowest common ancestor node of the source node and the destination node to the pixel location in the render target.

18. The apparatus of claim 17 , wherein the hierarchical structure includes a binary tree, the apparatus further comprising:

means for determining, based at least in part on the source pixel value, the source node index associated with the source node; and

means for determining, based at least in part on the destination pixel value, the destination node index associated with the destination node.

19. The apparatus of claim 18 , wherein the means for determining the resulting node index further comprises:

means for aligning the first set of bits that make up the source node index and the second set of bits that make up the destination node index under a highest set bit of each of the first set of bits and the second set of bits by right-shifting the greater of the first set of bits and the second set of bits;

means for determining the resulting node index as being made up of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set bit as a third set of bits associated with the lowest common ancestor node.

20. The apparatus of claim 18 , wherein the means for aligning the first set of bits and the second set of bits further comprises:

means for left-aligning the first set of bits that make up the source node index and a second set of bits that make up the destination node index, by left-shifting one or more of the first set of bits and the second set of bits, such that a respective highest bit the left-aligned first set of bits and the left-aligned second set of bits are each set; and

means for determining the resulting node index as being made up of at least a portion of a set of consecutive common bits between the aligned first set of bits and second set of bits, starting from the highest set.

21. The apparatus of claim 17 , further comprising:

means for binding a plurality of primitive of a scene into a plurality of bounding volumes;

means for organizing the plurality of bounding volumes in the hierarchical structure, wherein a plurality of nodes of the hierarchical structure are associated with the plurality of bounding volumes;

means for rasterizing representations of one or more of the bounding volumes to the render target, including:

means for rasterizing a representation of a first bounding volume to a first set of pixel locations in the render target, and

means for rasterizing a representation of a second bounding volume to a second set of pixel locations in the render target, wherein first set of pixel locations and the second set of pixel locations both include the pixel location in the render target.

22. The apparatus of claim 21 , further comprising:

means for mapping a ray to one or more pixels of the render target;

means for determining, based at least in part the one or more pixels of the render target mapped to the ray including the pixel location, a non-root node of the hierarchical data structure associated with the resulting pixel value of the pixel location 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 one or more intersections between the ray and one or more of the plurality of primitives.

23. The apparatus of claim 17 , further comprising:

means for updating one or more pixel values for one or more locations of the scene based at least in part on determining the one or more intersections between the ray and the one or more of the plurality of primitives; and

means for rendering the scene based at least in part on the one or more pixel values for the one or more locations of the scene for display by a display device.

24. A non-transitory computer-readable storage medium storing instructions that, when executed, cause one or more programmable processors to:

receive a source pixel value to be written to a pixel location in a render target, wherein the source pixel value is associated with a source node in a hierarchical structure having a plurality of nodes associated with a plurality of node indices, and wherein the source node is associated with a source node index made up of a first set of bits;

output a resulting pixel value associated with the lowest common ancestor node of the source node and the destination node to the pixel location in the render target.

25. The non-transitory computer-readable storage medium of claim 24 , wherein the hierarchical structure includes a binary tree, and further comprising instructions that, when executed, cause one or more programmable processors to:

determine, based at least in part on the source pixel value, the source node index associated with the source node; and

determine, based at least in part on the destination pixel value, the destination node index associated with the destination node.

26. The non-transitory computer-readable storage medium of claim 25 , further comprising instructions that, when executed, cause one or more programmable processors to:

27. The non-transitory computer-readable storage medium of 25 , further comprising instructions that, when executed, cause one or more programmable processors to:

28. The non-transitory computer-readable storage medium of claim 24 , further comprising instructions that, when executed, cause one or more programmable processors to:

bind a plurality of primitive of a scene into a plurality of bounding volumes;

organize the plurality of bounding volumes in the hierarchical structure, wherein a plurality of nodes of the hierarchical structure are associated with the plurality of bounding volumes; and

rasterize representations of one or more of the bounding volumes to the render target, including:

rasterize a representation of a first bounding volume to a first set of pixel locations in the render target, and

29. The non-transitory computer-readable storage medium of claim 28 , further comprising instructions that, when executed, cause one or more programmable processors to:

map a ray to one or more pixels of the render target;

30. The non-transitory computer-readable storage medium of claim 29 , further comprising instructions that, when executed, cause one or more programmable processors to:

render the scene based at least in part on the one or more pixel values for the one or more locations of the scene for display by a display device.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 4, 2016

From: OBERT, JURAJ; WANG, TAO; GOEL, VINEET

To: QUALCOMM INCORPORATED

Reel/Frame 038187/0045 →

Continuity (1)

Related Publication 20170249771A1 · Aug 31, 2017