Ooh, ooh, ooh! 3D Voronoi!

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. voronoi 3d: 2 points in a box 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… voronoi 3d: 3 points in a box or ten (the mad­ness!).. voronoi 3d: 10 points in a box 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.)

voronoi3d

body in a box, W:Blut, 2009

notes

notes2

6 comments

  1. excel­lent work ! I was already your fan ;)

    this is really impres­sive.
    keep up your awe­some work.

  2. Hey Frederik, amaz­ing work you’ve done here. I’m fac­ing sim­i­lar prob­lem, but in a dif­fer­ent envi­ron­ment. I’m using qhull to obtain Voronoi dia­gram from set of points. The result is, using your words “inter­sect­ing mess”, and I’m hav­ing hard time get­ting any solid out of it.

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>