• Advertisement
Sign in to follow this  

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

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.






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




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
  • Advertisement
  • Popular Now

  • Advertisement
  • Similar Content

    • By 00Kevin
      I'm looking for solutions to a Line of Effect system I'm creating.  
      Specifically,  I'm looking for a real-time algorithm that helps an AI unit find the closest tile in range that has a line of effect to its target
      At the moment, I'm using raycasting (in Unity)  to determine what tiles have lines of effect (no obstructions) to each other.  
      This information is then used by the AI to locate an unobstructed targeting position within range.  
      The end result is that every tile has a list of other tile locations it has a clear line of effect to.  
      The problem is that it takes forever to scan and makes the map far too static for my needs. 
      Anyone implement something similar?  
    • By MidnightFoxGaming
      Hi I’m looking for a school to attend for game development and design online.
      i have a large interest in wanting to learn game development and programming and design but I don’t have the time or schools close enough to me for an on campus education since my current job has me travel rather often all over the country.
      id prefer one without liberal arts and get right into the core aspects of the major but it seems most schools love them way too much right now.
      if anyone has any suggestions for schools to look into that would allow me to get my bachelors and be able to possibly find a job in the field please let me know
    • By abe97
      Hello all! I'm new to the forum and I'm glad to have found a lot of interesting discussions/topics! 
      Quick intro, I'm currently in school for Independent (indie) Video Game Design, on my last semester and the job search will start in less than 4 months (I'm nervous to say the least). I've learned a lot in school and I'm proud to say that I can make a decent game independently and market it properly. The problem is that I can do all of this, but I don't specialise in anything specific. I'm pretty good at modeling (but definitely not a pro, can only make simple clean models), okay at scripting, design isn't my strength but a big interest and I'm pretty okay at UI/UX but definitely not proficient at all.
      I can't say I specialise in any of the above fields and I know that specialising in something is important in order to have a consistent portfolio and finding a job. 
      Should I focus on specialising on a specific field in the next 4 months (practice 24/7) in order to sell myself to employers or should I practice everything and sell myself as a Jack-of-all-trades? I really want to get a designer job as I enjoy writing GDDs and discussing design during Pre-Production but my Rational Design knowledge is weak and I've never been considered a designer in all my previous projects (always was responsible for art or UI). 
    • By KarimIO
      Hey guys,
      Are lightmaps still the best way to handle static diffuse irradiance, or is SH used for both diffuse and specular irradiance now?
      Also, do any modern games use direct light in lightmaps, or are all direct lighting handled by shadow maps now?
      Finally, how is SH usually baked?
    • By KarimIO
      Hey guys
      So I was wondering how modern terrain and water geometry works both with and without tesselation. Essentially:
      1) Is Geoclipmapping still the best CPU tesselation technique?
      2) Is Geoclipmapping still used with tesselation?
      3) Is non-tesselated water just flat? Is there any other (reasonable) ways to simulate it? Do people use Geoclipmapping for that too?
  • Advertisement