Jump to content
  • Advertisement
Sign in to follow this  
Helderash

Four Sided Polygon - Sphere Intersection

This topic is 4061 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

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
Advertisement
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
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!