Collision detection algorithm for sphere tree (static)

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

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.