W:Blut

I’m sorry, I got a bit excited. But I never thought I’d get this far: actual, geometrically correct 3D Voronoi subdivision. Following my shot­gun approach to 3D Voronoi sub­di­vi­sions in the voronoiBall, it was time to recon­sider the problem.

A 3D Voronoi sub­di­vi­sion is not that hard to imag­ine. Consider 2 lonely points in a box. A good way of divid­ing the box is split­ting it with the bisec­tor plane. This plane is per­pen­dic­u­lar to the line con­nect­ing the two points and put exactly halfway between them. There’s no need to limit our­selves to two points. Once we can split by a plane, we can repeat this as often as we like. With three points… or ten (the mad­ness!).. Anyway you got the idea. Now, if you cut by more than one plane, you need some way of select­ing the proper seg­ments. Otherwise you end up with a mess of planes cut­ting planes. It’s an inter­est­ing mess and I might get back to it one day, but it’s not what we’re look­ing for today. If done prop­erly you end up with the Voronoi sub­di­vi­sion of the points bounded by the cube. In anal­ogy with my dabblings in 2D Voronoi, I thought this selec­tion was going to be the tough part. Boy, was I wrong…

To be con­tin­ued. (In the mean­time, feel free to explore the code.)