面向海量三角形场景、允许5%误差的快速3D三角形近似最近点求解方案咨询
面向海量三角形场景、允许5%误差的快速3D三角形近似最近点求解方案咨询
我现在遇到这么个需求:要给大量三角形计算到球心的最近点,但对精度要求不高——大概有5%的误差是完全可以接受的。
目前我用的是两套检测逻辑:先判断点是否在三角形内(IsPointInTriangle),再对三角形的三条边分别计算最近点(GetClosestPointOnLine)。具体代码如下:
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; }
这两个函数本身速度不算慢,除了GetClosestPointOnLine里有个开方运算。但面对海量三角形的场景,我总觉得应该有更快的方法——毕竟精度可以放宽到5%呢。有没有数学大佬能给我支个招,提供一种牺牲精度换速度的近似最近点求解方法?
另外我自己琢磨了一个思路:用四个平面(三角形所在平面加上三个沿法向方向的边平面),先把点投影到三角形平面,再用边平面做裁剪。但不确定这个方法会不会更快。
备注:内容来源于stack exchange,提问作者KiraHoneybee
相关产品推荐
相关产品推荐

