**0**

# interpolation between arbitrary quadrilaterals

###
#1
Members - Reputation: **100**

Posted 23 June 2009 - 12:59 PM

###
#2
Members - Reputation: **727**

Posted 23 June 2009 - 05:56 PM

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.

###
#3
Members - Reputation: **100**

Posted 23 June 2009 - 06:13 PM

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

###
#4
Members - Reputation: **727**

Posted 23 June 2009 - 07:42 PM

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:

M

_{x}= (1-s)A

_{x}+ st(A-D+C-B)

_{x}- t(A-D)

_{x}

M

_{y}= (1-s)A

_{y}+ st(A-D+C-B)

_{y}- t(A-D)

_{y}

We can solve for s in each case:

M

_{x}= (s)(t(A-D+C-B)

_{x}- A

_{x}) + A

_{x}- t(A-D)

_{x}

M

_{y}= (s)(t(A-D+C-B)

_{y}- A

_{y}) + A

_{y}- t(A-D)

_{y}

s = (M

_{x}+ t(A-D)

_{x}- A

_{x})/(t(A-D+C-B)

_{x}- A

_{x})

s = (M

_{y}+ t(A-D)

_{y}- A

_{y})/(t(A-D+C-B)

_{y}- A

_{y})

Setting these equal and solving for t:

(M

_{x}+ t(A-D)

_{x}- A

_{x})/(t(A-D+C-B)

_{x}- A

_{x}) = (M

_{y}+ t(A-D)

_{y}- A

_{y})/(t(A-D+C-B)

_{y}- A

_{y})

Also, for my sanity in typing this:

T = M-A

U = A-D

V = A-D+C-B

(T

_{x}+tU

_{x})(tV

_{y}-A

_{y}) = (T

_{y}+tU

_{y})(tV

_{x}-A

_{x})

-A

_{y}T

_{x}+ t(T

_{x}V

_{y}- U

_{x}A

_{y}) + t

^{2}U

_{x}V

_{y}= -A

_{y}T

_{x}+ t(T

_{x}V

_{y}- U

_{x}A

_{y}) + t

^{2}U

_{x}V

_{y}

Lastly:

t

^{2}(U

_{x}V

_{y}- U

_{y}V

_{x}) + t(T

_{x}V

_{y}- U

_{x}A

_{y}- T

_{y}V

_{x}+ U

_{y}A

_{x}) + (A

_{x}T

_{y}- A

_{y}T

_{x}) = 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.)

###
#6
Members - Reputation: **100**

Posted 24 June 2009 - 03:22 AM

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?

###
#7
Members - Reputation: **982**

Posted 24 June 2009 - 03:45 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]

###
#8
Members - Reputation: **100**

Posted 24 June 2009 - 04:13 AM

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

###
#9
Members - Reputation: **1169**

Posted 24 June 2009 - 04:33 AM

###
#10
Members - Reputation: **100**

Posted 24 June 2009 - 08:09 AM

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

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

(T

_{x}+ tU

_{x})*(tV

_{y}+ B

_{y}- A

_{y}) =

(T

_{y}+ tU

_{y})*(tV

_{x}+ B

_{x}- A

_{x})

and:

t

^{2}U⊗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...

###
#11
Members - Reputation: **727**

Posted 02 July 2009 - 03:19 PM

Quote:

Original post by diegovar

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

I ran through this again (after sleeping) and have a successfully tested solution. If you still need it, I'll post it. (Otherwise, it's too much typing!)

###
#12
Members - Reputation: **100**

Posted 04 July 2009 - 01:53 AM

a = (A-D)⊗(C-B)

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

c = (M-A)⊗(B-A)

Here's a pic showing the texture coords at work.

I must've messed up the code previously, because it worked, we presented our work on Thursday and the professor was very pleased :D.

Here's a couple of pictures of our resulting work.

Thanks a lot for all your help!

Diego

###
#14
Members - Reputation: **138**

Posted 27 October 2012 - 07:50 AM

Unfortunately, I think erissian's formula is flawed. There is a small error which kept me busy for a while, but I solved it and thought I could share the solution:

erissian wrote:

M

_{x}= (1-s)A

_{x}+ st(A-D+C-B)

_{x}- t(A-D)

_{x}

M

_{y}= (1-s)A

_{y}+ st(A-D+C-B)

_{y}- t(A-D)

_{y}

But it should be:

M

_{x}= sB

_{x}+(1-s)A

_{x}+ st(A-D+C-B)

_{x}- t(A-D)

_{x}

M

_{y}= sB

_{y}+(1-s)A

_{y}+ st(A-D+C-B)

_{y}- t(A-D)

_{y}

This simplifies to these coefficients of the quadratic equation at

^{2}+ bt + ct = 0

a = C⊗D+D⊗B+A⊗C+B⊗A

b = M⊗C+D⊗M+B⊗M+M⊗A+C⊗A+B⊗D+2(A⊗B)

c = M⊗B+A⊗M+B⊗A

I don't know if these are the same values diegovar calculated in the end, but they work