# Find a corresponding point on a transformed Mesh

Lets say i have 2 polygons A and B where polygon B has been derived from Polygon A by an unknown(!) transformation matrix:

Now i have a point p that is placed somewhere on the surface of polygon A. How can i find the corresponding point p' on polygon B when i know [a,b,c,d] and [a', b', c', d'] ?

• Im curious , why would you need this? , So there might be work arounds aswell – Knuckles209cp Jan 17 '15 at 4:16

For triangles you can use mathutils.geometry.barycentric_transform:

import mathutils.geometry
pd = mathutils.geometry.barycentric_transform(p, v1, v2, v3, d1, d2, d3)


To test if the point is inside a triangle you can use mathutils.geometry.intersect_point_tri.

• This is a neat solution! And I have one more question. I think the barycentric combination should be same for p and pd under the unknown transform. And I know that the affine transform preserve the invariants of barycentric coordinates. So the unknown transform is limited to affine transform(I am not quite sure of this...), is it a problem in application? – TheBusyTypist Jan 18 '15 at 1:32

I will assume that:

• The transformation matrix represents a projective transformation.

By this assumption the problem can be solved using 2D projective transform.

In general there are following steps in this solution:

1. Use 3 vertices to construct a 2D frame(I name it M) of A.
2. Project all vertices of A, and your input vertex p into M of A; project all vertices of B into M of B. I call these projected vertices as PA[0], PA[1], ..., PA[3], PP, PB[0], ..., PB[3].
3. Compute a 2D projective transform(name it T) between PA and PB.
4. Compute the destination vertex of PP using T. I call the result vertex as PPB.
5. Transform back(un-project) the PPB to get the final result, the corresponding vertex of p in B.

Here are some sample codes. I use numpy here, so you may modify it to use bpy.mathutils.Vector and bpy.mathutils.Matrix.

• Construct 2D frame

def Construct2DFrame(p0, p1, p2):
u = [p1[0] - p0[0], p1[1] - p0[1], p1[2] - p0[2]]
h = [p2[0] - p0[0], p2[1] - p0[1], p2[2] - p0[2]]
n = np.cross(u, h)
v = np.cross(n, u)
m = np.matrix([u, v, n]).T
return m

• Compute a 2D projective transform

def ComputeProjectiveTransform2D(src, dst):
# src and dst are lists of 4 2D coordinates.
u = lambda i : src[i][0]
v = lambda i : src[i][1]
x = lambda i : dst[i][0]
y = lambda i : dst[i][1]

a = [
[u(0), v(0), 1, 0, 0, 0, -u(0) * x(0), -v(0) * x(0)],
[u(1), v(1), 1, 0, 0, 0, -u(1) * x(1), -v(1) * x(1)],
[u(2), v(2), 1, 0, 0, 0, -u(2) * x(2), -v(2) * x(2)],
[u(3), v(3), 1, 0, 0, 0, -u(3) * x(3), -v(3) * x(3)],
[0, 0, 0, u(0), v(0), 1, -u(0) * y(0), -v(0) * y(0)],
[0, 0, 0, u(1), v(1), 1, -u(1) * y(1), -v(1) * y(1)],
[0, 0, 0, u(2), v(2), 1, -u(2) * y(2), -v(2) * y(2)],
[0, 0, 0, u(3), v(3), 1, -u(3) * y(3), -v(3) * y(3)],
]

m = np.matrix(a, dtype=np.double)
rhs = np.array([x(0), x(1), x(2), x(3), y(0), y(1), y(2), y(3)],
dtype=double)
s = np.linalg.solve(m, rhs)

return np.matrix([
s[0:3],
s[3:6],
[s[6], s[7], 1]
])


References:

https://www.cs.cmu.edu/~ph/texfund/texfund.pdf

This provides all the theoretical background of this solution. You can start reading from section 2.2.3.

• If i understand you correct, then your solution assumes the polygons are flat, thus you can construct triangles which define the planes on which you further calculate the result. I guess this would then be equivalent to triangulating the model and only work with tris? – Gaia Clary Jan 17 '15 at 17:04
• Yes, you are right. – TheBusyTypist Jan 18 '15 at 0:56
• Gaia Clary: no, that's not what he's doing. Think of what he's doing as un-projecting one quad, and then re-projecting the quad onto the second one. The difference with triangulating is this projection assumes there's a perspective transformation involved. All four points are being considered simultaneously unlike using triangles where only three points are being considered at a time. – Gato Jun 3 '18 at 3:47