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$
1
  • $\begingroup$ Im curious , why would you need this? , So there might be work arounds aswell $\endgroup$ Jan 17, 2015 at 4:16

2 Answers 2

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$
1
  • $\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$ Jan 18, 2015 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$
3
  • $\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, 2015 at 17:04
  • $\begingroup$ Yes, you are right. $\endgroup$ Jan 18, 2015 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, 2018 at 3:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .