Jump to content
  • Advertisement
Sign in to follow this  
coderchris

Optimizing Seperating Axis Thm?

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

In 2d, SAT works great and extremely fast, but Im finding that with simple box's in 3d, its starting to run very slowely, mostly due to having to check all the edges on A x edges on B. Iv looked all over and could find nothing.. Does anyone know of any optimizations I could make it run faster? For example are there any checks I can do to quickly reject having to check certain edges/faces?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by coderchris
In 2d, SAT works great and extremely fast, but Im finding that with even a simple box in 3d, its starting to run very slowely, mostly due to having to check all the edges on A x edges on B.

Iv looked all over and could find nothing..
Does anyone know of any optimizations I could make it run faster? For example are there any checks I can do to quickly reject having to check certain edges/faces?
Could you clarify what you mean by 'box'? For a rectilinear box (e.g. an OBB), most of the axis tests can be optimized away. For arbitrary polyhedra in 3D however the SAT may be a less suitable solution due to the aforementioned edge cross-product tests.

Perhaps you could describe in a bit more detail what sort of shapes you'll be working with.

Share this post


Link to post
Share on other sites
You checking all edges?

You should just check the three major axes of the boxes. That should give 15 tests, very manageable.

As for the bottom line optimisation, check out Dave Eberly's papers n the subject. He has the optimisations all worked out for box-box, box-triangle and triangle-triangle.

Share this post


Link to post
Share on other sites
What I mean by box is a 6 sided 3-dimensional one, but im generalizing my tests to work with any convex object. At the moment im doing a total of 15 checks. I was wondering if any of these could be ruled out before I do them.

I tried adding in a check to see if the edge's normal was in the same direction as the object thats being collided against, and while it did speed it up a bit, it also led to missed collisions..

Share this post


Link to post
Share on other sites
You're cutting out of the tests early when you find a separating axis, right? Unless the objects are colliding or very close to colliding, you'll usually find a separating axis within the first 6 or so axes tested.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!