Quote:Original post by Emergent 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?
Hmmm... It's been too long since I was comfortable with this subject. You can convert any projective reference into any other projective reference. Projective references in the plane are sets of 4 points such that any 3 are not collinear. It might be the case that the homography will send a line that intersects the quadrilateral to infinity, which might not satisfy your idea of "mapping between two quads". My intuition tells me this would happen when you try to map a convex quad to a non-convex quad, but I am not completely sure.
I wouldn't even try a non-convex quad with the transform being built. Actually, even a triangle with an extra point along one of the sides (to fake a quad) fails the math (which I'll show in code shortly). Therefore the quad must be 'truly' convex (have internal angles less than 180d). A test triangle was working but no longer after some observational corrections so I'm stuck at trying to do the homography from unit square to triangle which might not be possible (ack!).
There will be two directions for the code: aspect-conserving and not. The latter is where the unit-square to quad applies the transformation to associated geometry - which will skew and shear it. The former will simply make sure that the geometry fits within the bounds of the quad without any homography transformation. This will be the case for circular geometries by default to avoid egg-shaped results that would occur in certain transformations.
Triangles have befuddled me here though. One solution, albeit rather contrived, is to simply truncate the triangle (which yields a quad) but this leaves the remaining area empty of geometry.
And the code:
<code>// 2D Matrix for doing collineation between quad and unit-square 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.0f; m1 = 0.0f; m3 = 0.0f; m4 = 0.0f; m5 = 1.0f; m7 = 0.0f; m12 = 0.0f; m13 = 0.0f; m15 = 1.0f; } // Copy this matrix to matrix M void CopyTo(Matrix2D& M) { M.m0 = m0; M.m1 = m1; M.m3 = m3; M.m4 = m4; M.m5 = m5; M.m7 = m7; M.m12 = m12; M.m13 = m13; M.m15 = m15; } // 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; q.z = (p.x*M.m1 + p.z*M.m5 + M.m13) * d; q.y = p.y; return q; } };
// Calculate matrix for unit-square to quad mapping // - vertices - square->quad transform //*---------------------------------------------------------------------------* Bool GMPThread::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;
// 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);
The 2D matrix is about as simple as you can get and, yes, I've been lazy and just retained the pseudo-indices of the matrix elements from those that were removed because they have no impact.
Quote:Original post by alvaro Hmmm... It's been too long since I was comfortable with this subject. You can convert any projective reference into any other projective reference. Projective references in the plane are sets of 4 points such that any 3 are not collinear. It might be the case that the homography will send a line that intersects the quadrilateral to infinity, which might not satisfy your idea of "mapping between two quads". My intuition tells me this would happen when you try to map a convex quad to a non-convex quad, but I am not completely sure.
That's why I'd asked... Now that I think about it, I'm relatively sure that you can't map between convex and non-convex quads (since the perspective transform preserves convexity).
Sounds like maybe the piecewise-affine method is useful after all (since it sounds like perspective is not inherent to the problem and we're just looking for a "nice" homeomorphism). The homography method has some really good features when convex quads are involved (it preserves lines); maybe this should be our "default" option but when non-convex quads are involved one could fall back on the piecewise-affine method. This violates my natural tendency to avoid special cases (it also would give you a homeomorphism that varies discontinuously as the vertices are moved, I think), but I think it'd satisfy most of OP's needs.
If I think of something smoother than piecewise affine homeomorphisms for the general case, I'll post back. Basically, it seems like any homeomorphism that maps the edges correctly and the inside of the quad "nicely" would be a suitable answer.
