射线与三角形求交

        射线与三角形求交 在几何选取、碰撞检测上 经常会用到，在计算机图形学上是最初级的应用。

        问题的由来 来自三维场景的鼠标点选，即通过鼠标点击 二维屏幕，对应于三维虚拟相机位置发出的一条射线，与场景中的几何进行求交。

        射线与三角形求交可以分为两步：

1. 射线与平面求交

2. 计算交点在对应三角形内的位置

        射线 可以描述为：p(t) = p0 + tu，    其中p0是射线的起始点，u是射线的方向向量（需要单位化），t在[0，+无穷]。

        平面 可以描述为：n.(p-p0) = 0，    其中p为平面上的任意一点，n为平面的单位法向量。

               设d = -n.p0   n=(a,b,c)   p=(x,y,z)，所以有：n.p+d = 0 即 ax+by+cz+d=0 为平面方程。

        空间中一点P，如果n.P + d =0，那么P在（n.p+d=0）表示的平面上，如果大于0，该点在平面的上面（法线所指的方向），如果小于0，该点在平面的下面。

射线与平面的交点：

        利用上面所介绍的射线和面的交点只要把 p(t) 代入（n.p+d=0）方程，就能够得到：

        n.p(t)+d = 0

        => n.(p_orig+t*vDir)+d=0;

        => n.p_orig+t*n.vDir+d=0;

        => t = (-d-n.p_orig)/ n.vDir = (n.p0-n.p_orig) / n.vDir

        => t = n.(p0- p_orig)/ n.vDir

        根据 p(t) = p_orig+t*vDir，如果 t 大于等于0说明射线和面有交点。

        代码可以描述为：

// 射线与三角形求交V0，V1，V2三角形三顶点 I为交点
bool rayIntersect(const Point3D& origin,const CVector3& rayDir,Point3D& interPoint)
{
	// 射线与三角形平行? 
	CVector3 u = v1 - v0;    // edge1
	CVector3 v = v2 - v0;    // edge2
	CVector3 norm = u.getCrossProduct(v);  // normal

	if (norm == CVector3(0.0f, 0.0f, 0.0f))  // triangle is degenerate 
	    return false;

	// 计算射线与平面法向夹角
	float b = norm.getDotProduct(rayDir);
	if (fabs(b) < e-5)      // ray is parallel to triangle plane   
	    return false;

	// 计算v0到射线起始点的向量
	CVector3 w0 = origin - v0;
	float a = -( norm.getDotProduct(w0) ); 

	// get intersect point of ray with triangle plane   
	float r = a / b;  
	if (r < 0.0f)                 // ray goes away from triangle   
	    return false;                 // => no intersect   
	// for a segment, also test if (r > 1.0) => no intersect   

	// 计算射线与平面的交点
	interPoint = origin + r * rayDir;

	// 计算交点是否在三角形内部?   
	float uu = u.getDotProduct(u);  
	float uv = u.getDotProduct(v);  
	float vv = v.getDotProduct(v);  
	CVector3 w = interPoint - v0;
	float wu = w.getDotProduct(u);
	float wv = w.getDotProduct(v);
	float D = uv * uv - uu * vv;

	// get and test parametric coords   
	float s = (uv * wv - vv * wu) / D;  
	if (s < 0.0f || s > 1.0f)       // I is outside T   
	    return false;  

	float t = (uv * wu - uu * wv) / D;  
	if (t < 0.0f || (s + t) > 1.0f) // I is outside T   
	    return false;  

	return true;   // 交点在三角形内部 
}

        里面用到的 点乘、叉乘等操作 比较简单，大家可以自己实现，作者也将会在后续章节中进行汇总实现。

        另外，场景求交是一个系统工程，需要考虑到复杂场景的大量计算，因此，效率是我们需要重点考虑的一个问题，通常，包围盒是一种非常好的加速计算的方法，可以大大减少非必要的求交计算过程。