Jump to content
  • Advertisement
Sign in to follow this  

separation axes between convex hull and sphere

This topic is 4555 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying some collision detection between basic primitives, and I'm trying to do it in some generic way. Right now, I know that the required separation axes needed to be tested between two convex hull are the edges of both convex hulls, plus the cross products of all of them. but, what about a sphere and a convex hull? which axes would be required to be tested? Right now, I was thinking in the edges of the convex hull plus: - the axis formed between the center of the sphere and the center of the convex hull (like a sphere-sphere test) - the axes formed between the center of the sphere and the vertices of the convex hull, ( plus their cross products? )

Share this post

Link to post
Share on other sites
I'm not sure that you can have a separating axis for a sphere. The only thing I can even think of to be a separating axis for a sphere is a line segment parallel to the separating axis of the convex hull, with a length of the sphere diameter.

For example, suppose your convex hull has an edge (call it A). The separating axis would be a line parallel to edge A. You compare two line segments:

1. The actual edge A.
2. A line segment whose center is at the sphere center, parallel to A (that's a given) and is as long as the diameter of the sphere (in effect, this imaginery edge WILL BE the sphere diameter).

You do this for each edge of the convex hull.

For the records - This is just an idea with no mathematical proof. Because sphere are symmetric in all directions it's possible that separating axis doesn't apply to them. One method that will surely work is to test the sphere's distance from each of the planes (in 2D they would be line segments naturally) making up the convex hull.

Share this post

Link to post
Share on other sites
I dont think that seperating axes will work with a sphere, because there are infinite posibilities.

My Intial idea for an alternative was to find the closest point (not necessarily vertex) in the polyhedra to the sphere, and test if that point is in the sphere.

The main problem is that if the sphere was completely contained within the polyhedra, then all the points are outside and the test fails - so at the same time you'd need to test whether the centre is inside each face (just check which side of the plane the point is on).

I had a look in the 'Real Time Collision Detection' (RTCD) book and it suggests a similar way.

The simplest (to implement - its O(n) to run) method to find the closest point (according to RTCD) is to find the closest point in every face to the centre, and return the closest. Its not very efficient tho.
RTCD mentions the 'Gilbert-Johnson-Keerthi' algorithm as a faster way of finding the closest point - i've only briefly scanned that section, so i cant help with that part sorry.

also from RTCD is a process for testing versus polygons (not polyhedra) :
1. Test if the sphere intersects the plane of the polygon. Exit with false if not.
2. Test each edge of the polygon to see if it pierces the sphere (point-to-line < radius).
3. Project sphere centre onto plane of polygon and do a point-in-polygon test.

So the extension to work with a polyhedra, as i see it, is to do that for each face, and take the closest point. But step 0 should be check whether the sphere is behind the polygon (dont work out intersection if it is - if its behind all, its inside the polyhedra)


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!