Critical Section


Sunday,  05/11/14  10:09 PM

Voronoi-zation - here's how you do it*.

0) Download and install Meshlab, an awesome open source program that let's you do all kinds of amazing transformations on meshes.  What's a mesh?  Any collection of vertices and faces.  In particular, any object you might want to 3D-print, or any object you might create with a CAD program like Tinkercad.  STL files contain meshes.

1) You need a starting point, the object to be "Voronoi-ed".  For example, here we have a 3D object which is the famous "Love" sculpture.  Launch Meshlab and perform File | Import Mesh to load the object.

2) Next we have to make sure there are hundreds of thousands of vertices in this object.  Perform Filters | Remeshing | Subdivision Surfaces: Loop.  Click Apply repeatedly and watch the number of faces multiply.  you might have to change the Edge Threshold from 1.0% to 0.5%, to get to 300,000 or so vertices.  You'll note that in the process some of the hard edges of the object are going to get softened, and that's good too.

3) Okay, now we cover the surface of this object with points, randomly.  These are going to be the centers of the little holes we will remove later to create the Voronoi effect.  Perform Filters | Sampling | Poisson-disk Sampling.  You might have to play with the number of samples; the more complicated the original shape, the more points you'll want.  For this example I've chosen 250, for a simpler object like a donut, maybe 100 would be okay.  You can see the points as white dots.

A little digression; Meshlab does not have "undo".  However in this case we are creating a new mesh from the old one, and we can delete the new mesh and create another, repeatedly.  Select View | Show Layer Dialog and you'll see each of the meshes separately.  You can right-click on the Poisson-disk Samples and select Delete Current Mesh if you want to retry.

4) Time to "Voronoi".  Perform Filters | Sampling | Voronoi Vertex Coloring.  Click BackDistance, and then click Apply.  The original mesh will be colored based on how far each vertex is from the points in the random Poisson distribution.  The far away areas are red - these are going to be the bones of the final object - and the close areas are green - these are going to be deleted.

At this point if you want to redo the operation, you can.  Simply delete the Poisson-disk samples, create a new random distribution of points, and perform the Voronoi Vertex Coloring again. 

5) Time to modify the mesh and create some holes!  First, perform View | Show Layer Dialog if you haven't already, right-click on the original mesh, and select Flatten Visible Layers, then click Apply (accept the defaults).  At this point the coloring is going to disappear, but the points are still there and the vertex distances from the points have been saved.

6) Next perform Filters | Selection | Select Faces by Vertex Quality.  The term "quality" here really means distance from the points.  Click "Preview" so you can see the vertices which have been selected; they'll be red.  Slide "Max" all the way to the right.  And now play with "Min" until you have the pattern you want.  You might have to type values if the slider is too granular.

Note this step just "selects" vertices, so you can play around until you get it the way you want.  In the next step we delete vertices and faces, and that's undoable.

7) When you've got the pattern just the way you want it, perform Filters | Selection | Delete Selected Faces and Vertices.  You've cut away the mesh now, and we're well on our way to Voronoization.

8) Now it's time to cleanup the cut away mesh; as you can see, the pattern is rather jagged.  Select Filters | Smoothing | Laplacian Smooth, and Apply a few times.  Each time you apply the pattern will be smoother, and you'll also notice the holes get rounder in the process, making the object more spidery.

9) Next comes the crucial step; we're going to make a 3D object out of this!  Right now the surface is the right pattern, but it has zero thickness, and that's not what we want.  Select Filters | Remeshing | Uniform Mesh Resampling.  Check the Absolute Distance box.  There are two parameters here, and they're both important.  The Precision value controls the level of detail, I usually set this to about 0.3.  And the Offset value controls the thickness of the new object.  You can play with this, I usually set around 0.5.  You want the object to be reasonably thick so it will print properly; also, that makes it look cooler.

This process can take a long time (minutes rather than seconds), and it creates a new mesh from the old one.  That means if you don't like the result, you can delete the mesh (right-click, select Delete Current Mesh), and try again.

10) Yay we have a 3D object!  Now we want to clean it up.  We have two tools for this; first, the Filter | Smoothing | Laplacian Smooth we used before in step (8), and second, the Filter | Remeshing | Subdivision Surfaces: Loop we used in step (2).  The Laplacian Smooth moves vertices, while the Subdivision Surfaces adds them.  Here's what the example looks like after a bit of smoothing:

11) And then after some Subdivision Surfaces to add vertices:

12) Awesome, right!  Now we just need to reduce the number of faces.  This figure currently has over 400,000, and while that makes for good definition, it's going to slow down our slicer amazingly when we try to print.  Perform Filters | Remeshing | Quadric Edge Collapse Decimation.  (Did you ever think you'd actually use a tool with that name? :)  This allows you to reduce the number of faces.  The target depends on the complexity of the object.  For this case, I chose to reduce to 150,000.  You probably won't even be able to tell the difference.

13) That's it we're done.  Now just select File | Export Mesh As and save as an STL, and you'll be able to print the Voronoi-ed object.  How cool is that?


* What is Voronoi-zation, you ask?  Well, it's the process of taking an object and creating a new object from it with a bunch of cool holes cut into it, useful for making interesting 3D-printable shapes.  Voronoi was a mathematician who studied surfaces; if you have a surface and imagine some selected points sprinkled over the surface, then for any point on the surface it is closest to a selected point.  You can score all the points by how far they are from the closest point, and that defines a pattern.  This pattern can be used to cut holes in an object.  Once you've cut the holes, you can then make the surface three dimensional, and poof! you have a Voronoi object.

'14   '13   '12
'11   '10   '09
'08   '07   '06
'05   '04   '03
About Me

Greatest Hits
Correlation vs. Causality
The Tyranny of Email
Unnatural Selection
Aperio's Mission = Automating Pathology
On Blame
Try, or Try Not
Books and Wine
Emergent Properties
God and Beauty
Moving Mount Fuji The Nest Rock 'n Roll
IQ and Populations
Are You a Bright?
Adding Value
The Joy of Craftsmanship
The Emperor's New Code
Toy Story
The Return of the King
Religion vs IQ
In the Wet
the big day
solving bongard problems
visiting Titan
unintelligent design
the nuclear option
estimating in meatspace
second gear
On the Persistence of Bad Design...
Texas chili cookoff
almost famous design and stochastic debugging
may I take your order?
universal healthcare
triple double
New Yorker covers
Death Rider! (da da dum)
how did I get here (Mt.Whitney)?
the Law of Significance
Holiday Inn
Daniel Jacoby's photographs
the first bird
Gödel Escher Bach: Birthday Cantatatata
Father's Day (in pictures)
your cat for my car
Jobsnotes of note
world population map
no joy in Baker
vote smart
exact nonsense
introducing eyesFinder
to space
where are the desktop apps?