# EPA (Expanding Polytope Algorithm)

In the last few posts we learned about using GJK for collision detection, distance between shapes, and finding the closest points. It was stated that GJK must be augmented, to find collision information like the penetration depth and vector, with another algorithm. One such algorithm is EPA.

I plan to cover the EPA algorithm and mention an alternative.

Like GJK, EPA uses the same concept of a Minkowski Sum, performing the difference operation instead of addition. Like the previous posts I will refer to this as the Minkowski Difference.

In the first GJK post we talked about how to determine if two convex shapes were intersecting; true or false. What we want to do now is after we determine that there is a collision, find the collision information: depth and vector.

Overview
In the GJK post we stated that we know the convex shapes are intersecting if the Minkowski Difference contains the origin. In addition to this, the distance from closest point on the Minkowski Difference to the origin is the penetration depth. Likewise, the vector from the closest point to the origin is the penetration vector.

Like GJK, EPA is an iterative algorithm. EPA stands for Expanding Polytope Algorithm and means just that. We want to create a polytope (or polygon) inside of the Minkowski Difference and iteratively expand it until we hit the edge of the Minkowski Difference. The key is to expand the closest feature to the origin of the polytope. If we perform this iteratively we will generate a polytope where the closest feature lies on the Minkowski Difference, thereby yeilding the penetration depth and vector.

EPA performs this task by using the same support function used in the other algorithms and the same notion of a simplex. One difference from GJK is that EPA’s simplex can have any number of points.

Starting Point
EPA needs an initial simplex to expand. The terminiation simplex from the GJK collision detection routine is a great start.

EPA needs a full simplex: Triangle for 2D and Tetrahedron for 3D. The GJK collision detection routine can be modified such that it always terminiates with the above cases. The GJK post will never terminiate, returning that the shapes are intersecting, until a triangle has been created.

Expansion
If we pass the termination simplex to EPA we can immediately start the expansion process:

Where the findClosestEdge looks something like:

Example

As always, I think its much easier to understand once you go through an example. We will use the example from the GJK post and determine the collision information using EPA.

We start by supplying the GJK termination simplex to EPA:

Iteration 1

Notice that we have expanded the simplex by adding another point. Its important to point out that the point we added is on the edge of the Minkowski Difference. Because all points that make up the simplex lie on the edge Minkowski Difference we can guarentee that the simplex is convex since the Minkowski Difference is convex. If the simplex was not convex then we wouldn’t be able to skip so many computations.

Another key that should be pointed out is how we add the new point to the simplex. We must add the new point in between the two points that create the closest edge. This way the shape stays convex. In this example the winding of the points doesn’t matter, however it is important to notice that insert the new point as we have done preserves the current winding direction. More on the simplex’s winding direction later…

Iteration 2

In the second iteration we see that the closest edge of the simplex actually lies on the Minkowski Difference. We can see by inspection that Edge 4’s normal is the collision normal and that the perpendicular distance from the edge to the origin is the penetration depth. This is confirmed in the last iteration.

We terminated on the second iteration because the distance to the new simplex point was not more than the distance to the closest edge indicating that we cannot expand our simplex any futher. If higher precision numbers were used we would see that the value of the dist variable would be much closer to zero which makes sense since the new support point lies on the closest edge.

We still need to have a tolerance because of curved shapes and finite precision math. For a curved Minkowski Difference, the simplex will build smaller and smaller edges to conform to the curvature. You can see this in figure 5, however it may be many more edges because of the increase precision.

Winding and Triple Product

Earlier I mentioned something about the winding of the simplex being preserved. This is important to handle a special case of collisions.

Small or touching collisions can cause EPA problems which stem from the use of the triple product. If the origin lies really close to the closest edge the triple product may return a zero vector (because of finite precision). When we go to normalize the vector we will divide by zero: not good.

If we look at the reason we are using the triple product we come up with another method to fix this problem. The triple product is used to get the normal vector of an edge in the opposite direction of the origin. We can do the same thing by using the per-product of the edge.

The per-product is defined as:

In this instance the left or right handedness actually is determined by the winding of the simplex. If the winding of the simplex is counter-clockwise then we want to use the right per-product. Likewise if the simplex winding is clockwise then we want to use the left per-product. We can assume this because we have already guarenteed that the origin is contained in the simplex.

So instead of using the triple product we can use the per-product to get the normal of the edge no matter how close the origin is to the closest edge. The new code looks something like this:

It was important to note that the winding of the simplex is preserved because this means we can determine the winding of the simplex once making the new code more efficient and robust.

Augmenting
EPA is often not used for small penetrations because of the computational cost. Therefore you may see EPA supplemented with GJK penetration detection algorithm. To use GJK for collision information involves using smaller versions of the colliding shapes (called core shapes) and performing a GJK distance check. Once the distance between the core shapes is found, subtract it from the sum of the radial shinkage applied to the shapes.

Alternatives

There are alternatives to using EPA to determine collision information after GJK has detected a collision. I’m only going to mention one here: sampling for the smallest penetration.

Generate a sample of directions. Find the distance from the origin to the surface of the Minkowski Difference (like we do in EPA) along each direction. Use the one with the smallest distance.

This is obviously an estimation instead of an exact answer, however it can be improved by intelligent selection of the directions.

• Evenly distribute the directions along the unit circle/sphere
• Use more directions
• Use the edge normals of each shape
• Use the vector from center to center of the shapes
• etc.

For low vertex count polygons this may seem like more work, but for high vertex count polyhedrons it can be faster than EPA and still yield an acceptable result.

The above EPA implementation adds 22+ operations every time a new simplex point is added. This is significant when the Minkowski Difference has many vertices or has curved edges.

## 48 thoughts on “EPA (Expanding Polytope Algorithm)”

• mikwolf says:

normal = edge.normal;
or normal = e.normal?

• William says:

Thanks again for finding that mistake. I fixed it within the post.

William

• mrful says:

Hi!

I really like your walkthrough of the EPA algorithm! But I have a question.
You talk a lot about the winding of the simplex, and I do understand how that would work in 2D, How would you do in 3d, as I am about to implement this in to my 3d game engine that already got GJK working nicely, it would be very practical if I knew this.

Greetings from Sweden!
Mr.Ful

• William says:

Very good question. It’s possible that you may obtain the zero vector in 3D also. I have not implemented the algorithm in 3D. However, EPA should be basically the same, instead of using edge normals, you use face normals. A face (which can be thought of as a plane) has two possible normals, one pointing outside of the shape, and one pointing inside. Getting one or the other depends on the winding of the face vertices.

You can attempt to solve the problem by forcing all faces to have the same winding (counter-clockwise to obtain the face normal pointing outside the shape) or you can save the normals with the shape itself with some reference to what face it is for.

If I were you, I would implement EPA without worrying about the zero vector problem. This only crops up when shapes are touching. Once you get it working for the majority of the cases then you can try to fix the outliers.

Another way to solve the problem is avoid using EPA for the “small penetration” cases. This is briefly explained in the Augmenting section of the post (see figure 6). This approach is probably much faster and more stable for 3D.

William

• weijin says:

I don’t understand how to get contact point from GJK and EPA.
Could you please give me some instructions

Thanks

• William says:

Good question, and the distinction is good to note here. The post only covered how to obtain the contact normal and depth, not the contact points. In fact, finding the contact points from the contact normal and depth is a entirely different subject in itself. I do not have a post on this yet.

The dyn4j project uses a modified clipping method (handling circle shapes is the only difference really) that is used in box2d to obtain the contact points from the contact normal and depth.

If you choose to go the “Core Shapes” route then you may be able to get this information by using the GJK distance algorithm. The GJK distance algorithm can be used on the “Core Shapes” to obtain the closest points and separation vector (see the GJK – Distance & Closest Points post). Then you can translate these points along the separation vector depth distance to obtain a collision point on each shape (you probably should only use one of them). I haven’t thought it through completely, but this may or may not be accurate. I want to say that bullet is doing this for shallow penetration, but I don’t remember. There are more details here, but this is probably enough to get you going for now.

• Hello says:

Hello,
First of all I want to say your guides are really good!

I know that they asked this already, but I can found the contact points of the collision if I project the vertex which I got from the distance algorithem onto the edge of the second shanpe?

If i have spelling mistakes, it’s because English isn’t my regular language :P
thank you!

• William says:

No problem. If you use core shapes, ie the shapes used to detect collision are smaller than the real shapes, then you can use the closest points from the GJK distance method. I haven’t researched the method enough to know for sure how to obtain the collision points from the closest points, but check out this PDF pages 40-44 it talks about using a collision margin and the GJK distance method to find the penetration depth and contacts.

In addition, Bullet uses something called contact caching to get enough points for stable stacking as well. As you can see in the PDF the distance method will typically give you just one contact point. So Bullet stores the contact point, waits until the next iteration of the engine to get another point, and so on until it has enough points to solve the collision. As new points are added, a reduction algorithm is used to only keep the points that are “best,” which is usually the deepest penetration points, or the points whose area is the largest, etc.

In Box2d and dyn4j, the contacts for each collision are found in one step instead of caching until enough points are available. This is done by a feature clipping method that really requires its own post to explain well.

William

• Pingback: GJK: Fast Convex Hull Collision Detection in 2D and 3D | FuriousBlog
• Tylor says:

I am also curious about how to detect winding of a simplex.

• William says:

The winding of the simplex can be found just like you would find the winding of any polygon. See this for more details.

As a performance enhancement, you only really need to know the value of the first non-zero cross product to determine the winding. In addition, since EPA retains the winding of the simplex throughout the algorithm, you only need to calculate the winding when the algorithm starts.

William

• Quentin says:

Hi and first of all thank you four your guides ! It is really the best I found on the subject (GJK & EPA).

I have yet a little problem:
I have a particular case where the origine belongs to the edge formed by the two first point of my simplex (in GJK). In this case the algorithm find that the shape are not colliding even if they are…
I tried to fix this by returning a colision if the origin belongs to an edge of the simplex but then I have a problem in the EPA who seems unable to find the closest edge (infinite loop).

English is not my first language so I’m not sure if I ‘m clear enough.

Here is my example :

Shape 1 points: (2,2),(2,5),(4,5),(4,2)
Shape 2 points: (3,3),(5,4),(5,2)
First d : center shape 1 – center shape 2
First edge in my simplex formed by :(-3,3), (1,-1)
epsilon chosen: 0.01

• Quentin says:

Little precision: When I fix this in GJK the output simplex only have 2 points and when I look for the closest edge the on I find has a e.distance =0 . So I never enter the if(d – e.distance < epsilon)…

• William says:

Yeah these are some of the cases where GJK and EPA can get tricky. First let me say that the EPA guide here requires that the final simplex from GJK is a triangle (for 2D) to work correctly.

There are two sub cases for the case in which the origin is on an edge of the simplex:
1. The edge of the simplex (which the origin lies on) is an edge of the Minkowski Sum
2. The edge of the simplex (which the origin lies on) lies inside of the Minkowski Sum

In the first case, this indicates touching contact between the two shapes.
The second case is a bit of a problem in 3D for the line segment case.

Thankfully in 2D we have an easy way out for both of these cases. If the origin lies on an edge of the simplex we can just use either perpendicular vector of that edge as the next search direction (the modified line segment case of GJK.containsOrigin):

William

• Quentin says:

Thank you so much for this fast and accurate answer William !

I’m in 2D(second case) and it works perfectly !

Just a little thing: in your correction I believe it is ab.left and not abPerp.left as abPerp is “null”.

Thanks a lot !

Quentin

• William says:

Awesome! Yeah, I meant to put ab.left() instead of abPerp. I fixed it in the previous comment of mine. Thanks for pointing that out!

William

• honestann says:

After a collision, why not separate objects by moving them back along their velocity vectors? This should get the objects back to their actual positions at the TOI (time of impact), which is clearly more precise.

• William says:

Sure, but how do you know how much to move them without first knowing how much they are penetrating? In addition, what happens when two bodies at rest (both have zero velocity) and are overlapping?

Can you elaborate a little more on what you are describing?

William

• Harry says:

If Polygon A = [(0, 0), (0, 4), (4, 4), (4, 0)]
and Polygon B = [(2, 3), (2, 7), (6, 7), (6, 3)]
then EPA will give a penetration depth of 1 and a vector of (0, 1)
but if A’s velocity was (2, 0) and B’s velocity was (-2, 0), the polygons’ ys shouldn’t change at all, so how is the info from EPA supposed to help?

• William Bittle says:

@Harry

Right, that wouldn’t be the correct normal even though that’s what EPA would find. This is because the objective of the algorithm. The algorithm’s objective is NOT to find the penetration normal of two moving convex shapes, but rather to find the minimum penetration normal of the two shapes. Clearly, these don’t mean the same thing and its obvious from your example.

Note that the SAT algorithm will suffer from this as well since its objective is the same. In addition, if you’ve ever heard of the “internal edge” problem, this is the cause.

Now with that said, you wouldn’t typically create your shapes overlapping in that manner and hopefully your simulation would run fast enough that a penetration of that sort wouldn’t happen.

William

• Harry says:

Do you know of any algorithms that get the penetration normal for moving shapes?

• ng says:

when you calculate the distance from origin to the edge shouldn’t a or normal( n ) be in opposite direction?

• William says:

@ng

Can you point to the place in the post where you think it should be in the opposite direction? More specifically, which iteration and which edge calculation?

I am making some assumptions that may not be apparent that may answer your question:
1. I’m using a right handed coordinate system
2. When computing the vector from A to B, you subtract the vectors in reverse order: A to B becomes B – A.

William

• Roy says:

Hi William,

I think he referred to the calculation of n in findClosestEdge(), using the triple product abxoaxab.
correct me if I’m wrong, but I think you get a reversed n pointing away from the origin.
You can see it in line 10 of iteration 1, n=(-32, 96), would point away.
perhaps you should have used ao instead of oa.

Roy

• Roy says:

nvm, got it.
as @alleysark said, it’s only the comment which is wrong. Should have been “get the vector from the edge away from the origin”

• alleysark says:

Hello, and thank you for this awesome article!!
Well, I had a same question with @ng, but I’ve understood it when I write my question :D
Could you please modify your comment at line 15 of findClosestEdge (“get the vector from the edge towards the origin”). I think it got me and @ng mixed up.
Thanks a lot!!

• Asylum says:

Hi!

I have a little problem with the 3D EPA algorithm. Considering a box-box collision, there are cases when the algorithm doesn’t terminate ever: the polytope is just getting bigger with redundant vertices.

Is there any way to detect this? (besides limiting the number of iterations/vertices)

• William says:

@Asylum

EPA should complete in a finite number of iterations for polytopes, although it could run forever on curved solids. Have you been able to get a reproducible test case that you can debug through? Have you looked through my 2D implementation here?

William

• Asylum says:

Hi!

Yes, I’m debugging it at the moment. The test case is two 1×1 boxes sitting exactly on eachother.

Initial simplex is:
0: (0, 0, 0)
1: (0, 1, 1)
2: (-1, 1, 0)
3: (-1, 0, 1)

The algorithm finds the first face to be the best (0, 1, 2). Normal vector is (-1, -1, 1), therefore the support vertex obtained in this direction will be vertex 4 -> redundancy.

I added a condition, so in the next iteration the algorithm will detect the infinite loop (it didn’t get closer to the origin), however the terminating triangle is not on the surface of the CSO -> contact normal will be bad.

I take a look at your code.

• Student says:

Hi!
I am a little confused:
1. EPA starts with a edge of Minkowski Difference(MD) so why simplex from GJK is needed?
2. In this example, the simplex is composed by two edges of MD so EPA tries to reach another edge of MD?

Btw, your tutorials are awesome! Thanks!

• William says:

@Student

1. EPA doesn’t have to start with the simplex from GJK. It could build its own, but to save time you might as well just use the one from GJK. If implemented appropriately, GJK in 2D will always end with a triangle simplex.

2. The example here isn’t the best, since the closest edge is already part of the simplex. Generally, this may not be the case. As a result, EPA expands the simplex until it finds the edge closest to the origin.

William

• Evan says:

Im doing epa in 3d and this is my code:

When I get to the part where Im crossing direction I dont understand what I should be doing because i dont know what your triple product was. Can this code even work?

• William says:

@Evan

The difference for 3d is that you expand the simplex until you obtain the face, rather than an edge, that is closest to the origin.

For each face in the simplex, we need to compute the face normal. Doing so allows us to compute the distance to the origin via the dot product.

For example, if A, B and C define the vertices of a 3d triangle, we can get a normal by taking the cross product of any two edges: N = AB X AC. Note that there are two normals here one that will point inward and one that will point outward. Using the dot product we can get the distance to the origin.

The triple product in the code here is a way to get the normal of the edge that points in the direction of the origin without doing a dot product with AO. To keep things simple, I’d stick with the dot product for now.

Loop over all faces and obtain the closest one. Once the closest is found, get a new support point in that direction. If its no closer than the face, then you are done. If it is closer, then you must split that face into 3 faces using the new support point.

William

• Harry says:

Since Vector a in findClosestEdge will change each loop, how does comparing Vector n with it (with the dot product) give an accurate comparison?

• William Bittle says:

@Harry

I’m not comparing n with a, I’m comparing d with closest.distance. This compares the distance of current edge with the distance of the closest edge I’ve found so far.

The dot product is a projection of the vector a onto the vector n. This gives us the perpendicular distance from the edge to the origin, which will be different for every edge.

William

• Olai Solheim says:

Thanks for the great articles, they’ve really helped.

I did some testing because I wanted to find the contact points after the EPA had terminated, and I found that by using the exact same technique using the Convex Collection and lambda expressions as in your GJK distance algorithm, I could use the final edge endpoints in Minkowski Space to find the two contact points in real space.

You mention you have to expand on EPA or use another algorithm to find these, som I just thought I’d share the expansion.

• William Bittle says:

@Olai

I’d love to see a in depth description of how you’ve expanded it to find the contact points. A link to a blog post about it would be great.

William

• shome says:

The EPA algorithm takes the terminating polygon from GJK algorithm to initialize itself. Does the EPA give correct distance for non intersecting convex hulls?

• William Bittle says:

@shome

No. EPA is only for the collision case. Take a look at the GJK – Distance & Closest Points post for the separation case.

Some collision detection engines drop EPA and instead use smaller “core” shapes (imagine a shrunken version of the shape) and then do the GJK distance method to handle both separation and penetration.

William

• Damien says:

Hi,
Thank you for your description of the EPA. In the end you say that due to its computational cost, the EPA is sometimes not used and the GJK distance algorithm runs with smaller homotheties of the shapes. I wonder what you call ‘small’ penetration depths, and how slower it is to use the EPA over GJK to compute contact points.
My current code does the second option (performing GJK on smaller solids), and is based on the Gino Van den Bergen implementation of GJK.
Thanks a lot
Damien

• William says:

@damien

GJK can detect collision regardless of depth. The issue is that the depth can be wrong when the penetration is large. On the flip side EPA continues to collect vertices that must be iterated on each iteration. This is especially true when the minkowski sun has curved edges.

As for a comparison, I’m not sure. In my experience EPA performance is acceptable, but I’m only speaking for 2D. If your set of shapes doesn’t include curved shapes, then I’d expect EPA to be very close to GJK.

• Atia says:

Hi William
Special Thanks for this useful tutorial, now am very clear.

my question is that for penetration depth between a single point and a convex object which algorithm is better?EPA or GJK distance or something else?

and penetration depth is not too much deep or even not very small (touching) something in the middle

I look forward to hearing back from you

Thanks Atia

• Atia says:

Also,
for implementing EPA in 3D, since first we have 4 points coming from GJK
sgould we check all four faces?or only three is enough?

This site uses Akismet to reduce spam. Learn how your comment data is processed.