This is all about the convertion of Paul Nettle's document.
General Collision Detection for Games Using Ellipsoids
Be sure to check it out.
Edit : The circle it's finished now to do it Elipsoid
Here is the translation of the Document's PseutoCode
with an example.
You will also need to save in the same directory.
The modified Vector type by SSS
and the Stuff that contains functions from the document
and other stuff that was needed.
General Collision Detection for Games Using Ellipsoids
Be sure to check it out.
Edit : The circle it's finished now to do it Elipsoid
Here is the translation of the Document's PseutoCode
with an example.
Strict Include "Vector.Bmx" Include "Stuff.Bmx" Global EPSILON:Double = 0.0002 '// The collision detection entry point '?collisionDetection(Point sourcePoint, Vector velocityVector, Vector gravityVector) Function collisionDetection(sourcePoint:TVector, velocityVector:TVector, gravityVector:TVector) 'DebugStop() '?{ '// We need To do any pre-collision detection work here. Such as adding '// gravity To our velocity vector. We want To do it in this '// separate routine because the following routine is recursive, And we '// don't want to recursively add gravity. '// Add gravity '?velocityVector += gravityVector; velocityVector.add(gravityVector , True) '// At this point, we_ll scale our inputs To the collision routine '?sourcePoint /= radiusVector; 'DivideVector(SourcePoint , radiusVector) '?velocityVector /= radiusVector; 'DivideVEctor(velocityVector , radiusVector) '// Okay! Time To do some collisions 'call collideWithWorld(sourcePoint, velocityVector); collideWithWorld(sourcePoint, velocityVector) '// Our collisions are complete, un-scale the output '?sourcePoint *= radiusVector; 'MultiplyVector(sourcePoint , RadiusVector) '?} End Function '// The collision detection_s recursive routine '?collideWithWorld(Point sourcePoint, Vector velocityVector) Function collideWithWorld(sourcePoint:TVector, velocityVector:TVector) '?{ '// How far do we need To go? '?Double distanceToTravel = length of velocityVector; Local distanceToTravel:Double = velocityVector.Magnitude() '// Do we need To bother? 'If (distanceToTravel < EPSILON) Then Return; '// Whom might we collide with? '?List potentialColliders = determine list of potential colliders; '// If there are none, we can safely move To the destination And bail '?If (potentialColliders is empty) If ListIsEmpty(TPolygon._List) '?{ '?sourcePoint += velocityVector; sourcePoint.add(velocityVector , True) '?Return; Return '?} End If '// You_ll need To write this routine To deal with your specific data '?scale_potential_colliders_to_ellipsoid_space(radiusVector); 'scale_potential_colliders_to_ellipsoid_space(radiusVector) '// Determine the nearest collider from the list potentialColliders '?bool collisionFound = False; Local collisionFound = False '?Double nearestDistance = -1.0; Local nearestDistance:Double = -1.0 '?Point nearestIntersectionPoint = Null; Local nearestIntersectionPoint:TVector = Null '?Point nearestPolygonIntersectionPoint = Null; Local nearestPolygonIntersectionPoint:TVector = Null If KeyDown(KEY_D) Then DebugStop() '?For (each polygon in potentialColliders) For Local _Pol:TPolygon = EachIn TPolygon._List '?{ Local j:Int = 3 For Local i:Int = 0 To 3 Local p1:TVector = _Pol._p[j].copy() Local p2:TVector = _Pol._p[i].copy() '// Plane origin/normal '?Point pOrigin = any vertex from current poly; Local pOrigin:TVector = _Pol._p[j].copy() '?Vector pNormal = surface normal (unit vector) from current poly; Local pNormal:TVector = _Pol._p[j].SubTract(_Pol._p[i]) pNormal.normalize() '// Determine the distance from the plane To the source '?Double pDist = intersect(pOrigin, pNormal, source, -pNormal); Local pDist:Double = intersect(pOrigin , pNormal , sourcePoint , pNormal.Multiply(-1 , False)) '?Point sphereIntersectionPoint; Local sphereIntersectionPoint:TVector '?Point planeIntersectionPoint; Local planeIntersectionPoint:TVector '// Is the source point behind the plane? '// '// [note that you can remove this condition If your visuals are Not '// using backface culling] '?If (pDist < 0.0) If (pDist < 0.0) '?{ 'Continue; j = i ''' As I am using this stily of loop Continue '?} Else '// Is the plane embedded (i.e. within the distance of 1.0 For our '// unit sphere)? '?If (pDist <= 1.0) If pDist <= RadiusVector._x '''' ELISPOID '?{ '// Calculate the plane intersection point '?Vector temp = -pNormal with length set To pDist; Local temp:TVector = pNormal.Multiply(-1 , False) temp.setMagnitude(pDist) '?planeIntersectionPoint = source + temp; planeIntersectionPoint = sourcePoint.add(temp) '?} Else '?{ '// Calculate the sphere intersection point '?sphereIntersectionPoint = source - pNormal; 'ELIPSOID for elipsoid the length of pNormal that if setted to one it's ok 'But for now we have to set it to circle radius Local tmp:TVector = pNormal.copy() tmp.setMagnitude(RadiusVector._x) sphereIntersectionPoint = sourcePoint.subtract(tmp) '// Calculate the plane intersection point '?Double t = intersect(pOrigin, pNormal, '? sphereIntersectionPoint, Velocity with '? normalized length); Local t:Double = intersect(pOrigin , pNormal ,.. sphereIntersectionPoint , velocityVector.normalise(False) ) '// Are we traveling away from this polygon? '?If (t < 0.0) Continue; If t < 0.0 j = i Continue End If '// Calculate the plane intersection point '?Vector V = velocityVector with length set To t; Local V:TVector = velocityVector.copy() V.setMagnitude(t) '?planeIntersectionPoint = sphereIntersectionPoint + V; planeIntersectionPoint = sphereIntersectionPoint.add(V) '?} End If '// Unless otherwise noted, our polygonIntersectionPoint is the '// same point as planeIntersectionPoint '?Point polygonIntersectionPoint = planeIntersectionPoint; Local polygonIntersectionPoint:TVector = planeIntersectionPoint.copy() '// So_ are they the same? Local closestPointPolygon:TVector = closestPointOnLine(_Pol._p[j] , _Pol._p[i],.. planeIntersectionPoint) '?If (planeIntersectionPoint is Not within the current polygon) If Not Abs(closestPointPolygon._x - polygonIntersectionPoint._x) < EPSILON If Not Abs(closestPointPolygon._y - polygonIntersectionPoint._y) < EPSILON '?{ '?polygonIntersectionPoint = nearest point on polygon's '?perimeter To planeIntersectionPoint; polygonIntersectionPoint = closestPointPolygon.copy() '?} End If End If '// Invert the velocity vector '?Vector negativeVelocityVector = -velocityVector; Local negativeVelocityVector:TVector = velocityVector.Multiply(-1 , False) '// Using the polygonIntersectionPoint, we need To reverse-intersect '// with the sphere (note: the 1.0 below is the unit-sphere_s '// radius) '?Double t = intersectSphere(sourcePoint, 1.0, '?polygonIntersectionPoint, negativeVelocityVector); Local t:Double = intersectSphere(polygonIntersectionPoint , negativeVelocityVector ,.. sourcePoint , RadiusVector._x) ''''' ELLIPSOID '// Was there an intersection with the sphere? '?If (t >= 0.0 && t <= distanceToTravel) If t >=0.0 And t<= distanceToTravel '?{ '// Where did we intersect the sphere? '?Vector V = negativeVelocityVector with length set To t; Local V:TVector = negativeVelocityVector.copy() V.setMagnitude(t) '?Vector intersectionPoint = polygonIntersectionPoint + V; Local intersectionPoint:TVector = polygonIntersectionPoint.add(V) '// Closest intersection thus far? '?If (!collisionFound || t < nearestDistance) If Not collisionFound Or t < nearestDistance '?{ '?nearestDistance = t; nearestDistance = t '?nearestIntersectionPoint = intersectionPoint; nearestIntersectionPoint = intersectionPoint.copy() '?nearestPolygonIntersectionPoint = polygonIntersectionPoint; nearestPolygonIntersectionPoint = PolygonIntersectionPoint.copy() '?collisionFound = True; collisionFound = True '?} End If '?} End If '?} End If j = i Next Next '// If we never found a collision, we can safely move To the destination '// And bail '?If (!collisionFound) If Not collisionFound '?{ '?sourcePoint += velocityVector; sourcePoint.add(velocityVector , True) '?Return; Return '?} End If '// Move To the nearest collision '?Vector V = velocityVector with length set To (nearestDistance - EPSILON); Local V:TVector = velocityVector.copy() V.setMagnitude(nearestDistance - EPSILON) '?sourcePoint += V; sourcePoint.add(V , True) '// What's our destination (relative to the point of contact)? 'Set length of V To (distanceToTravel _ nearestDistance); V.setMagnitude(distanceToTravel - nearestDistance) 'Point destinationPoint = nearestPolygonIntersectionPoint + V; Local destinationPoint:TVector = nearestPolygonIntersectionPoint.add(V) '// Determine the sliding plane '?Point slidePlaneOrigin = nearestPolygonIntersectionPoint; Local slidePlaneOrigin:TVector = nearestPolygonIntersectionPoint.copy() '?Vector slidePlaneNormal = nearestPolygonIntersectionPoint - sourcePoint; Local slidePlaneNormal:TVector = nearestPolygonIntersectionPoint.subtract(sourcePoint) slidePlaneNormal.normalise() '' ELIPSOID this will be removed '// We now project the destination point onto the sliding plane '?Double time = intersect(slidePlaneOrigin, slidePlaneNormal, '?destinationPoint, slidePlaneNormal); Local time:Double = intersect(slidePlaneOrigin , slidePlaneNormal , .. destinationPoint , slidePlaneNormal) DrawText time , 10 , 50 '?Set length of slidePlaneNormal To time; slidePlaneNormal.setMagnitude(time) '?Vector destinationProjectionNormal = slidePlaneNormal; Local destinationProjectionNormal:TVector = slidePlaneNormal.copy() '?Point newDestinationPoint = destination + destinationProjectionNormal; Local newDestinationPoint:TVector = destinationPoint.add(destinationProjectionNormal ) '// Generate the slide vector, which will become our New velocity vector '// For the Next iteration '?Vector newVelocityVector = newDestinationPoint _nearestPolygonIntersectionPoint; Local newVelocityVector:TVector = newDestinationPoint.subtract(nearestPolygonIntersectionPoint) '// Recursively slide (without adding gravity) '?collideWithWorld(sourcePoint, newVelocityVector); collideWithWorld(sourcePoint , newVelocityVector) '} End Function Function scale_potential_colliders_to_ellipsoid_space(RadiusVector:TVector) For Local _P:TPolygon = EachIn TPolygon._List For Local i:Int = 0 To 3 DivideVector(_P._p[i] , RadiusVector) Next Next End Function Function scale_back_potential_colliders_from_ellipsoid_space(RadiusVector:TVector) For Local _P:TPolygon = EachIn TPolygon._List For Local i:Int = 0 To 3 MultiplyVector(_P._p[i] , RadiusVector) Next Next End Function 'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW 'WWWWWWWWWWWWWWWWWW TEST 'WWWWWWWWWWWWWWWWWWWWWWWWWWWWW Global Test:Int = 1 Local P1:TPolygon = TPolygon .CreateFromVectors( TVector.create( 0 , 340 ) , .. TVector.create( 37 , 349 ) , .. TVector.create( 22 , 553 ) , .. TVector.create( 0 , 555 ) ) Local P2:TPolygon = TPolygon .CreateFromVectors( TVector.create( 21 , 554 ) , .. TVector.create( 85 , 555 ) , .. TVector.create( 175 , 598 ) , .. TVector.create( 14 , 593 ) ) Local P3:TPolygon = TPolygon .CreateFromVectors( TVector.create( 175 , 599 ) , .. TVector.create( 294 , 549 ) , .. TVector.create( 428 , 547 ) , .. TVector.create( 531 , 588 ) ) Local P4:TPolygon = TPolygon .CreateFromVectors( TVector.create( 532 , 590 ) , .. TVector.create( 596 , 539 ) , .. TVector.create( 656 , 514 ) , .. TVector.create( 759 , 525 ) ) Local P5:TPolygon = TPolygon .CreateFromVectors( TVector.create( 756 , 524 ) , .. TVector.create( 746 , 439 ) , .. TVector.create( 796 , 418 ) , .. TVector.create( 796 , 530 ) ) Local cOrigin:TVector = TVector.create( 341 , 511 ) Local cVelocity:TVector = TVector.create(1 , 1) Local GravityVector:TVector = TVEctor.create(0,0.01) Global RadiusVector:TVector = TVector.create(10 , 10) Local speed:Double = 1.0 Graphics 800 , 600 While Not KeyDown(KEY_ESCAPE) Cls SetColor 255 , 0 , 0 For Local Poly:TPolygon = EachIn TPolygon._List Poly.Draw() Next SetColor 0 , 255 , 0 DrawOval cOrigin._x - RadiusVector._x , cOrigin._y - RadiusVector._y , RadiusVector._x * 2 , RadiusVector._y * 2 SetColor 0 , 0 , 255 cVelocity.Draw(cOrigin._x , cOrigin._y) collisionDetection(cOrigin , cVelocity , GravityVector) If MouseDown(1) cOrigin.set(MouseX() , MouseY()) End If If KeyDown(KEY_LEFT) cVelocity.add(TVector.create(-speed , 0) , True) End If If KeyDown(KEY_RIGHT) cVelocity.add(TVector.create(speed , 0) , True) End If DrawText "FPS : " + TFPS.getFPS(),10,100 DrawText "Mem : " + GCMemAlloced(),10,120 Flip TFPS.Update() Wend Type TFPS Global FPS:Int = 0 Global Time:Int = 0 Global frames:Int = 0 Function getFPS:Int() Return FPS End Function Function Update() If Time = 0 Then Time = MilliSecs() If MilliSecs()-Time > 999 Then FPS = frames frames = 0 Time = MilliSecs() Else frames:+1 EndIf End Function End Type End
You will also need to save in the same directory.
The modified Vector type by SSS
and the Stuff that contains functions from the document
and other stuff that was needed.