c++ 快速，但不一定精确，3D三角形上的最近点？

kcrjzv8t 于 2023-08-09 发布在其他

关注(0)|答案(2)|浏览(117)

我有一个例子，我需要在很多三角形上找到最接近球体中心的点。然而，准确性并不那么重要...它需要是模糊准确的，但是5%的误差率是可以接受的。
目前我使用两个测试-- IsPointInTriangle和所有三个三角形边的直线上的最近点。具体来说，这段代码：

Vector Math::GetClosestPointOnLine(Vector thePos, Vector theL1, Vector theL2)
{
    //
    // Do NOT try to optimize this like the 2D version... when I did it screwed up all the Hamsterball physics!
    //
    Vector aC=thePos-theL1;
    Vector aV=theL2-theL1; 

    float aD=aV.Length();
    aV/=aD;

    float aT=Dot(aV,aC);

    if (aT<0.0f) return (theL1);
    if (aT>aD) return (theL2);

    // Return the point between ‘a’ and ‘b’
    //set length of V to t. V is normalized so this is easy
    aV*=aT;
    return (theL1+aV);  
}

bool Math::IsPointInTriangle(Vector thePos, Vector theT1, Vector theT2, Vector theT3)

//bool IsPointInTriangle(const VECTOR& point,
//  const VECTOR& pa,const VECTOR& pb, const VECTOR& pc)
{
    Vector e10=theT2-theT1;
    Vector e20=theT3-theT1;
    float a = e10.Dot(e10);
    float b = e10.Dot(e20);
    float c = e20.Dot(e20);
    float ac_bb=(a*c)-(b*b);
    Vector vp(thePos.mX-theT1.mX, thePos.mY-theT1.mY, thePos.mZ-theT1.mZ);
    float d = vp.Dot(e10);
    float e = vp.Dot(e20);
    float x = (d*c)-(e*b);
    float y = (e*a)-(d*b);
    float z = x+y-ac_bb;
    return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000)!=0;
}

字符串
这两个都是相当快的，除了一个sqrt在closestpointonline。但似乎有更快的方法。有没有数学奇才能告诉我一个更快的方法--以牺牲准确性为代价--粗略地说“三角形的最近点，误差阈值可能是5%？”“
编辑以添加：我能想到的唯一替代方法是制作四个平面（三角形平面+三角形法线方向的边平面），然后落在三角形的平面上，然后剪切到所有边平面。但我不确定这是否会更快。

c++

来源：https://stackoverflow.com/questions/76797905/fast-but-not-necessarily-pinpoint-accurate-closest-point-on-3d-triangle

2条答案

按热度按时间

pepwfjgg1#

这不是一个算法优化，但你可以在GetClosestPointOnLine中完全摆脱sqrt。
这就是你在第一部分中计算的内容：

aC = thePos - theL1
aV1 = theL2 - theL1 // first value of aV
aD = sqrt(aV1x*aV1x + aV1y*aV1y + aV1z*aV1z)
aV2 = aV1/aD // second value of aV
aT = aV2x*aCx + aV2y*aCy + aV2z*aCz = (aV1x*aCx + aV1y*aCy) / aD
// comparisons aT < 0.0f and aT > aD
aV3 = aV2*aT = aV1 * (aV1x*aCx + aV1y*aCy) / (aD*aD) // third value of aV

字符串
我们将假设aD > 0，否则您已经在aV/=aD中拥有UB。
对于aT < 0.0f，不需要1/aD比例因子。
对于aT > aD，您可以改为写aT*aD > aD*aD，即：

aV1x*aCx + aV1y*aCy > aV1x*aV1x + aV1y*aV1y

型
如果你在aD中删除sqrt，删除aV/=aD行，并相应地更改最后一个返回值（aV3），那么计算变为：

aC = thePos - theL1
aV1 = theL2 - theL1
aD = aV1x*aV1x + aV1y*aV1y
aT = aV1x*aCx + aV1y*aCy
// comparisons aT < 0.0f and aT > aD
aV3 = aV1*aT/aD

型
代码：

Vector Math::GetClosestPointOnLine(Vector thePos, Vector theL1, Vector theL2)
{
    Vector aC=thePos-theL1;
    Vector aV=theL2-theL1; 

    float aD = aV.LengthSquared(); // or Dot(aV, aV)
    float aT = Dot(aV, aC);

    if (aT<0.0f) return (theL1);
    if (aT>aD) return (theL2);

    aV*=aT/aD;
    return (theL1+aV);  
}

型
我用几个随机向量做了a quick test，采用所有三条路径，以确保两个版本返回相同的向量。

赞(0）回复(0）举报 2023-08-09

xxe27gdn2#

设三角形的顶点为A、B和C。
找到三角形P的质心（我们需要三角形内的任意点，这是一个很容易计算的顶点平均值）。
现在假设你想找到三角形中最接近点X的点。首先将X投影到三角形的平面上（称此点为Y）。
现在计算norm(P-A).(P-Y)，norm(P-B).(P-Y)，norm(P-C).(P-Y)。找出哪两个点的值最大。这是具有最小Angular triangle_vertex-centroid-Y的两个顶点，并且将是三角形上最接近的点所在的线的两个点。
现在找到从Y到这两点定义的直线的最近点。它必然位于这两点之间。称该点为Z。
现在返回abs(P-Z)<abs(P-Y) ? Z : Y（如果它已经在三角形上并且Z更远，则返回Y）。
这应该更快，因为它只计算一次直线上最近的点，并且您跳过了显式检查该点是否在三角形中。
（norm(vector)是归一化向量，或vector/abs(vector)，abs(vector)是向量的大小，在您的代码中似乎是vector.Length()）

赞(0）回复(0）举报 2023-08-09

我来回答

c++ 快速，但不一定精确，3D三角形上的最近点？

2条答案

相关问题

热门标签

最新问答