最近在看recast&detour源码的时候有遇到许多数学上的算法问题，特此记录，以便以后查看。

分析

问题：已经线段pq (p起点 q终点) ，三角形abc，判断pq与abc有无交点。

一是求射线与三角形所在平面的交点，二是判断交点是否在三角形内部。这是在如下函数中处理的：

static bool intersectSegmentTriangle(const float* sp, const float* sq,
                                     const float* a, const float* b, const float* c,
                                     float &t)
{
    float v, w;
    float ab[3], ac[3], qp[3], ap[3], norm[3], e[3];
    rcVsub(ab, b, a);
    rcVsub(ac, c, a);
    rcVsub(qp, sp, sq);

    // Compute triangle normal. Can be precalculated or cached if
    // intersecting multiple segments against the same triangle
    rcVcross(norm, ab, ac);

    // Compute denominator d. If d <= 0, segment is parallel to or points
    // away from triangle, so exit early
    float d = rcVdot(qp, norm);
    if (d <= 0.0f) return false;

    // Compute intersection t value of pq with plane of triangle. A ray
    // intersects iff 0 <= t. Segment intersects iff 0 <= t <= 1. Delay
    // dividing by d until intersection has been found to pierce triangle
    rcVsub(ap, sp, a);
    t = rcVdot(ap, norm);
    if (t < 0.0f) return false;
    if (t > d) return false; // For segment; exclude this code line for a ray test

    // Compute barycentric coordinate components and test if within bounds
    rcVcross(e, qp, ap);
    v = rcVdot(ac, e);
    if (v < 0.0f || v > d) return false;
    w = -rcVdot(ab, e);
    if (w < 0.0f || v + w > d) return false;

    // Segment/ray intersects triangle. Perform delayed division
    t /= d;

    return true;
}

这是一个纯粹的数学问题：设P、Q为射线的起止点，三角形的三个顶点分别为A、B、C，我们得到如下的几何模型：

空间中直线段和三角形的相交算法
程序先求三角形所在平面的法向量norm−→−−norm→，再用叉乘将AP−→−AP→、QP−→−QP→分别映射到norm−→−−norm→所在方向，分别得到高度t和d，若t>d，则射线PQ肯定与平面没有交点，直接return。
接下来再判断交点是否在三角形内部。这里要用到的一个概念叫做质心坐标系（不明白的可以百度）。大概意思就是三角形ABC所在平面的点可以表示成：
M=(1−λ1−λ2)a→+λ1b→+λ2c→M=(1−λ1−λ2)a→+λ1b→+λ2c→
而三角形内部的点必定满足：λ1λ1和λ2λ2都在(0,1)范围内。
通过这个性质，再加一系列的方程计算和矩阵变换可以判断出交点是否在三角形内部（演算过程这里略过，具体可看《空间中直线段和三角形的相交算法》，说得很详细了）。若不在则直接return，否则将t/d作为返回值传出，后面会用来求取最终的交点坐标。

空间中直线段和三角形的相交算法

分析

相关推荐