3D空间中射线与三角形的交叉检测算法

小灰灰 2022-07-15 23:53 200阅读 0赞

http://blog.csdn.net/i\_dovelemon/article/details/38332499

# 引言 #

射线Ray，在3D图形学中有很多重要的应用。比如，pick操作就是使用射线Ray来实现的，还有诸如子弹射线的碰撞检测等等都可以使用射线Ray来完成。所以，在本次博客中，将会简单的像大家介绍下，如何进行Ray-Triangle的交叉检测。

# Ray-Triangle交叉检测算法 #

在Tomas Moller的MT97论文中，提出了一种新的算法。这种算法能够减少以前进行Ray-Triangle交叉检测所需要的内存消耗。在以前，进行Ray-Triangle交叉检测，主要是计算射线与三角形所构成的平面的交点，然后重新判断交点是否在三角形上，从而来判断是否发生了交叉。这种方法很直观，符合我们一直以来所学的数学知识。但是，这种检测方法进行的计算较多，而且还需要根据三角形来求它所在的平面，这样又需要进行计算，同时也需要另外开辟空间来保存计算出来的平面。

数学之美，就在于能够找到其他的方法来代替这种显而易见的方式，从而将问题简化到一定的程度。这种简化的过程，不需要在代码中实现，只需要我们事先根据条件，然后在草稿纸上计算出最后的结论，我们只需要在我们的代码中直接使用最终得到的结论即可。

在Tomas Moller的论文中，它提到了这样的一个概念：

如果一个点在三角形V0， V1， V2上，那么这个点就可以用如下的方式来表示：

T(u, v) = (1 - u - v) \* V0 + u \* V1 + v \* V2 ;

这里u+v <= 1, u >= 0 , v >=0

而对于射线，我们一般使用如下的方程来表示它：

R (t)= O + t \* D ; (O为射线的起始点，D为射线的方向)

所以，既然他们要有交点，我们就能够直接使用如下的方法来得出：

O + t \* D = (1 - u - v) \* V0 + u \* V1 + v \* V2

然后在进行一系列的变换，最终得到结果。感兴趣的读者可以自行阅读[Tomas Moller的论文][Tomas Moller]，论文中详细的解释了推导过程。这里不再赘述。

# Ray-Triangle交叉检测算法实现 #

以下是Ray-Triangle交叉检测算法的Moller算法实现，基本上就是Tomas Moller论文中代码的拷贝，如下所示：

**\[cpp\]** [view plain][] [copy][view plain]

1.  <span style="font-family:Microsoft YaHei;">**bool** Ray::intersectWithTriangle(VECTOR3 v0,VECTOR3 v1, VECTOR3 v2, 
2.  **bool** bCull, 
3.  **float** \*t) 
4.  \{ 
5.   VECTOR3 edge1, edge2, tvec, pvec, qvec ; 
6.  **float** det, inv\_det ; 
7.  **float** u,v ; 
8.  
9.  //Find vectors for two edges sharing vert0
10.  Vec3Sub(edge1, v1, v0); 
11.  Vec3Sub(edge2, v2, v0); 
12. 
13. //Begin calculating determinant - also used to calculate U parameter
14.  Vec3Cross(pvec, dir, edge2); 
15. 
16. //If the determinant is near zero, ray lies in plane of triangle
17.  Vec3Dot(det, edge1, pvec); 
18. 
19. //If bCull is true
20. **if**(bCull) 
21.  \{ 
22. **if**(det < 0.00001f) 
23. **return****false** ; 
24. 
25. //Calculate distance from vert0 to ray origin
26.  Vec3Sub(tvec, origin, v0); 
27. 
28. //Calculate U parameter and test bounds
29.  Vec3Dot(u, tvec, pvec); 
30. **if**(u < 0.0 || u > det) 
31. **return****false** ; 
32. 
33. //Prepare to test v parameter
34.  Vec3Cross(qvec, tvec, edge1); 
35. 
36. //Calculate V parameter and test bounds
37.  Vec3Dot(v, dir, qvec); 
38. **if**(v < 0.0f || u + v > det) 
39. **return****false** ; 
40. 
41. //Calculate t , scale paramter, ray intersect triangle
42.  Vec3Dot(\*t, edge2, qvec); 
43.  inv\_det = 1.0f / det ; 
44.  \*t \*= inv\_det ; 
45.  u \*= inv\_det ; 
46.  v \*= inv\_det ; 
47.  \} 
48. **else**
49.  \{ 
50. **if**(det > -0.00001f && det < 0.00001) 
51. **return****false** ; 
52.  inv\_det = 1.0f / det ; 
53. 
54. //calculate distance from v0 to ray origin
55.  Vec3Sub(tvec, origin, v0); 
56. 
57. //Calculate u parameter and test bounds
58.  Vec3Dot(u, tvec, pvec); 
59.  u \*= inv\_det ; 
60. **if**(u < 0.0 || u > 1.0) 
61. **return****false** ; 
62. 
63. //prepare to test v parameter
64.  Vec3Cross(qvec, tvec, edge1); 
65. 
66. //Calculate v parameter and test bounds
67.  Vec3Dot(v, dir, qvec); 
68.  v \*= inv\_det ; 
69. **if**(v < 0.0 || u + v > 1.0) 
70. **return****false** ; 
71. 
72. //calculate t, ray intersect triangle
73.  Vec3Dot(\*t, edge2, qvec); 
74.  \*t \*= inv\_det ; 
75.  \} 
76. 
77. **return****true** ; 
78. \}// end for intersectWithTriangle</span>

# 示例程序截图 #

这个图是在没有发生交叉的时候的情况，

![SouthEast][]

下图是在发生了交叉之后的截图：

![SouthEast 1][]

今天的笔记就此结束。以后会陆续出现这种文章，请大家关注吧！！！

[Tomas Moller]: http://blog.csdn.net/i_dovelemon/article/details/www.graphics.cornell.edu/pubs/1997/MT97.html
[view plain]: http://blog.csdn.net/i_dovelemon/article/details/38332499#
[SouthEast]: /images/20220716/67c5b806470a48ebb71049b2e333386a.png
[SouthEast 1]: /images/20220716/968e5dfe0bd5400599f1a6dfe1c94300.png