Hello and welcome back to my blog!

This article is a kind of companion article to Physics engines for dummies and talks about the act of actually detecting a collision between two shapes.

This article assumes the reader has a basic grasp of maths and geometry.

**Definitions**

I will define matrices in bold uppercase, vectors in uppercase and scalars in lowercase. The dot product will be shown as . and cross product as x.

||A|| means the magnitude of A.

|A| means the absolute value of A.

When I want to express individual components of a vector, I will write A_x to mean the x component of A.

I will use * to denote multiplication, but also note that sV might be used to show the scalar s multiplied by the vector V.

## Collision Detection

Briefly, collision detection is the process of detecting when two shapes are about to collide or have already collided. There is a distinction there because there are chiefly two different types of collision detection methods:

**Discrete**

This type will only tell you whether two shapes are intersecting at the current time.

At frame 1, the objects are not colliding, but by frame 2 they are.

**Continuous**

This type tries to predict the exact point and time of collision between the two objects.

At frame 1, the objects are *predicted* to collide before frame 2 arrives. The system estimates the point and time of the collision so that when frame 2 does arrive the objects are not intersecting.

Obviously the continuous method seems the better choice, since we don't want our objects to be intersecting on screen - however before we can understand the way this method works, we must first explore the other method.

## Discrete collision detection

**Penetration distance**

In discrete collision detection, it's very important to know exactly how much one shape has penetrated into another and what the shortest direction to push the two apart again is.

This is important because we will need to be able to *resolve *the collision and push the two shapes apart so they are just touching.

In Figure 1, the penetration distance is *d* and the direction to push is *n*.

Let's start having a look at some common collision detection cases.

**Circle vs circle**

Two circles *A *and *B *are defined as having a centre and a radius. They collide when the distance between the two centres is less than the sum of their radii:

||A-B|| < (r1+r2)

Of course you can speed this up by not having the compute the magnitude ||A-B|| which involves a sqrt by squaring both sides of the equation:

||A-B||² < (r1+r2)²

So to calculate a measure of the penetration we can say:

p = ||A-B|| - (r1+r2)

You can see that this is a simple rearrangement of the collision test inequality

||A-B|| < (r1+r2)

=

||A-B|| - (r1+r2) < 0

All I have done is to subtract (r1+r2) from both sides of the inequality which is handily also the measure of penetration between the two circles. So, when

p < 0

The two spheres are penetrating by distance p. We would also like the *penetration vector *so that we can correct the penetration once we discover it. This is the vector that moves both circles to the point where they just touch, correcting the penetration. Importantly it is not only just a vector that does this, it is the *only *vector which corrects the penetration by moving the minimum amount. This is important because we only want to correct the error, not introduce more by moving too much when we correct, or too little.

N = (A-B) / ||A-B||

P = N*p

Here we have calculated the normalised vector N between the two centres and the penetration vector P by multiplying our unit direction by the penetration distance.

At this point you may have noticed that I haven't tried to optimise this part of the calculation by using squared lengths etc. This is generally ok because we can still do the initial intersection test using squared maths and then once we have detected an intersection, we can go for the heavier maths since it will happen far less often.

You may also have noticed that during our calculations we have calculated the collision normal N.

**AABB vs AABB**

Similarly as useful as the mighty circle, the Axis Aligned Bounding Box, or AABB is defined by its corner points and represents a un-rotatable rectangle in 2d. These are generally used to bound more complex objects so that a simple overlap check can be done to determine broad overlap, and then a more expensive fine grained check can be performed later.

*Figure 2* shows complex object *A *bounded by its AABB.

For two AABBs *A *and *B *defined by their centres and half-extents (half width, half height), overlap can be determined quite simply:

D = |centreB-centreA| - (halfExtentsA+halfExtentsB)

binary overlap = D_x < 0 && D_y < 0; |

In the example below the half extents are shown in red.

Fun AABB facts:

To build an AABB from a complex object, just loop through all the vertices keeping a track of the minimum and maximum coordinate in each axis:

/// <summary> /// /// </summary> static public function BuildAABB(points:Vector.<Vector2>):AABB { var min:Vector2 = new Vector2(Number.MAX_VALUE, Number.MAX_VALUE); var max:Vector2 = min.m_Neg; for each(var p:Vector2 in points) { min = p.Min(min); max = p.Max(max); } return new AABB ( min.Add(max).MulScalar(0.5), max.Sub(min).MulScalar(0.5) ); } |

To build an AABB from two separate AABBs, do the same thing, but form the min and max points of each AABB and use them as the vertices:

static public function CombineAABBs(a:AABB, b:AABB):AABB { const minA:Vector2 = a.m_centre.Sub( a.m_halfExtents ); const maxA:Vector2 = a.m_centre.Add( a.m_halfExtents ); const minB:Vector2 = b.m_centre.Sub( b.m_halfExtents ); const maxB:Vector2 = b.m_centre.Add( b.m_halfExtents ); const min:Vector2 = minA.Min(minB); const max:Vector2 = maxA.Max(maxB); const centre:Vector2 = min.Add(max).MulScalar(0.5); const halfExtents:Vector2 = max.Sub(min).MulScalar(0.5); return new AABB( centre, halfExtents ); } |

**Circle vs AABB**

Not terribly useful in the real world, but very useful as tool for understanding, the circle vs AABB test is also reasonably simple - the trick is to convert this problem into the simpler problem of circle vs circle. For an AABB A and a circle B:

The first step is to get the centre of the circle and project it on to the boundary of the AABB. Fortunately this is as easy as forming the vector *V *between AABB and circle and simply clamping it against the half extents of the AABB. This yields point B_{c}. In *Figure 2*, the clamped x, y region of V is shown in red.

B_{c} is actually the closest point on the AABB to the circle, which means the distance from the AABB to the circle is simply the length of the vector from B_{c} to B minus the radius of the circle.

D = B - B_{c}

distance = ||D|| - radius

**Circle vs OBB**

Circle vs Oriented Bounding Box or OBB is much more useful in the real world, but more tricky because the box now has an orientation to worry about. But, once again we can convert this problem into a simpler one, that of circle vs AABB by simply transforming the circle into the space of the OBB first.

public class OBB { /// <summary> /// /// </summary> public override function Collide( vis:Visual ):Contact { if ( vis is Circle ) { const c:Circle = Circle( vis ); // transform circle into OBB space const v:Vector2 = m_matrix.TransformIntoSpaceOf( c.m_Pos ); const clamped:Vector2 = v.Clamp( m_halfExtents.m_Neg, m_halfExtents ); // form point on OBB const point:Vector2 = m_matrix.TransformBy( clamped ); // get distance to circle const d:Vector2 = c.m_Pos.Sub( point ); const dist:Number = d.m_Len - c.m_Radius; return new Contact( d.m_Unit, dist, point ); } else { throw new NotImplementedException( ); } } } |

That's the code snippet.

**OBB vs OBB**

Now we're starting to get into the interesting stuff. Oriented Bounding Box vs Oriented Bounding Box is actually pretty much the same complexity as convex polygon vs convex polygon. A lot of people advocate using the Separating Axis Test in order to solve this problem, but personally I've never been able to visualise it and generally, if I can't visualise something, I'm not going to use it as a solution.

A concept I have been able to visualise and the one I'm going to demonstrate here is that of the Minkowski Difference. Once again the idea behind using this technique is that it enables us to covert this difficult problem into a more simple one.

The Minkowski Difference consists of the convex hull of every point on the boundary of one shape *subtracted* from every point on the boundary of the other shape. Its easier to imagine this as shrinking one of the shapes down until it becomes a point, and expanding the other shape by the shape of the first. *Configuration space* is the space that the Minkowski difference resides within - the set of vector differences of two objects.

*Figure 4* shows objects *A *and *B*, and then also shows object *B *shrunk down to a point, while *A *grows by the shape of *B*. Of course, because its a subtraction of one from the other, the position of the resulting shape changes, and it's the relationship with the origin (0,0) which then becomes very interesting.

It turns out that when the Minkowski Difference (written *MD *from now on) of two shapes contains the origin, the two shapes are intersecting. Furthermore, the distance from the origin to the MD is actually the distance between the two shapes, and the vector between the two gives you the *Minimum Translational Distance* which is the globally shortest distance you can move either shape from penetration until they both just touch.

In the above demo, you can manipulate the OBBs *A *and *B *by moving them, or you can drag the handles to rotate them. Note the MD *B-A* shown and how it reacts as the objects are moved. The origin is shown as the black dot in the centre - note that when *A *and *B *intersect, the MD contains the origin. The *Minimum Translational Distance* between the two shapes is shown as the blue line.

The observant among you will also notice the coloured edges in the MD - these represent the shape they originated from; red edges come from the red shape *A *and green from *B*.

So, how do you build this MD for two OBBs, then? Each edge in the MD is made up of a vertex from one shape subtracted from an edge from the other. In order to know which vertices we subtract from which edges, we need to define the concept of a *supporting vertex*.

A *supporting vertex* is simply a vertex which is "most in the direction of" a given direction vector. Mathematically, this can be found as the vertex which has the greatest dot product with a given direction vector.

Once we have this we can simply loop through all the edges of *A*, finding the supporting vertex in B for each edge by using reversed edge normal. The edge normal is reversed because we want to find the vertex "most opposite" this edge. As we do so, we project the origin onto each edge, and keep track of the distance - we're looking for the least negative distance, which will be the *Minimum Translational Distance*.

Once we've gone through edges of *A*, we do the same thing with *B*, this time using supporting vertices from A, again tracking the least negative distance. If we're only concerned about penetration we can terminate our search as soon as we find a positive distance - since this represents a separating axis.

var p0:Vector2 = new Vector2( ); var p1:Vector2 = new Vector2( ); var leastPenetratingDist:Number = -Number.MAX_VALUE; var leastPositiveDist:Number = Number.MAX_VALUE; // face of A, vertices of B for ( var i:int = 0; i<A.m_numPoints; i++ ) { // get world space normal var wsN:Vector2 = A.GetWorldSpaceNormal( i ); // world space edge var wsV0:Vector2 = A.GetWorldSpacePoint( i ); var wsV1:Vector2 = A.GetWorldSpacePoint( ( i+1 )%A.m_numPoints ); // get supporting vertices of B, most opposite face normal var s:Vector.<SupportVertex> = B.GetSupportVertices(wsN.m_Neg); for (var j:int=0; j<s.length; j++) { // form point on plane of minkowski face var mfp0:Vector2 = s[j].m_v.Sub(wsV0); var mfp1:Vector2 = s[j].m_v.Sub(wsV1); var faceDist:Number = mfp0.Dot( wsN ); // project onto minkowski edge var p:Vector2 = ProjectPointOntoEdge( new Vector2( ), mfp0, mfp1 ); // get distance var dist:Number = p.m_Len*Scalar.Sign(faceDist); // track negative if ( dist>leastPenetratingDist ) { p0 = p; leastPenetratingDist = dist; } // track positive if ( dist > 0 && dist<leastPositiveDist ) { p1 = p; leastPositiveDist = dist; } } } // face of B, vertices of A for ( i = 0; i<B.m_numPoints; i++ ) { // get world space normal wsN = B.GetWorldSpaceNormal( i ); // world space edge wsV0 = B.GetWorldSpacePoint( i ); wsV1 = B.GetWorldSpacePoint( ( i+1 )%B.m_numPoints ); // get supporting vertices of A, most opposite face normal s = A.GetSupportVertices(wsN.m_Neg); for (j=0; j<s.length; j++) { // form point on plane of minkowski face mfp0 = wsV0.Sub(s[j].m_v); mfp1 = wsV1.Sub(s[j].m_v); faceDist = -mfp0.Dot( wsN ); // project onto minkowski edge p = ProjectPointOntoEdge( new Vector2( ), mfp0, mfp1 ); // get distance dist = p.m_Len*Scalar.Sign(faceDist); // track negative if ( dist>leastPenetratingDist ) { p0 = p; leastPenetratingDist = dist; } // track positive if ( dist > 0 && dist<leastPositiveDist ) { p1 = p; leastPositiveDist = dist; } } } if ( leastPenetratingDist<0 ) { // penetration by leastPenetratingDist } else { // separated by leastPositiveDist } |

The above snippet also tracks positive distance so can be simplified if you only want to track penetration. One caveat to watch out for is the case where the two shapes are exactly aligned - as they are in the demo above. In this case, you have to deal with the possibility of there being two supporting vertices for an edge instead of one, and it's important to re-project onto the edge from the origin to make sure you don't accidentally pick the wrong edge-vertex pair. The above code deals with this case.

**Poly vs Poly**

The really good thing about this technique is that it applies directly to arbitrary convex polygons as well.

Again, manipulate the live demo by dragging the shapes and their handles...

So, we can now calculate the penetration distance for two arbitrary convex polygons.

## Continuous

So, finally we get around to talking about continuous collision detection. Now we start to be able to reap the rewards of all this *Minkowski Difference* nonsense 🙂

**Continuous Linear**

It turns out that if all we want to do is a linear sweep of our shapes to find the first time of collision ignoring rotation, the only thing we have to do is to ray-cast from the origin towards the MD using the relative velocity of the two objects as the ray segment end!

In *Figure 5*, the first time of collision of *B *with *A *can be found by shooting a ray from the origin towards the MD of *B-A*.

For polygons this is the same amount of work as calculating the penetration distance - you fire the ray at the edges of the MD, which you build as usual. You can even avoid testing edges if the ray is back-facing with respect to the edge normal.

In the above demo, A is being swept against B along A's velocity; the pink A' shows where A hits B. The MD shows what this looks like in Configuration Space - don't forget to rotate/move A and B to see what the result looks like. Notice how the ray at the origin fired against the MD corresponds exactly to when A hits B?

One caveat is that A must not intersect B to start with, or the test will fail. Gino Van Den Bergen has generalised this approach to work with the GJK algorithm, this is well worth taking a look at if you want to cast against non-polygonal shapes, like circles or capsules.

The basic idea is this:

You provide a function which can return the closest distance between two shapes and the normal at that point. These two return values are also the distance from the MD to the origin and the direction that distance is in. In this example, the function used is returning distance and normal between two circles - shown in the diagram is the MD of two circles.

In *Figure 6*, two iterations of Gino Van Den Bergen's algorithm are shown, I_{1} and I_{2}. The black point represents the current estimate, and starts at the origin in I_{1} and moves along the velocity shown as the arrow. The green point represents part of the information returned by the function - the closest point on the MD, which is at the distance returned, also the normal at that point has been found as well (again, returned by the function).

The algorithm intersects the velocity ray against the returned normal and produces the red point shown in the diagram. Then it moves on to the next iteration. The red point becomes the new estimate and the function is queried again for the distance to the MD and the normal. The information returned results in the new red intersection point in I_{2} and at this point the diagram becomes less useful because we're so close to the visible tolerance. In practice the algorithm will terminate when the distance returned from the function is less than some predefined tolerance.

I'm describing this algorithm because it will be useful when we think about intersection including angular velocity.

**Continuous Angular/Linear**

Things start to get a little more tricky when we want to calculate the exact hit time where there is rotation present. To solve this problem, we must turn to the work of Brian Mirtich, Gino Van Den Bergen and Erwin Coumans.

Brian Mitch's thesis presents some of the fundamental building blocks used in solving this problem:

In *Figure 7*, (lifted directly from his thesis) he shows two bodies, with their closest points shown and the two actual contact points *x1 *and *x2 *for this collision. Given the fact that these bodies are convex, he shows that the distance between the closest points represents the first possible time of collision between the two shapes under **no rotation**. Further, he shows that, given the point with the largest distance from the centre for each body, it's possible to bound the earliest time of collision between two rotating shapes.

You can see why by looking at *Figure 8* - on the left, the thin rectangle rotates and extreme point p moves to p' following the rotation. The length of the arc travelled by p can be found by simply using the circular arc length formula from geometry - L=theta*r as shown on the right in *Figure 8*. Therefore if we know the maximum distance from the origin of the shape, and we know the angular velocity, we can find an *upper bound* for the linear component of the angular rotation of a shape, and therefore we can simply add this linear distance value on to the bound that we had for non-rotating shapes.

Erwin Coumans took this idea and using a method similar to the linear cast of Gino Van Den Bergen, produced a new algorithm which determines the time of impact between translating/rotating bodies:

The live demo above shows A and A', the position of A after some linear and angular motion, 90 degrees to be precise. The various iterations of the MD are shown on the right. Don't forget to move the shapes around!

The thing to note is that the **shape **of the MD changes under rotation of either body, unlike with linear only motion where it just translates.

Each of the MDs shown represent one iteration of the algorithm. The algorithm itself is exactly the same I described using Figure 6 above, except that there is an extra distance term added which means that instead of the ray intersecting the plane and the estimate getting moved directly there, it only approaches it instead - taking care not to advance more than the extra distance terms allows each iteration. This way, the correct result is approached each iteration, or the algorithm terminates with a miss.

The actual code behind the algorithm is quite small:

public function AngularCast( B:Polygon, velA:Vector2, velB:Vector2, avA:Number, avB:Number ):LinearCastResult { const A:Polygon = this; const origin:Vector2 = new Vector2( ); var t:Number = 0; // relative linear velocity const ray:Vector2 = velB.Sub( velA ); var mA:Matrix23 = new Matrix23( A.m_Pos.Add( velA.MulScalar( t ) ), A.m_angle+avA*t ); var mB:Matrix23 = new Matrix23( B.m_Pos.Add( velB.MulScalar( t ) ), B.m_angle+avB*t ); var contact:Contact = GetDistance( B, mA, mB, parent, screenCentre ); while ( contact.m_dist>kAngularTollerance ) { // intersect velocity against normal const rayN:Number = ray.Dot( contact.m_normal ); const dRel:Number = rayN + A.m_r*Math.abs(avA) + B.m_r*Math.abs(avB); // compute conservative advancement t += contact.m_dist/dRel; if ( t<0 || t>1 ) { // never hit return new LinearCastResult( false, t, new Vector2( ) ); } // interpolate mA = new Matrix23( A.m_Pos.Add( velA.MulScalar( t ) ), A.m_angle+avA*t ); mB = new Matrix23( B.m_Pos.Add( velB.MulScalar( t ) ), B.m_angle+avB*t ); // get distance again contact = GetDistance( B, mA, mB, parent, screenCentre ); } return new LinearCastResult( true, t, contact.m_normal ); } |

As you play around with the demo, you'll notice it sometimes takes this algorithm a while to converge - in production code you would most likely limit the number of allowed iterations. Something like having it terminate if its not making 'enough' progress in each iteration might be a good idea.

## Conclusion

In this article, we have explored the various forms of collision detection and the algorithms behind them, from the simplest possible case of discrete circle vs circle to the complex case of continuous translating/rotating polygons. I hope this article has been intelligible and will inspire people to start diving in and exploring these techniques in more detail.

## Source code

As always, you can buy the source-code accompanying this article if you wish - it is written in Actionscript 3.0 but the techniques are applicable to all OO languages. All purchases are very much appreciated and ensure that I can afford to make more like this one 🙂

You get code for every single demo on this page, containing useful functions for computing the distance between arbitrary convex polygons, penetrating or not, and for computing the exact time of contact between rotating/translating polygons and best of all, the licence allows you to use this code for commercial and non-commercial applications alike 🙂

USD 5.99

Subscribers can access the source here

Until next time, have fun!

Cheers, Paul.

JonJanuary 1, 2014 at 4:25 amHi Paul,

A happy new year to you.

Thank you as ever for a very interesting and inspiring read; I used some of your ideas (along with many others) to write an (almost) complete 2d physics engine ..it’s taken a long time!

I have just revisted some of my code which is based on some of the ideas in this article, because I found a problem, and I believe that I can present to you a (rare) edge case where the supported vertices approach detailed here can fail to resolve the correct penetration distance.

I have a slightly tilted falling box whose motion bounds eventually intersect the bounds of a static triangle; the lower box edge is wrongly selected as the edge feature. Because i’m using motion bounds, one of the box corners is slightly higher than the top point of the triangle, and just misses it in x- (the top point of the triangle is a supporting vertex because it obviously most opposes the bottom edge). the projected point is clamped to the lower edge as normal- and it’s distance is certainly the smallest- but it is large enough combined with the velocity in my speculative-contact-impulse calulation to determine that a corrective impulse is to be applied, even though the polys completely miss each other! this code has been given *a lot* of testing, and appears to be the only outstanding problem.

Im aware that even though i’ve had a go, it’s very difficult to explain this in words. I can send you small images of the complete setup if you wish.

I wondered if perhaps you had time to pass your eye over this problem with me, out of interest sake? I like this appoach, it has elegance- and I really don’t want to revert to something like SAT unless i can help it..

cheers,

Jon

Jon SlaterJanuary 1, 2014 at 4:04 pmHi Paul,

I’ve been debugging this thing- and realised i missed a wrong negative sign, which fixes my issue.

thanks again for an excellent article.

cheers,

Jon

Paul FirthJanuary 4, 2014 at 12:44 pmHi Jon,

Glad you got your problem sorted, all the best with it!

Cheers, Paul.

MyriamMarch 31, 2014 at 9:43 amHi Paul

I am currently developing a haptic stage, I import models in 3DS, I have a problem of collision detection between objets.j I need help.

thank you

SeptimraApril 5, 2014 at 12:10 amHey Paul!

Got a quick question, its about the angular velocities. I am trying to understand how the rotational information gets tacked onto linear velocity information. I’ve been examining it for a while, and have made little to know break-through’s 😛

Paul FirthApril 7, 2014 at 9:15 amHi there,

I recommend taking a look at this article by Chris Hecker which explains it quite well: http://chrishecker.com/images/c/c2/Gdmphys2.pdf

Cheers, Paul.

EuropeanArtistJune 7, 2014 at 3:50 pmPaul, I’m stomped!

I’m an artist, bad at math, but using VB.NET 2010, I’ve been able to figure out collision detection, but I can’t figure how to bounce images away in an angle from each other. I’m creating a 2d game for my kids that incorporates parodied TV commercials I’m creating myself. Would really appreciate your help with below. My coding is kinda sad. 🙂

Dim ax As Single = 0

Dim ay As Single = 0

Dim speedx As Single = 0

Dim speedY As Single = 0

Dim minusx As Single = 0

Dim minusY As Single = 0

Dim Friction As Single = 0.98

Dim Uloc_x As Single

Dim Uloc_y As Single

Dim p1 As Point

Dim p2 As Point

Dim px As Integer

Dim py As Integer

Dim collision As Integer

Dim ppx As Single

Dim ppy As Single

Dim calc As Single

Dim radius As Integer = 60

Private Sub gameloop_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles gameloop.Tick

p1 = New Point(CInt(Uloc_x), CInt(Uloc_y))

p2 = New Point(CInt(606), CInt(263))

speedY += ay

speedx += ax

minusY -= ay

minusx -= ax

speedY *= Friction

speedx *= Friction

minusY *= Friction

minusx *= Friction

Uloc_x += speedx

Uloc_y += speedY

px = p1.X - p2.X

py = p1.Y - p2.Y

collision = CInt(radius * radius > px * px + py * py)

If collision < 0 Then

'Works if an object aproaches another at exactly the right location. It's off a bit if the approaching object is a little high or low, but still bounces away

If p2.X < Uloc_x + 60 Then

calc = Uloc_x + 60

ppx = calc - p2.X

Uloc_x = Uloc_x - ppx

speedx *= -1

End If

'the following code should bounce the object in the opposite direction, but instead transports the object to the opposite side of a stationary object. Also had this problem trying to figure out Y coordinates which is not shown below:

If (p2.X + 60) < Uloc_x Then

speedx *= -1

calc = p2.X + 60

ppx = calc - Uloc_x

Uloc_x = Uloc_x + ppx

End If

Label1.Text = "Hit!"

Else

Label1.Text = ""

End If

`End Sub`

Presently my objects can bounce off walls and rotate in angles, but bouncing off each other has me stomped! Couldn’t figure how to translate your math into anything workable in VB.NET since I’m a novice.

Paul FirthJune 8, 2014 at 1:19 pmTake a look at the article I wrote on physics engines, it should give you some pointers – but note that a full simulation with rotating inter-object collisions is no easy task for the beginner and out of the scope of a reply on here 🙂

http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/

Valentin PrulièreOctober 4, 2014 at 6:26 pmHello Paul.

I am building a game engine and this article has helped me tremendously, so thank you very much for that.

Quick question, when doing the minkowski difference between two convex polygons A and B in order to get the “true minkowski shape”, I get the feeling that A should always be the polygon with the most edges.

I have not found a case where this does not apply and was wondering if you knew wether this theory was true or false.

Thanks!

Paul FirthOctober 5, 2014 at 11:39 amHi Valentin,

There is no requirement for either A or B to have the most number of edges – that’s just how the demos turned out 🙂

Cheers, Paul.

Don VisznekiOctober 17, 2014 at 8:13 amThis article is quite old, but thought I’d leave this note here for others like me who are still reading.

With regards to calculating AABB, OP sez:

>To build an AABB from a complex object, just loop through all the vertices keeping a track of the minimum and maximum coordinate in each axis.

If your vertices change orientation relative to the axes your bounding box is aligned to (your polygon rotates) then you must recalculate your AABB! This can be expensive with a lot of points, but there is an easy way to cut down on the cost, though by how much depends on your polygon. Convex polygons will not be helped, but neither are they really hindered. The exact details of the technique are not the most efficient, but as they occur ahead-of-time, at some stage when you can preprocess your game’s assets, you’ll find it quite fast enough!

I’ve read the term “convex hull” used, and that may be what this is.

Any vertex which lies on any line which does not bisect your polygon is a vertex in a convex polygon which entirely contains your polygon. Also, any line which intersects fewer than two vertices in your polygon will not entirely contain any of this convex polygon’s sides. The technique that follows is not the most efficient but it works:

For each unique pair of vertices in your polygon, find the line they have in common, and compare all other vertices against this line.

If the line bisects this collection of vertices, discard the line, and move onto the next unique vertex pairing.

If you find one side of your line is absent any vertices, flag both vertices in your unique vertex pair as being in the convex polygon we seek (such a flag does not exempt these vertices from being reused in subsequent unique vertex pairs, nor does it exempt them from the line test!)

Also, if all vertices lie *on* your line, you’ve got a degenerate polygon, and you should take a long, hard look at your art team.

Finally, write out the set of flagged vertices somehow. Your game engine should load them when loading the polygon they were derived from. When calculating your AABB, you could save many calculations by only working with this set of vertices.

This same approach, incidentally, is easily translated into 3D (using planes instead of lines, and unique vertex triples instead of unique vertex pairs,) and may be useful in any other algorithm which seeks to find any convex bounding volume of any polygon or 3D mesh, since it allows you to effectively ignore any vertices which are entirely contained in any volume which bounds your input.

Hope someone finds this useful!

davideFebruary 9, 2015 at 9:34 pmHi, I really liked your explanation. To better understand and use this algorythm for my utility I made the donation, you deserve it!

Unfortunally I don’t know Actionscript, but I know some java, and I know it is similar.

Since I was interested in the first poly example, do I need to use (transform to java) all of the files I find into “poly” directory, or only a part?

You can also answer privately, if you prefer, i think you can see my email address.

if not, just tell, but please give me an hint on what to do.

Thanks! davide.

Paul FirthFebruary 9, 2015 at 9:48 pmHi Davide,

The main bulk of the functionality is in Polygon.as, which depends mainly on Vector2.as. Should be easy enough to convert to java. 🙂

Cheers, Paul.

unknownFebruary 23, 2015 at 2:21 pmHello Paul,

I really like your article, the algorithms are well explained and the demos really help.

I have several questions concerning the Minkowski Difference of convex shapes (I do not really understand the code, or at least I could not make it work).

So,

1. How do we compute the vertices’ normals (used with “wsN”) ?

2. Does dist>0 (so by extent facedist>0) mean that there is no collision?

3. How can we resolve the collision so that the two bodies stop colliding? (collision response)

4. What does your version of ProjectPointOntoEdge take as argument?

5. What “gets” out of GetWorldSpacePoint and GetWorldSpaceNormal? The translated/rotated vertex and normal? or the mesh’s vertex and normal?

Thank you a lot for your help!

unknownFebruary 23, 2015 at 2:47 pmAnother question,

what do you mean by “face of A, vertices of B”?

I found out the answer to ProjectPointOntoEdge , it was on your angry birds tutorial.

For computing the normals of a vector, is it “normalize(perp(vector))”? (considering there is no rotation)

Thank you!

Paul FirthFebruary 23, 2015 at 5:35 pmFeature pairs are always pair of features, one from each object made by subtracting vertices of A from faces of B and visa versa.

You are correct about normalised face computation.

Paul FirthFebruary 23, 2015 at 5:32 pmHi there,

1) Vertices don’t have normals, the normals always come from the faces of each object.

2) dist > 0 means there is a separating axis

3) push them apart by the min(dist) along the collision normal

4) a point and an edge

5) correct.

Cheers, Paul.

unknownFebruary 28, 2015 at 11:33 amHi again. Thank you for your reply.

How do we compute the collision normal?

Paul FirthFebruary 28, 2015 at 12:25 pmThat’s kind of the whole point of the technique – to compute the collision normal and the penetration distance.

unknownFebruary 28, 2015 at 1:13 pmYeah, but the collision normal is the contact point or the normalization of the contact point?

Dave WhittingtonMay 25, 2015 at 7:13 pmPaul,

This might be pretty basic to you but here goes. I am using a flight simulation called FSX by Microsoft. It uses an internal format called BGL for its 3D objects. It also now uses a GPU shader language (C++ looking) to generate many special effects like fireworks and moving waves. I want to use shader code to simply detect my eyepoint distance (from a consumer level RC helicopter model) from moderately complex objects – like a bridge with openings underneath – without having to generate bounding boxes and such for the model. Can’t I simply read the depth buffer to find the least distance away? I don’t want to collide and figure out the reaction – just to get a warning for distance less than a foot or so. Here is some example shader code that provides a simulated radar image image but I don’t know if that could help me.

#define DISABLE_PROJECTION 0

struct VS_INPUT

{

float4 position : POSITION;

float2 uv : TEXCOORD;

uint instance : SV_InstanceID;

};

VS_OUTPUT VS( VS_INPUT In )

{

VS_OUTPUT Out;

const float2 pixelSize = 1.0f / float2( (float)DataDrawInstanceColumns, (float)DataDrawInstanceRows );

const uint2 instanceXY = uint2( In.instance / DataDrawInstanceRows, In.instance % DataDrawInstanceRows );

const float2 lerp = pixelSize * instanceXY;

const float2 uv = lerp + In.uv * pixelSize;

const float quadScale = DataDrawInstanceRows/SubDataDimensions.y;

const int depthIndexV = quadScale*instanceXY.y;

const int depthIndexU = ( ViewDimensions.x – 1 ) / DataDrawInstanceColumns * instanceXY.x;

float depth = txDepth.Load( int3( depthIndexU, depthIndexV, 0 )).x;

const float depth1 = txDepth.Load( int3( depthIndexU, depthIndexV+quadScale, 0 )).x;

const float depth2 = txDepth.Load( int3( depthIndexU, ( depthIndexV + 2 * quadScale ), 0 )).x;

const float delta01 = saturate( – depth1 + depth );

const float delta12 = saturate( – depth2 + depth1 );

const float offset = min( delta01, delta12 );

depth -= In.uv.y * offset;

const float viewSpaceZ = ( ViewQ * ViewNear / ( ViewQ – depth )); // for use with normal depth

const float viewSpaceY = viewSpaceZ * abs( 2 * lerp.y – 1 ) / ViewYScale;

const float viewSpaceX = viewSpaceZ * abs( 2 * lerp.x – 1 ) / ViewXScale;

const float dist = length( float3( viewSpaceX, viewSpaceY, viewSpaceZ ));

const float dataRangeY = 2 * ( dist – SubDataMinRange ) / ( SubDataMaxRange – SubDataMinRange ) – 1;

Out.position.x = ( 2 * uv.x ) – 1;

Out.position.y = dataRangeY – ( .5 * pixelSize.x * In.uv.y );

Out.position.zw = In.position.zw;

Out.uv = uv;

#if DISABLE_PROJECTION

Out.uv = In.uv;

Out.position = In.position;

#endif

return Out;

}

Scott BlackJanuary 6, 2016 at 5:39 pmThe angular cast method you described at the bottom of the article will work with with Poly/Circle collisions too, right?

Paul FirthJanuary 6, 2016 at 6:21 pmAs long as the polygons are convex, yes.

Scott BlackJanuary 6, 2016 at 10:30 pmConvex Polys. Is there anything they can’t do?

Thanks, Paul.

Scott BlackJanuary 8, 2016 at 8:56 pmI think it would be helpful to note which way the edge normals are facing(inwardly or outward) for the polygons. That wasn’t clear to me when I went through this. I’m not even sure if there is a standard way.

Scott BlackJanuary 10, 2016 at 1:10 amI got mixed up because the coordinate system I’m using had Y+ pointing down.