logo标签列表

在3D空间中两个三角形之间映射点

mathgeometrycomputational-geometry
3

编辑

我不知道这是否重要，但目标三角形的角度可能与源三角形不同。这个事实是否使变换非仿射？（我不确定）

alt text

我有两个在三维空间中的三角形。已知第一个三角形中某点的坐标(x,y,z)和向量V1,V2,V3。我需要找到点(x',y',z')。使用向量V1,V2,V3对点(x,y,z)进行什么转换才能得到第二个三角形中的变换点呢？

感谢您的帮助！！！

1
仿射变换允许平移，因此您提出的角度问题并不是一个独立的问题。线性变换可以用于改变三角形的形状、大小和方向，而没有任何真正的问题。当结果线性变换将对象放置在向量空间中的错误位置时，需要使用仿射变换来重新定位它。我已更新我的答案，以便找到解决方案而无需应用任何高级技术。 - andand
6个回答
5
这个问题比起初看来更加复杂，而且你对问题的限制需要一些比你想象的更高级的技巧。
因此，为了解释清楚，我会稍微改变你的符号表示。考虑三对向量（它们对应于你问题中两个三角形的顶点）： 
u = <u0, u1, u2, 1>
u' = <u0', u1', u2', 1>

v = <v0, v1, v2, 1>
v' = <v0', v1', v2', 1>

w = <w0, w1, w2, 1>
w' = <w0', w1', w2', 1>

通常情况下，您的问题可以通过识别形式为以下线性变换来解决:

    |a0,0  a0,1  a0,2  a0,3|
A = |a1,0  a1,1  a1,2  a1,3|
    |a2,0  a2,1  a2,2  a2,3|
    |0     0     0     1   |


这里有一个矩阵 A：



Au = u'
Av = v'
Aw = w'



满足以下条件：
这个公式是必需的，因为该变换似乎是3D仿射变换，而不是3D线性变换。如果它是线性变换，则包含原点的任何三角形必然映射到另一个包含原点的三角形。将其扩展到4D空间允许使用4D线性变换执行3D仿射变换。
也就是说，首先要注意的是，这个问题是欠约束的（12个未知数的9个方程式）；不存在唯一解。实际上存在无限多个解。但是，您的问题比这更受约束，所以还有一些希望。给定一个向量 p = 找到
Ap = p' = 使得（使用定义向量a、b和c）

a · p + d = p'
b · p + e = p'
c · p + f = p'

|u - p|   |u' - p'|
------- = ---------
|u - a|   |u' - Aa|

|v - p|   |v' - p'|
------- = ---------
|v - b|   |v' - Ab|

|w - p|   |w' - p'|
------- = ---------
|w - c|   |w' - Ac|
这是一个涉及到编程的公式，描述了三个向量之间的关系。
虽然这给问题增加了一个约束条件，但它将问题从一个可以使用线性方法轻松解决的问题变成了需要使用凸规划才能找到唯一解的问题。 话虽如此，这里有一些可能的方法： 1.继续使用凸规划来解决问题。 虽然比线性问题更难解决，但实际上并不是很难。 2.回到2D情况，而不是3D情况。 这可以在不诉诸距离测量所施加的非线性约束的情况下完成。 3.选择第四个点，而不是处理三角形，改为处理四面体。 这再次从问题中删除了非线性。 更新：我经过思考，发现一种方法可以生成正确的仿射变换，而无需使用凸规划。 它可以通过为每个三角形生成第四个顶点（称为y和y'）来完成：其中×是两个向量的3-D叉积（即省略每个向量中的最后一个1；但记得一旦计算出y和y'，就将1附加到它们上）。 从那里开始，您可以应用从列向量创建矩阵M和M'的标准技术：并使用Steve Emmerson建议的方法（在4-D而不是3-D中）：
感谢对问题进行深入分析。 - Agnius Vasiliauskas
很棒的答案。在我找到你的帖子之前，我卡在了有9个方程和12个未知数的点上。我在这里有一个问题：为什么y和**y'可以作为第四个点？我的意思是，它不是独立的，同样好的你可以使用三角形的中心点y = mean(x,y,z)**（好吧，好吧，可能你不能，但我不明白为什么叉积更好）。 - Jakub M.
你可以使用任何与三角形的边线性无关的向量。y和y'是其他两条边的叉积，满足这个约束条件，并且实质上创建了一个单纯形。使用平均值会产生一个线性相关的向量，因此M将没有逆矩阵。 - andand
3

请查看andand的评论以了解理论。

// Qt 代码

QMatrix4x4 m;
QMatrix4x4 t1;
QMatrix4x4 t2;

QVector3D v1(0,0,0);
QVector3D v2(0,1,0);
QVector3D v3(1,0,0);
QVector3D v4 = v1 + QVector3D::crossProduct(v2-v1, v3-v1);

QVector3D v1p(0,0,2);
QVector3D v2p(0,3,2);
QVector3D v3p(1,0,1);
QVector3D v4p = v1p + QVector3D::crossProduct(v2p-v1p, v3p-v1p);

t1.setColumn(0, QVector4D(v1, 1));
t1.setColumn(1, QVector4D(v2, 1));
t1.setColumn(2, QVector4D(v3, 1));
t1.setColumn(3, QVector4D(v4, 1));

t2.setColumn(0, QVector4D(v1p, 1));
t2.setColumn(1, QVector4D(v2p, 1));
t2.setColumn(2, QVector4D(v3p, 1));
t2.setColumn(3, QVector4D(v4p, 1));

m = t2 * t1.inverted();

for(float i=0.0; i<2.5; i+=0.05)
{
    QVector4D p(0.2+i,i,0,1);
    QVector4D pp( m * p );

    glBegin(GL_LINE_STRIP);
    glColor4f(1,1,1,1);
    glVertex3d(p.x(), p.y(), p.z());

    glColor4f(1,0,1,1);
    glVertex3d(pp.x(), pp.y(), pp.z());
    glEnd();
}

以下是此代码的演示视频： http://www.youtube.com/watch?v=yOU90pBoyZY

3
我认为您可能正在寻找重心坐标？
+1 确认。找到源三角形上一点的重心坐标，然后在目标三角形上定位这些重心坐标。 - phkahler
1
你需要一个矩阵变换T，使得T X = X'，其中X是第一个三角形顶点坐标的列矩阵，X'是第二个三角形的顶点坐标的列矩阵。将两边都乘以X的逆矩阵，则有T = X' X-1。
这是我一开始的想法，但随着我的深入研究，问题显然是欠约束的。我相信一旦包括距离约束，就可以找到唯一的解决方案，但要找到这个唯一的解决方案需要凸规划，并且不能使用你概述的线性方法来解决。 - andand
@andand 矩阵变换将所有三个顶点变为它们的对应物。它也是一种线性变换；因此，第一个三角形内部的任何点都将以保持与顶点成比例的距离的方式转化为第二个三角形内部的点。 - Steve Emmerson
假设原点是第一个三角形内部的点，但它不是第二个内部点。使用线性变换无法实现这一点；原点总是被映射到原点上。所述问题需要一种仿射（而非线性）变换，以便在定义域中的原点可以被映射到范围中的其他位置。 - andand
@andand 你说得对。我答案中的X和X'应该由每个三角形重心到其顶点的向量构成。将三角形1中的一个点进行变换包括以下步骤：1）减去第一个三角形的重心；2）应用T；3）加上从三角形1重心到三角形2重心的位移向量。 - Steve Emmerson
0

只需将向量添加到每个点即可。 点 + 向量 == 新点。 这基本上是创建向量的相反过程：V1 ==（x1'-x1，y1'-y1，z1'-z1），因此（x1'，y1'，z1'）==（x1 + V1x，y1 + v1y，z1 + V1z）。

1
我认为这并没有回答问题。我认为 OP 的意思是 (x, y, z) 是三角形中的任意一点。 - Colin Fine
是的，我也感觉这不是解决方案，因为点应该受到所有三个向量V1、V2、V3的影响（因为所有顶点都改变了），而不仅仅是一个V1。 - Agnius Vasiliauskas
0

让

 x = αx1 + βx2 + γx3

那么 x' = αx1' + βx2' + γx3' 因此

x' = α(x1+V1) + β(x2+V2) + γ(x3+V3)
这是一个三维线性变换。问题需要进行三维仿射变换。 - andand
我不太明白。你的意思是：x' = α(x1+V1.x) + β(x2+V2.x) + γ(x3+V3.x) 吗？另外，如何计算α、β、γ？ - Agnius Vasiliauskas
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接