Wednesday, December 3, 2014

Unit-weaving voxel surfaces

A unit-weaving pattern for the enveloping surface of a union of voxels. The weavers are four squares long. The black squares are holes in the fabric. The dashed lines are voxel boundaries. (Alternatively, the corners of the voxels could be centered on the holes.) In either case, if the weave pattern is made up of unit squares, the modulus of the votels is the square root of 5. 

The over-and-under of weaving can play tricks on the imagination—for example, when weaving a non-orientable surface like a Klein bottle. The reliable way to picture an over-and-under weave is as a chess-coloring of a four-valent map. (A map is a generalization of a polyhedron we are no longer concerned with measurements of angle and distance, i.e., geometry, but only with the way the polygonal faces are mated with each other and the way the surface connects to itself; i.e., we are only concerned with topology.)

Starting with any map we can convert it to a chess-colorable, 4-valent map via the map operation medial. In this way we can discover a way to weave any tessellation of any surface, orientable or non-orientable. That's the universal method.

For special maps there may be alternative ways to do the weaving. For example, if the original map is already 4-valent and chess-colorable there is no need to take its medial, the original map is directly weavable. The dual of a 4-valent, chess-colorable map is a quad-faced, bipartite map. Thus, if we are given a quad-faced, bipartite map we do not need to take its medial—we can simply take its dual and weave that. As an example of the difference the choice makes, consider the map of a cube: it has 6 quad faces and its vertices can be colored black and white in such a way that no two adjacent vertices have the same color (in other words, the map of a cube is bipartite.) If we weave the map of a cube using the universal method we will end up with one weave crossing for every edge in the original map: a total of 12 weave crossings. If we use the special method (i.e., we directly weave the map's dual) we will end up with a crossing for each face in the original map: a total of 6 crossings. The special method yields a coarser and simpler way to weave the same surface.

A commonly encountered surface that is quad-faced and bipartite is the envelope of any union of voxels. Clearly such a surface is quad-faced. It is also bipartite because the entire 3-D, Cartesian mesh of unit squares is can be vertex 2-colored such that no two adjacent vertices have the same color. When we sculpt a union of voxels out of this space, the vertices can keep their colors. Left in view is a surface that is clearly bipartite.

Alternate ways to unit-weave a voxel whose modulus is the square root of five times the weaver width.

No comments: