Tri Tri Intersection ?

Blitz3D Forums/Blitz3D Programming/Tri Tri Intersection ?

jfk EO-11110 (Posted 2007) [#1]

Is there some sourcecode for a (2D) Triangle to Triangle intersection test? Or what is in your opinion the best way to align 2 triangles onscreen with minimal space requirement?

jfk EO-11110 (Posted 2007) [#2]

haha, probably I will simply create two masked images and use ImagesCollide <:o)

b32 (Posted 2007) [#3]

I don't know any tri tri intersection code, but do you mean side-by-side alignment ? I wrote a routine a while back that could do something like that. If you give it the coords for two points, and the length of the three splines, it calculates where the 3rd point should be. There are two possibilities, so I used a forth point as a reference: ;--------------------------------------------------------------------------------------------------- ; C2 ; /\ ; / \ ; / \ ; A __________ B ; \ / ; \ / ; \/ ; C1 . D ; ; this program calculates (X,Y) of point C1/C2, ; given are the coordinates of point A, B and D. ; also known are the distances between each point. ;--------------------------------------------------------------------------------------------------- ;declare float variables Local mx#, my# Local ax#, ay#, bx#, by#, dx#, dy# Local cx1#, cy1#, cx2#, cy2# Local oax#, oay#, obx#, oby#, ocx#, ocy# Local organgle#, distance# Local h1#, d1#, h2#, d2#, h3#, d3# Local AB#, BC#, AC#, CD# Local C1#, C2# ;--------------------------------------------------------------------------------------------------- ; Main Program ;--------------------------------------------------------------------------------------------------- ;setup Graphics 320, 240 SetBuffer BackBuffer() SeedRnd MilliSecs() ;main loop Repeat Cls Locate 0, 0 ;----- ;INPUT ;----- ;generate three points ax = Rand(250) + 35 ay = Rand(80) + 120 bx = Rand(250) + 35 by = Rand(80) + 120 cx = Rand(250) + 35 cy = Rand(80) + 120 ;this point is used to determine which ;of the two possible points is valid by checking the distance dx = Rand(250) + 35 dy = Rand(80) + 120 ;calculate their distances AC = VDist(ax, ay, cx, cy) AB = VDist(ax, ay, bx, by) BC = VDist(bx, by, cx, cy) CD = VDist(cx, cy, dx, dy) ;------- ;PROCESS ;------- ;----------------------------------------------------- ;goal - (re)calculate the position of point C (cx, cy) ;----------------------------------------------------- ;store the position of point A, for translate purposes oax = ax oay = ay ;and point B and C as well for drawing purposes obx = bx oby = by ocx = cx ocy = cy ;calculate angle and distance from A to B organgle = (450 - ATan2(bx - ax, by - ay)) Mod 360 distance = vdist(ax, ay, bx, by) ;set new coordinates A and B (0,0)-(AB,0) ;because the formula works only with points A and B aligned on the X-axis. (y=0) ax = 0 ay = 0 bx = distance by = 0 ;---------------------------------------------------------------------------------- ; this is the main formula ; it calculates (x,y) for ; the third point ;there is two possibilities: C1 and C2 ;---------------------------------------------------------------------------------- cx1 = ((AB ^ 2) - (BC ^ 2) + (AC ^ 2)) / (2 * AB) cy1 = Sqr(((4 * AB ^ 2 * AC ^ 2) - (AB ^ 2 - BC ^ 2 + AC ^ 2) ^ 2) / (4 * AB ^ 2)) cx2 = cx1 cy2 = -cy1 ;----------------------------------------------------------------------------------- ; using the 4th point (D) we could determine which option is valid ;----------------------------------------------------------------------------------- Color 0, 0, 255 Rect 0, 0, 320, 40 Color 255, 255, 255 ;;check distances(lengths) Print "AB=" + vdist(ax, ay, bx, by) + " (" + AB + ")" Print "BC=" + vdist(bx, by, cx1, cy1) + " (" + BC + ")" Print "AC=" + vdist(ax, ay, cx1, cy1) + " (" + AC + ")" ;calculate midpoint 1 mx1 = (ax + bx + cx1) / 3 my1 = (ay + by + cy1) / 3 ;calculate angles (h1,h2,h3,h4) and distances (d1,d2,d3,d4) ;point A h1 = 450 - ATan2((ax - mx1), (ay - my1)) d1 = vdist(ax, ay, mx1, my1) ;point B h2 = 450 - ATan2((bx - mx1), (by - my1)) d2 = vdist(bx, by, mx1, my1) ;point C1 h3 = 450 - ATan2((cx1 - mx1), (cy1 - my1)) d3 = vdist(cx1, cy1, mx1, my1) ;point C2 h4 = 450 - ATan2((cx2 - mx1), (cy2 - my1)) d4 = vdist(cx2, cy2, mx1, my1) ;AB are rotated back into their original position ;C1 and C2 rotate along ax = Cos(h1 + organgle) * d1 ay = Sin(h1 + organgle) * d1 bx = Cos(h2 + organgle) * d2 by = Sin(h2 + organgle) * d2 cx1 = Cos(h3 + organgle) * d3 cy1 = Sin(h3 + organgle) * d3 cx2 = Cos(h4 + organgle) * d4 cy2 = Sin(h4 + organgle) * d4 ;translate points so that point A is at it's original position cx2 = cx2 - ax + oax cy2 = cy2 - ay + oay cx1 = cx1 - ax + oax cy1 = cy1 - ay + oay bx = bx - ax + oax by = by - ay + oay ax = ax - ax + oax ay = ay - ay + oay ;determine what C is valid If Abs(VDist(cx1, cy1, dx, dy) - CD) < Abs(VDist(cx2, cy2, dx, dy) - CD) Then cx = cx1 cy = cy1 Else cx = cx2 cy = cy2 End If ;------ ;OUTPUT ;------ Viewport 0, 40, 320, 200 Color 0, 64, 0 ;draw original points to the screen Oval oax - 3, oay - 3, 7, 7, False Oval obx - 3, oby - 3, 7, 7, False Oval ocx - 3, ocy - 3, 7, 7, False ;draw reference point D Oval dx - 2, dy - 2, 5, 5, False ;draw triangle Color 64, 64, 0 Line ax, ay, bx, by Line bx, by, cx, cy Line cx, cy, ax, ay ;text labels Color 180, 180, 180 Text ax, ay, "A", True, False Text bx, by, "B", True, False Text dx, dy, "D", True, False Color 255, 0, 0 Text cx, cy, "C", True, False Viewport 0, 0, GraphicsWidth(), GraphicsHeight() Flip ;wait for a key now = MilliSecs() Repeat Delay 50 Until (MilliSecs() - now > 750) Or KeyDown(1) Or KeyDown(205) Until KeyHit(1) End ;--------------------------------------------------------------------------------------------------- ; END ;--------------------------------------------------------------------------------------------------- ;---------------------------------------------------------------------------------------------------- ; VDist() ;---------------------------------------------------------------------------------------------------- ;return distance between two points Function VDist#(x1#, y1#, x2#, y2#) Return Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2) End Function

jfk EO-11110 (Posted 2007) [#4]

Thanks, IŽll check this out.

Beaker (Posted 2007) [#5]

Can't you just do 3 ray-to-triangle2 tests (one ray for each triangle1 edge)? Move triangle1 away from triangle2 by the amount of intersection?

jfk EO-11110 (Posted 2007) [#6]

Maybe yes, but I guess this wouldn't recognize an enclosed triangle?

Beaker (Posted 2007) [#7]

Or maybe test if each corner is inside the triangle (both ways).

Rob Farley (Posted 2007) [#8]

I think Beaker's solution sounds pretty straight forward... especially if you had a function to detect if a point was inside a triangle... Hmm... if only

jfk EO-11110 (Posted 2007) [#9]

Hmmmmmmmmmmm... wait a minute - what if they are intersecting, but there's no vertex inside the other tri? Like when two lines are crossing two lines of the 2nd tri. Well, Beakers first suggestion with 3* ray vs tri sounds good. Then I still have to ckeck if a tri is enclosed (all 3 vertices within Tri 1), by using Robs code. Wrapped in a neat function this may be pretty good.