polygon collision

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.

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.

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)

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

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

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

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)

very nice

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.