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 shotgun approach to 3D Voronoi subdivisions in the voronoiBall, it was time to reconsider the problem.

A 3D Voronoi subdivision is not that hard to imagine. Consider 2 lonely points in a box. A good way of dividing the box is splitting it with the bisector plane. This plane is perpendicular to the line connecting the two points and put exactly halfway between them. There's no need to limit ourselves 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 madness!).. Anyway you got the idea. Now, if you cut by more than one plane, you need some way of selecting the proper segments. Otherwise you end up with a mess of planes cutting planes. It's an interesting mess and I might get back to it one day, but it's not what we're looking for today. If done properly you end up with the Voronoi subdivision of the points bounded by the cube. In analogy with my dabblings in 2D Voronoi, I thought this selection was going to be the tough part. Boy, was I wrong...

To be continued. (In the meantime, feel free to explore the code.)