3
$\begingroup$

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

enter image description here

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'] ?

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

For triangles you can use mathutils.geometry.barycentric_transform:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – TheBusyTypist Jan 18 '15 at 1:32
3
$\begingroup$

I will assume that:

  • Your polygons are planar.
  • 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Gaia Clary Jan 17 '15 at 17:04
  • $\begingroup$ Yes, you are right. $\endgroup$ – TheBusyTypist Jan 18 '15 at 0:56
  • $\begingroup$ 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. $\endgroup$ – Gato Jun 3 '18 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.