Blob Tree [C++]

The principle behind the blob tree is quite simple : instead of considering an object by an group of vertices with specific coordinates, we decide to take the whole object as an set of points verifiying a function. We can then modify a surface without specifying manually what points have to move.

This of course is not free, and hardly doable in real time.

An example of a blob tree. The sphere are not a set of vertices, the envelop is actually computed from the center of the sphere. The blend function between each node of the tree results in the spheres merging.

Experimenting :

The scene is a binary tree, containing at first the green sphere and the red disc. When the green sphere collides with the disc, it drops off a subtracting node at the disc side of tree.
Then all along its way down, its drops off a lot of these subtracting nodes, so that when the computing is done, it seems that the disc is « eaten » by the sphere.

Due to the process used here, the size of the tree grows drastically.

Optimising:
   A first optimisation is to balance the tree to avoid seeing it size grow too rapidly. We could you an octree, but I was lacking time to implement it. So a simple algorithm will do it for now.

A second optimisation is to simulate the scene before displaying it, storing the positions of the green sphere in an array, and the negative blobs its generating.
This is not the main performance issue, but we’ll also avoid the collision processes with this method.

The first graph below show the evolution of the tree size with the number of blobs created.
In blue with no optim, in red with the first optim

The second graph shows the evolution of FPS during the scene, also according to the number of blobs.