Jump to content
  • Advertisement
Sign in to follow this  
Misery

Algorithm Collision detection algorithm for sphere tree (static)

Recommended Posts

I am programming boolean operations on 3D meshes which are described by sphere trees. They do not deform, nor change in time anyhow. However to generate the environments I need to perform boolean operations on them as fast as possible. I need to find all the collisions between polygons (triangles). What is the best approach / algorithm for that purpose? I haven't found anything particularly useful via Google.

In detail: I am in need for an algorithm that will take two sphere trees and return the buffer of all collisions. I do not have much experience in using sphere trees so my idea is to check every polygon from the first mesh with the second mesh sphere tree and vice versa.  Somehow I feel that is a waste of CPU power. Could anyone give me a description of better approach or some useful links?

 

Share this post


Link to post
Share on other sites
Advertisement

A sphere can be represented precisely using a simple equation. Storing a bounding volume as a polygon mesh is kind of defeating the purpose of a bounding volume, which is to be easier to operate on than the geometry inside it.

You can do some simple fast math to get sphere-sphere intersections, and thereby compute the exact set of space that overlaps between two hierarchies.

https://en.m.wikipedia.org/wiki/Sphere#Equations_in_three-dimensional_space

https://en.m.wikipedia.org/wiki/Bounding_volume_hierarchy

 

http://mathworld.wolfram.com/Sphere-SphereIntersection.html

 

If you specifically want to do collision e.g. for physics, the area to research is broadphase algorithms such as:

https://en.m.wikipedia.org/wiki/Sweep_and_prune

 

 

Share this post


Link to post
Share on other sites
2 hours ago, Misery said:

my idea is to check every polygon from the first mesh with the second mesh sphere tree and vice versa.

That's the usual way to do it, and i'd recommend doing so and focus on the larger problem of the boolean operations first. (People say this hard due to limited floating point precision if you need robust results that keeps a closed surface. Read here how libigl warps two libraries: Cork which probably works like you intend, and another (maybe from CGAL) using exact arithmetic to guarantee robustness but being slow: http://libigl.github.io/libigl/tutorial/tutorial.html#booleanoperationsonmeshes)

Back on the tree topic: You could change the algorithm to find potential overlaps by going wider and using much more memory, somehow (but not exactly!) like this:

 

For each tree level starting from the root

{

For each node store a list of intersecting nodes of the same tree level.

for each child go over parents intersection list and refine to their children.

}

 

At the end you have for each node a list of intersecting neighbours.

Advantage is that you do not start at root again and again for each triangle, and you do not everything twice. But code complexity is higher - usually worth only for realtime work and it may need too much memory to store all lists for high poly models. Consider it as a optimization you might do later.

 

Edit: Thinking more if it, did you consider just using a regular grid? High memory needs as well but much less work.

 

Edited by JoeJ

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  

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