Watertight ray triangle intersection
A hardware-based traversal coprocessor provides acceleration of tree traversal operations searching for intersections between primitives represented in a tree data structure and a ray. The primitives may include triangles used in generating a virtual scene. The hardware-based traversal coprocessor is configured to properly handle numerically challenging computations at or near edges and/or vertices of primitives and/or ensure that a single intersection is reported when a ray intersects a surface formed by primitives at or near edges and/or vertices of the primitives.
1. A system including:
memory that stores at least a portion of an acceleration data structure including a plurality of hierarchical nodes, at least one node identifying a primitive range of a virtual scene; and
hardware circuitry operatively coupled to the memory and configured to:
determine intersections between a ray defined in a ray coordinate space and primitives in the primitive range; and
when the ray is determined to intersect an edge or vertex shared by N primitives, where N>1, select less than N primitives to report based on a tie-breaking rule that compares vertex values of vertices shared by the N primitives in the ray coordinate space.
2. The system of claim 1 , wherein the primitives include triangles and determining intersections between the ray and the triangles includes, for each triangle:
transforming triangle vertices into the ray coordinate space;
determining edge function values of post-transform triangle edges defined by transformed triangle vertices;
if all edge function values are nonzero and have a same sign, identifying the triangle as being intersected by the ray; and
if one or more of the edge function values is zero, determining whether the triangle is intersected based on whether another triangle shares the triangle vertices and whether one or more edge function values of the other triangle are zero.
3. The system of claim 1 , wherein the hardware circuitry includes a fused floating point operation unit configured to combine multiple floating-point arithmetic operations to determine intersections between the ray and the primitives.
4. The system of claim 3 , wherein the fused floating point operation unit is configured to perform arithmetic operations using single precision floating-point format.
5. The system of claim 3 , wherein the fused floating point operation unit is configured to perform arithmetic operations with expanded 10-bit exponent range.
6. The system of claim 1 , wherein the hardware circuitry is configured to determine primitives in the primitive range received from the memory which are intersected by the ray without using double-precision floating-point arithmetic.
7. A system including:
memory that stores at least a portion of an acceleration data structure including a plurality of hierarchical nodes, at least one node identifying a primitive range of a virtual scene; and
hardware circuitry operatively coupled to the memory and comprising:
projection circuitry configured to project vertex values of primitives in the primitive range received from the memory into a 2D coordinate space of a ray; and
intersection test circuitry coupled to the projection circuitry and configured to determine intersections between the ray and primitives in the primitive range based on the projected vertex values and to report, when the ray is determined to intersect an edge or vertex shared by a plurality of primitives, a single primitive of the plurality of primitives based on a comparison of the projected vertex values of the plurality of primitives.
8. The system of claim 7 , wherein the intersection test circuitry includes a plurality of fused floating point operation units configured to combine multiple floating-point arithmetic operations used to determine primitives in the primitive range intersected by the ray.
9. The system of claim 8 , wherein the fused floating point operation unit is configured to perform arithmetic operations with expanded 10-bit exponent range.
10. A tree traversal unit comprising:
ray-surface testing hardware configured to test whether a ray intersects plural geometric surfaces arranged in 3D space; and
tie breaking hardware configured to report a single surface from multiple geometric surfaces based on a comparison of vertex values of the multiple geometric surfaces projected into a two-dimensional coordinate space, when the ray-surface testing hardware determines the ray intersects each of the multiple geometric surfaces at an edge or vertex shared by the multiple geometric surfaces.
11. The tree traversal unit of claim 10 , wherein ray-surface testing hardware is configured to receive, from a processor, a query including ray information and information about a bounding volume hierarchy, traverse the bounding volume hierarchy to determine a bounding volume within said bounding volume hierarchy the ray intersects, and test intersection between the ray and the plural geometric surfaces associated with the bounding volume intersected by the ray.
12. The tree traversal unit of claim 10 , wherein the ray-surface testing hardware includes a spatial transformer that projects the plural geometric surfaces onto a plane for ray intersection testing.
13. A tree traversal unit comprising hardware circuitry configured to:
receive, from a processor, instructions to test intersections between a ray and a plurality of primitives;
determine, using an arithmetic unit, whether the ray going through a surface formed by the plurality of primitives intersects an edge or vertex shared by N primitives, N>1; and
when the ray is determined to intersect the edge or vertex shared by N primitives, push intersection information for less than N primitives sharing the edge or vertex onto a stack based on comparing vertex locations of vertices shared by the N primitives and transformed into a two-dimensional coordinate space; and
report, to the processor, intersection information in the stack.
14. The tree traversal unit of claim 13 , wherein when the ray is determined to intersect the edge or vertex shared by the N primitives, intersection information for a single primitive of the N primitives is push onto the stack.
15. The tree traversal unit of claim 13 , wherein the hardware circuitry is further configured to, when the ray is determined to intersect the edge or vertex of a primitive not shared by another primitive, push onto the stack intersection information for the intersected primitive.
16. The tree traversal unit of claim 13 , wherein the hardware circuitry is further configured to, when the ray is determined to intersect a primitive not on an edge or vertex, push onto the stack intersection information for the intersected primitive.
17. The tree traversal unit of claim 13 , wherein the intersection information for less than N primitives from the N primitives is determined based on a tie-breaking rule that compares vertex values of vertices shared by the N primitives transformed into ray coordinate space.
18. The tree traversal unit of claim 13 , wherein the arithmetic unit includes a fused floating point operation unit configured to combine multiple floating-point arithmetic operations used in determining whether the ray goes through a surface formed by the plurality of primitives.
19. The tree traversal unit of claim 13 , wherein the arithmetic unit is configured to perform arithmetic operations with expanded 10-bit exponent range.