Transform arbitrary quadrangle to square

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 29/06/2009 at 18:27, xxxxxxxx wrote:

User Information:
Cinema 4D Version:   R10-R11
Platform:   Windows ;   Mac OSX ;
Language(s) :     C++ ;

---------
I'm having a brainfart and difficulty finding the correct affine transformation to map an arbitrary (but planar) quadrangle into a square space. Something similar is done in UV mapping but, again, having difficulty finding information on this. I'll keep looking but does anybody know how to do this?

Thanks!

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 29/06/2009 at 23:45, xxxxxxxx wrote:

I wrote once a little COFFEE plugin based on an algorithm posted by Per Anders that does exactly the same thing. It turns selected polygons into squares.

> \> MyMenuPlugin::Execute(doc) \> { \> // Called when the menu item is chosen \> var op = GetActiveObject(doc); \> if(!op) return; \> if (!instanceof(op,PolygonObject)) return; \> var sel=op->GetPolygonSelection(); \> if (!sel) return; // no polygon selection, exit now \> \> doc->StartUndo(); \> doc->AddUndo(UNDO_OBJECT,op); \> \> \> var cnt=op->GetPolygonCount(); \> var pnt=op->GetPoints(); \> \> //loop through all the polygons to find the selected ones \> var i=0; \> for (i=0;i<cnt;i++) \> { \> //check if the current polygon is selected \> if (sel->IsSelected(i)) \> { \> //get the polygon points \> var pol=op->GetPolygon(i); \> var p1=pnt[pol->a]; \> var p2=pnt[pol->b]; \> var p3=pnt[pol->c]; \> var p4=pnt[pol->d]; \> \> //calculate the polygon normal, midpoint and size \> var dir=vnorm(vcross(p3-p1,p4-p2)); \> var p5=(p1+p2+p3+p4)/4.0; \> var len=(vlen(p1-p3)+vlen(p2-p4))/4.0; \> \> //set the point positions correctly \> var v1=vnorm(vcross(dir,vnorm(p5-p2))); \> var v2=vnorm(vcross(dir,v1)); \> p1=(len\*v1)+p5; \> p2=(len\*v2)+p5; \> p3=(-len\*v1)+p5; \> p4=(-len\*v2)+p5; \> \> pnt[pol->a]=p1; \> pnt[pol->b]=p2; \> pnt[pol->c]=p3; \> pnt[pol->d]=p4; \> \> op->SetPoints(pnt); \> op->Message(MSG_UPDATE); \> } \> } \> // TODO: Do whatever you want \> doc->EndUndo(); \> op->Message(MSG_UPDATE); \> GeEventAdd(DOCUMENT_CHANGED); \> } \>

cheers,
Matthias

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 30/06/2009 at 14:47, xxxxxxxx wrote:

Unfortunately, it must be a transformation matrix since geometry will be inverse transformed (from the square back to the quadrangle). I've found some quad-to-square algorithms but they aren't working for some reason and there is definitely some modification of the matrix homogeneous vector (something that cannot be done with Cinema 4D's matrix as it is always assumed to be (0,0,0,1)!). Typically, a projective transform is applied (when an affine tranformation cannot).

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 30/06/2009 at 20:50, xxxxxxxx wrote:

Found it finally! :D

Here's the full 'test' plugin code just for the curious. This is a 2D transformation only!

////////////////////////////////////////////////////////////////
// TestingPlugin.cpp
////////////////////////////////////////////////////////////////
// CommandPlugin class
////////////////////////////////////////////////////////////////
// V0.1 2008.05.28 Robert Templeton
////////////////////////////////////////////////////////////////

#include "TestingPlugin.h"

class Matrix2D
{
     public:
          Real     m0;
          Real     m1;
          Real     m3;
          Real     m4;
          Real     m5;
          Real     m7;
          Real     m12;
          Real     m13;
          Real     m15;
          Matrix2D()
          {
               // Unit Matrix
               m0 =     1.0;
               m1 =     0.0;
               m3 =     0.0;
               m4 =     0.0;
               m5 =     1.0;
               m7 =     0.0;
               m12 =     0.0;
               m13 =     0.0;
               m15 =     1.0;
          }
          // transform point p by matrix M: q = p*M
          friend const Vector operator * (const Vector& p, const Matrix2D& M)
          {
               Real     d = p.x*M.m3 + p.z*M.m7 + M.m15;
               if (d)          d = 1.0f/d;
               else          return Vector(0.0f);
               Vector     q;
               q.x =          ((p.x*M.m0 + p.z*M.m4 + M.m12) * d)-0.5f;
               q.z =          ((p.x*M.m1 + p.z*M.m5 + M.m13) * d)-0.5f;
               q.y =          0.0f;
               return q;
          }
};

// Calculate matrix for unit-square to quad mapping
//                     - vertices        - square->quad transform
//*---------------------------------------------------------------------------*
Bool SquareToQuad(Real quad[4][2], Matrix2D* SQ)
//*---------------------------------------------------------------------------*
{
     Real     x0 =     quad[0][0];
     Real     x1 =     quad[1][0];
     Real     x2 =     quad[2][0];
     Real     x3 =     quad[3][0];

Real     y0 =     quad[0][1];
     Real     y1 =     quad[1][1];
     Real     y2 =     quad[2][1];
     Real     y3 =     quad[3][1];

Real dx3 = x0 - x1 + x2 - x3;
Real dy3 = y0 - y1 + y2 - y3;

// afine transform
     if (!dx3 && !dy3)
     {
          SQ->m0 = x1-x0; SQ->m1 = y1-y0; SQ->m3 = 0.0f;
          SQ->m4 = x2-x1; SQ->m5 = y2-y1; SQ->m7 = 0.0f;
          SQ->m12 = x0;   SQ->m13 = y0;   SQ->m15 = 1.0f;
     }
     // projective transform
     else
     {
          Real dx1 = x1 - x2;
          Real dx2 = x3 - x2;
          Real dy1 = y1 - y2;
          Real dy2 = y3 - y2;

// determinants
          Real gtop    = dx3 * dy2 - dx2 * dy3;
          Real htop    = dx1 * dy3 - dx3 * dy1;
          Real bottom = dx1 * dy2 - dx2 * dy1;

if (!bottom) return FALSE;
bottom = 1.0 / bottom;

Real g = gtop*bottom;
Real h = htop*bottom;

Real a = x1 - x0 + g * x1;
          Real b = x3 - x0 + h * x3;
          Real d = y1 - y0 + g * y1;
          Real e = y3 - y0 + h * y3;

SQ->m0 = a;   SQ->m1 = d;   SQ->m3 = g;
          SQ->m4 = b;   SQ->m5 = e;   SQ->m7 = h;
          SQ->m12 = x0; SQ->m13 = y0; SQ->m15 = 1.0f;
     }
     // Invert
     //*SQ =     !(*SQ);
     return TRUE;
}
// Calculate matrix for quad to unit-square mapping
//                     - vertices        - square->quad transform
//*---------------------------------------------------------------------------*
void QuadToSquare(Real quad[4][2], Matrix2D* SQ)
//*---------------------------------------------------------------------------*
{
     if (!SquareToQuad(quad, SQ))     return;

// invert through adjoint
     Real a = SQ->m0, d = SQ->m1, g = SQ->m3;
     Real b = SQ->m4, e = SQ->m5, h = SQ->m7;
     Real c = SQ->m12, f = SQ->m13;

Real A = e - f * h;
     Real B = c * h - b;
     Real C = b * f - c * e;
     Real D = f * g - d;
     Real E = a - c * g;
     Real F = c * d - a * f;
     Real G = d * h - e * g;
     Real H = b * g - a * h;
     Real I = a * e - b * d;

// Probably unnecessary since 'I' is also scaled by the determinant,
     //   and 'I' scales the homogeneous coordinate, which, in turn,
     //   scales the X,Y coordinates.
     // Determinant =   a * (e - f * h) + b * (f * g - d) + c * (d * h - e * g);
     Real idet = 1.0f / (a * A           + b * D           + c * G);

SQ->m0 = A*idet; SQ->m1 = D*idet; SQ->m3 = G*idet;
SQ->m4 = B*idet; SQ->m5 = E*idet; SQ->m7 = H*idet;
SQ->m12 = C*idet; SQ->m13 = F*idet; SQ->m15 = I*idet;
}

// METHODS: TestingPlugin
// Execute
//*---------------------------------------------------------------------------*
Bool TestingPlugin::Execute(BaseDocument* doc)
//*---------------------------------------------------------------------------*
{
     PolygonObject*     op =     PolygonObject::Alloc(4L, 1L);
     if (!op)                    return FALSE;
     doc->InsertObject(op, NULL, NULL, FALSE);
     CPolygon*          pa =     op->GetPolygonW();
     Vector*               va =     op->GetPointW();
     if (!(pa && va))          return FALSE;
     pa->a =                         0L;
     pa->b =                         2L;
     pa->c =                         3L;
     pa->d =                         1L;
     /*
     va[0] =                         Vector(-25.0f, -96.593f, 6.699f);
     va[1] =                         Vector(-25.882f, -96.593f, 0.0f);
     va[2] =                         Vector(-48.296f, -86.603f, 12.941f);
     va[3] =                         Vector(-50.0f, -86.603f, 0.0f);
     */
     va[0] =                         Vector(35.355f, -70.711f, -61.237f);
     va[1] =                         Vector(50.0f, -70.711f, -50.0f);
     va[2] =                         Vector(43.301f, -50.0f, -75.0f);
     va[3] =                         Vector(61.237f, -50.0f, -61.237f);
     op->Message(MSG_UPDATE);

// Test
     // tv MUST BE IN POLYGON ORDER!
     Vector     tv0 =               va[pa->a];
     Vector     tv1 =               va[pa->b];
     Vector     tv2 =               va[pa->c];
     Vector     tv3 =               va[pa->d];
     // Center of polygon
     Vector     center =          (tv0+tv1+tv2+tv3) * 0.25f;
     // Move polygon to world 0,0,0
     tv0 -=                         center;
     tv1 -=                         center;
     tv2 -=                         center;
     tv3 -=                         center;
     // Rotate polygon so that normal made coincident with +Y axis and 0->1 vertices are horizontal on X-Z plane
     Vector     u =                    !(tv1-tv0);
     Vector     n =                    !((tv1-tv3)%(tv2-tv0));
     Vector     v =                    !(u%n);
     Matrix     m;
     m.v1 =                         Vector(u.x, n.x, v.x);
     m.v2 =                         Vector(u.y, n.y, v.y);
     m.v3 =                         Vector(u.z, n.z, v.z);
     va[pa->a] =                    tv0 * m;
     va[pa->b] =                    tv1 * m;
     va[pa->c] =                    tv2 * m;
     va[pa->d] =                    tv3 * m;

// Transform quad to unit square
     // - Reverse order since C4D uses clockwise and everyone else uses counter-clockwise
     tv0 =                         va[pa->a];
     tv1 =                         va[pa->d];
     tv2 =                         va[pa->c];
     tv3 =                         va[pa->b];
     Real     qi[4][2];
     qi[0][0] =     tv0.x; qi[0][1] =     tv0.z;
     qi[1][0] =     tv1.x; qi[1][1] =     tv1.z;
     qi[2][0] =     tv2.x; qi[2][1] =     tv2.z;
     qi[3][0] =     tv3.x; qi[3][1] =     tv3.z;
     Matrix2D     T;
     QuadToSquare(qi, &T;);
     // Yes!
     va[pa->a] =               tv0 * T;
     va[pa->d] =               tv1 * T;
     va[pa->c] =               tv2 * T;
     va[pa->b] =               tv3 * T;

op->Message(MSG_UPDATE);
EventAdd();
return TRUE;
}

//*---------------------------------------------------------------------------*
LONG TestingPlugin::GetState(BaseDocument* doc)
//*---------------------------------------------------------------------------*
{
return CMD_ENABLED;
}

// Global Registrant Method for TestPlugin plugin
//*---------------------------------------------------------------------------*
Bool RegisterTestPluginCommand()
//*---------------------------------------------------------------------------*
{
return RegisterCommandPlugin(ID_TESTPLUGIN, "TestPlugin", 0, NULL, "TestPlugin", gNew TestingPlugin);
}