空間中判斷點在三角形内算法(方程法)

詳細介紹了空間中判斷點在三角形内算法的實作。

目錄

• 1. 概述
• 2. 詳論
  • 2.1. 原理
  • 2.2. 實作
• 3. 參考

三維空間中判斷點在三角形内外的算法與平面中有所不同，《平面中判斷點在三角形内算法(同向法)》中提到的算法在三維空間中已經無法生效，也很難利用上。一個最簡單的思路就是，擷取三角形的空間向量方程，判斷點是否能讓這個空間向量方程成立。

在我的另外一篇文章《空間射線與三角形相交算法的兩種實作》中提到了三角形的空間向量方程。對于三個頂點為V0，V1，V2組成的空間三角形，對于三角形内的任一點P，有如下參數方程：

\[\vec{P} = (1 - u - v) \vec{V_0} + u \vec{V_1} + v \vec{V_2}

\]

變換位置，有：

\[\vec{P} - \vec{V_0} = (\vec{V_0} - \vec{V_1}) u + (\vec{V_0} - \vec{V_2}) v

\[\vec{V_0P} = (\vec{V_0V_1}) u + (\vec{V_0V_2}) v

其中，u，v是未知的，而使用的向量是三維向量。顯然，這是一個超定方程組。求解這個方程組，如果解是沖突的，說明點不在空間三角形内；否則，點可能在三角形上。

具體的C++代碼如下：

//空間三角形
//按照逆時針順序插入值并計算法向量
template <class T>
class Triangle
{
public:
    Vec3<T> v0;
    Vec3<T> v1;
    Vec3<T> v2;

    Vec3<T> vn;

    Vec3<T> min;
    Vec3<T> max;

    Triangle()
    {

    }

    Triangle(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2)
    {
        this->v0 = v0;
        this->v1 = v1;
        this->v2 = v2;

    }

    void Set(Vec3<T> v0, Vec3<T> v1, Vec3<T> v2)
    {
        this->v0 = v0;
        this->v1 = v1;
        this->v2 = v2;
    }


    // 判斷點P是否在空間三角形内
    bool PointInTriangle3D(Vec3<T>& P)
    {
        auto v0p = P - v0;
        auto v0v1 = v1 - v0;
        auto v0v2 = v2 - v0;

        double D = v0v1.x() * v0v2.y() - v0v1.y() * v0v2.x();
        if(D == 0.0)
        {
            return false;
        }

        double D1 = v0p.x() * v0v2.y() - v0p.y() * v0v2.x();
        double D2 = v0v1.x() * v0p.y() - v0v1.y() * v0p.x();

        double u = D1/D;
        double v = D2/D;

        double eps = v0v1.z() * u + v0v2.z() * v - P.z();
        if(u >= 0 && v >= 0 && u + v <= 1 && abs(eps) < 0.000001)
        {
            return true;
        }

        return false;
    }
           

這裡采取的算法是，通過x，y分量組成的兩個方程式解出方程組的暫時u、v。然後将u、v帶入到z分量方程式，檢查能否保證z分量方程式成立。如果成立，且滿足三角形内部點方程的條件（u >= 0， v >= 0， u + v <= 1），說明點在空間三角形上，反之，點在空間三角形外。

1. 《平面中判斷點在三角形内算法(同向法)》
2. 《空間射線與三角形相交算法的兩種實作》

詳細代碼