检查线段或三角形是否与平截头体相交

Question

我有一个由六个平面组成的平截头体，法线全部指向内。我可以用这个函数检查一个点是否在截锥体内：

char ClassifyPoint(float x, float y, float z, char thePlane)
    {
        Vector& aPos=mPlane[thePlane].mPos;
        Vector& aNorm=mPlane[thePlane].mNormal;
        float aD=(aPos.mX-x)*aNorm.mX+(aPos.mY-y)*aNorm.mY+(aPos.mZ-z)*aNorm.mZ;
        if (aD<-0.0005f) return 1;if (aD>0.0005f) return -1;return 0;
    }

如果该点位于每个平面的前面、上面或后面，则给出 -1、0、1。这对于单个点来说效果很好，但是线段或三角形可能具有截锥体之外的所有点，但仍然与其相交。

判断直线或三角形是否相交的正确方法是什么？我尝试过的所有方法总是会产生误报，因为要检查六架飞机。

编辑，更多信息：

为了对一条线进行分类，我尝试了以下方法：

inline char ClassifyLine(Vector theL1, Vector theL2, char thePlane) 
    {
        return ClassifyPoint(theL1,thePlane)+ClassifyPoint(theL2,thePlane);
    }

如果两个点都在平面前面，则应生成“2”；如果跨过平面，则应生成 0；如果两个点都在平面后面，则应生成任何负数 - 对吗？

但是然后我尝试这个函数来查看平截头体是否包含一条线：

inline bool ContainsLine(Vector theLine1, Vector theLine2)
    {
        if (ClassifyLine(theLine1,theLine2,0)<0) return false;
        if (ClassifyLine(theLine1,theLine2,1)<0) return false;
        if (ClassifyLine(theLine1,theLine2,2)<0) return false;
        if (ClassifyLine(theLine1,theLine2,3)<0) return false;
        if (ClassifyLine(theLine1,theLine2,4)<0) return false;
        if (ClassifyLine(theLine1,theLine2,5)<0) return false;
        return true;
    }

对于某些跨越的线，我会同时得到误报和误报。我在这里做错了什么？

Answer 1

将线段剪切到由六个平面定义的六个半空间中的每一个。当且仅当此后仍有任何东西时，线段与截头体相交：

• 令 (a, b) 为点 a 和 b 之间的线段
• 对于每个平面 P：
  • 如果 a 和 b 都在 P 的“内侧”，则继续
  • 如果 a 和 b 都在 P 的“外侧”，则返回 false
  • 求 P 和 (a, b) 的交集 x
  • 如果 a 在 P 的“内部”一侧，则赋值 b := x
  • else（b 在 P 的“内部”一侧），分配 a := x
• 返回真