Thanks, George, for pointing me to your terrific paper! (44MBytes for your 9-page paper must be some sort of a record! I suspect that hi-rez full-color versions of your pictures lurk within this PDF.) It sounds like you were approaching exactly the same problem from a slightly different perspective: that of an artist. I am also trying to build 3D 'watertight' manifolds from triangulated surfaces -- e.g., the binary '.stl' file format -- but my goals aren't aesthetic, but engineering: how to build the strongest/stiffest structures from a minimum of material. I believe that my approach to struts will yield surfaces with perhaps one order of magnitude fewer vertices & triangles than yours, because none of my struts are 'twisted' (twisted struts don't preserve the area of the cross-section). My approach also trivially extends to cylindrical struts with >3 faces; the 'angle bisector' part of the proof below also works for regular n-gons. BTW, the proof below might also enable a consistent 'paint scheme' for the faces of the cylindrical struts, which would be aethetically pleasing. The 'angle bisector' proof would also work for strut cross-sections which are non-regular n-gons, so long as they have (bilateral?) symmetry, because the orientation is preserved across every edge intersection at a vertex. It is interesting that an entire structure made up of O(10^6) vertices/edges/faces may have only 1 degree of freedom, so that the orientation of exactly 1 strut will force the orientation of _all_ of the rest of the struts! I'm going to call my theorem the 'No-Twist' theorem. If you're on the inside of one of these tubes & follow any cyclic path through the structure, you will arrive back where you started without undergoing _any_ net rotations. I would imagine that other mathematicians will be happy to explore networks in which paths exist (especially with regular n-gons) where you undergo a net rotation of 360*i/n for any integer i. This might be useful if some of the 'struts' are in tension -- i.e., they are 'ropes'/'wires' instead of compression struts. I also have the goal of eliminating complex (and very expensive) 'solid geometry' operations, so that I can quickly build O(10^6) sized objects without taking a long time. I believe that I should also be able to pre-compute all of my intersection triangles without having to call upon CSG union/intersection/difference algorithms, but I haven't yet finished those algorithms. --- I conjecture that the number of 'degrees of freedom' = the number of connected components of the undirected graph. Proof sketch. Consider any simple cyclic path in the graph & throw away the rest of the graph (for the moment). Each vertex in the path now has degree exactly 2. But the same 'angle bisector' argument for the triangle (see below) shows that once the angle choice is made for one of the struts incident on the vertex, the same choice is required for the other incident strut. By induction, the choice on one strut constrains the choice on every other strut in the cycle. We thus have at most one consistent labelling for the entire cycle. But can we always make a consistent choice for the entire cycle? Yes, because we can always _triangulate_ the cycle. I.e., if we start from a particular vertex in the cycle, this constrains both incident edges. But we can now shorten the cycle by one edge & one vertex by removing that vertex & both incident edges & installing a new edge between the opposite ends of the removed edges. Eventually, we produce a triangle, which we already know can be consistently labelled. Reversing the steps, we now know that the entire cycle is determined by the rotation of any single strut edge in the cycle. But this means that any one edge incident on the vertex constrains every other edge incident on that vertex, because we can always choose a path that includes both edges. Thus, the entire connected component has at most one degree of freedom, and at least one degree of freedom. It would be neat to _animate_ such an embedded graph by rotating the faces of all the struts in unison. (What kind of gear train would be required inside the vertices in order to achieve this unanimous rotation?) At 09:16 AM 6/4/2013, George Hart wrote:
Henry,
Here is one solution to your problem, but this approach doesn't require right regular cylindrical polyhedra. Permitting more general strut shapes allows for a simple algorithm. It scales well to large graphs as it is based on many small convex hull operations in local neighborhoods:
George Hart, "An Algorithm for Constructing 3D Struts," Journal of Computer Science and Technology, 24:1, 2009, pp. 56-64.
http://jcst.ict.ac.cn:8080/jcst/EN/Y2009/V24/I1%20%20%20%20%20%20%20%20%20/5...
http://www.georgehart.com/rp/Algorithmfor%20Constructing3DStruts.pdf
George http://georgehart.com/
On 6/4/2013 8:53 AM, Henry Baker wrote:
I've been hacking some code for building 'networks' in 3D out of 'nodes' and 'links'.
Here's the problem.
I have a very large undirected graph -- e.g., O(10^6) vertices/faces/edges -- that I want to embed in 3D.
I make an assignment of vertices to 3D points, and would then like to 'link' these points together with 'links'/'struts' which are right regular cylindrical polyhedra.
Thus, given points P1=[x1,y1,z1], P2=[x2,y2,z2], I want to 'link' P1 to P2 with a 'strut' whose cross section is a regular n-gon (e.g., equilateral triangle) of some fixed size (e.g., side length = 10 millimeters).
For the moment, I will completely ignore the problem of choosing the 3D locations of the vertices so that the struts do not interfere/intersect -- except where two (or more) struts meet at a vertex node. (This will be easy if I construct the graph embedding in the first place with no such interferences/intersections.)
We thus assume that we have a 'good' embedding of vertices/nodes in 3D such that the struts don't interfere/intersect except at the vertices/nodes themselves.
Note that when we have a 'strut' from P1 to P2, the line down the exact center of this strut goes exactly from P1 to P2.
However, the angles/faces where two such struts meet can be quite complex.
Thus, the only degree of freedom for the strut from P1 to P2 is the _rotation angle_ of the strut around the line from P1 to P2 as the axis of rotation.
I'd like to minimize the complexity (in terms of the number of faces/facets) of the overall structure, which means minimizing the number of faces where the struts come together at the vertices.
Consider one of the simplest examples: a complete graph of 3 vertices joined by 3 edges/links, which I embed in 3D as an equilateral triangle.
I want the links to have cross-sections which are regular n-gons -- e.g., triangles.
I could choose to have the 'flat' part of all three struts on the _outside_ of the big triangle linking the 3 nodes. Each pair of struts would meet at a 60 degree angle and generate no additional faces.
Or I could choose to have the 'edge' part of all three struts on the _ outside_ of the big triangle linking the 3 nodes. Each pair of struts would still meet at a 60 degree angle and generate no additional faces.
But I could choose _any angle_ for one strut around its long axis, and -- so long as I choose the _same angle_ for the other two struts -- I can still arrange for the struts to meet at the vertices/nodes with no additional faces.
I.e., the complete graph of 3 vertices and 3 edges has only 1 degree of freedom.
Q: what happens if the location assignment of the graph to 3D is no longer equilateral? Am I now forced to have additional faces?
A: No, we can still have simple joins. Proof: look at the 3 planes which are the angle bisectors of the embedded triangle. When 2 struts meet at such an angle bisector plane, they intersect the angle bisector plane at the same triangle if their rotation angle about their long axis is the same. Thus, _any_ embedded triangle still has exactly 1 degree of freedom: if we choose the rotation angle of any 1 of the 3 struts, the rotation angles of the other two struts are constrained to be the same.
Q: what happens with more complex objects -- e.g., what happens if I start with a _planar_ graph & use a location assignment that preserves its planarity. What exactly do the nodes look like where the struts come together at random angles?
Q: what happens with non-planar embeddings -- e.g., a graph that looks like a regular (or perhaps non-regular) tetrahedron?