Li : Dev Actionscript Development Blog

Voronoi Collisions?

So, it's Saturday night, my flat mates are all heading out to cool party 'A' and cool party 'B'. Unfortunately, I have to stay indoors in quarantine since I was blessed with a flu last Thursday. Damn it! I hate it when I fall Ill just before the weekend. It's so unfair!

Anyway, I needed something to do and I think I watched practically every single new film in megavideo, so I decided to have another play with our friend Voronoi. The experiment revolves around the following question: If voronoi diagrams provide so much information about the spacial distribution of a set of points in space, couldn't this information be used to detect collisions between circles?

Apparently the experiment above says 'yes' (click on the image to run it - view source is enabled). What you would normally do to have a bunch of circles collide with each other is, on each frame, evaluate the distance of each circle to all others in some sort of nested loop. If the distance is smaller than the sum of the radii of the 2 circles being compared, you have a collision. I think that everyone involved in programming with at least a small affinity with physics has had a go at this. Even though the collision check is very simple, the amount of distance calculations is brutal. 'n' circles means 'n' to the power of 2 collision checks per frame. Of course, there are optimizations as dividing the space in a grid and only checking for collisions in the current cell and neighboring cells, which can reduce the calculations a lot.

So even though the experiment looks like what we've all seen (and/or done) 1000 times, the implementation is completely different, at least for me. On each frame the position of the circles is used to construct a Voronoi diagram. This produces a set of line segments attributed to each Voronoi focus point (which are the centers of the circles). If you compare the distance of such point to its related Voronoi edges in the Voronoi cell, with the radius of the circle, you can detect when the circle is colliding with something. If you do have a collision, you can use the vector involved in the collision check to exert a force on the circle, so once you know that something is colliding, there's no need to do any complex calculations to resolve the collision; the voronoi diagram also provides the info for you to resolve it!

I'm sure that the physics in the demo is not exactly right, and that the code could run much faster if optimized (its just an experiment after all, a proof of concept). I didn't worry much about physics correctness or using inlining or any other Flash Player optimization techniques, I preferred to keep the code clear and simple to understand. Currently its resolving collisions for 250 circles and it runs ok. I wonder how many circles it could manage if optimized, and if it would be faster than the more commonly known approaches. I have a feeling that this could be some sort of BSP collision detection system.

Uses of this? None, absolutely NONE what so ever!! Perhaps only providing a visual programmer some time to be entertained while on quarantine Saturday night :s