[bb] Ray Intersect Triangle Test by sswift [ 1+ years ago ]

[BlitzBot]

Title : Ray Intersect Triangle Test
Author : sswift
Posted : 1+ years ago

Description : This function is very useful and important for 3D programmers to have.  

It allows you to specify an infinite line in 3D (a ray) and a triangle, and determine if the line interesects the triangle.

As an added bonus, the intersection test this function performs also calculates the UV coordinates of the intersection point.   That means that if you have a texture tiled across the triangle once, you can determine which texel of the texture you hit.

The function does not return the U and V values by default.  You will have to modify it to do that if you need those values.

The original C source code to this function is located here:
<a href="http://www.acm.org/jgt/papers/MollerTrumbore97/code.html" target="_blank">http://www.acm.org/jgt/papers/MollerTrumbore97/code.html[/url]

This code has a slightly diffrent inner structure... there's a second set of code for if you want the function to do a backface check and report no collision if the polygon is facing away from the point specified on the line.  You should be able to add that functionality yourself with access to both these code snippets if you need it.

You can also modify the function to return a value T with the U and V values.  This T value can be used with the U and V values to find the point in world space where the collision occured.  This itself is very useful.  Unfortunately I don't know the math involved in making that conversion at this time.

The code also has another use.  It demonstrates how to do cross and dot products on vectors.  These are two very important equations used in a lot of 3D math.  I won't go into a big explanation for what they do or how they work... because I honestly don't even remember myself.  But if you come across an equation ont he net that requires one, well, there's how to do it!

Code :

Code: BlitzBasic

1. ; -------------------------------------------------------------------------------------------------------------------
2. ; This function returns TRUE if a ray intersects a triangle.
3. ;
4. ; It also calculates the UV coordinates of said colision as part of the intersection test,
5. ; but does not return them.
6. ;
7. ; V0xyz, V1xyz, and V2xyz are the locations of the three vertices of the triangle.
8. ;
9. ; V0 is location of UV(0,0).  V1 is the location of UV(1, 0).  V2 is the location of UV(0,1)
10. ; These are important to know if you want to return the exact location in texture space of the collision, but
11. ; you don't have to worry about them if you only want to find out if a collision occured.
12. ;
13. ; Pxyz is a point on the line.
14. ;
15. ; Dxyz is a vector providing the slope of the line.
16. ; -------------------------------------------------------------------------------------------------------------------
17. Function Ray_Intersect_Triangle(Px#, Py#, Pz#, Dx#, Dy#, Dz#, V0x#, V0y#, V0z#, V1x#, V1y#, V1z#, V2x#, V2y#, V2z#)
18.  
19.  
20.         ; A couple definitions for vector operations:
21.  
22.                 ;crossproduct(a,b,c) =
23.                 ;ax = (by * cz) - (cy * bz)
24.                 ;ay = (bz * cx) - (cz * bx)    
25.                 ;az = (bx * cy) - (cx * by)
26.  
27.                 ;dotproduct(v,q) = (vx * qx) + (vy * qy) + (vz * qz)   
28.  
29.  
30.         ; vector(e1,v1,v0)
31.         E1x# = V1x# - V0x#
32.         E1y# = V1y# - V0y#
33.         E1z# = V1z# - V0z#
34.  
35.  
36.         ; vector(e2,v2,v0)
37.         E2x# = V2x# - V0x#
38.         E2y# = V2y# - V0y#
39.         E2z# = V2z# - V0z#
40.  
41.  
42.         ; crossproduct(h,d,e2)
43.         Hx# = (Dy# * E2z#) - (E2y# * Dz#)
44.         Hy# = (Dz# * E2x#) - (E2z# * Dx#)
45.         Hz# = (Dx# * E2y#) - (E2x# * Dy#)
46.  
47.  
48.         ; a = dotproduct(e1,h)
49.         A# = (E1x# * Hx#) + (E1y# * Hy#) + (E1z# * Hz#)
50.  
51.        
52.         ; If the ray is parallel to the plane then it does not intersect it.
53.         If (A# > -0.00001) And (A# < 0.00001)
54.                 Return False
55.         EndIf
56.  
57.        
58.         F# = 1.0 / A#
59.        
60.  
61.         ; vector(s,p,v0)
62.         Sx# = Px# - V0x#
63.         Sy# = Py# - V0y#
64.         Sz# = Pz# - V0z#
65.  
66.                
67.         ;u = f * (dotProduct(s,h))
68.         U# = F# * ((Sx# * Hx#) + (Sy# * Hy#) + (Sz# * Hz#))
69.  
70.        
71.         ; If the value of the U coordinate is outside the range of values inside the triangle,
72.         ; then the ray has intersected the plane outside the triangle.
73.         If (U# < 0.0) Or (U# > 1.0)
74.                 Return False
75.         EndIf
76.  
77.        
78.         ; crossProduct(q,s,e1)
79.         Qx# = (Sy# * E1z#) - (E1y# * Sz#)
80.         Qy# = (Sz# * E1x#) - (E1z# * Sx#)
81.         Qz# = (Sx# * E1y#) - (E1x# * Sy#)
82.        
83.  
84.         ; v = f * dotProduct(d,q)
85.         V# = F# * ((Dx# * Qx#) + (Dy# * Qy#) + (Dz# * Qz#))
86.  
87.        
88.         ; If the value of the V coordinate is outside the range of values inside the triangle,
89.         ; then the ray has intersected the plane outside the triangle.
90.         ;
91.         ; U + V cannot exceed 1.0 or the point is not in the triangle.
92.         ;
93.         ; If you imagine the triangle as half a square this makes sense.  U=1 V=1 would be  in the
94.         ; lower left hand corner which would be in the second triangle making up the square.
95.         If (V# < 0.0) Or ((U# + V#) > 1.0)
96.                 Return(False)
97.         EndIf
98.        
99.  
100.         ; The point was in the triangle.  Yay!         
101.         Return True
102.  
103.                
104.         ; Note that you could also return the U and V coordinates calculated from this function
105.         ; if you need those values!
106.  
107.  
108. End Function

Comments : none...