Sign in to follow this  
Helderash

Four Sided Polygon - Sphere Intersection

Recommended Posts

Hey folks! I'm currently working on a deformation project, and am now working on some collisions between rigid bodies and my deformable body. The deformable body is currently a cube, split into many smaller hexahedral elements, and the rigid body is a sphere. At each frame I'm needing to know whether the sphere is colliding (intersecting) with the outer surface of any of the smaller hexahedral elements. My collision detector currently detects when the sphere has passed within the bounding box of the deformable mesh, but from here I'm unsure how best to proceed... My thoughts have been to parse through every surface element (the four-sided polygons making up the surfaces of each hexahedral element), and determine whether the sphere intersects with each one... perhaps by determining the minimum distance between the centre of the sphere and a point on the polygon, and assertain a collision has occured if this distance is less than the radius of the sphere. I'm unsure how to determine the minimum distance between the centre of the sphere and the four-sided polygon however. I already know the co-ordinates of the sphere, and the four co-ordinates of the polygon corners. I've heard by calculating the polygon normal and doing a dot-product with the sphere co-ordinate vector you can determine the distance between the two, but does this take into account the finite size of the polygon? If anyone can help clear my confusion and set me on the right path I'd be very appreciative. Thanks in advance! James.

Share this post


Link to post
Share on other sites
Find the closest point on the tetrahedron to the sphere centre, and check for containment of that point in the sphere.

Finding the closest point, you can use a geometrical method like a simple voronoi region search, or more cleanly, a purely algebraic method (probably involves some matrices, plucker coordinates, and whatnot). The GJK algorithm uses something like that to work out collisions.

Share this post


Link to post
Share on other sites
Hi oliii,

Thankyou very much for the help, I'll certainly read through the GJK code. I have managed to get a temporary fix in place. I'm now testing each vertex of the deformable cube to check whether it is inside the sphere. This works providing I ensure the distance between vertices is significantly less than the sphere's diameter.

Share this post


Link to post
Share on other sites
I seem to remember looking at the code in GJK a long time ago (Gino's implementation). It not that straight forward, but not hard to leech the code. They use a weighted average of the four vertices to compute the point. I used that for some fun projects, but it's on a retired hard drive. maybe I have it somewhere in my 'attic'.

Share this post


Link to post
Share on other sites
Nope, nothing in the attic. however it's an interesting problem. A voronoi decomposition would be quite tedious, but feasable.

There are also a lot of performance issues if you want to do this quickly. If you do many spheres versus tetrahedrons, there is a lot of potential for caching useful information (a matrix mapping to convert the tetrahedron frame to and from a unit, orthogonal frame for example).

Share this post


Link to post
Share on other sites
simplest would be to find the distance to each triangle faces, then take the minimum. Check if point is inside the tetrahedron first.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this