interpolation between arbitrary quadrilaterals
Author
Hi, I´m new here and I just joined to see if someone could help me with a problem I´m facing. I´m writing a ray tracer for a University project, and I´ve arrived to the point of attempting texture mapping. To try things I simply mapped the entire texture to each of the 4 corners of a quad, and it works, but I´m now trying to implement the concept of texture coordinates for each vertex and making this work for non-rectangle quads.
The problem I´m facing is mapping a point inside a Quad to its corresponding texel given the 4 points that define the Quad and their corresponding texture coordinates (which need not form a rectangle). A professor told me to look up the concept of linear interpolation, more specifically bilinear interpolation, but this assumes that the quad is a rectangle, which is not necessarily the case. I tried extending the formulas found in the wikipedia article on this subject to the more general scenario, but I got a non-linear system of equations which I´m not going to attempt to solve in real-time for each texel :)
Could someone help me a bit to solve this?
Thanks in advance
Diego
Bilinear interpolation works just as well for non-rectangular quadrilaterals. Consider that you have the coordinates (s,t) each with values in the range 0..1, in the manner that I'm sure you've already read about.
The coordinate s will represent the texel's position between A and B, as well as between D and C. Considered the two points along these lines; we will call theme P and Q. The coordinate t is the relative position between P and Q.
As you can see, this works well for both cases. The only real problem is that the texture will be deformed to fit the quad.
The coordinate s will represent the texel's position between A and B, as well as between D and C. Considered the two points along these lines; we will call theme P and Q. The coordinate t is the relative position between P and Q.
As you can see, this works well for both cases. The only real problem is that the texture will be deformed to fit the quad.
Author
thanks for the reply, but what I can't seem to get is how to find the (s,t) coordinates given the point's absolute position. I know the 3D positions of the 4 vertices of the non-rectangular original quad and I also know the 3D position of the point inside this Quad, I can easily project this into a 2D representation, but I can't see how to get the (s,t) coordinates you show in the second drawing from this.
I tried expressing the positions of the points to find s and t like this:
P = A + (B-A)s
Q = D + (C-D)s
thus the resulting point, which I know (M) is:
M = P + (Q-P)t
this gives me a non-linear system of equations on s and t :(
Thanks in advance
Diego
I tried expressing the positions of the points to find s and t like this:
P = A + (B-A)s
Q = D + (C-D)s
thus the resulting point, which I know (M) is:
M = P + (Q-P)t
this gives me a non-linear system of equations on s and t :(
Thanks in advance
Diego
Well, the math gets a little rough, but the answer is elegant.
P = A+(B-A)s = A(1-s) + Bs
Q = D+(C-D)s = D(1-s) + Cs
M = P+(Q-P)t = P(1-t) + Qt
= A(1-s)(1-t) + B(1-t)s + D(1-s)t + Cst
= A(1+st-s-t) + B(s-st) + Cst + D(t-st)
= A + Ast - As - At + Bs - Bst + Cst + Dt - Dst
= (1-s)A + st(A-D+C-B) - t(A-D)
This might seem like a problem, having two unknowns and one equation, but that's not really the case. What we really have is:
Mx = (1-s)Ax + st(A-D+C-B)x - t(A-D)x
My = (1-s)Ay + st(A-D+C-B)y - t(A-D)y
We can solve for s in each case:
Mx = (s)(t(A-D+C-B)x - Ax) + Ax - t(A-D)x
My = (s)(t(A-D+C-B)y - Ay) + Ay - t(A-D)y
s = (Mx + t(A-D)x - Ax)/(t(A-D+C-B)x - Ax)
s = (My + t(A-D)y - Ay)/(t(A-D+C-B)y - Ay)
Setting these equal and solving for t:
(Mx + t(A-D)x - Ax)/(t(A-D+C-B)x - Ax) = (My + t(A-D)y - Ay)/(t(A-D+C-B)y - Ay)
Also, for my sanity in typing this:
T = M-A
U = A-D
V = A-D+C-B
(Tx+tUx)(tVy-Ay) = (Ty+tUy)(tVx-Ax)
-AyTx + t(TxVy - UxAy) + t2UxVy = -AyTx + t(TxVy - UxAy) + t2UxVy
Lastly:
t2(UxVy - UyVx) + t(TxVy - UxAy - TyVx + UyAx) + (AxTy - AyTx) = 0
Which can be stuffed into the quadratic equation. From here it should be trivial to find a solution, if one exists, where t is between 0 and 1. Then by plugging it back into the above equation, you can find an s, if one exists, that meets the same conditions.
(The solution can probably be simplified, and in fact I see many cross product candidates. Maybe I'll come back later.)
P = A+(B-A)s = A(1-s) + Bs
Q = D+(C-D)s = D(1-s) + Cs
M = P+(Q-P)t = P(1-t) + Qt
= A(1-s)(1-t) + B(1-t)s + D(1-s)t + Cst
= A(1+st-s-t) + B(s-st) + Cst + D(t-st)
= A + Ast - As - At + Bs - Bst + Cst + Dt - Dst
= (1-s)A + st(A-D+C-B) - t(A-D)
This might seem like a problem, having two unknowns and one equation, but that's not really the case. What we really have is:
Mx = (1-s)Ax + st(A-D+C-B)x - t(A-D)x
My = (1-s)Ay + st(A-D+C-B)y - t(A-D)y
We can solve for s in each case:
Mx = (s)(t(A-D+C-B)x - Ax) + Ax - t(A-D)x
My = (s)(t(A-D+C-B)y - Ay) + Ay - t(A-D)y
s = (Mx + t(A-D)x - Ax)/(t(A-D+C-B)x - Ax)
s = (My + t(A-D)y - Ay)/(t(A-D+C-B)y - Ay)
Setting these equal and solving for t:
(Mx + t(A-D)x - Ax)/(t(A-D+C-B)x - Ax) = (My + t(A-D)y - Ay)/(t(A-D+C-B)y - Ay)
Also, for my sanity in typing this:
T = M-A
U = A-D
V = A-D+C-B
(Tx+tUx)(tVy-Ay) = (Ty+tUy)(tVx-Ax)
-AyTx + t(TxVy - UxAy) + t2UxVy = -AyTx + t(TxVy - UxAy) + t2UxVy
Lastly:
t2(UxVy - UyVx) + t(TxVy - UxAy - TyVx + UyAx) + (AxTy - AyTx) = 0
Which can be stuffed into the quadratic equation. From here it should be trivial to find a solution, if one exists, where t is between 0 and 1. Then by plugging it back into the above equation, you can find an s, if one exists, that meets the same conditions.
(The solution can probably be simplified, and in fact I see many cross product candidates. Maybe I'll come back later.)
Okay, I couldn't help it:
t = [-b ± √(b2-4ac)]/2a
where:
a = (A-D)⊗(C-B)
b = M⊗(A-D+C-B) - A⊗(C-B)
c = A⊗M
I am too tired to make any assumptions as to whether or not this will work with any vector not of the form <x,y,0>
t = [-b ± √(b2-4ac)]/2a
where:
a = (A-D)⊗(C-B)
b = M⊗(A-D+C-B) - A⊗(C-B)
c = A⊗M
I am too tired to make any assumptions as to whether or not this will work with any vector not of the form <x,y,0>
Author
Thank you so much for all your help!, the solution is really elegant :)
As to whether this would work outside the z=0 plane, as originally I have 4 (x,y,z) points, I would actually have 3 formulas instead of 2, but one of them would be unnecessary because all the points lie on a plane. However, due to floating point error, this might not be the case when you plug everything in, so I guess the best way to deal with this would be to project everything into a 2D coordinate system.
It's really great how in the resulting formula for t, most of the values can be precalculated during the creation of the Quad. Does anyone know if this is how OpenGL does texture mapping?
As to whether this would work outside the z=0 plane, as originally I have 4 (x,y,z) points, I would actually have 3 formulas instead of 2, but one of them would be unnecessary because all the points lie on a plane. However, due to floating point error, this might not be the case when you plug everything in, so I guess the best way to deal with this would be to project everything into a 2D coordinate system.
It's really great how in the resulting formula for t, most of the values can be precalculated during the creation of the Quad. Does anyone know if this is how OpenGL does texture mapping?
The "standard" answer (which OpenGL uses, AFAIK) is to simply not use quads; use triangles. Then you have a nice, simple, and unique mapping: barycentric interpolation. Using triangles is also no limitation, since obviously you can split quads into triangles.
Here's how it works:
Say you have a triangle with vertices (p1, p2, p3) and a point p. Also, let's say the triangle has edge vectors e2=p2-p1 and e3=p3-p1, and normal n=(p2-p1)x(p3-p1), where 'x' is the cross product. Then, form the 3x3 matrix
M = [e2, e3, n]
whose columns are the vectors introduced above, and compute
q = M^(-1) (p - p1) .
The vector q=(q1,q2,q3) that you get gives the coordinates of p in the "local frame" of the triangle. If p lies on the plane of the triangle, then q3=0. The barycentric coordinates of the projection of p onto the plane of the triangle are given by b=(b1,b2,b3)=(1-q1-q2, q1, q2). (Clearly if p is on the plane then these are simply the barycentric coordinates of p).
Now, suppose that vertex p1 of the triangle has been assigned the texture coordinates (u1, v1); p2 has been assigned (u2, v2), and so on. The u,v coordinates of p in the texture are simply
(u,v) = b1 (u1, v1) + b2 (u2, v2) + b3 (u3, v3) .
Since you can compute M^(-1) ahead of time, you see that this method requires just some multiplications, additions, and subtraction -- no square roots, etc.
Cheers.
[Edited by - Emergent on June 24, 2009 10:45:23 AM]
Here's how it works:
Say you have a triangle with vertices (p1, p2, p3) and a point p. Also, let's say the triangle has edge vectors e2=p2-p1 and e3=p3-p1, and normal n=(p2-p1)x(p3-p1), where 'x' is the cross product. Then, form the 3x3 matrix
M = [e2, e3, n]
whose columns are the vectors introduced above, and compute
q = M^(-1) (p - p1) .
The vector q=(q1,q2,q3) that you get gives the coordinates of p in the "local frame" of the triangle. If p lies on the plane of the triangle, then q3=0. The barycentric coordinates of the projection of p onto the plane of the triangle are given by b=(b1,b2,b3)=(1-q1-q2, q1, q2). (Clearly if p is on the plane then these are simply the barycentric coordinates of p).
Now, suppose that vertex p1 of the triangle has been assigned the texture coordinates (u1, v1); p2 has been assigned (u2, v2), and so on. The u,v coordinates of p in the texture are simply
(u,v) = b1 (u1, v1) + b2 (u2, v2) + b3 (u3, v3) .
Since you can compute M^(-1) ahead of time, you see that this method requires just some multiplications, additions, and subtraction -- no square roots, etc.
Cheers.
[Edited by - Emergent on June 24, 2009 10:45:23 AM]
Author
I see a problem with that approach however, imagine (I can't figure out how to include an image :S) you have a quad shaped like this:
P0=(0,0)
P1=(1,0)
P2=(1,1)
P3(0,10)
Also, assume you're assigning the texture coordinates (0,0), (1,0), (1,1) and (0,1) to these 4 points resp.
If you divide it into 2 triangles (say (P0 P1 P2) and (P0 P2 P3)) and chose to interpolate depending on which triangle the point is in, you would have a very big difference in the stretching of the texture the minute you step beyond the P0 P2 line from one triangle to another. Maybe you can treat this as collateral damage given that the 2-triangle approach is more efficient, but I think this is an unwanted effect
P0=(0,0)
P1=(1,0)
P2=(1,1)
P3(0,10)
Also, assume you're assigning the texture coordinates (0,0), (1,0), (1,1) and (0,1) to these 4 points resp.
If you divide it into 2 triangles (say (P0 P1 P2) and (P0 P2 P3)) and chose to interpolate depending on which triangle the point is in, you would have a very big difference in the stretching of the texture the minute you step beyond the P0 P2 line from one triangle to another. Maybe you can treat this as collateral damage given that the 2-triangle approach is more efficient, but I think this is an unwanted effect
You do not want to use a bilinear interpolation method. Use a perspective transformation instead so that you preserve lines and quadratics. See my Miscellaneous page, files Wm4QuadToQuadTransforms.{h,cpp}. The comments in the header show how to do the bilinear interpolation and what problems arise. The second PDF link on that page shows how to perform the perspective transformation.
Author
Dave Eberly:
That looks promising, but I'll have to devote time to get to understand it, a time I don't have given that the deadline for my work is next week. I plan to continue working on the raytracer though, so I may look into Perspective Transformations in the future.
erissian:
I was checking the formulas you derived and I found you ommited the term Bs when stepping from this line:
= A + Ast - As - At + Bs - Bst + Cst + Dt - Dst
to this one
= (1-s)A + st(A-D+C-B) - t(A-D)
I added it and arrived to the following:
s = [ M - A + t(A-D) ] / <br><br><br>This gives the following when substituting for T, U and V:<br><br><br>(T<sub>x</sub> + tU<sub>x</sub>)*(tV<sub>y</sub> + B<sub>y</sub> - A<sub>y</sub>) =<br>(T<sub>y</sub> + tU<sub>y</sub>)*(tV<sub>x</sub> + B<sub>x</sub> - A<sub>x</sub>)<br><br>and:<br><br>t<sup>2</sup>U⊗V + t(T⊗V + U⊗(B-A)) + T⊗(B-A) = 0<br><br>so the coefficients of the quadratic formula are:<br><br>a = (A-D)⊗(C-B)<br>b = (M-A)⊗(A-D+C-B) + (A-D)⊗(B-A)<br>c = (M-A)⊗(B-A)<br><br>However, there must be something wrong with my calculations, because the texture is not displaying properly. Substituting A by M yields a correct t (0), and the same happens for B (0), but substituting for C doesn't…
That looks promising, but I'll have to devote time to get to understand it, a time I don't have given that the deadline for my work is next week. I plan to continue working on the raytracer though, so I may look into Perspective Transformations in the future.
erissian:
I was checking the formulas you derived and I found you ommited the term Bs when stepping from this line:
= A + Ast - As - At + Bs - Bst + Cst + Dt - Dst
to this one
= (1-s)A + st(A-D+C-B) - t(A-D)
I added it and arrived to the following:
s = [ M - A + t(A-D) ] / <br><br><br>This gives the following when substituting for T, U and V:<br><br><br>(T<sub>x</sub> + tU<sub>x</sub>)*(tV<sub>y</sub> + B<sub>y</sub> - A<sub>y</sub>) =<br>(T<sub>y</sub> + tU<sub>y</sub>)*(tV<sub>x</sub> + B<sub>x</sub> - A<sub>x</sub>)<br><br>and:<br><br>t<sup>2</sup>U⊗V + t(T⊗V + U⊗(B-A)) + T⊗(B-A) = 0<br><br>so the coefficients of the quadratic formula are:<br><br>a = (A-D)⊗(C-B)<br>b = (M-A)⊗(A-D+C-B) + (A-D)⊗(B-A)<br>c = (M-A)⊗(B-A)<br><br>However, there must be something wrong with my calculations, because the texture is not displaying properly. Substituting A by M yields a correct t (0), and the same happens for B (0), but substituting for C doesn't…
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
