Looking for rotated, scaled box collisions

BlitzMax Forums/BlitzMax Programming/Looking for rotated, scaled box collisions

Robert Cummings

(Posted 2007) [#1]

Hi,

Looking for something pretty cool like this, or using vectors. Its for a shootemup, be nice to define a rectangle area then check collisions against its rotated and scaled state with other rects and circles.

Does such a library exist?

tonyg

(Posted 2007) [#2]

this?

Jesse

(Posted 2007) [#3]

I converted this lib from BlitzBasic:
name it :"npoly.bmx"


' nPoly - Polygonal Collision Library
' By Jocelyn 'GoSsE' Perreault, <a href="http://www.nuloen.com/" target="_blank">http://www.nuloen.com/</a>
' Last Updated: July 8 2004
' Version: 1.0.0

' This source code is copyrighted (c) To Jocelyn Perreault.
' It is FreeWare. You have no limitiations in regard To 
' applications/games that you Release/create with it, either
' they be freeware Or commercial. However, you cannot Release
' this source code under another name Or Release a similar
' library with it. It cannot be redistributed. The code may be 
' modified To be tweaked but you cannot distribute it. If you
' made a modification that you think the community would
' benifit, please let me know.
' If you make tons of money with a commercial project,
' a free copy wouldn't hurt ')
' I would love To have an e-mail And a place in the credits
' of your projects, but it is up To you.
' Thanks,
'                 Jocelyn "GoSsE Korupted" Perreault
'                  gosse@...
'                  Nuclear Loaded Entertainment
'                  <a href="http://www.nuloen.com/" target="_blank">http://www.nuloen.com/</a>

' ======================================================================
' Globals And Constants
' ======================================================================
Const nP_MAX = 32			' Maximum number of vertices For a poly

' ======================================================================
' Different objects
' ======================================================================

' Polygon
Type nP_Poly
	Field iX[nP_MAX]		' Vertices X position
	Field iY[nP_MAX]		' Vertices Y position
	Field fX#[nP_MAX]		' Scaled And rotated X position
	Field fY#[nP_MAX]		' Scaled And rotated Y position
	Field iVertexCount		' Number of vertices
	Field fScaleX#			' X-Scale
	Field fScaleY#			' Y-Scale
	Field fAngle#			' Angle rotation
	Field iMinX				' Bounding box
	Field iMinY				' Bounding box
	Field iMaxX				' Bounding box
	Field iMaxY				' Bounding box
End Type

' ======================================================================
' Functions
' ======================================================================

' Creates a New empty polygon
Function nP_CreatePoly:nP_Poly()
	Local nPoly:nP_Poly = New nP_Poly
	nPoly.fScaleX = 1
	nPoly.fScaleY = 1
	Return nPoly
End Function

' ----------------------------------------------------------------------

' Adds a vertex To a polygon
Function nP_AddVertex(poly:nP_Poly, x, y, bUpdate = True)
	Local nPoly:nP_Poly = poly
	If nPoly.iVertexCount > nP_MAX Then
		RuntimeError "Cannot add one more vertex to polygon!"
	Else
		nPoly.iX[nPoly.iVertexCount] = x
		nPoly.iY[nPoly.iVertexCount] = y
		nPoly.iVertexCount = nPoly.iVertexCount + 1
		If bUpdate Then
			nP_UpdatePoly(poly)
		End If
	End If
End Function

' ----------------------------------------------------------------------

' Checks If 2 polygons overlap each other
Function nP_PolyOverlap(poly1:nP_Poly, x1, y1, poly2:nP_Poly, x2, y2, bCheckBounding = True)
	' Polygons
	Local nPoly1:nP_Poly = poly1
	Local nPoly2:nP_Poly = poly2
	' Temp positions
	Local tx1#, ty1#, tx2#, ty2#, tx3#, ty3#, tx4#, ty4#
	' Delta calculations
	Local dSqr#, d1#, d2#, dx#, dy#
	' Last vertex
	Local lx1#, ly1#, lx2#, ly2#
	' Counters
	Local i, j
	' Checks bounding box first (If specified)
	If bCheckBounding Then
		tx1 = X1 + nPoly1.iMinX
		ty1 = Y1 + nPoly1.iMinY
		tx2 = X1 + nPoly1.iMaxX
		ty2 = Y1 + nPoly1.iMaxY
		tx3 = X2 + nPoly2.iMinX
		ty3 = Y2 + nPoly2.iMinY
		tx4 = X2 + nPoly2.iMaxX
		ty4 = Y2 + nPoly2.iMaxX
		If Not (tx3 > tx1 And ty3 > ty1 And tx3 < tx2 And ty3 < ty2) Then
			If Not (tx4 > tx1 And ty4 > ty1 And tx4 < tx2 And ty4 < ty2) Then
				If Not (tx3 > tx1 And ty4 > ty1 And tx3 < tx2 And ty4 < ty2) Then
					If Not (tx4 > tx1 And ty3 > ty1 And tx4 < tx2 And ty3 < ty2) Then
						Return False
					End If
				End If
			End If
		End If
	End If
	' Store the last vertex
	lx1 = nPoly1.fX#[0] + X1
	ly1 = nPoly1.fY#[0] + Y1
	lx2 = nPoly2.fX#[0] + X2
	ly2 = nPoly2.fY#[0] + Y2
	' Cycle through all other vertices
	For i = 1 To nPoly1.iVertexCount - 1
		For j = 1 To nPoly2.iVertexCount - 1
			' Store vertices
			tx1 = nPoly1.fX#[i] + X1
			ty1 = nPoly1.fY#[i] + Y1
			tx3 = nPoly2.fX#[j] + X2
			ty3 = nPoly2.fY#[j] + Y2
			tx2 = lX1
			ty2 = lY1
			tx4 = lX2
			ty4 = lY2
			' Calculate deltas
			dSqr = (ty4-ty3)*(tx2-tx1)-(tx4-tx3)*(ty2-ty1)
			d1 = (ty1-ty3)
			d2 = (tx1-tx3)
			dX = ((tx2-tx1)*d1-(ty2-ty1)*d2)
			dY = ((tx4-tx3)*d1-(ty4-ty3)*d2)
			' Parallel
			If dSqr = 0 Then
				' Coincident
				If dX = 0 And dY = 0 Then
					Return True
				End If
			Else
				' Otherwise
				d1 = dX / dSqr
				d2 = dY / dSqr
				If (d1 >= 0 And d1 <= 1) And (d2 >= 0 And d2 <= 1) Then
					Return True
				End If
			End If
			' Store last vertex
			lX2 = tx3
			lY2 = ty3
		Next
		' Store last vertex
		lX1 = tx1
		lY1 = ty1
	Next
	Return False
End Function

' ----------------------------------------------------------------------

Function nP_PolyOverlapsCircle(poly:nP_Poly, X, Y, iCircleX, iCircleY, iCircleRadius, bCheckBounding = True)
	Local nPoly:nP_Poly = poly
	' Temp positions
	Local tx1#, ty1#, tx2#, ty2#, tx3#, ty3#, tx4#, ty4#
	Local CX1#, CY1#, CX2#, CY2#, pX1#, pY1#, pX2#, pY2#, pXT#, pYT#
	' Delta calculations
	Local d1#, d2#, dX#, dY#, dSqr#
	' Checks bounding box first (If specified)
	If bCheckBounding Then
		tx1 = X + nPoly.iMinX
		ty1 = Y + nPoly.iMinY
		tx2 = X + nPoly.iMaxX
		ty2 = Y + nPoly.iMaxY
		tx3 = iCircleX - iCircleRadius
		ty3 = iCircleY - iCircleRadius
		tx4 = iCircleX + iCircleRadius
		ty4 = iCircleY + iCircleRadius
		If Not (tx3 > tx1 And ty3 > ty1 And tx3 < tx2 And ty3 < ty2) Then
			If Not (tx4 > tx1 And ty4 > ty1 And tx4 < tx2 And ty4 < ty2) Then
				If Not (tx3 > tx1 And ty4 > ty1 And tx3 < tx2 And ty4 < ty2) Then
					If Not (tx4 > tx1 And ty3 > ty1 And tx4 < tx2 And ty3 < ty2) Then
						Return False
					End If
				End If
			End If
		End If
	End If
	' Store the last vertex & circle
	lx = nPoly.fX#[0] + X
	ly = nPoly.fY#[0] + Y
	CX2# = iCircleX
	CY2# = iCircleY
	' Cycle through all other vertices
	For i = 1 To nPoly.iVertexCount - 1	
		CX1# = nPoly.fX#[i] + X
		CY1# = nPoly.fY#[i] + Y
		pX1 = lX - CX1
		pY1 = lY - CY1
		pX2 = CX2 - CX1
		pY2 = CY2 - CY1
		d1 = pX1 * pX2 + pY1 * pY2
		If d1 <= 0 Then
			dX# = CX2 - CX1
			dY# = CY2 - CY1
			dSqr# = dX * dX + dY * dY
		Else
			d2 = pX1 * pX1 + pY1 * pY1
			If (d2 <= d1) Then
				dX# = CX2 - lX
				dY# = CY2 - lY
				dSqr# = dX * dX + dY * dY
			Else
				d1 = d1 / d2
				pXT# = CX1 + d1 * pX1
				pYT# = CY1 + d1 * pY1
				dX# = CX2 - pXT
				dY# = CY2 - PYT
				dSqr# = dX * dX + dY * dY
			End If
		End If
		If dSqr# < iCircleRadius * iCircleRadius Then
			Return True
		End If
		lx = CX1
		ly = CY1
	Next
	Return False	
End Function

' ----------------------------------------------------------------------

' Returns True If both circles overlap
Function nP_CirclesOverlap(x1, y1, rad1, x2, y2, rad2)
	Local dx# = x2 - x1
	Local dy# = y2 - y1
	Local rsqr = rad1 + rad2
	rsqr = rsqr*rsqr
	Return (dx*dx+dy*dy < rsqr)
End Function

' ----------------------------------------------------------------------

' Scales the polygon by the specified scale
Function nP_ScalePoly(poly:nP_Poly, sx#, sy#, bUpdate = True)
	Local nPoly:nP_Poly = poly
	nPoly.fScaleX# = nPoly.fScaleX# * sx#
	nPoly.fScaleY# = nPoly.fScaleY# * sy#
	If bUpdate Then
		nP_UpdatePoly(poly)
	End If
End Function

' ----------------------------------------------------------------------

' Resizes the polygon To the specieid scale
Function nP_ResizePoly(poly:nP_Poly, sx#, sy#, bUpdate = True)
	Local nPoly:nP_Poly = poly
	nPoly.fScaleX# = sx#
	nPoly.fScaleY# = sy#
	If bUpdate Then
		nP_UpdatePoly(poly)
	End If
End Function

' ----------------------------------------------------------------------

' Rotates the polygon by the specified rotation angle
Function nP_RotatePoly(poly:nP_Poly, fRot#, bUpdate = True)
	Local nPoly:nP_Poly = poly
	nPoly.fAngle# = nPoly.fAngle# + fRot#
	If bUpdate Then
		nP_UpdatePoly(poly)
	End If
End Function

' ----------------------------------------------------------------------

' Turns the polygon To the specified angle
Function nP_FreeRotatePoly(poly:nP_Poly, fAngle#, bUpdate = True)
	Local nPoly:nP_Poly = poly
	nPoly.fAngle# = fAngle#
	If bUpdate Then
		nP_UpdatePoly(poly)
	End If
End Function

' ----------------------------------------------------------------------

' Updates the polygon according To scale And rotation
Function nP_UpdatePoly(poly:nP_poly)
	Local nPoly:nP_Poly = poly
	Local fX#, fY#, f1#, f2#
	Local i
	' Set up big extremums
	nPoly.iMinX = 9999999
	nPoly.iMinY = 9999999
	nPoly.iMaxX = -9999999
	nPoly.iMaxY = -9999999
	' Find a valid collision setting
	For i = 0 To nPoly.iVertexCount - 1
		' Standard data
		fX = nPoly.iX[i]
		fY = nPoly.iY[i]
		' Scale
		fX = fX * nPoly.fScaleX
		fY = fY * nPoly.fScaleY
		' Rotation
		If nPoly.fAngle# <> 0 Then
			f1 = Cos(nPoly.fAngle#) * fX - Sin(nPoly.fAngle#) * fY
			f2 = Sin(nPoly.fAngle#) * fX + Cos(nPoly.fAngle#) * fY
			fX = f1
			fY = f2
		End If
		' Final Values
		nPoly.fX#[i] = fX
		nPoly.fY#[i] = fY
		' Check For bounding box
		If fX < nPoly.iMinX Then
			nPoly.iMinX = fX
		End If
		If fY < nPoly.iMinY Then
			nPoly.iMinY = fY
		End If
		If fX > nPoly.iMaxX Then
			nPoly.iMaxX = fX
		End If
		If fY > nPoly.iMaxY Then
			nPoly.iMaxY = fY
		End If
	Next
End Function

' ----------------------------------------------------------------------

' Draws the polygon on screen at the specified location
Function nP_DrawPoly(poly:nP_Poly, x, y, r=255, g=255, b=255, bDrawBoundingBox=True, br=255, bg=255, bb=255)
	Local nPoly:nP_Poly = poly
	Local i, lx, ly
	' Draw bounding box (If specified)
	If bDrawBoundingBox Then
		SetColor br, bg, bb
		DrawRect nPoly.iMinX + x, nPoly.iMinY + y, nPoly.iMaxX - nPoly.iMinX + 1, nPoly.iMaxY - nPoly.iMinY + 1', False
	End If
	' Draw all the lines
	SetColor r, g, b
	lx = nPoly.fX[0] + x
	ly = nPoly.fY[0] + y
	For i = 1 To nPoly.iVertexCount - 1
		DrawLine lx, ly, nPoly.fX[i] + x, nPoly.fY[i] + y
		lx = nPoly.fX[i] + x
		ly = nPoly.fY[i] + y
	Next
End Function

' ----------------------------------------------------------------------

' Copies a polygon And Return the newly created poly
Function nP_CopyPoly:nP_Poly(poly:nP_Poly)
	Local nPoly:nP_Poly = poly
	Local newPoly:nP_Poly = New nP_Poly
	Local i
	' Copy point data
	For i = 0 To nPoly.iVertexCount - 1
		newPoly.iX[i] = nPoly.iX[i]
		newPoly.iY[i] = nPoly.iY[i]
		newPoly.fX#[i] = nPoly.fX#[i]
		newPoly.fY#[i] = nPoly.fY#[i]
	Next
	' Copy all data
	newPoly.iVertexCount = nPoly.iVertexCount
	newPoly.fScaleX# = nPoly.fScaleX#
	newPoly.fScaleY# = nPoly.fScaleY#
	newPoly.fAngle# = nPoly.fAngle#
	newPoly.iMinX = nPoly.iMinX
	newPoly.iMinY = nPoly.iMinY
	newPoly.iMaxX = nPoly.iMaxX
	newPoly.iMaxY = nPoly.iMaxY
	Return newPoly
End Function

' ----------------------------------------------------------------------

' Deletes the polygon from memory
'Function nP_FreePoly(poly)
'	Local nPoly.nP_Poly = Object.nP_Poly(poly)
'	Delete nPoly
'End Function

below is the demo
put both files in the same folder.


SetGraphicsDriver GLMax2DDriver()
Graphics 640, 480, 0, 2
glEnable GL_LINE_SMOOTH

SeedRnd MilliSecs()
Global tmrFPS = CreateTimer(60)
AppTitle ="nPoly Demo"

Include "nPoly.bmx"

gear1 = nP_CreatePoly()
nP_AddVertex(gear1, 0, -50, False)
nP_AddVertex(gear1, 10, -10, False)
nP_AddVertex(gear1, 50, 0, False)
nP_AddVertex(gear1, 10, 10, False)
nP_AddVertex(gear1, 0, 50, False)
nP_AddVertex(gear1, -10, 10, False)
nP_AddVertex(gear1, -50, 0, False)
nP_AddVertex(gear1, -10, -10, False)
nP_AddVertex(gear1, 0, -50)
gear2 = nP_CopyPoly(gear1)
nP_ScalePoly(gear2, 0.7, 0.7)

lever = nP_CreatePoly()
nP_AddVertex(lever, -100, 5, False)
nP_AddVertex(lever, 0, 5, False)
nP_AddVertex(lever, 0, -5, False)
nP_AddVertex(lever, -100, -5, False)
nP_AddVertex(lever, -100, 5)

Const MAXC = 4
Local cylinder:nP_Poly[MAXC]
Local cy:Int[MAXC]
cylinder[0] = nP_CreatePoly()
nP_AddVertex(cylinder(0), -9, 20, False)
nP_AddVertex(cylinder(0), 9, 20, False)
nP_AddVertex(cylinder(0), 9, -20, False)
nP_AddVertex(cylinder(0), -9, -20, False)
nP_AddVertex(cylinder(0), -9, 20)
cy(0) = 100
For i = 0 To MAXC-1
	cylinder(i) = nP_CopyPoly(cylinder[0])
	cy(i) = cy(0)
Next

box = nP_CreatePoly()
nP_AddVertex(box, 0, 0, False)
nP_AddVertex(box, 200, 0, False)
nP_AddVertex(box, 170, 70, False)
nP_AddVertex(box, 200, 200, False)
nP_AddVertex(box, 30, 200, False)
nP_AddVertex(box, 65, 130, False)
nP_AddVertex(box, 0, 180, False)
nP_AddVertex(box, 0, 0)
rad = 15

maxb = 100
maxr = 15

minx = 20
miny = 270
maxx = 620
maxy = 460
Local balllist:TList
Type ball
	Field poly
	Field rad
	Field x#
	Field y#
	Field velx#
	Field vely#
End Type

For i = 1 To maxb
	balls:ball = New ball
	balls.x = Rnd(minx + maxr, maxx - maxr)
	balls.y = Rnd(miny + maxr, maxy - maxr)
	balls.rad = Rnd(4, maxr)
	If Not balllist  Then balllist = CreateList()
	balllist.addlast(balls)
	k = False
	For b:ball = EachIn balllist
		If b <> balls Then
			If nP_CirclesOverlap(balls.x, balls.y, balls.rad, b.x, b.y, b.rad) Then
				ListRemove(balllist,balls)
				k = True
				Exit
			End If
		End If
	Next
	If Not k Then
		balls.velx = Rnd(0, 3) - 1.5
		balls.vely = Rnd(0, 3) - 1.5
		If Rand(1, 3) > 1 And balls.rad > 4 Then
			balls.poly = nP_CreatePoly()
			brad# = balls.rad
			srad# = Rand(2, balls.rad - 2)
			pikes = Rand(3, 7)
			deg = 0
			degstep = 180 / pikes
			For j = 1 To pikes
				nP_AddVertex(balls.poly, brad*Cos(deg), brad*Sin(deg), False)
				deg = deg + degstep
				nP_AddVertex(balls.poly, srad*Cos(deg), srad*Sin(deg), False)
				deg = deg + degstep
			Next
			nP_AddVertex(balls.poly, brad*Cos(deg), brad*Sin(deg), False)
		End If
	End If
Next

While Not KeyDown(KEY_escape)

	starttmr = MilliSecs()
	WaitTimer tmrFPS
	endtmr = MilliSecs()
	timFPS = timFPS + endtmr - starttmr

	If MilliSecs() > timFPS Then
		timFPS = MilliSecs() + 1000
		lastFPS = FPS
		FPS = 0
	Else
		FPS = FPS + 1
	End If
	
	framestart = MilliSecs()
	colchecks = 0
	colchecks2 = 0
	colchecks3 = 0
	
	Cls
	
	nP_RotatePoly(gear1, 1)
	colchecks = colchecks + 1
	' Gears
	While nP_PolyOverlap(gear1, 150, 150, gear2, 212, 150, False)
		nP_RotatePoly(gear2, -1)
		colchecks = colchecks + 1
	Wend
	colchecks = colchecks + 1
	' Gear And lever
	If Not nP_PolyOverlap(gear2, 212, 150, lever, 320, 130, False)
		nP_RotatePoly(lever, -1)
	End If
	colchecks = colchecks + 1
	While nP_PolyOverlap(gear2, 212, 150, lever, 320, 130, False)
		nP_RotatePoly(lever, 1)
		colchecks = colchecks + 1
	Wend
	
	' Cylinders with lever
	For i = 0 To MAXC-1
		colchecks = colchecks + 1
		If Not nP_PolyOverlap(cylinder(i), 230 + 22 * i, cy(i), lever, 320, 130, False)
			cy(i) = cy(i) + 3
		End If	
		colchecks = colchecks + 1
		While nP_PolyOverlap(cylinder(i), 230 + 22 * i, cy(i), lever, 320, 130, False)
			cy(i) = cy(i) - 1
			colchecks = colchecks + 1
		Wend
	Next

	' Resize box And mouse ball
	If KeyDown(200) Then
		nP_ScalePoly(box, 1.01, 1.01)
	End If
	If KeyDown(208) Then
		nP_ScalePoly(box, 0.99, 0.99)
	End If
	If KeyDown(203) Then
		nP_RotatePoly(box, 3)
	End If
	If KeyDown(205) Then
		nP_RotatePoly(box, -3)
	End If
	rad = 15 + MouseZ() * 3
	mx = MouseX()
	my = MouseY()

	nP_DrawPoly(gear1, 150, 150, 255, 0, 0, False)
	nP_DrawPoly(gear2, 212, 150, 255, 0, 0, False)
	nP_DrawPoly(lever, 320, 130, 255, 0, 0, False)
	For i = 0 To MAXC-1
		nP_DrawPoly(cylinder(i), 230 + 22 * i, cy(i), 255, 0, 0, False)
	Next
	DrawText "All polygonal collisions",110, 200
	DrawText "done real-time",110,215
	nP_DrawPoly(box, 400, 50, 255, 255, 0, False)
	DrawText "Hover mouse about this box",400,5
	DrawText "Arrow keys, mouse wheel",400,20
	colchecks2 = colchecks2 + 1
	If nP_PolyOverlapsCircle(box, 400, 50, mx, my, rad, False)
		SetColor 0, 0, 255
	Else
		SetColor 255, 255, 255
	End If
	DrawOval mx - rad, my - rad, rad*2, rad*2
	SetColor 0, 255, 0
	'DrawRect minx, miny, maxx - minx, maxy - miny', False
	For balls:ball = EachIn balllist
		balls.x = balls.x + balls.velx
		balls.y = balls.y + balls.vely
		If balls.x + balls.rad >= maxx Or balls.x - balls.rad <= minx Then
			balls.velx = -balls.velx
		End If
		If balls.y + balls.rad >= maxy Or balls.y - balls.rad <= miny Then
			balls.vely = -balls.vely
		End If
		If balls.poly = 0 Then
			DrawOval balls.x - balls.rad, balls.y - balls.rad, balls.rad*2, balls.rad*2
		Else
			nP_RotatePoly(balls.poly, balls.velx - balls.vely)
			nP_DrawPoly(balls.poly, balls.x, balls.y, 0, 255, 0, False)
		End If
		For b:ball = EachIn balllist
			If b <> balls Then
				If b.poly = 0 And balls.poly = 0 Then
					colchecks3 = colchecks3 + 1
					col = nP_CirclesOverlap(balls.x, balls.y, balls.rad, b.x, b.y, b.rad)
				ElseIf b.poly = 0 Then
					colchecks2 = colchecks2 + 1
					col = nP_PolyOverlapsCircle(balls.poly, balls.x, balls.y, b.x, b.y, b.rad)
				ElseIf balls.poly = 0 Then
					colchecks2 = colchecks2 + 1
					col = nP_PolyOverlapsCircle(b.poly, b.x, b.y, balls.x, balls.y, balls.rad)
				Else
					colchecks = colchecks + 1
					col = nP_PolyOverlap(balls.poly, balls.x, balls.y, b.poly, b.x, b.y)
				End If
				If col Then
					x# = balls.x - b.x
					y# = balls.y - b.y
					balls.velx = Abs(balls.velx) * Sgn(x#)
					balls.vely = Abs(balls.vely) * Sgn(y#)
					b.velx = Abs(b.velx) * -Sgn(x#)
					b.vely = Abs(b.vely) * -Sgn(y#)
					tx# = balls.velx * 0.7 + Abs(b.velx) * Sgn(x#) * 0.3
					ty# = balls.vely * 0.7 + Abs(b.vely) * Sgn(y#) * 0.3
					b.velx = b.velx * 0.7 + Abs(balls.velx) * -Sgn(x#) * 0.3
					b.vely = b.vely * 0.7 + Abs(balls.vely) * -Sgn(y#) * 0.3
					balls.velx = tx#
					balls.vely = ty#
					Exit
				End If
			End If
		Next
	Next

	SetColor 255, 255, 255
	DrawText "FPS: " + lastfps,0,0
	DrawText "Collision checks:",0,15
	DrawText "Poly vs poly:     " + colchecks,0,30
	DrawText "Poly vs circle:   " + colchecks2,0,45
	DrawText "Circle vs circle: " + colchecks3,0,60
	DrawText "Total:            " + (colchecks + colchecks2 + colchecks3),0,75
	
	Flip False

Wend

End

BlitzSupport

(Posted 2007) [#4]

Wow, nice!

Robert Cummings

(Posted 2007) [#5]

Wow perfect! really neat stuff thanks!

mongia2

(Posted 2007) [#6]

it work perfectly!
thanks

TartanTangerine (was Indiepath)

(Posted 2007) [#7]

Or grab my poly lib http://modules.indiepath.com

xMicky

(Posted 2007) [#8]

I just found out that the bounding box check in Function nP_PolyOverlap() must be executed lately (and always at least one time, while the first bounding box check may be skipped with bCheckBounding = FALSE) to avoid wrongly detection of collisions if two sides of two non-overlapping polygons are parallel and within the same line. See the code sample (you have to bring two parallel sides of the two polygons in the same line while the polygons may not overlap):

' nPoly - Polygonal Collision Library
' By Jocelyn 'GoSsE' Perreault, <a href="http://www.nuloen.com/" target="_blank">www.nuloen.com/</a>
' Last Updated: July 8 2004
' Version: 1.0.0

' This source code is copyrighted (c) To Jocelyn Perreault.
' It is FreeWare. You have no limitiations in regard To 
' applications/games that you Release/create with it, either
' they be freeware Or commercial. However, you cannot Release
' this source code under another name Or Release a similar
' library with it. It cannot be redistributed. The code may be 
' modified To be tweaked but you cannot distribute it. If you
' made a modification that you think the community would
' benifit, please let me know.
' If you make tons of money with a commercial project,
' a free copy wouldn't hurt ')
' I would love To have an e-mail And a place in the credits
' of your projects, but it is up To you.
' Thanks,
'                 Jocelyn "GoSsE Korupted" Perreault
'                  <a href=\"mailto:gosse@nuloen.com\">gosse@...;
'                  Nuclear Loaded Entertainment
'                  <a href="http://www.nuloen.com/" target="_blank">www.nuloen.com/</a>

' ======================================================================
' Globals And Constants
' ======================================================================
Const nP_MAX = 32			' Maximum number of vertices For a poly

' ======================================================================
' Different objects
' ======================================================================

' Polygon
Type nP_Poly
	Field iX[nP_MAX]		' Vertices X position
	Field iY[nP_MAX]		' Vertices Y position
	Field fX#[nP_MAX]		' Scaled And rotated X position
	Field fY#[nP_MAX]		' Scaled And rotated Y position
	Field iVertexCount		' Number of vertices
	Field fScaleX#			' X-Scale
	Field fScaleY#			' Y-Scale
	Field fAngle#			' Angle rotation
	Field iMinX				' Bounding box
	Field iMinY				' Bounding box
	Field iMaxX				' Bounding box
	Field iMaxY				' Bounding box
End Type

' ======================================================================
' Functions
' ======================================================================

' Creates a New empty polygon
Function nP_CreatePoly:nP_Poly()
	Local nPoly:nP_Poly = New nP_Poly
	nPoly.fScaleX = 1
	nPoly.fScaleY = 1
	Return nPoly
End Function

' ----------------------------------------------------------------------

' Adds a vertex To a polygon
Function nP_AddVertex(poly:nP_Poly, x, y, bUpdate = True)
	Local nPoly:nP_Poly = poly
	If nPoly.iVertexCount > nP_MAX Then
		RuntimeError "Cannot add one more vertex to polygon!"
	Else
		nPoly.iX[nPoly.iVertexCount] = x
		nPoly.iY[nPoly.iVertexCount] = y
		nPoly.iVertexCount = nPoly.iVertexCount + 1
		If bUpdate Then
			nP_UpdatePoly(poly)
		End If
	End If
End Function

' ----------------------------------------------------------------------

' Checks If 2 polygons overlap each other
Function nP_PolyOverlap(poly1:nP_Poly, x1, y1, poly2:nP_Poly, x2, y2, bCheckBounding = True)
	' Polygons
	Local nPoly1:nP_Poly = poly1
	Local nPoly2:nP_Poly = poly2
	' Temp positions
	Local tx1#, ty1#, tx2#, ty2#, tx3#, ty3#, tx4#, ty4#
	' Delta calculations
	Local dSqr#, d1#, d2#, dx#, dy#
	' Last vertex
	Local lx1#, ly1#, lx2#, ly2#
	' Counters
	Local i, j
	' Checks bounding box first (If specified)
	If bCheckBounding Then
		tx1 = X1 + nPoly1.iMinX
		ty1 = Y1 + nPoly1.iMinY
		tx2 = X1 + nPoly1.iMaxX
		ty2 = Y1 + nPoly1.iMaxY
		tx3 = X2 + nPoly2.iMinX
		ty3 = Y2 + nPoly2.iMinY
		tx4 = X2 + nPoly2.iMaxX
		ty4 = Y2 + nPoly2.iMaxX
		If Not (tx3 > tx1 And ty3 > ty1 And tx3 < tx2 And ty3 < ty2) Then
			If Not (tx4 > tx1 And ty4 > ty1 And tx4 < tx2 And ty4 < ty2) Then
				If Not (tx3 > tx1 And ty4 > ty1 And tx3 < tx2 And ty4 < ty2) Then
					If Not (tx4 > tx1 And ty3 > ty1 And tx4 < tx2 And ty3 < ty2) Then
						Return False
					End If
				End If
			End If
		End If
	End If
	' Store the last vertex
	lx1 = nPoly1.fX#[0] + X1
	ly1 = nPoly1.fY#[0] + Y1
	lx2 = nPoly2.fX#[0] + X2
	ly2 = nPoly2.fY#[0] + Y2
	' Cycle through all other vertices
	For i = 1 To nPoly1.iVertexCount - 1
		For j = 1 To nPoly2.iVertexCount - 1
			' Store vertices
			tx1 = nPoly1.fX#[i] + X1
			ty1 = nPoly1.fY#[i] + Y1
			tx3 = nPoly2.fX#[j] + X2
			ty3 = nPoly2.fY#[j] + Y2
			tx2 = lX1
			ty2 = lY1
			tx4 = lX2
			ty4 = lY2
			' Calculate deltas
			dSqr = (ty4-ty3)*(tx2-tx1)-(tx4-tx3)*(ty2-ty1)
			d1 = (ty1-ty3)
			d2 = (tx1-tx3)
			dX = ((tx2-tx1)*d1-(ty2-ty1)*d2)
			dY = ((tx4-tx3)*d1-(ty4-ty3)*d2)
			' Parallel
			If dSqr = 0 Then
				' Coincident
				If dX = 0 And dY = 0 Then
'=======================================================>
				  If lateBoundingBoxCheck Then
      		If Not (tx3 > tx1 And ty3 > ty1 And tx3 < tx2 And ty3 < ty2) Then
			      If Not (tx4 > tx1 And ty4 > ty1 And tx4 < tx2 And ty4 < ty2) Then
				      If Not (tx3 > tx1 And ty4 > ty1 And tx3 < tx2 And ty4 < ty2) Then
					      If Not (tx4 > tx1 And ty3 > ty1 And tx4 < tx2 And ty3 < ty2) Then
						      Return False
					      End If
				      End If
			      End If
		      End If				
		      End If 
					Return True
				End If
			Else
				' Otherwise
				d1 = dX / dSqr
				d2 = dY / dSqr
				If (d1 >= 0 And d1 <= 1) And (d2 >= 0 And d2 <= 1) Then

					Return True
				End If
			End If
			' Store last vertex
			lX2 = tx3
			lY2 = ty3
		Next
		' Store last vertex
		lX1 = tx1
		lY1 = ty1
	Next
	Return False
End Function

' ----------------------------------------------------------------------

' Updates the polygon according To scale And rotation
Function nP_UpdatePoly(poly:nP_poly)
	Local nPoly:nP_Poly = poly
	Local fX#, fY#, f1#, f2#
	Local i
	' Set up big extremums
	nPoly.iMinX = 9999999
	nPoly.iMinY = 9999999
	nPoly.iMaxX = -9999999
	nPoly.iMaxY = -9999999
	' Find a valid collision setting
	For i = 0 To nPoly.iVertexCount - 1
		' Standard data
		fX = nPoly.iX[i]
		fY = nPoly.iY[i]
		' Scale
		fX = fX * nPoly.fScaleX
		fY = fY * nPoly.fScaleY
		' Rotation
		If nPoly.fAngle# <> 0 Then
			f1 = Cos(nPoly.fAngle#) * fX - Sin(nPoly.fAngle#) * fY
			f2 = Sin(nPoly.fAngle#) * fX + Cos(nPoly.fAngle#) * fY
			fX = f1
			fY = f2
		End If
		' Final Values
		nPoly.fX#[i] = fX
		nPoly.fY#[i] = fY
		' Check For bounding box
		If fX < nPoly.iMinX Then
			nPoly.iMinX = fX
		End If
		If fY < nPoly.iMinY Then
			nPoly.iMinY = fY
		End If
		If fX > nPoly.iMaxX Then
			nPoly.iMaxX = fX
		End If
		If fY > nPoly.iMaxY Then
			nPoly.iMaxY = fY
		End If
	Next
End Function

' ----------------------------------------------------------------------

' Draws the polygon on screen at the specified location
Function nP_DrawPoly(poly:nP_Poly, x, y, r=255, g=255, b=255, bDrawBoundingBox=True, br=255, bg=255, bb=255)
	Local nPoly:nP_Poly = poly
	Local i, lx, ly
	' Draw bounding box (If specified)
	If bDrawBoundingBox Then
		SetColor br, bg, bb
		DrawRect nPoly.iMinX + x, nPoly.iMinY + y, nPoly.iMaxX - nPoly.iMinX + 1, nPoly.iMaxY - nPoly.iMinY + 1', False
	End If
	' Draw all the lines
	SetColor r, g, b
	lx = nPoly.fX[0] + x
	ly = nPoly.fY[0] + y
	For i = 1 To nPoly.iVertexCount - 1
		DrawLine lx, ly, nPoly.fX[i] + x, nPoly.fY[i] + y
		lx = nPoly.fX[i] + x
		ly = nPoly.fY[i] + y
	Next
End Function



SetGraphicsDriver GLMax2DDriver()
Graphics 640, 480, 0, 2
glEnable GL_LINE_SMOOTH
SetClsColor 0,0,255

SeedRnd MilliSecs()
Global tmrFPS = CreateTimer(60)
AppTitle ="nPoly Demo"

Local balllist:TList
Type ball
	Field poly
	Field rad
	Field x#
	Field y#
	Field velx#
	Field vely#
End Type

Global lateBoundingBoxCheck:Int =False

balllist = CreateList()

balls:ball = New ball
balls.x =400
balls.y =270
balls.velx =0
balls.vely =0
balllist.addlast(balls)
balls.poly = nP_CreatePoly()
nP_AddVertex(balls.poly, 0, 0, False)
nP_AddVertex(balls.poly, 100, 0, False)
nP_AddVertex(balls.poly, 0, 100, False)
nP_AddVertex(balls.poly, 0, 0, True)

balls2:ball = New ball
balls2.x =120
balls2.y =320
balls2.velx =0
balls2.vely =0
balllist.addlast(balls2)
balls2.poly = nP_CreatePoly()
nP_AddVertex(balls2.poly, 0, 0, False)
nP_AddVertex(balls2.poly, 100, 0, False)
nP_AddVertex(balls2.poly, 0, 100, False)
nP_AddVertex(balls2.poly, 0, 0, True)
Rem
balls2:ball = New ball
balls2.x =120
balls2.y =140
balls2.velx =0
balls2vely =0
balllist.addlast(balls2)
balls2.poly = nP_CreatePoly()
nP_AddVertex(balls2.poly, 0, 0, False)
nP_AddVertex(balls2.poly, 100, 0, False)
nP_AddVertex(balls2.poly, 100, 150, False)
nP_AddVertex(balls2.poly, 0, 150, False)
nP_AddVertex(balls2.poly, 0, 0, True)
EndRem
While Not KeyDown(KEY_escape)

	starttmr = MilliSecs()
	WaitTimer tmrFPS
	endtmr = MilliSecs()
	timFPS = timFPS + endtmr - starttmr

	If MilliSecs() > timFPS Then
		timFPS = MilliSecs() + 1000
		lastFPS = FPS
		FPS = 0
	Else
		FPS = FPS + 1
	End If
	
	framestart = MilliSecs()
	colchecks = 0
	colchecks2 = 0
	colchecks3 = 0
	
	Cls
	
	balls.x = MouseX()
	balls.y = MouseY()
	
	SetColor 0, 255, 0
	nP_DrawPoly(balls.poly, balls.x, balls.y, 0, 255, 0, False)
	nP_DrawPoly(balls2.poly, balls2.x, balls2.y, 0, 255, 0, False)
	
	For ballsX:ball = EachIn balllist
  	
		For b:ball = EachIn balllist
			If b <> ballsX Then
				colchecks = colchecks + 1
				col = nP_PolyOverlap(ballsX.poly, ballsX.x, ballsX.y, b.poly, b.x, b.y, False) 
				                                                                      ' FALSE =no bounding box check !
				If col Then
				  SetColor 255, 0, 0
        	DrawText "COLLISION DETECTED !", 10, 30

					Exit
				End If
			End If
		Next
	Next
	If KeyHit(key_D) Then
  	 lateBoundingBoxCheck =False
  ElseIf KeyHit(key_E) Then
  	 lateBoundingBoxCheck =True
  End If
  SetColor 255, 255, 255
	If lateBoundingBoxCheck Then
  	DrawText "Key D : Disable late bounding box check", 10, 10
	Else  
  	DrawText "Key E : Enable late bounding box check", 10, 10
  End If
	Flip False

Wend

End