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.)

pekoExcellent work! I‘m your fan from now

nicoptereexcellent work ! I was already your fan

this is really impressive.

keep up your awesome work.

Frederik VanhoutteThanks!

skratHey Frederik, amazing work you’ve done here. I’m facing similar problem, but in a different environment. I’m using qhull to obtain Voronoi diagram from set of points. The result is, using your words “intersecting mess”, and I’m having hard time getting any solid out of it.

Pingback: Data is political » Blog Archive » Thinking about using 3D Voronoi today for an architectural project

AndyLovely, impressive stuff — you work is legendary