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