什么是find重心坐标的最有效的方法?

在我的剖析器中,find重心坐标显然有些瓶颈。 我正在寻求使它更有效率。

它遵循shirley中的方法,计算通过将点Pembedded三角形形成的三角形的面积。

巴里

码:

Vector Triangle::getBarycentricCoordinatesAt( const Vector & P ) const { Vector bary ; // The area of a triangle is real areaABC = DOT( normal, CROSS( (b - a), (c - a) ) ) ; real areaPBC = DOT( normal, CROSS( (b - P), (c - P) ) ) ; real areaPCA = DOT( normal, CROSS( (c - P), (a - P) ) ) ; bary.x = areaPBC / areaABC ; // alpha bary.y = areaPCA / areaABC ; // beta bary.z = 1.0f - bary.x - bary.y ; // gamma return bary ; } 

这种方法的作品,但我正在寻找一个更有效的一个!

从Christer Ericson的实时碰撞检测 (顺便说一下,这是一本很好的书)转录:

 // Compute barycentric coordinates (u, v, w) for // point p with respect to triangle (a, b, c) void Barycentric(Point p, Point a, Point b, Point c, float &u, float &v, float &w) { Vector v0 = b - a, v1 = c - a, v2 = p - a; float d00 = Dot(v0, v0); float d01 = Dot(v0, v1); float d11 = Dot(v1, v1); float d20 = Dot(v2, v0); float d21 = Dot(v2, v1); float denom = d00 * d11 - d01 * d01; v = (d11 * d20 - d01 * d21) / denom; w = (d00 * d21 - d01 * d20) / denom; u = 1.0f - v - w; } 

这是Cramer解决线性系统的有效规则。 如果这仍然是一个瓶颈(可能是:它看起来不像现在的algorithm在计算方面有很大的不同),那么你可能需要find其他的地方获得加速。

请注意,这里有相当数量的值与p无关,如果需要,可以使用三角形caching它们。

稍微快一点:预先计算分母,并乘以而不是除法。 分支比乘法要昂贵得多。

 // Compute barycentric coordinates (u, v, w) for // point p with respect to triangle (a, b, c) void Barycentric(Point a, Point b, Point c, float &u, float &v, float &w) { Vector v0 = b - a, v1 = c - a, v2 = p - a; float d00 = Dot(v0, v0); float d01 = Dot(v0, v1); float d11 = Dot(v1, v1); float d20 = Dot(v2, v0); float d21 = Dot(v2, v1); float invDenom = 1.0 / (d00 * d11 - d01 * d01); v = (d11 * d20 - d01 * d21) * invDenom; w = (d00 * d21 - d01 * d20) * invDenom; u = 1.0f - v - w; } 

然而在我的实现中,我caching了所有的自variables。 我在构造函数中预先计算以下内容:

 Vector v0; Vector v1; float d00; float d01; float d11; float invDenom; 

所以最终的代码如下所示:

 // Compute barycentric coordinates (u, v, w) for // point p with respect to triangle (a, b, c) void Barycentric(Point a, Point b, Point c, float &u, float &v, float &w) { Vector v2 = p - a; float d20 = Dot(v2, v0); float d21 = Dot(v2, v1); v = (d11 * d20 - d01 * d21) * invDenom; w = (d00 * d21 - d01 * d20) * invDenom; u = 1.0f - v - w; } 

克莱默的规则应该是解决这个问题的最好方法。 我不是一个graphics家伙,但我想知道为什么在实时碰撞检测这本书,他们不做以下简单的事情:

 // Compute barycentric coordinates (u, v, w) for // point p with respect to triangle (a, b, c) void Barycentric(Point p, Point a, Point b, Point c, float &u, float &v, float &w) { Vector v0 = b - a, v1 = c - a, v2 = p - a; den = v0.x * v1.y - v1.x * v0.y; v = (v2.x * v1.y - v1.x * v2.y) / den; w = (v0.x * v2.y - v2.x * v0.y) / den; u = 1.0f - v - w; } 

这直接解决了2×2线性系统

 v v0 + w v1 = v2 

而本书的方法解决了这个系统

 (v v0 + w v1) dot v0 = v2 dot v0 (v v0 + w v1) dot v1 = v2 dot v1 

我会使用John发布的解决scheme,但是我会使用SSS 4.2 dot内在和sse rcpss内在的鸿沟,假设你可以限制自己Nehalem和更新的进程和有限的精度。

或者,您可以使用sse或avx一次计算多个重心坐标,进行4或8倍加速。

我试图将@ NielW的代码复制到C ++,但是没有得到正确的结果。

阅读https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles并计算在那里给出的lambda1 / 2/3更容易(不需要任何向量函数)。

如果p(0..2)是具有x / y / z的三角形的点:

三角形预分析:

 double invDET = 1./((p(1).yp(2).y) * (p(0).xp(2).x) + (p(2).xp(1).x) * (p(0).yp(2).y)); 

那么点“点”的lambdas是

 double l1 = ((p(1).yp(2).y) * (point.xp(2).x) + (p(2).xp(1).x) * (point.yp(2).y)) * invDET; double l2 = ((p(2).yp(0).y) * (point.xp(2).x) + (p(0).xp(2).x) * (point.yp(2).y)) * invDET; double l3 = 1. - l1 - l2; 

您可以通过投影一个轴alignment的平面并使用user5302提出的方法将3D问题转换为2D问题。 这将导致完全相同的重心坐标,只要你确定你的三角形不投影成一条线。 最好的办法是投射到尽可能接近你的猎鹰方向的轴alignment平面。 这避免了共线性问题,并确保最大的准确性。

其次,您可以预先计算分母并将其存储为每个三角形。 这在之后节省了计算。

对于三角形ABC内的给定点N,可以通过将三角形ABN的面积除以三角形ABC的总面积来得到点C的重心权重。