Fo some reason I cannot find any maths for this. It could be a projective transform or a UV mapping type transform but I know that what is required here is a transformation matrix since the mapping must go both ways (inverse as well). For any arbitrary planar quadrangle, how do you map it into a unit square with a transformation matrix? Thanks!

Can't always be done. Not all quads can be transformed by an affine transformation to a unit square. In fact, only parallelograms can...

Of course, here I'm assuming you want to map a 2d quad to a 2d square. Do you actually want to infer perspective or something? Then you have more degrees of freedom...

The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping.

Quote:Original post by Emergent
Can't always be done. Not all quads can be transformed by an affine transformation to a unit square. In fact, only parallelograms can...

Of course, here I'm assuming you want to map a 2d quad to a 2d square. Do you actually want to infer perspective or something? Then you have more degrees of freedom...

You assume correctly. :) A 3D quadrangle polygon has been transformed to the world center and 'placed' on the X-Z plane so that its y-values are 0.0f (essentially a 2D quadrangle). Now I want to matrix transform it to a unit square (on the same plane) for operations on geometry being placed on its surface (the geometry would be inverse transformed to fit the original quadrangle after the operations). I expect the polygon to be planar and convex (from polygonization by the supporting application).

Code from Qt (QTransform::quadToSquare) is the type of transformation I think that I'm seeking but I cannot make it work (for hours!). It is using a 2D transform whereas I am limited to 3D transform matrices with an assumed (0,0,0,1) homogeneous vector. Their projective transform looks to be setting the homogeneous vector to (g, h, 1). I'm in the process of testing a self-made 2D transform using this code but am still a bit wary of the results.

Thanks!

Quote:Original post by Dave Eberly
The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping.

How would this relate to matrix transformation? As I stated, this must go both ways with an inversion of the quad-to-unitsquare after some processing.

Thanks!

Yes, there is a projective transformation (or homography) that will map your quadrilateral to a square. Notice that it will map homogeneous coordinates to homogeneous coordinates, so you may want to divide by the third coordinate at the end.

I can think of two ways to proceed:
1) Write the whole thing as a system of linear equations: 12 equations with 13 variables (you get an extra level of freedom because all scalings of the matrix represent the same homography). [EDIT: If I do it differently I get 8 equations with 9 variables directly: See section 2.1 here.]
2) Find the line that will be mapped to infinity first, and then find an affine transformation that will finish the job. You can see some details here: http://www.robots.ox.ac.uk/~vgg/publications/papers/liebowitz98.pdf

Quote:Original post by Kuroyume0161

Quote:Original post by Dave Eberly
The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping.

How would this relate to matrix transformation? As I stated, this must go both ways with an inversion of the quad-to-unitsquare after some processing.

Thanks!

So write the equations using a homogeneous matrix. You still need to do the perspective divide (the denominators of the expression in the paper are your w-terms). The equations have (u,v) as functions of (x,y). The algebra to invert and solve for (x,y) as functions of (u,v) is straightforward, and this may also be written using a homogeneous matrix.

Quote:Original post by Kuroyume0161
You assume correctly. :) A 3D quadrangle polygon has been transformed to the world center and 'placed' on the X-Z plane so that its y-values are 0.0f (essentially a 2D quadrangle). Now I want to matrix transform it to a unit square (on the same plane)

Perhaps I'm missing something, but I'm not sure that the posts about perspective are really on-topic... What you're talking about is entirely a 2d problem, right?

[EDIT: Indeed I was missing something! I needed to read up on homographies. I won't take this post down because it's not completely useless, but I think the homography method is better.]

Then, as I said, what you're describing is exactly the case that you can't do with a single affine transformation, unless the quad that you start with is a parallelogram. However, it also sounds like you'd be happy with any reasonable homeomorphism from 2d to 2d (more precisely: R^2 to R^2) that maps the edges of your quad to the edges of a unit square and "looks nice" in-between, right?

If that's the case, you could do it with a piecewise affine transformation by splitting your quad into a two triangles. Let's say you have a quad with vertices (u1,v2),...,(u4,v4), split down a diagonal to make two triangles, 'A' and 'B,' as shown below (note that although I've drawn it as a rectangle it needn't be):

(u1,v1)------(u2,v2)  | .       B   |  |      .      |  |  A        . |(u3, v3)-----(u4,v4)

Then to all points in triangle A you can perform the affine transformation

  (x,y)     |-->     Ma-1 ((x,y)-(u3,v3)) + (u3, v3)

where Ma is the matrix [(u4,v4)-(u3,v3) , (u1,v1)-(u3,v3)]. By this I mean that the vector (u4,v4)-(u3,v3) is its first column, etc. And to all points in triangle B you can perform the transformation

  (x,y)     |-->     Mb-1 ((x,y)-(u2,v2)) + (u2, v2)

where Mb is the matrix [(u2,v2)-(u1,v1) , (u2,v2)-(u4,v4)].

(About notation: My "|-->" notation means "maps to." So "|-->" is an infix operator that returns a function. For instance, the expression "x |--> x^2" evaluates to "the function that squares its argument." So it's kind of like 'lambda' in LISP.)

Hope that helps.

[Edited by - Emergent on July 1, 2009 9:12:20 AM]

Apologies... I wasn't familiar enough with homographies, so my whole previous post may be pointless. alvaro: I haven't thought about this much; can a homography map between any two quads in R^2? Are there any restrictions on the types of quads that can be mapped to each other?

[Edited by - Emergent on June 30, 2009 10:26:55 PM]

Already found a solution. Homography transforms was the correct direction - then on to collineation matrices and warps.

Yes, this is a 2D problem. And code exists everywhere - if you only know what the heck you're trying to find! It shows up a lot in scanner/projector/image correction and manipulation sources. This link code works absolutely perfectly (even on triangles!!! - if you treat it as a quad with two identical points - which is what I actually want to do).

http://code.google.com/p/wiimotetuio/source/browse/trunk/WiimoteTUIO/Warper.cs

The projective transform (or affine in limited cases) was only one part of the puzzle. To do this correctly every time, it needs to be a properly inverted matrix from unit-square to quad that then does quad to unit-square (through the inversion). And the matrix multiplication of the points was not a simple transform matrix operation (as this isn't a transform matrix and 'w' is not always (0,0,1)). Once I understood the process and stopped evaluating the crappy incorrect code out there, proper code was found.