Hi Gustavo and Matt,
Thank you for giving such detailed feedback - it is really helpful to see all these files and comparisons.
Sorry it has taken me a while to respond - I’ve been thinking for a while now about a number of different approaches to this, each with different trade-offs…
-
What we have now - radial connections of struts. This gives simple all quad meshes, and works well for things like wireframes coming from surfaces, and pretty well for things like animals or humans that can be seen topologically as collections of tubes branching off each other. It is badly suited for things like volumetric lattice structures or space-frames, where you often need connections from all directions.
-
The fully implicit surfacing approach - the mesh is created by taking a contour of some scalar field around the struts, using marching cubes or similar. This can be robust, and handle all spatial node configurations, but the down side is that the resulting mesh will be an unstructured and dense triangulation, especially for structures with slender struts, meaning processing large structures can get heavy, and there’s no conversion to subd.
-
Placing polygons for the ends of each strut and taking their convex hull. This is the approach me and Dave Stasiuk used when we made Exoskeleton, which was roughly based on this paper http://people.tamu.edu/~ergun/research/topology/papers/caadfutures05a.pdf . This gives a triangular mesh around the node, often with quite badly shaped triangles, so it generally needs some remeshing and can’t convert nicely to subd. At least the tubes are simple though, you can choose how many sides they have, and the face count is much lower than with implicit surfaces. It is also not always obvious how to choose a good orientation for the section polygon about each strut’s axis.
-
Taking the Voronoi on a sphere of the intersections of all the connecting edges, then extruding these polygons outwards. This gives a mesh of all quads around the node, but one issue is that the connections can then each have different numbers of sides. So when it comes to adding the tubes between nodes, you sometimes have to connect a 4 sided tube at one end to a 5 sided one at the other. There’s no way topologically to do this with all quads without T-junctions - you can increase or decrease by 2 sides, but not by 1. So you have to either accept the occasional triangle, or double the number of divisions so it is always steps of 2.
-
Orienting a cube to somehow best fit the connecting edges, then extruding those faces (something like this paper https://www.ece.lsu.edu/xinli/Research/LLWQ13TVCG.pdf or this one http://vcg.isti.cnr.it/Publications/2015/ULPTS15/- and it looks like T-Splines approach works along these lines). This works nicely when you have structures which have up to 6 connecting edges, each of which can be fit to one of sides of the cube. It gives simple quad meshes that convert nicely to subd. It gets tricky though when you have more connections, or several edges want to share one side of the cube, since splits then need to propagate through the rest of the mesh. I think also always sticking to 4 sided tubes can sometimes miss some simpler solutions - for example, in the file you posted, if we use triangular sections we don’t need the extra quads on the nodes that the T-splines solution gives.
-
Segmenting a sphere with 3 of the edges, then adding each of the other edges one at a time, splitting whatever face they intersect (as described in this relatively recent paper: https://hal.inria.fr/hal-01532765v2/document). This can handle spatial configurations, and gives simple all quad meshes with no extra faces on the nodes. I like a lot about this method, but not that it depends on the order the edges are added in. I’ve been thinking about whether there is any way to avoid this.
I think it would also be good to switch between these options in certain cases. For instance, if the arrangement of edges is close to lying in a plane but not exactly, the Voronoi in option 4 could have some very short edges, and it could be cleaner to revert to option 1. You might also want to detect cubic-like arrangements and use option 5 for these, but option 4 or 6 otherwise.
While they are obviously linked, I see generating the mesh topology and shaping the geometry as separate issues, with the first being the much harder problem that needs to be solved first, though to make it more useful as a tool I can see there need to be better ways of controlling the size of nodes and struts, and the amount of webbing.
Once you have the topology, it should be possible to pull vertices in or out to get them onto a chosen target surface. It could also be helpful here to apply at least one subdivision step first to have more vertices to work with to control the shape.
These target surfaces could come from summed distance potentials (like Dendro uses). One nice thing about these is that by varying the power you raise the distance to you can choose between something with a lot of smoothing to what is essentially a Boolean union of cylinders in the limit.
Thanks again for the feedback. I realise this post doesn’t solve your current issues, but I thought I’d share some of my current thinking on this. As you say, it’s a hard problem - it’s very closely linked to general quad meshing of surfaces, which still has a lot of open questions. Hopefully I can get to something more useful for spatial cases like your example soon (probably using some development or combination of options 4/5/6 described above).