Developing 'Meshagons' : The Long (long) Story
1. Origins
Mesh of a human knee
Meshagons evolved from my research work (and class teachings) in Finite Element (FE) meshing/analyses. I have been working in FE mesh generation for over 15 years. In particular developing single and multi-domain FE meshes for Bioengineering applications. FE meshing and analyses are by far the most widely used mathematical methods for analyses of stresses and deformations of materials/parts; from car engines to airplanes and even biological tissues and implants. If you are interested in FEA in general, a couple good places to start are:
http://en.wikipedia.org/wiki/Finite_element_method
http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html
There are so many applications of FEA; too many to even begin to list. A quick search on google images shows the amazing variety of meshes and solutions (click here). I've always been fascinated by the meshes and visualization and have developed several tools in Matlab, Blender3D, Meshlab, and Gmsh to visualize tetrahedral FE meshes in 3-D. But these are all 'on the screen'. They are useful for my personal understanding of mesh structure and for class teachings, but it is still just on the computer display.
Then, about 8 months ago, I had a thought... Given the advent of new 3-D printing technologies, what if I can actually print a 3-D mesh for 'real'? Can I make a 3-D printable solid out of a 'wire-frame' tetrahedral mesh? Sounds interesting!
At first I thought, "Sure, that will be easy", but it turned out to be a MAJOR PAIN IN THE ASS. Mostly due to difficult topological issues (detailed in parts 3-4 below) and the resolving of 'slivers' (very thin tetrahedra) that are a result of (as far as I know) all Delaunay based tetrahedral mesh generation algorithms.
http://en.wikipedia.org/wiki/Finite_element_method
http://www.sv.vt.edu/classes/MSE2094_NoteBook/97ClassProj/num/widas/history.html
There are so many applications of FEA; too many to even begin to list. A quick search on google images shows the amazing variety of meshes and solutions (click here). I've always been fascinated by the meshes and visualization and have developed several tools in Matlab, Blender3D, Meshlab, and Gmsh to visualize tetrahedral FE meshes in 3-D. But these are all 'on the screen'. They are useful for my personal understanding of mesh structure and for class teachings, but it is still just on the computer display.
Then, about 8 months ago, I had a thought... Given the advent of new 3-D printing technologies, what if I can actually print a 3-D mesh for 'real'? Can I make a 3-D printable solid out of a 'wire-frame' tetrahedral mesh? Sounds interesting!
At first I thought, "Sure, that will be easy", but it turned out to be a MAJOR PAIN IN THE ASS. Mostly due to difficult topological issues (detailed in parts 3-4 below) and the resolving of 'slivers' (very thin tetrahedra) that are a result of (as far as I know) all Delaunay based tetrahedral mesh generation algorithms.
2. Modeling, Meshing, and the 'Sliver problem'
|
|
To make a mesh, we start by building some kind of surface. For that I use either my own software written in Matlab (SuperSlicer) to create surfaces from MRI or CT scans, or solid modeling tools. I prefer Blender3D. I've been using Blender for several years now and can make complicated surfaces quite easily.
Shown in the slideshow (left) are some pictures detailing my SuperSlicer software for reconstruction of 3-D volumetric data and some typical results. Also shown are some details of 'slivers' and a mesh of a vertebra. I have written my own tetrahedral mesh generator based in part on code/concepts from Olaf Persson (distmesh) and the CGAL libraries (cgal.org). I can now mesh pretty much any single or multi-domain volume (e.g. arteries, skull and brain, complex objects drawn in Blender, etc). I've had to write a lot of supporting code such as a voxel-to-surface converter, boundary cohesion and smoothing filters, and many others. |
The meshing code is a bit slow as I am not a computer science expert (I could definitely use some help here). It can take several hours to generate a high quality mesh on my (getting old now) 1.8 GHz quad Intel... There are some other drawbacks; e.g. there is no GUI (it's all command line) and it's not fully parallel (just vectorized). I do most of my visualization of mesh and FE results in Gmsh. Still, my meshing code works great, is robust and fully automated, and in many cases 'beats the pants' off the available commercial codes such as Simpleware and Materialize (I'm bragging a bit here :) . However, a major issue that cropped-up (again) are 'slivers'.
Slivers are a major problem for tetrahedral mesh generation. A 'sliver' is a poorly shaped tetrahedron that always results when Delaunay mesh generation methods are used. Slivers are essentially very 'flat' tetrahedra. They are very difficult to remove. I've spent 8+ years (no kidding) writing comprehensive code to remove slivers (recently successful I might add!). Detailing my solution for sliver removal is far too lengthy and boring for this reading, but I'll summarize. Basically, I developed an algorithm that searches and finds all slivers in a mesh and then uses a brute-force method that surrounds each sliver with it's nearest-neighbor tetrahedral 'most convex' manifold. Slivers are then removed by either edge-flipping (for simple cases) or new 'intelligent' node placement within the manifold and remeshing the local space until the sliver is resolved. It's a lot more complex than that, but suffice it to say that it works.
It turns out that removing slivers is essential for creating topologically 'convex' or closed meshagons, thus I was 're-motivated' to resolve this problem. The issue is if you have a very flat tetrahedron (sliver), the edges of the tetrahedron come very close to overlapping. This results in an impossible situation for the conversion of the mesh into a meshagon (if the edges overlap, then the topology is no longer manifold). After several more months of work I have the 'sliver problem' solved, but there are still more heavy-duty topological problems/issues, as I would soon find out...
Slivers are a major problem for tetrahedral mesh generation. A 'sliver' is a poorly shaped tetrahedron that always results when Delaunay mesh generation methods are used. Slivers are essentially very 'flat' tetrahedra. They are very difficult to remove. I've spent 8+ years (no kidding) writing comprehensive code to remove slivers (recently successful I might add!). Detailing my solution for sliver removal is far too lengthy and boring for this reading, but I'll summarize. Basically, I developed an algorithm that searches and finds all slivers in a mesh and then uses a brute-force method that surrounds each sliver with it's nearest-neighbor tetrahedral 'most convex' manifold. Slivers are then removed by either edge-flipping (for simple cases) or new 'intelligent' node placement within the manifold and remeshing the local space until the sliver is resolved. It's a lot more complex than that, but suffice it to say that it works.
It turns out that removing slivers is essential for creating topologically 'convex' or closed meshagons, thus I was 're-motivated' to resolve this problem. The issue is if you have a very flat tetrahedron (sliver), the edges of the tetrahedron come very close to overlapping. This results in an impossible situation for the conversion of the mesh into a meshagon (if the edges overlap, then the topology is no longer manifold). After several more months of work I have the 'sliver problem' solved, but there are still more heavy-duty topological problems/issues, as I would soon find out...
3. Creating meshagons: A Molecular Modeling Approach
Here's where things got 'tricky' and the story gets long (sorry). My 'simple' goal was to take the 'wire-frame' FE tet-mesh, consisting of 'nodes' (i.e. joints) and connecting 'edges' (tetrahedra) and somehow 'thicken' them into volumes suitable for 3-D printing. My first thought, and attempt, was to use a molecular modeling approach. After all, molecular models visualize the atoms as 'balls' and the bonds as 'sticks' so that is very similar to a 'mesh', right? Well, it sort-of worked. I got some great help from Patrick Fuller and Chris Wilmer to get my meshes displayed as 'sticks and balls' in Blender and it looked quite promising... I wrote more code to convert tet-meshes to the JSON data format (here are some interesting molecular visualizations from P.Fuller). In fact, I have produced several FE mesh models using this method, and am still interested in pursuing this approach for sculptures, particularly in the future in color.
Sphere FE mesh rendered as a 'molecule'.
|
The 'infinity' mesh in Blender3D rendered in a molecular fashion as 'sticks-and-balls'.
|
Actual 3-D printed 'infitity' mesh in white plastic. Conversion to 'stl' was challenging.
|
This 'sticks-and-balls' method works... but, ultimately it wasn't satisfying to me. What I really wanted was a continuous (manifold) of joined mesh 'tubes' without having to have 'balls' at every joint. I didn't want the meshes to look like molecules. Rather I wanted a continuous smoothly transitioning manifold mesh structure. The balls do serve the purpose of allowing multiple edges (e.g. sticks) to join, essentially 'masking' the overlapping end-caps of the mesh edges, but it is still not a continuous manifold structure. Thus, using this 'sticks-and-balls' approach I could not perform whole object smoothing or other manifold operations. Basically, what I wanted was to eliminate the 'balls' and just have edges connect smoothly at the joints. Well, that turned out to be a tough problem.
4. Manifolds and difficulties
I investigated several softwares and approaches to expanding wire-frame meshes to volumes (3DSmax, Meshlab, Netfabb, Rhinocerous, Grasshopper, and even other custom codes with no success). In Blender there is a 'skinning' algorithm that somewhat works. It works for relatively simple 'branches' where there are only 2 or 3 connecting edges and the angles are not too sharp (e.g. >40deg). But after that it fails to generate a manifold surface. Tetrahedral FE meshes often have 10 or even 20 'edges' joined at a node (see right below). It seemed like an intractable problem. I submitted the issue to various forums (e.g. blender (see here), blenderartists, etc.) and I was told that basically it is impossible. I almost gave up.
'Pi' mesh solidified (skinned) in Blender. Looks good so far in this render...
|
But, upon further inspection there are many non-manifold joints (highlighted orange). It's impossible. There are too many.
|
When there are too many edges intersecting at the 'joint' (node) the Blender (and other) skinning algorithms fail to create manifold. There is no 'fix'. Above is highlighted some of the hundreds of 'non-manifold' edges...
|
5. Finally, a solution that works
Well, I didn't give up. Although frustrated, I continued to try all kinds of things such as various boolean methods in Blender, Rhino, Meshlab (and others). Unfortunately booleans simply wont work with the complex joints of a tetrahedral solid. I tried subdividing the surface and remeshing with many variations of order and methods. Nope. It seemed for a while that nothing would work.
Then, I stumbled across a description of an interesting class of objects known as "alpha shapes" (link). Blender has a version of alpha shapes that they call 'metaballs'. After a bunch of 'tinkering' I managed to convert my wireframe meshes to a customized pseudo-metaball. This looked promising in preliminary tests.
Over the next couple months, I wrote some more Python code to generate metaball-based structures from my FE meshes. And... it works. I finally had fully manifold structures, but at a price. It was super-slow. In my first tests it took 24-30 HOURS to generate one simple structure.
There had to be some way to speed this up. I started digging into the metaball class in Blender, and found out a few interesting things. For one, it turns out to be possible to generate a base metaball that is actually not displayed. Thus, one can then generate all the metaball coordinates in a 'pre-construction' step, and then after it's all built (in the Python pre-read/build code), later enable the display property for the whole structure at once. This was a huge speed improvement. After several other 'tinkerings' and customizations, including a crude parallelization, I can now cut my time down from 30 hours to an hour or two. I'm sure that there are more ways to improve performance, and future work (hopefully) will improve speed. Of course, a cluster of fast computers would be good. :)
Then, I stumbled across a description of an interesting class of objects known as "alpha shapes" (link). Blender has a version of alpha shapes that they call 'metaballs'. After a bunch of 'tinkering' I managed to convert my wireframe meshes to a customized pseudo-metaball. This looked promising in preliminary tests.
Over the next couple months, I wrote some more Python code to generate metaball-based structures from my FE meshes. And... it works. I finally had fully manifold structures, but at a price. It was super-slow. In my first tests it took 24-30 HOURS to generate one simple structure.
There had to be some way to speed this up. I started digging into the metaball class in Blender, and found out a few interesting things. For one, it turns out to be possible to generate a base metaball that is actually not displayed. Thus, one can then generate all the metaball coordinates in a 'pre-construction' step, and then after it's all built (in the Python pre-read/build code), later enable the display property for the whole structure at once. This was a huge speed improvement. After several other 'tinkerings' and customizations, including a crude parallelization, I can now cut my time down from 30 hours to an hour or two. I'm sure that there are more ways to improve performance, and future work (hopefully) will improve speed. Of course, a cluster of fast computers would be good. :)
6. Smoothing, fairing, and output for 3-D printing (success! )
After all this work, the meshes were manifold and structurally sound, but still not suitable for 3-D printing. They were 'jagged' and uneven. This had to be fixed. I experimented with several smoothing methods in Blender and other codes with no luck. The problem was that any 'smoothing' step would 'break' the mesh and I would be left again with a non-manifold mesh (which of course is not printable). Then, I had a major breakthrough. I had been experimenting with Taubin's smoothing method for another project, and my colleague suggested why not try that for my meshagons... After writing a bunch more code to implement the Taubin method, it works.
Above is a series of renderings of the 'Pi' meshagon, which is one of the most difficult meshing objects that I have attempted. Close-ups of the mesh are shown as indicated. This 'Pi' meshagon was very difficult because the shape has both thick and also very thin regions. At left is the 'original' mesh which looks quite rough and 'jagged'. Middle is after 1 smoothing iteration and it looks much better. Right is after 50% decimation and 10 (extreme) smoothing steps to make the mesh have a more 'organic' structure... Looks great ! I'm happy.
|
Analysis with Meshlab (left) shows that the "Pi" meshagon is fully manifold and oriented. Which means it's ready to print.
Final steps ensure uniform normals and output to a viable STL file for 3-D printing. I have confirmed that this is indeed a printable model via Shapeways and NetFabb analyses. This 'Pi' meshagon is approximately 300 mm high, and is printable in white poly, aluminide, and various other materials such as ceramic. With some further processing this could also be printed in sandstone. |
7. Rooms for Improvement : Sculpture Ideas and Code
At this point I am finally very happy with the meshagons. After years of work, many problems have been solved and I have reliable methods/workflow. Still, there are many areas that I would like to improve, and new ideas to pursue.
Control of edge and joint thicknesses
Right now the edge and joint (chamfer) thicknesses are uniform. I would like to add code to parametrically control these thicknesses to make more interesting, organic shapes and also for engineering applications. For example, I would like to have thicker edges where the outer shape of the meshagon is 'thick' and thinner edges where the meshagon is 'thin'. Parametric control of edge thickness and chamfer would be useful for developing optimized mechanical structures.
Code and speed improvements
There is definitely room(s) for improving the code. I am very interested in using GPU acceleration for the meshing algorithm. I think this is very 'do-able' because the main force/optimization step in the meshing algorithm is already vectorized. I think full parallelization could provide orders of magnitude speed improvement. Parallelizing the metaball construction is also possible. I envision building a 32 cpu box (in my dreams :) capable of truly massive meshagon construction...
New 'Iconic' shapes/sculptures
I am always looking for new 'iconic' shapes to mesh. I have ideas for a massive cylinder, a flat large wall-panel and others. This is going to require a more powerful computer. I'm always interested in new ideas and applications so feel free to email me at tcd@tensortek.com. I'm also very interested in lighting and lamps. Meshagons would make awesome 'lampshades' or other innovative lighting. Since I can mesh practically anything at this point, it should be quite easy to design for LED lighting and wiring. I am also interested in 'jewelry' applications. Small meshagons can be easily printed in silver or bronze. The possibilities are exciting.
Large scale art/installations
Currently, meshagons can be printed up to approximately 1x1x2 meters in size (that's pretty large) although currently costly (in the thousands of dollars). BUT, I can envision how amazing these would look printed at that scale. It would be incredible. I even envision very (very) large meshagons (how about 3x3x3 meters!!). Of course these would have to be printed in sections, but it could be done with technology available now. A meshagon at that scale would be very impressive in a museum exhibit, corporate lobby, or city/landscape installation. I believe that with the rapid advances in 3-D printing the costs of printing these large scale objects will be going down. Even now the cost of printing large-scale structures is not prohibitive.
Control of edge and joint thicknesses
Right now the edge and joint (chamfer) thicknesses are uniform. I would like to add code to parametrically control these thicknesses to make more interesting, organic shapes and also for engineering applications. For example, I would like to have thicker edges where the outer shape of the meshagon is 'thick' and thinner edges where the meshagon is 'thin'. Parametric control of edge thickness and chamfer would be useful for developing optimized mechanical structures.
Code and speed improvements
There is definitely room(s) for improving the code. I am very interested in using GPU acceleration for the meshing algorithm. I think this is very 'do-able' because the main force/optimization step in the meshing algorithm is already vectorized. I think full parallelization could provide orders of magnitude speed improvement. Parallelizing the metaball construction is also possible. I envision building a 32 cpu box (in my dreams :) capable of truly massive meshagon construction...
New 'Iconic' shapes/sculptures
I am always looking for new 'iconic' shapes to mesh. I have ideas for a massive cylinder, a flat large wall-panel and others. This is going to require a more powerful computer. I'm always interested in new ideas and applications so feel free to email me at tcd@tensortek.com. I'm also very interested in lighting and lamps. Meshagons would make awesome 'lampshades' or other innovative lighting. Since I can mesh practically anything at this point, it should be quite easy to design for LED lighting and wiring. I am also interested in 'jewelry' applications. Small meshagons can be easily printed in silver or bronze. The possibilities are exciting.
Large scale art/installations
Currently, meshagons can be printed up to approximately 1x1x2 meters in size (that's pretty large) although currently costly (in the thousands of dollars). BUT, I can envision how amazing these would look printed at that scale. It would be incredible. I even envision very (very) large meshagons (how about 3x3x3 meters!!). Of course these would have to be printed in sections, but it could be done with technology available now. A meshagon at that scale would be very impressive in a museum exhibit, corporate lobby, or city/landscape installation. I believe that with the rapid advances in 3-D printing the costs of printing these large scale objects will be going down. Even now the cost of printing large-scale structures is not prohibitive.
8. Final thoughts and Engineering/Bioengineering applications
I'm quite excited about the potential for 'meshagon sculptures' and also for applications in Engineering, Biomedical, and Architectural designs. I'm working on some new challenging meshes; a large elliptical toroid, a large 'wall panel' (essentially a flattened rectilinear object), and a 'monolithic' cylinder shape. Another problem I'm working on is how best to 'skin' the meshagon so that it has a defined solid outer surface with controllable thickness. This is essential for creating accurate parts/components for engineering purposes.
See my Sci/Eng page for more info about applications.
Finally, done; here is the latest 'Pi' mesh ready and confirmed to print. Can't wait to see this one in ceramic or sandstone.
See my Sci/Eng page for more info about applications.
Finally, done; here is the latest 'Pi' mesh ready and confirmed to print. Can't wait to see this one in ceramic or sandstone.
