Jump to content
  • Advertisement
Deku

Separating axis theorem 3D - polygons

Recommended Posts

I have been working on a collision engine in Java, utilizing the Separating Axis Theorem in 3D space. I have it working successfully in all cases (that I could think of testing) with object-oriented bounding boxes, but I'm finding that SAT isn't super accurate at detecting collisions as immediately with other convex 3D polygons. Corners of rotated polygons may overlap a small amount before any valid collision is found, and the subsequent clipping algorithm I use to calculate contact points will fail. I'll highlight the main points on my current SAT implementation below, and I'd just like to get some feedback to see if I was on the right track with this or if I'm fundamentally missing something in the theory. Trying to refrain from pasting code since its moderately long.

Do note that I am using object models imported from Blender in wavefront.obj files, so I'm using the vertex normals in these files to populate my collision bodies in simulation. I'm not sure if that could cause issues with ordering or normal calculations.

 

Input two collision bodies (BodyA, BodyB)

 

Calculate distance between the centers of bodyB and bodyA (the offset)

 

for each face normal (axis) in bodyA:

- Project the vertices of both bodyA and bodyB along this axis to get the 2D minimum and maximum projections along that direction

- add offset to projection of bodyA

- check for overlap along the projections of both bodies, exit the separating axis test if their is no overlap along this projection as this is a separation. Otherwise continue the loop.

 

for each face normal (axis) in bodyB:

- Project the vertices of both bodyA and bodyB along this axis to get the 2D minimum and maximum projections along that direction

- add offset to projection of bodyA

- check for overlap along the projections of both bodies, exit the separating axis test if their is no overlap along this projection as this is a separation. Otherwise continue the loop.

 

for each face normal in bodyA (axisA):

- for each face normal in bodyB (axisB):

- - get the cross product of axisA and axisB (axis)

- - Project the vertices of both bodyA and bodyB along this axis to get the 2D minimum and maximum projections along that direction

- - add offset to projection of bodyA

- - check for overlap along the projections of both bodies, exit the separating axis test if their is no overlap along this projection as this is a separation. Otherwise continue the loop.

 

 

Most SAT resources I have read seem to be concerned with AABB or OBB collision and don't care for more complex polygon shapes so any resources you might know of that deal with a more general 3D SAT implementation would be a great help.

Thanks.

 

Edited by Deku

Share this post


Link to post
Share on other sites
Advertisement

Been taking a look at your slides, great stuff. I'm not done altering my implementation but swapping from min/max projections to separating planes seems to already be working better in the face cases after some preliminary testing.

 

Thanks Dirk, you've really set me on the right track with this. I was quite stuck

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

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