As regular readers of this blog will know, I’m passionate about the use of relaxation and force-based methods for optimizing geometry in a very interactive way.
There is a great variety of form-finding that can be done by assigning physical forces as interactions between sets of particles. However, in my investigations so far, the topology of these interactions has usually remained fixed. So the overall shape changes dramatically, but the number of points -and the underlying network of which point interacts with which- remains the same throughout the simulation.
I have written about topology optimization before, in my post on self organizing structures, but the videos above use a fundamentally different approach than any of the examples shown there, as this new work is based on purely local interactions, which reconfigure their connectivity as the geometry changes.
I did experiment a while back with a different technique for dynamic remeshing based on repelling/colliding particles or spheres (see this video, skip to around 1:27 for the mesh generation), but this was limited by a number of factors – although the spheres only exert force on each other when they are closer than a certain distance, they still need to be constantly checked against all the other spheres to see if they are within this distance. Checking every sphere against every other one means the number of interactions increases as the square of the number of particles, which becomes slow for even modest meshes of a few thousand vertices.
There are various ways of significantly reducing this complexity and cutting down the number of distance calculations to be performed at each iteration (such as partitioning the space into cubic cells, and only checking for interactions between particles in the same or neighbouring cells). However, there still remains the question of how to remove or add spheres if they get too close or too spread out. Then even when a fairly equal distribution of points across the surface has been achieved, turning this into a clean mesh can still be tricky.
Instead, using the mesh connectivity itself from the very beginning as the network of which vertices interact with which, and updating it iteratively and locally based on its changing geometry, solves all of these problems at once. This connectivity update can be done by using repetitions and combinations of just 3 essential moves :
edge flip
edge collapse
edge split
(or alternatively, one can use edge flip, vertex insertion and vertex removal)
vertex insertion/removal
I’m always using a triangulated mesh here. In the 2nd and 3rd videos at the start, the underlying physics is still working with triangles, but I’ve shown the dual of this, which exchanges the roles of faces and vertices, turning a mesh of mostly triangles into one of mostly hexagons:
Notice that the irregular vertices of the triangle mesh (ones which have 5 or 7 connected edges instead of the regular 6) correspond to pentagons and heptagons in the dual. Finding the right number and placement of these irregular vertices is an important part of making a good mesh. There is a close relationship between these irregular vertices and the overall topology and curvature of the mesh. Euler’s polyhedron theorem gives us a precise relationship between the number of faces/edges/vertices, and the genus of the mesh (F-E+V=2-2g). This is linked to Descarte’s polyhedron theorem, which relates the total angle defect at the vertices to the genus, and is itself a discrete version of the continuous Gauss-Bonnet theorem which describes a similar relationship for the integral of Gaussian curvature in the smooth case.
Keeping a good quality triangular mesh (close to even sized equilateral elements, with no obtuse, skinny or degenerate ones) can be very useful for many other types of optimization and simulation, as well as an advantage for fabrication if it is to be built as a physical structure.
I’m thinking I could also vary the remeshing rules depending on whether the priority is regularity of geometry, or regularity of connectivity. For example, on a sphere, a geodesic dome has a small number of irregular vertices (this is sometimes referred to as a semi-regular mesh), but a fair amount of variation in edge length, whereas solutions to the Thomson or Tammes problems reduce the variation of distance, but have larger numbers of irregular vertices.
If the triangles all have identical edge lengths, then all of the angle defect is concentrated at the irregular vertices, whereas if the edges can vary slightly, the angle defect can be spread out across the mesh. As mentioned above, by Descarte’s theorem, the total angle defect is fixed, but if the number of vertices is increased it can be divided between more of them. Subdividing each triangle (using a smoothing scheme such as Loop subdivision) does not alter the configuration of irregular vertices, but reduces the angle defect at each vertex (and in the smooth limit it approaches zero as the number of vertices approaches infinity).
The remeshing can also be based on other criteria than just equal triangles. Reducing triangle size in high curvature areas is an obvious one, but I have a hunch there could also be some interesting ways of basing it not just on geometry, but on stresses, and using it for structural optimization.
I find remeshing fascinating because the same geometric rules and operations have relevance across so many different disciplines and at a variety of scales.
For example, in the carbon nanostructures graphene and nanotubes, which are hexagonal arrangements of atoms, there is a much studied crystallographic defect which occurs called the Stone-Wales defect – where instead of all hexagons we get 2 pentagons and 2 heptagons. It has important implications for the material’s mechanical and electrical properties. If we look again at our edge-flip move on a regular triangular mesh, and its effect on the dual, we see that it is exactly the Stone Wales defect!
There are even hypothetical carbon nanostructures (proposed by Mackay and Terrones) in the shape of doubly curved triply periodic minimal surfaces known as Schwarzites.
(from the paper Curved nanostructured materials)
As the bond lengths between the Carbon atoms are very rigid, the only way these curved structures can be formed is through the variations in mesh connectivity.
Because such complex geometries are only dependent on the way in which many identical elements are connected, rather than variation in the elements themselves, they can be modelled using simple materials (no laser cutting involved – just clever assembly!):
(by Bih-Yaw Jin from the beaded molecules)
(by Dimitry Tishchenko)
(by Loop.ph)
Going down to even smaller scales, we can even find the use of similar ideas about mesh connectivity in theories of loop quantum gravity, spin foams, and Regge calculus (for example, see Canonical Simplicial Gravity by Dittrich and Höhn, or The Feynman diagramatics for the spin foam models). Pachner moves or bistellar flips generalize the mesh moves described earlier to higher dimensional simplices.
(images from Canonical Simplicial Gravity)
So as well being potentially useful for design, meshes and their properties have profound relevance to our understanding of the nature of space and curvature, because of the way they link the discrete and the continuous.
I’ll be continuing to work on these remeshing tools and their combination with other types of relaxation and optimization. These recent developments are not publicly available for now, but I’ll update here with any news.
Here are a few more references on remeshing:
Dynamic Remeshing and Applications
A Remeshing Approach to Multiresolution Modeling
__________________________
also – a general update : Around a year ago I started working full time for Foster+Partners in the Specialist Modelling Group. This has been a really great experience, working on (and applying Kangaroo on) some big and exciting projects, but core Kangaroo development (and posts here) did necessarily slow down a bit during this time. However, I have recently left F+P and things will be changing ! More news to follow…
September 20, 2012 at 2:31 pm
Great to see you updating the blog again! I don’t understand half of what you are actually doing (and I suppose I’m not the only one) but I’m always stunned by what you achieve!
September 20, 2012 at 4:28 pm
Great post! Other than computation time, is there an inherent geometrical advantage to updating the mesh connectivity?
I’m wondering if maybe using a Kd-tree or spatial hash to reduce the nearest neighbour search might achieve the same thing…..and possible even broaden the range of configurations? I guess point insertion is always necessary, though…..
September 20, 2012 at 4:38 pm
Just reread the post – you totally answered that question….
September 20, 2012 at 5:16 pm
Thanks Daniel,
Actually, I think there may still be a use for a spatial neighbour search in combination with this approach. Because with just the 3 remeshing moves described, it isn’t possible to change the genus of the surface, whereas with the free particle approach it is.
So either there would need to be some additional remesh moves for cutting/reconnecting the surface, or perhaps switch back occasionally from local/mesh based connectivity to a global neighbour search to check if the surface topology changes.
September 20, 2012 at 5:21 pm
maybe an alpha shape implementation….?
September 20, 2012 at 6:00 pm
Interesting idea – I’ve never looked much at alpha shapes, but it does seem like it maybe could be useful here
September 20, 2012 at 8:59 pm
Thanks for the illustrative blog post. Can you hint a little more at the structure of your implementation? It’s particularly the relationship between this remeshing and the dynamic modeling that I’m interested in. What is the relationship between the three moves you mention and kangaroo – is the mesh being altered concurrently to the dynamic simulation within kangaroo? Is kangaroo handling the positions of the vertices and then a secondary process handling the remeshing?
September 22, 2012 at 8:14 pm
Andrew, You asked the question that I’m most interested in too. This has been one of the most difficult issues in using kangaroo up to this point. Having the mesh topology update while the simulation is going is a huge step.
Daniel: Good luck with where and whatever you are doing next.
September 22, 2012 at 8:24 pm
Daniel, Maybe I missed this, but once you find the dual of the triangulated mesh, how are you displaying the surface geometry? Does Rhino allow faces with more than 4 vertices now or have you created a custom mesh type, or are you somehow making these into nurbs patches for display? I know that Evolute made some sort of custom mesh type that allows faces with more than 4 vertices, but am curious how you are accomplishing this.
In a related project where I used Kangaroo to create a catenary surface with dual tiling, I simply displayed everything as curves and reconstructed faceted, triangular polysurfaces which could be unfolded for fabrication with no interior seams per polysurface:
http://matsysdesign.com/2012/04/13/catalyst-hexshell/
September 23, 2012 at 1:12 pm
Great stuff. Nice to see you posting again!
September 24, 2012 at 1:02 pm
Thanks for the comments guys.
The remeshing is happening in the same loop as the physics/relaxation (I had previously tried a proof of concept using HoopSnake and separate physics/remeshing loops, but wasn’t able to get interactive speeds that way)
It’s part of some major changes to how Kangaroo works under the hood, and there’s still some things to work out with exactly how this fits together with all the rest of the force connection types, but like you say – it should be a big step forward.
September 24, 2012 at 5:09 pm
Amazing, and thanks for the reply. Looking forward to a public release when you get everything working. And if you ever need a guinea pig/beta tester you know I’m always eager… :)
September 25, 2012 at 9:59 am
Thanks for explaining all this Daniel. I really appreciate what you show.
Triply periodic minmal surfaces can be woven triaxially – the mesh is deformed by weaving irregular cells (pentagons and hexagons) into the hexagonal grid. Positive and negative curved surfaces result without bending or imposition of form.
September 28, 2012 at 4:10 pm
Wow, your blog is extremely fascinating. Thank you for the link.
September 28, 2012 at 8:41 pm
The key word above for me is interactive. Real time feedback completely changes a design workflow, and this method’s ability to deal with “messy” inputs without breaking is key. I’d love to see similar interface attempts with tensor fields or dipoles, as they could take advantage of an intuitive interface through the placement of singularities or lines of force. Please keep wowing us with more work in this vein!!
October 12, 2012 at 7:08 pm
[…] I’ve just posted a new article about something I’ve been working on recently: https://spacesymmetrystructure.wordpress.com/2012/09/20/meshmash/ I’m quite […]
October 15, 2012 at 10:15 pm
[…] of the mesh (ie. some irregular vertices) can help reduce the magnitude of these variations (see my previous post for more on this), but still leaves many different panel […]
December 10, 2012 at 7:50 pm
this is something i’ve been discussing with a colleague on my monday morning travels… here’s something for you http://www.cs.columbia.edu/cg/pdfs/13-Grinspun-2002-CHARMS.pdf i’d be happy to share some of the related work we’ve been doing. keep up the inspiring work. cheers c
December 28, 2012 at 11:33 am
Hello,
This work is fantastic! I am a physics student at Berkeley completing my thesis in quantum gravity and am faced with a computational question which you may be able to answer: I need to triangulate (viz, create a triangular tesselation) a perfect sphere of arbitrary radius with equilateral triangles–which are all the same sidelength–and nothing else. Our group’s current attempts at algorithms to do this are dismal to say the least–we are definitely not computer scientists. Do you know of an efficient algorithm which may be used to do this? It looks as if at least the first video is doing something like what we want.
Lastly I am wowed by the beauty of the image between the words “(and in the smooth limit it approaches zero as the number of vertices approaches infinity).” and “The remeshing can also be based on other criteria than just equal triangles.” and would like your permission to use it in my thesis to illustrate something called the conformal Regge Calculus. Of course your work would be acknowledged in the print thesis and in any publications in which we may decide to use it in. To be honest I was so struck by the quality of the image that I considered just lifting it but thought it best to ask you first.
November 5, 2013 at 12:22 pm
We are a gaggle of volunteers and opening a new
scheme inn our community. Your site provided us with useful info too work on.
You’ve done an impressive job and our whole group will likely be thankful to you.
May 15, 2014 at 7:15 pm
[…] for preparing the meshes before relaxation. Since the last time I wrote about dynamic remeshing here, I have made significant improvements to these tools (making use of the Plankton half-edge mesh […]
December 25, 2017 at 6:04 am
I am actually delighted to glance at this website posts which includes lots of helpful facts, thanks for providing these statistics.