Jump to content
  • Advertisement
Sign in to follow this  

interpolation between arbitrary quadrilaterals

This topic is 2088 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites
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


Share this post

Link to post
Share on other sites
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

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.)

Share this post

Link to post
Share on other sites
Okay, I couldn't help it:

t = [-b ± √(b2-4ac)]/2a

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>

Share this post

Link to post
Share on other sites
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?

Share this post

Link to post
Share on other sites
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.


[Edited by - Emergent on June 24, 2009 10:45:23 AM]

Share this post

Link to post
Share on other sites
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:


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

Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites
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.


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) ] / [ B - A + t(A-D+C-B) ]

This gives the following when substituting for T, U and V:

(Tx + tUx)*(tVy + By - Ay) =
(Ty + tUy)*(tVx + Bx - Ax)


t2U⊗V + t(T⊗V + U⊗(B-A)) + T⊗(B-A) = 0

so the coefficients of the quadratic formula are:

a = (A-D)⊗(C-B)
b = (M-A)⊗(A-D+C-B) + (A-D)⊗(B-A)
c = (M-A)⊗(B-A)

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...

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!