为了计算该平面上的3D点的重心坐标,我必须先将平面和点投影到2D空间中。
在搜寻网络后,我已经很好地理解了如何在2D空间中计算重心坐标,但我卡在了找到将我的3D点投影到合适的2D平面的最佳方法上。
有人建议我通过“删除投影最小的轴”来实现这一点。在没有测试每个世界轴(xy、yz、xz)投影时形成的多边形面积的情况下,我该如何确定哪个投影是最佳的(具有最大的面积),因此最适合计算最准确的重心坐标?
这是根据OP的要求计算三维空间重心坐标的示例。给定:
"x"表示两个3D向量的叉积。
"len"表示3D向量的长度。
"u"、"v"、"w"是属于v0、v1和v2的重心坐标。
triArea = len((v1 - v0) x (v2 - v0)) * 0.5
u = ( len((v1 - p ) x (v2 - p )) * 0.5 ) / triArea
v = ( len((v0 - p ) x (v2 - p )) * 0.5 ) / triArea
w = ( len((v0 - p ) x (v1 - p )) * 0.5 ) / triArea
=> p == u * v0 + v * v1 + w * v2
叉积的定义如下:
v0 x v1 := { v0.y * v1.z - v0.z * v1.y,
v0.z * v1.x - v0.x * v1.z,
v0.x * v1.y - v0.y * v1.x }
警告 - 我对使用重心坐标和使用矩阵解决线性方程的几乎所有知识都是在昨晚学到的,因为我发现这个问题非常有趣。因此,以下内容可能是错误的,但是我放入的一些测试值似乎可以工作。
各位,请随意批评我是否完全搞砸了 - 但是让我们开始吧。
在三维空间中找到重心坐标(借助维基百科)
给定:
v0 = (x0, y0, z0)
v1 = (x1, y1, z1)
v2 = (x2, y2, z2)
p = (xp, yp, zp)
找到点p相对于由v0、v1和v2定义的三角形的重心坐标:b0、b1、b2。
已知:
xp = b0*x0 + b1*x1 + b2*x2
yp = b0*y0 + b1*y1 + b2*y2
zp = b0*z0 + b1*z1 + b2*z2
这可以被写为
[xp] [x0] [x1] [x2]
[yp] = b0*[y0] + b1*[y1] + b2*[y2]
[zp] [z0] [z1] [z2]
或者
[xp] [x0 x1 x2] [b0]
[yp] = [y0 y1 y2] . [b1]
[zp] [z0 z1 z2] [b2]
-1
[b0] [x0 x1 x2] [xp]
[b1] = [y0 y1 y2] . [yp]
[b2] [z0 z1 z2] [zp]
3x3矩阵的行列式为:
det = x0(y1*z2 - y2*z1) + x1(y2*z0 - z2*y0) + x2(y0*z1 - y1*z0)
它的伴随是
[y1*z2-y2*z1 x2*z1-x1*z2 x1*y2-x2*y1]
[y2*z0-y0*z2 x0*z2-x2*z0 x2*y0-x0*y2]
[y0*z1-y1*z0 x1*z0-x0*z1 x0*y1-x1*y0]
提供:
[b0] [y1*z2-y2*z1 x2*z1-x1*z2 x1*y2-x2*y1] [xp]
[b1] = ( [y2*z0-y0*z2 x0*z2-x2*z0 x2*y0-x0*y2] . [yp] ) / det
[b2] [y0*z1-y1*z0 x1*z0-x0*z1 x0*y1-x1*y0] [zp]
b0 = ((x1*y2-x2*y1)*zp+xp*(y1*z2-y2*z1)+yp*(x2*z1-x1*z2)) / det
b1 = ((x2*y0-x0*y2)*zp+xp*(y2*z0-y0*z2)+yp*(x0*z2-x2*z0)) / det
b2 = ((x0*y1-x1*y0)*zp+xp*(y0*z1-y1*z0)+yp*(x1*z0-x0*z1)) / det
这里涉及到不少加减乘除的计算,但没有平方根或三角函数。显然,这需要比纯2D计算更长时间,但根据你的投影启发式和计算的复杂程度,这可能是最快的方法。
正如我所提到的 - 我不知道我在说什么 - 但也许这个方法可以行得通,或者其他人可以来纠正它。
e1 = v1-v0
e2 = v2-v0
r = normalise(e1)
n = normalise(cross(e1,e2))
u = normalise(n X r)
temp = p-v0
pd.x = dot(temp, r)
pd.y = dot(temp, u)
pd.z = dot(temp, n)
现在可以通过设置pd.z = 0将pd投影到平面上。同时,pd.z是点与由3个三角形定义的平面之间的距离。即,如果投影点位于三角形内部,则pd.z是到三角形的距离。
另一个需要注意的点是,在旋转和投影到该平面后,顶点v0位于原点,v1沿x轴。
希望对你有所帮助。
更新:请忽略此方法,因为它并不适用于所有情况
我认为我已经找到了一个有效的解决方案。
NB:我需要将其投影到二维空间,而不是使用三维重心坐标进行操作,因为我需要尽可能地实现最高效的算法。查找适合的投影平面所产生的额外开销仍应小于使用更复杂的操作(如sqrt或sin()cos()函数)时产生的开销(我想我可以使用正弦/余弦的查找表,但这会增加内存占用,并且违背了这个任务的目的)。
我的第一次尝试是找到多边形每个轴上最小/最大值之间的差,然后消除具有最小差的轴。然而,正如@PeterTaylor所建议的,有些情况下,删除具有最小差异的轴可能会导致在投影到二维空间时产生直线而非三角形。这很糟糕。
因此,我的修订方案如下...
我还没有时间对这种方法进行单元测试,但经过初步测试,它似乎运行得非常好。我很想知道这是否实际上是最好的方法?
我的原始解决方案涉及使用子增量计算每个轴的分数,但存在缺陷,因为可能会生成所有三个轴的零分数,在这种情况下,要丢弃的轴仍然无法确定。“解决这个困境的方法是选择投影平面,使得投影三角形的面积最大化。这可以通过检查平面法线来完成;具有最大绝对值的坐标是我们将要丢弃的坐标。例如,如果法线是[–1, 0, 0],那么我们将丢弃顶点和p的x值,投影到yz平面上。”
我不确定这个建议是否真的是最好的。将三角形投影到包含它的平面上并不太难。在这里,我假设p实际上在那个平面内。
令d1 = sqrt((v1-v0).(v1-v0)) - 即v0-v1的距离。 同样地,令d2 = sqrt((v2-v0).(v2-v0))
v0 -> (0,0)
v1 -> (d1, 0)
那么v2呢?嗯,你知道v0-v2的距离为d2。你所需要的就是v1-v0-v2的角度。(v1-v0).(v2-v0) = d1 d2 cos(theta)。不失一般性,你可以将v2看作具有正y值。
然后对p应用类似的过程,只有一个例外:你不能保证它具有正y值。相反,你可以通过取(v1-v0)x(v2-v0) . (v1-v0)x(p-v0)的符号来检查它是否与v2具有相同的y符号。
你不需要确定最佳区域来找到一个合适的投影。
实际上,根本没有必要找到“最佳”投影,只需要找到一个足够好的投影,而且在投影到二维平面时不会退化成一条直线。
编辑 - 算法已删除,因为我没有考虑到退化情况。