polygon collision

BlitzMax Forums/BlitzMax Beginners Area/polygon collision

Bremer (Posted 2006) [#1]

Can anyone point me in the right direction as far as something that will show me how to check if two polygons overlap. I have the transformed x and y values in two arrays and the polygons is drawn correctly, but I can't seem to figure out how to get the collision working. Or if someone would be as kind as to show me an easy to follow example of how its done using two sets of pixel coordinates, I would be extremely grateful. Its the only thing missing before I can release my sprite module for bmax. The vertex data is held in two arrays of variable size depending on how many points the polygon consist of, but at a minimum of three. Field vx:Int[] Field vy:Int[] The points are in clockwise order. If someone helps me solve this, I will provide them with the sprite module free of charge. Its probably going to be sold at around 25 euros. [edit] Let me know if more info is needed.

Oddball (Posted 2006) [#2]

I've just, about 5 mins ago, finished the poly2poly collisions for my game. I broke my polys up into triangles and then did tri2tri collision. Not sure if this is the best way but it works.

Dreamora (Posted 2006) [#3]

The fastest way might be SAT (projects to different axis' and if there is only 1 axis where they don't overlap, then they are not colliding. Axis = each side of the first or the second polygon, depending on which one has fewer sides)

Bremer (Posted 2006) [#4]

It will have to be able to check for collision between two polygon frames like those in the above image and similar shapes. I would like to avoid having to try and make triangles out of the frames. I am not great at math myself, which is why I am asking for someone to help me out with this problem. I think that I have a good and useful sprite module going, but without polygon frame collision, its probably a lot less useful. Info on the sprite module, for those interested in knowing more, can be found here: http://zac-interactive.dk/tools/zsprite/zsprite.htm

Dreamora (Posted 2006) [#5]

For shape like that, SAT is definitely the easiest way to go. The cross ensures, that you only have 2 things to test: xmin - xmax as well as ymin - ymax. This then would show that they intersect on y but not on x thus they don't intersect. Would suggest you look for deeper informations on SAT and especially how to implement. Should be too hard on math, only a little vector and vector projection math ... thats game programming base knowledge, so no problem :-)

Bremer (Posted 2006) [#6]

I did some searching on "Separating Axis Theorem" and found this page, which seems to cover the basics of it. http://www.harveycartel.org/metanet/tutorials/tutorialA.html It could be useful to others, so I figured that I post it here. I am going to have a read through and see if I can understand it. If someone have ideas and possibly example code on how this works then that would still be highly appreciated :)

Diablo (Posted 2006) [#7]

Got some BMax code for you: SuperStrict ' Vector type ( A VERY SIMPLE VECTOR TYPE ) Type TVector Field x#, y# Function Create:TVector(_x#, _y#) Local v:TVector = New TVector v.x = _x v.y = _y Return v End Function Method DivEq(_scale#) x:/ _scale y:/ _scale End Method Method MulEq(_scale#) x:* _scale y:* _scale End Method Method AddEq(v:TVector) x:+ v.x y:+ v.y End Method Method MinEq(v:TVector) x:- v.x y:- v.y End Method Method CrossProduct#(v:TVector) Return x * v.y - y * v.x End Method Method Dot#(v:TVector) Return x * v.x + y * v.y End Method Method Mul:TVector(_scale#) Return TVector.Create(x * _scale, y * _scale) End Method Method Div:TVector(_scale#) Return TVector.Create(x / _scale, y / _scale) End Method Method Add:TVector(v:TVector) Return TVector.Create(x + v.x, y + v.y) End Method Method Sub:TVector(v:TVector) Return TVector.Create(x - v.x, y - v.y) End Method Method Leng#() Return Sqr(x * x + y * y) End Method rem Do two vectors intersect along a given axis endrem Function Intersect@(a:TVector[], b:TVector[], xa:TVector, _offset:TVector) Local min0#, max0# Local min1#, max1# min0 = IntervalMin(a, xa) max0 = IntervalMax(a, xa) min1 = IntervalMin(b, xa) max1 = IntervalMax(b, xa) Local h# = _offset.Dot(xa) min0:+ h max0:+ h Local d0# = min0 - max1 Local d1# = min1 - max0 If d0 > 0.0 or d1 > 0.0 Then Return False Else Return True End If End Function rem Min / Max functions nothing sepcial endrem Function IntervalMin#(verts:TVector[], xa:TVector) Local m# = verts[0].Dot(xa) For Local i% = 0 To verts.length - 1 Local d# = verts[i].Dot(xa) If d < m Then m = d Next Return m End Function Function IntervalMax#(verts:TVector[], xa:TVector) Local m# = verts[0].Dot(xa) For Local i% = 0 To verts.length - 1 Local d# = verts[i].Dot(xa) If d > m Then m = d Next Return m End Function End Type ' A simple polygon type Type TPolygon Field x#, y# ' Draw offset Field vx#[] ' Zero Based Field vy#[] ' Zero based Field vc# ' Vertex Count ' Just to help Function CreateByVectorList:TPolygon(_v:TList) Local p:TPolygon = New TPolygon p.vx = New Float[_v.count()] p.vy = New Float[_v.count()] p.vc = _v.count() Local i% = 0 For Local v:TVector = EachIn _v p.vx[i] = v.x p.vy[i] = v.y i:+ 1 Next Return p End Function ' Draw it Method Render() SetColor 255, 0, 0 Local _vx#[2], _vy#[2] For Local i% = 0 To vc - 2 _vx[0] = vx[i] + x _vy[0] = vy[i] + y _vx[1] = vx[i + 1] + x _vy[1] = vy[i + 1] + y DrawLine _vx[0], _vy[0], _vx[1], _vy[1] Next _vx[0] = vx[vc - 1] + x _vy[0] = vy[vc - 1] + y _vx[1] = vx[0] + x _vy[1] = vy[0] + y DrawLine _vx[0], _vy[0], _vx[1], _vy[1] SetColor 0, 0, 0 End Method ' Set position Method SetPos(_x%, _y%) x = _x y = _y End Method ' Test Collide _offset you shouldnt need to worry about but just incase... Method Collide@(p:TPolygon, _offset:TVector = Null) SetColor 0, 255, 0 If _offset = Null Then _offset = TVector.Create(x, y).Sub(TVector.Create(p.x, p.y)) End If Local a:TVector[], b:TVector[] Local i% a = New TVector[vc] For i = 0 To vc - 1 a[i] = New TVector a[i].x = vx[i] a[i].y = vy[i] Next b = New TVector[p.vc] For i = 0 To p.vc - 1 b[i] = New TVector b[i].x = p.vx[i] b[i].y = p.vy[i] Next Local xv:TVector[64] Local ai% = 0 Local j% = vc - 1 For Local i% = 0 To vc - 1 Local e0:TVector = a[j] Local e1:TVector = a[i] Local e:TVector = e1.Sub(e0) xv[ai] = TVector.Create(-e.y, e.x) If not TVector.Intersect(a, b, xv[ai], _offset) Return False EndIf j = i ai:+ 1 Next j% = p.vc - 1 For Local i% = 0 To p.vc - 1 Local e0:TVector = b[j] Local e1:TVector = b[i] Local e:TVector = e1.Sub(e0) xv[ai] = TVector.Create(-e.y, e.x) If not TVector.Intersect(a, b, xv[ai], _offset) Return False EndIf j = i ai:+ 1 Next Return True End Method End Type Local Box:TList = CreateList() Box.AddLast(TVector.Create(0, 0)) Box.AddLast(TVector.Create(100, 0)) Box.AddLast(TVector.Create(100, 100)) Box.AddLast(TVector.Create(0, 100)) Local Shape:TList = CreateList() Shape.AddLast(TVector.Create(25, 0)) Shape.AddLast(TVector.Create(50, 0)) Shape.AddLast(TVector.Create(75, 25)) Shape.AddLast(TVector.Create(50, 50)) Shape.AddLast(TVector.Create(25, 50)) Shape.AddLast(TVector.Create(0, 25)) Global ap1:TPolygon = TPolygon.CreateByVectorList(Box) ap1.SetPos(200, 200) Global ap2:TPolygon = TPolygon.CreateByVectorList(Shape) ap2.SetPos(100, 100) Graphics 800, 600 While not KeyHit(KEY_ESCAPE) Cls ap2.SetPos(MouseX(), MouseY()) ap1.Render() ap2.Render() SetColor 255, 255, 255 If ap2.Collide(ap1) Then DrawText "COLLIDED!!!", 10, 10 Flip 0 Wend The code is a quick ripp from This Good Chap Edit: It dosent always work the way you might want it to but i'll leave you to experiment. The above link has got a link to download a .zip with some code in it. (cpp source)

SillyPutty (Posted 2006) [#8]

very nice

Bremer (Posted 2006) [#9]

Had a look at that tutorial I found, understood most of it. Then took another look at my code, and found out that I had been using a wrong array for one set of vertices. Once I corrected that, my current code actually worked. Go figure. Its bugs like that, which is hardest to track down, especially when you have staired yourself blind looking at the same code for hours on end. Thanks for everyones input so far.