Quadrilateral Interpolation

BlitzMax Forums/BlitzMax Programming/Quadrilateral Interpolation

JoshK (Posted 2009) [#1]

Given four points, each with a 2D texcoord, how do you find the texcoord of any point within? The quad cannot be split into two triangles and solved separately. http://www.gamedev.net/community/forums/topic.asp?topic_id=538963

GfK (Posted 2009) [#2]

Don't know the answer but I'm positive there was some Blitz3D sample code (written by Birdie?) that did exactly this. If his code was based on a mathematical algorithm then it wouldn't be hard to adapt to Blitzmax.

slenkar (Posted 2009) [#3]

is there any way you can use the texture matrix to solve this?

JoshK (Posted 2009) [#4]

That quad does look an awful lot like a frustum matrix, but I am not sure how to turn it into one.

_Skully (Posted 2009) [#5]

I wonder if the poly rendering sites would be helpful here. It's a point in a poly translated into a normal

JoshK (Posted 2009) [#6]

I solved it this way: Find the point where the top and bottom lines meet. Find the angle of each point from the intersection point. Now find the angle of the point we want to find, from the intersection point. It will be between the other two angles, and its percentage of each tells you how to interpolate between those two values. Do the same for the left and right side, for the other coordinate. You have to check for the case where the edges are parallel, but that is easy.

Midimaster (Posted 2009) [#7]

sorry, empty post

beanage (Posted 2009) [#8]

Thanks.

xMicky (Posted 2009) [#9]

I would prefer a simple geometric solution: Strict Graphics 800,600 Type vertex Field x#, y# Field u#, v# Field r, g, b 'just to mark the vertex individually End Type Local curVertic:vertex[5] For Local z:Int =0 To 4 curVertic[z] =New vertex Next curVertic[0].x# =300 curVertic[0].y# =100 curVertic[0].u# =0 curVertic[0].v# =0 curVertic[0].r =255 curVertic[0].g =255 curVertic[0].b =255 curVertic[1].x# =500 curVertic[1].y# =100 curVertic[1].u# =1 curVertic[1].v# =0 curVertic[1].r =255 curVertic[1].g =0 curVertic[1].b =0 curVertic[2].x# =500 curVertic[2].y# =300 curVertic[2].u# =1 curVertic[2].v# =1 curVertic[2].r =0 curVertic[2].g =255 curVertic[2].b =0 curVertic[3].x# =300 curVertic[3].y# =300 curVertic[3].u# =0 curVertic[3].v# =1 curVertic[3].r =0 curVertic[3].g =0 curVertic[3].b =255 curVertic[4].x# =400 curVertic[4].y# =200 curVertic[4].r =255 curVertic[4].g =0 curVertic[4].b =255 Local drag:Int =-1 While Not (KeyHit(key_escape) Or AppTerminate()) Cls SetColor 255, 255, 255 DrawLine curVertic[0].x# +2, curVertic[0].y# +2, curVertic[4].x# -2, curVertic[4].y# -2 DrawLine curVertic[4].x# -2, curVertic[4].y# -2, curVertic[1].x# -2, curVertic[1].y# +2 DrawLine curVertic[1].x# -2, curVertic[1].y# +2, curVertic[0].x# +2, curVertic[0].y# +2 Local areaWhite# =AreaTriangle(curVertic[0].x#, curVertic[0].y#, curVertic[4].x#, curVertic[4].y#, curVertic[1].x#, curVertic[1].y#) DrawText areaWhite#, 10, 50 SetColor 255, 0, 0 DrawLine curVertic[1].x# +2, curVertic[1].y# +2, curVertic[4].x# +2, curVertic[4].y# -2 DrawLine curVertic[4].x# +2, curVertic[4].y# -2, curVertic[2].x# +2, curVertic[2].y# +2 DrawLine curVertic[2].x# +2, curVertic[2].y# +2 , curVertic[1].x# +2, curVertic[1].y# +2 Local areaRed# =AreaTriangle(curVertic[1].x#, curVertic[1].y#, curVertic[4].x#, curVertic[4].y#, curVertic[2].x#, curVertic[2].y#) DrawText areaRed#, 10, 70 SetColor 0, 255, 0 DrawLine curVertic[2].x# -2, curVertic[2].y# +2 , curVertic[4].x# +2, curVertic[4].y# +2 DrawLine curVertic[4].x# +2, curVertic[4].y# +2, curVertic[3].x# +2, curVertic[3].y# +2 DrawLine curVertic[3].x# +2, curVertic[3].y# +2 , curVertic[2].x# -2, curVertic[2].y# +2 Local areaGreen# =AreaTriangle(curVertic[2].x#, curVertic[2].y#, curVertic[4].x#, curVertic[4].y#, curVertic[3].x#, curVertic[3].y#) DrawText areaGreen#, 10, 90 SetColor 0, 0, 255 DrawLine curVertic[3].x# -2, curVertic[3].y# +2 , curVertic[4].x# -2, curVertic[4].y# +2 DrawLine curVertic[4].x# -2, curVertic[4].y# +2, curVertic[0].x# -2, curVertic[0].y# +2 DrawLine curVertic[0].x# -2, curVertic[0].y# +2, curVertic[3].x# -2, curVertic[3].y# +2 Local areaBlue# =AreaTriangle(curVertic[3].x#, curVertic[3].y#, curVertic[4].x#, curVertic[4].y#, curVertic[0].x#, curVertic[0].y#) DrawText areaBlue#, 10, 110 SetColor 66, 66, 66 DrawText "(Sum : "+ Trim$(areaBlue# +areaGreen# +areaRed# +areaWhite#) +")", 10, 130 Local u4:String =Trim$(areaBlue# /(areaBlue# +areaRed#)) Local v4:String =Trim$(areaWhite# /(areaWhite# +areaGreen#)) If Instr(u4, ".") >0 And Instr(u4, ".") < (Len(u4) -2) Then u4 =Left$(u4, Instr(u4, ".") +2) EndIf If Instr(v4, ".") >0 And Instr(v4, ".") < (Len(v4) -2) Then v4 =Left$(v4, Instr(v4, ".") +2) EndIf For Local z:Int =0 To 4 Local radius =6 If drag =-1 Then If Sqr((MouseX() -curVertic[z].x#) ^2 +(MouseY() -curVertic[z].y#) ^2) <6 Then radius =10 If MouseDown(1) Then drag =z EndIf End If ElseIf Not(MouseDown(1)) Then drag =-1 EndIf SetColor curVertic[z].r, curVertic[z].g, curVertic[z].b If drag =z Then If drag =4 Then If InsideQuad(MouseX(), MouseY(), curVertic[0].x#, curVertic[0].y#,.. curVertic[1].x#, curVertic[1].y#, curVertic[2].x#, curVertic[2].y#,.. curVertic[3].x#, curVertic[3].y#) Then curVertic[z].x# =MouseX() curVertic[z].y# =MouseY() Else MoveMouse curVertic[z].x#, curVertic[z].y# EndIf Else curVertic[z].x# =MouseX() curVertic[z].y# =MouseY() EndIf End If DrawOval curVertic[z].x# -radius, curVertic[z].y# -radius, 2 *radius, 2 *radius SetColor 255, 255, 66 If z <4 Then DrawRect curVertic[z].x# +10, curVertic[z].y# -30, 45, 25 SetColor 3, 3, 3 If z =0 Then DrawText "0, 0", curVertic[z].x# +12, curVertic[z].y# -27 ElseIf z =1 Then DrawText "1, 0", curVertic[z].x# +12, curVertic[z].y# -27 ElseIf z =2 Then DrawText "1, 1", curVertic[z].x# +12, curVertic[z].y# -27 ElseIf z =3 Then DrawText "0, 1", curVertic[z].x# +12, curVertic[z].y# -27 EndIf Else DrawRect curVertic[z].x# +10, curVertic[z].y# -30, 90, 25 SetColor 3, 3, 3 DrawText u4 +", "+ v4, curVertic[z].x# +12, curVertic[z].y# -27 EndIf Next Flip Wend '------------------------------------------------------------------------------------------------------------------------------------- Function InsideQuad(px#, py#, x0#, y0#, x1#, y1#, x2#, y2#, x3#, y3#) If InsideTriangle(px#, py#, x0#, y0#, x1#, y1#, x3#, y3#) Then Return True ElseIf InsideTriangle(px#, py#, x1#, y1#, x2#, y2#, x3#, y3#) Then Return True Else Return False EndIf End Function '------------------------------------------------------------------------------------------------------------------------------------- Function InsideTriangle(px#, py#, ax#, ay#, bx#, by#, cx#, cy#) Local bc#, ca#, ab#, ap#, bp#, cp#, abc# bc# =bx *cy -by *cx ca# =cx *ay -cy *ax ab# =ax *by -ay *bx ap# =ax *py -ay *px bp# =bx *py -by *px cp# =cx *py -cy *px abc# =Sgn(bc +ca +ab) If (abc *(bc -bp +cp) >0) And (abc *(ca -cp +ap) >0) And (abc *(ab -ap +bp) >0) Then Return True End Function '------------------------------------------------------------------------------------------------------------------------------------- Function AreaTriangle:Float(x1#, y1#, x2#, y2#, x3#, y3#) Return Abs(x1# *(y2# -y3#) +x2# *(y3# -y1#) +x3# *(y1# -y2#)) /2 End Function '-------------------------------------------------------------------------------------------------------------------------------------

BlitzSupport (Posted 2009) [#10]

Nice! I tried for ages a couple of years ago to do this, to no avail. I imagine I'll make use of this at some point -- thanks.