投影到二维平面进行重心计算

4
我有三个顶点,它们在3D空间中构成一个平面/多边形,分别是v0、v1和v2。
为了计算该平面上的3D点的重心坐标,我必须先将平面和点投影到2D空间中。
在搜寻网络后,我已经很好地理解了如何在2D空间中计算重心坐标,但我卡在了找到将我的3D点投影到合适的2D平面的最佳方法上。
有人建议我通过“删除投影最小的轴”来实现这一点。在没有测试每个世界轴(xy、yz、xz)投影时形成的多边形面积的情况下,我该如何确定哪个投影是最佳的(具有最大的面积),因此最适合计算最准确的重心坐标?

如果p确实位于由v0、v1和v2定义的平面上,并且在由相同点跨越的三角形内部,那么请继续使用叉积计算重心坐标 - 它也适用于3D,你知道的。 - Dave O.
@DaveO,尝试在三维空间中寻找重心坐标是否与在二维平面中寻找一样高效呢?如果是这样的话,您能否提供一个如何尝试此操作的示例呢? - Thomas Sampson
今天你可能不再需要这个,但如果有人偶然遇到这个问题。所寻找的内容在《实时光线追踪和交互式全局照明》一书中被详细描述为“投影方法”,该书由德国萨尔布吕肯萨尔兰大学计算机图形学小组的Ingo Wald编写,第103页。 - Kevin Streicher
7个回答

2

这是根据OP的要求计算三维空间重心坐标的示例。给定:

  • 定义三角形的3D点v0、v1、v2
  • 在由v0、v1和v2定义的平面上,存在于同一点组成的三角形内的3D点p。

"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 }

这看起来是一个不错的解决方案,但正如我在早先的评论中所建议的那样,我正在寻找一种使用快速数学运算(不包括sqrt和三角函数)的解决方案。我假设“len”函数需要一个sqrt。我认为我已经找到了一个投影到2D空间的解决方案,我现在会发布出来。 - Thomas Sampson

2

警告 - 我对使用重心坐标和使用矩阵解决线性方程的几乎所有知识都是在昨晚学到的,因为我发现这个问题非常有趣。因此,以下内容可能是错误的,但是我放入的一些测试值似乎可以工作。

各位,请随意批评我是否完全搞砸了 - 但是让我们开始吧。

在三维空间中找到重心坐标(借助维基百科)

给定:

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]

如果您需要对三角形进行多个点的测试,请在此处停止。仅为三角形计算上述3x3矩阵一次(同时除以行列式),然后将该结果与每个点进行点积,以获得每个点的重心坐标。
如果您只需对每个三角形执行一次,则以上内容如下(由Maxima提供):
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计算更长时间,但根据你的投影启发式和计算的复杂程度,这可能是最快的方法。

正如我所提到的 - 我不知道我在说什么 - 但也许这个方法可以行得通,或者其他人可以来纠正它。


嘿 @Gavin,这看起来立刻就和我之前正在处理的一些代码相似,那是从《实时碰撞检测》这本书中获取的。我会在有机会检查后再回复你。感谢你的兴趣! - Thomas Sampson

1
为了将点p投影到由顶点v0、v1和v2定义的平面上,您必须计算旋转矩阵。让我们称投影点为pd。
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轴。

希望对你有所帮助。


1

更新:请忽略此方法,因为它并不适用于所有情况

我认为我已经找到了一个有效的解决方案。

NB:我需要将其投影到二维空间,而不是使用三维重心坐标进行操作,因为我需要尽可能地实现最高效的算法。查找适合的投影平面所产生的额外开销仍应小于使用更复杂的操作(如sqrt或sin()cos()函数)时产生的开销(我想我可以使用正弦/余弦的查找表,但这会增加内存占用,并且违背了这个任务的目的)。

我的第一次尝试是找到多边形每个轴上最小/最大值之间的差,然后消除具有最小差的轴。然而,正如@PeterTaylor所建议的,有些情况下,删除具有最小差异的轴可能会导致在投影到二维空间时产生直线而非三角形。这很糟糕

因此,我的修订方案如下...

  1. 找到多边形 { abs(v1.x-v0.x), abs(v2.x-v1.x), abs(v0.x-v2.x) } 在每个轴上的子 delta,这将导致每个轴上的 3 个标量值。
  2. 接下来,将这些标量值相乘以计算得分。重复此过程,为每个轴计算得分。(这样任何 0 的 delta 都会强制得分为 0,自动消除该轴,避免三角形退化)
  3. 消除得分最低的轴以形成投影,例如,如果 x 轴的得分最低,则投影到 y-z 平面。

我还没有时间对这种方法进行单元测试,但经过初步测试,它似乎运行得非常好。我很想知道这是否实际上是最好的方法?


你的得分函数看起来非常不错,但是放弃其中一个轴线必然会导致精度的损失。你可以试着近似计算平方根函数,然后使用我的技巧。我建议你实施三种技术:自己的、我的近似平方根和高精度平方根。比较前两种方法与最后一种方法的性能和误差。这是你唯一确定它是否最好的方法。 - Dave O.
我想我会继续使用您提到的3种实现。您关于精度损失的评论很有趣,因为它与@Alnitak早期提供的答案相矛盾...“根本不需要找到“最佳”投影,只需要找到一个足够好的投影,并且在投影到2D时不退化为一条线。” - Thomas Sampson

1
经过讨论,解决在投影到二维空间时如何知道要丢弃哪个轴的问题其实非常简单。3D Math Primer for Graphics and Game Development中给出了答案:

“解决这个困境的方法是选择投影平面,使得投影三角形的面积最大化。这可以通过检查平面法线来完成;具有最大绝对值的坐标是我们将要丢弃的坐标。例如,如果法线是[–1, 0, 0],那么我们将丢弃顶点和p的x值,投影到yz平面上。”

我的原始解决方案涉及使用子增量计算每个轴的分数,但存在缺陷,因为可能会生成所有三个轴的零分数,在这种情况下,要丢弃的轴仍然无法确定。
因此,使用碰撞平面的法线(可以预先计算以提高效率)来确定在投影到二维平面时要丢弃哪个轴是最佳方法。

0

我不确定这个建议是否真的是最好的。将三角形投影到包含它的平面上并不太难。在这里,我假设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符号。


作为替代方案,您可以在四面体情况下对矩阵方程使用线性代数求解器,将四面体的第四个顶点取为v0 + (v1-v0)x(v2-v0),如果需要则进行归一化处理。

你好,你的假设是正确的,我已经测试了点p确实在平面上。然而,我正在使用重心坐标来寻找交点测试的最有效解决方案(这排除了任何需要sqrt或三角函数的方法)。 - Thomas Sampson

0

你不需要确定最佳区域来找到一个合适的投影。

实际上,根本没有必要找到“最佳”投影,只需要找到一个足够好的投影,而且在投影到二维平面时不会退化成一条直线。

编辑 - 算法已删除,因为我没有考虑到退化情况。


不是一个好主意。例如,v0 =(0,0,0),v1 =(1,1,0),v2 =(0,0,0.1)。绝对差最小的轴是z轴。但沿z轴投影会产生一个面积为0的退化三角形:v0' = v2' =(0,0)。 - Henrik
我认为我可能有一种方法,可以消除任何在投影后形成线的投影。我正在查看每个x、y和z坐标之间形成多边形/平面的三个增量。然后,我将这三个增量相乘,以产生每个增量的得分。得分为0表示该投影不适合(因为它会形成一条线),因此被“删除”以形成投影。 - Thomas Sampson

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接