Robust ray-triangle intersection

• US 10,692,271 B1
• Filed: 12/13/2018
• Issued: 06/23/2020
• Est. Priority Date: 12/13/2018
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Saleh, Skyler Jonathon
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US16/219,809
• Publication Number:
  US 20200193683A1
• Time in Patent Office: 558 Days
• Field of Search: None
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

A technique for classifying a ray tracing intersection with a triangle edge or vertex avoids either rendering holes or multiple hits of the same ray for different triangles. The technique employs a tie-breaking scheme in which certain types of edges are classified as hits and certain types of edges are classified as misses. The test is performed in a coordinate space that comprises a projection into the viewspace of the ray, and thus where the ray direction has a non-zero magnitude in one axis (e.g., z) but a zero magnitude in the two other axes. In this coordinate space, edges are classified as one of top, bottom, left, and right, and an intersection on an edge counts as a hit if the intersection hits a top or left edge, but a miss if the intersection hits a bottom or right edge. Vertices are processed in a related manner.

Claims

1. A computing device configured to test for intersection of a ray by a triangle, the computing device comprising:

a processor configured to generate a ray intersection test request for testing for intersection between a ray and a triangle; and

a ray intersection test unit configured to receive the ray intersection test request and to test for intersection between the ray and a triangle, by;

determining a location of an intersection between the ray and the triangle;

detecting that the intersection is on one of an edge or a vertex of the triangle;

classifying the intersection as one of an intersection with a left edge, a right edge, a top edge, a bottom edge, a vertex bordering both left edges or one left edge and one top edge, or a vertex bordering a right edge or a bottom edge; and

based on the classifying, classifying the intersection as a hit or a miss.

2. The computing device of claim 1, wherein the intersection falls on an edge of the triangle and classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme wherein intersections on edges that border multiple triangles are classified as hits for triangles on one side of the edge but not on the other side of the edge.

3. The computing device of claim 1, wherein classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which intersections on left edges or top edges are classified as hits and intersections on right edges or bottom edges are classified as misses.

4. The computing device of claim 1, wherein:

a top edge comprises an edge that is exactly horizontal and has an outward facing normal that points in a positive y direction;

a bottom edge comprises an edge that is exactly horizontal and has an outward facing normal that points in a negative y direction;

a left edge comprises an edge that has an outward facing normal with a negative x component; and

a right edge comprises an edge that has an outward facing normal with a positive x component.

5. The computing device of claim 1, wherein the intersection falls on a vertex of the triangle and classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which, for an intersection that falls on a vertex that is shared between triangles, the intersection is classified as a hit for only one triangle that borders the vertex.

6. The computing device of claim 1, wherein classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which intersections on vertices that border both left edges or a top edge and a left edge are classified as hits and intersections on vertices that border either a bottom edge or a right edge are classified as misses.

7. The computing device of claim 1, wherein determining a location of an intersection between the ray and the triangle comprises determining barycentric coordinates of a point corresponding to the ray within the triangle, in a coordinate space in which the ray direction points in the negative z direction and has no x or y components.

8. The computing device of claim 7, wherein detecting that the intersection is on an edge comprises detecting that one of the barycentric coordinates has a value of zero.

9. The computing device of claim 8, wherein detecting that the intersection is on a vertex comprises detecting that two of the barycentric coordinates have a value of zero.

10. A method for testing for intersection of a ray by a triangle, the method comprising:

in response to a ray intersection test request for testing for intersection between the ray and the triangle;

determining a location of an intersection between the ray and the triangle;

detecting that the intersection is on one of an edge or a vertex of the triangle;

classifying the intersection as one of an intersection with a left edge, a right edge, a top edge, a bottom edge, a vertex bordering both left edges or one left edge and one top edge, or a vertex bordering a right edge or a bottom edge; and

based on the classifying, classifying the intersection as a hit or a miss.

11. The method of claim 10, wherein the intersection falls on an edge of the triangle and classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme wherein intersections on edges that border multiple triangles are classified as hits for triangles on one side of the edge but not on the other side of the edge.

12. The method of claim 10, wherein classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which intersections on left edges or top edges are classified as hits and intersections on right edges or bottom edges are classified as misses.

13. The method of claim 10, wherein:

a top edge comprises an edge that is exactly horizontal and has an outward facing normal that points in a positive y direction;

a bottom edge comprises an edge that is exactly horizontal and has an outward facing normal that points in a negative y direction;

a left edge comprises an edge that has an outward facing normal with a negative x component; and

a right edge comprises an edge that has an outward facing normal with a positive x component.

14. The method of claim 10, wherein the intersection falls on a vertex of the triangle and classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which, for an intersection that falls on a vertex that is shared between triangles, the intersection is classified as a hit for only one triangle that borders the vertex.

15. The method of claim 10, wherein classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme in which intersections on vertices that border both left edges or a top edge and a left edge are classified as hits and intersections on vertices that border either a bottom edge or a right edge are classified as misses.

16. The method of claim 10, wherein determining a location of an intersection between the ray and the triangle comprises determining barycentric AMD-180445-US-NP coordinates of a point corresponding to the ray within the triangle, in a coordinate space in which the ray direction points in the negative z direction and has no x or y components.

17. The method of claim 16, wherein detecting that the intersection is on an edge comprises detecting that one of the barycentric coordinates has a value of zero.

18. The method of claim 17, wherein detecting that the intersection is on a vertex comprises detecting that two of the barycentric coordinates have a value of zero.

19. A ray intersection test unit configured to receive a ray intersection test request and to test for intersection between the ray and a triangle, by:

determining a location of an intersection between the ray and the triangle;

detecting that the intersection is on one of an edge or a vertex of the triangle;

classifying the intersection as one of an intersection with a left edge, a right edge, a top edge, a bottom edge, a vertex bordering both left edges or one left edge and one top edge, or a vertex bordering a right edge or a bottom edge; and

based on the classifying, classifying the intersection as a hit or a miss.

20. The ray intersection test unit of claim 19, wherein the intersection falls on an edge of the triangle and classifying the intersection as a hit or a miss comprises classifying the intersection according to a scheme wherein intersections on edges that border multiple triangles are classified as hits for triangles on one side of the edge but not on the other side of the edge.