# Point vs Convex Hull

I'm trying to implement a simple collision response to a point intersecting a convex hull.

So far I can detect if the point is inside the hull.

But now I want a collision response that translates and rotates the hull away from the point so it no longer intersects.

I'd like the simplest algorithm possible, I don't want to implement a physics engine or rigid bodies.

Can someone point me in the right direction?

• Is the point stationary, or is it also moving? Are you doing this for many objects, or just two at a time? What physical properties do you have available, if you have no formal physics engine? Dec 8 '13 at 23:59

Since you can detect if the point is in your polygon, all you need to do find which face is the axis of minimum penetration. This tells you what direction to press your two objects apart. This direction is called the collision normal.

In order to know this you will be using the results of your plane tests. When you do collision testing against your polygon you can compute the distance of the point to each face plane. Keep track of the greatest signed value. If the greatest signed distance is negative then you know the point lies within the polygon. This greatest signed distance (which is still negative) comes from the plane which is the axis of minimum penetration. This distance is your penetration depth.

Once you have this axis you use the face normal of this plane as the direction of which to press these two objects apart. Exactly how you press them apart can be extremely simple or very complicated. Since you asked for something simple I'll recommend modifying position directly.

Take the position of your polygon and move it along the collision normal a distance equivalent to the penetration depth.

This resolution is called linear projection and it is very simple. You can also rotate your object accordingly, if you so wish. This gets more complicated. You can also apply an impulse to the velocity and integrate your velocity to move the position -this can result in a more stable and physically accurate resolve. If you want to know more about this try searching for "Impulse Resolution", I wrote some articles about this topic.

You can use the GJK distance algorithm as well as a simple iterative contact resolver.

Basically, given a position and rotation of the body expressed as functions of time t, you want to solve for a value of t that reduces the distance from the point to the edge of the convex hull to exactly zero, and integrate the body using that time value. It's possible to do this analytically, but for a game it's more efficient (and much easier) to do it numerically.

With the numerical method, you just incrementally change t until you get a distance value that lies within an acceptable threshold. The simplest way to do this is to switch the direction you change t and also reduce the magnitude of the delta whenever the point switches from interior or exterior, or vice versa. A more complex algorithm (that will also converge in fewer steps) will increment based on the arc length between the point and the body (this is what Bullet does in its CCD solver).

Note that this only makes sense when you know the linear and angular velocities of the body, or reduce the movement to either translation or rotation, not both. Otherwise, the problem is vastly underdetermined and will have a huge number of complex solutions.

• Will this rotate as well as translate the body? Have you got any links to resources where this has been implemented? Dec 9 '13 at 9:22
• This will translate and rotate the body, depending on the linear and angular velocities you pass into it (to vary the body's position and rotation by t). This is similar to the Bullet CCD solver, albeit Bullet uses it for collision detection a priori, while you want to use it for collision resolution a posteriori. Dec 9 '13 at 23:02
• Have you got any links to code that have implemented this I don't have time to research it and do my own implementation right now. Dec 10 '13 at 12:25
• Erwin Coumans (the Bullet developer) published a paper about the algorithm. gamedevs.org/uploads/… You can look into the Bullet source as well, especially this: bulletphysics.org/Bullet/BulletFull/… Dec 10 '13 at 20:02