collision - What is the *fastest* algorithm for detecting intersection between polyhedra? -

say there n 3-dimensional objects (polyhedra). fastest way calculate intersection of objects o(n ^ 2)?

right now, i'm using library forces t(n) equal n ^ 2:

for each object: // there n objects     list of intersecting objects // takes n steps 

that literally takes n ^ 2 steps.

the faster way can think of still o(n ^ 2), t(n) = n(n+1) / 2, or (n*n + n) / 2.

here's pseudocode:

for(int = 0; < len(objects) - 1; i++)     for(int j = + 1; j < len(objects); j++)         if object @ intersects object @ j:             object @ . addtointersectlist ( object @ j )             object @ j . addtointersectlist ( object @ ) 

this way don't have check see if 2 objects intersect twice. know there 3000 objects in list iterating through. algorithm takes 4501500 steps, whereas original algorithm takes double that, 9000000 steps.

am missing something? best can get?

while there few ways improve o(n²) performance changing looping stuff, there significant improvements can made changing other things way collision checking.

one of main inefficiencies in code way relies on checking each polyhedron against every other polyhedron, not necessary. don't need intensive intersection test if 2 shapes aren't close together, , if have 2 clusters of shapes separated vast expanse of space, not need check each member of 2 clusters against every member of other cluster, either. techniques performing optimizations of sort include:

• locality-sensitive hashing
• space partitioning
• bounding volumes

you can use these techniques majorly speed collision search.