Make It Tile User's Manual

Topology Mutation |

Even after a topology has been created, its vertex, face, and edge relations can still be modified in restricted way.

This topic contains the following sections:

Edge Pivot and Spin Operations

The topology data structure does not allow for the addition or removal of elements once created. But the relations among them can be altered pivoting and spinning edges. A pivot keeps the near vertex or face as it is, but moves the far vertex or face clockwise or counter-clockwise to the next vertex or face. A spin is essentially two pivots; first the edge being spun is pivoted, and then its twin is pivoted around its own near vertex or face, which is the far element of the original edge.

These operations can be performed on an instance of Topology, using functions such as PivotEdgeForward or SpinEdgeBackward. As elsewhere, forward refers to clockwise rotation, and backward to counter-clockwise rotation. If an instance of TopologyVertexEdge is passed to one of these functions, then the pivots happen around the near vertex, and no face relation changes for the edge being modified (though other edges will necessarily have face relations changed). If an instance of TopologyFaceEdge is passed instead, then the near face is the element to pivot on.

Using these operations will increase the number of neighbors that some elements have, while decreasing the number of neighbors that other nearby elements have. A spin operation, being a pair of pivots, is more balanced, such that spinning a vertex edge does not change the neighbor counts of any faces, only vertices, and spinning a face edge likewise does not change the neighbor counts of any vertices, only faces. This can be a useful property if, for example, you start with a topology of hexagons, and you want to ensure that no matter what, every vertex continues to have exactly three neighbors. (Among other things, this avoids any undesirable effects of diagonal movement common in square grids, where some faces touch each other only at a single point, due to vertices having more than three neighbors.)

Full Topology Randomization

If the purpose of mutating a topology is to jumble it up, randomize it so that the tiles do not adhere to a highly ordered and thus predictable pattern, the TopologyRandomizer class can assist. It essentially performs a series of random edge spin operations, taking care to massage the manifold's vertex positions back into an acceptable state as the process advances.

It performs this process in one or more passes. After each pass through all edges, some relaxation and repair passes are performed to fix up any positional anomalies produced in the main pass. These anomalies are due to the fact that the main pass alters the topological relations only, and does not adjust vertex positions or any other attributes at all. Faces are likely to become concave or even inside out during the main pass.

The relaxation passes attempt to gently nudge vertex positions around in order to conform to certain constraints. The two constraints implemented by Make It Tile aim for regularity and equal per-face area, respectively. Regularity refers to polygon regularity. This constraint prefers that all edge lengths be equal, but it strongly biases faces with more neighbors to be significantly larger than faces with fewer neighbors. The equal area constraint on the other hand prefers all faces to have roughly equal area, but it tends to produce irregular polygon faces and edges of varying lengths. The two constraints can also be blended with each other, with any desired proportional balance between the two, and other constraints that you wish to implement yourself can be used in their place or blended with them.

The repair pass is more of a blunt process to correct for any egregious errors produced in the main pass and not fixed by relaxation, as well as such errors that are actually produced by the relaxation pass. These are errors of concavity or more serious flaw in the shape of a face.

See Also