Until now I have been using Newton for doing physics and collision detection with Quake 3 and Half-Life level geometry. This works great for normal solid geometry, but now I'm implementing non-solid collision (water, slime, lava, etc.) and I would like to do my own collision detection and response. I could probably find a way to do this using Newton, but I'm mainly in it for the learning experience. So, can anyone point me in the right direction (tutorial, code, etc.) on how to do ellipsoid->convex hull collision detection and sliding? I've managed to correctly do ray->convex hull collision (easy). Adapting the ellipsoid collision tutorial to hulls gives terrible results (either really slow and buggy, or really buggy and slow, depending on the method I use). At least the level renders!

Quote:Adapting the ellipsoid collision tutorial to hulls gives terrible results...

To which tutorial are you referring? And what sort of bugs/problems are you running into?

@jyk:
He probably means Paul Nette's Generic Collision Detection for Games Using Ellipsoids

@jikbar:

If so, well, the PDF on the link claims to be an updated version, when I first read it, there were 2 big flaws in it.

1 - It is for collision detection between triangles and sweeping spheres/ellipsoids, leading the reader (me at the time), that you could use it for concave shapes... BAD IDEA. you're asking for Convex Hulls, so you already know better than I did [smile].

2 - It didnt cover the case where the sphere touched the triangle indirectly (when the closest point from the triangle plane and the center of the sphere and the closest point between the triangle and the center of the sphere are not the same, in these cases the sphere might be colliding with one of the triangle edges or vertices), I would asume this one was one of the problems fixed on the latest version, I know it was a known flaw.

On to your question!

The way I finally did it (and I am quite happy with it) is to first find out if the ray from the initial position of the sphere to the final position was crossing one of the planes descrived by the faces of the convex hull.

You can discard faces by calculating the dot product of the trayectory ray and each of the faces' normal, if this is positive, your sphere is comming from behind the face, so no need to check against that face.

When you find that the ray crosses a face you need to find if the point on the plane of the face is inside the polygon, you can do this either with a point in triangle function against all the triangles in the polygon or by modifiying the point in triangle function so it takes more than 3 edges, if the point is inside the polygon, move the sphere to the collision point and slide it along the collision plane.

[ This was where Nette Tutorial breaks ]

If the point is NOT inside the polygon, you need to find on which Voronoi region of the polygon the point is, this will give you the closest feature (either an edge or a vertice), I made the point in polyhedron return the closest feature if the point is not in the polygon to save computations.

Once you have the closest feature find if the sphere collides against it (use closest point between rays for edges and closest point in line for vertices) by using the closest distance to it against the radius of the sphere.

If there is a collision, the use the normalized vector from the closest feature to the center of the sphere as the normal for the sliding plane, move the sphere to the collision position and slide.

To Slide, just project the vector constructed by substracting the point in the plane from the (original) final position of the sphere over the collision plane.

Hope I didnt bore you [smile]

Looking back on my post, it seems a bit unclear.

The problem i am having is trying to collide an ellipsoid with a convex hull composed of intersecting planes, like a frustum, where the area behind all the planes is what makes up the solid geometry. Thankfully, this makes it a lot simpler to do intersection tests because you don't have to mess around with edges and vertices. With a ray it's fairly simple since you only need to find the front-facing plane intersection with the highest time value, or the back one when the ray is inside the region.

Now that I think of it, using ellipsoids shouldn't be much more difficult. It's basically finding the time value of intersection of each plane with the ellipsoid, then clipping them like in the normal ray code. I'll try recoding the function and i'll post here if i run into any more problems. Things always seem to be clearer the 3rd time around :)

@Kwizatz: i'll remember your post when I do sphere->triangle collision, i'll definately read up more on indirect collisions later

Actually what you are trying to do and what I descrived is not that different, in fact I keep both the plane collection data and the face (verts and edges) data, think of it as levels of detail... first you test for bounding box intersection, then you go one level up to the plane (defined as normal+distance from the origin right?) intersection, and finally the highest level test for face intersection.

Anyway, post if you need more help [smile].