How It Works
Topology
The topology is maintained as a "winged edge" data structure.
Each edge is actually represented as a pair of directed edges.
This simplifies quite a bit of code! Each directed edge keeps
track of one endpoint of the edge, and sits in a doubly linked
list of all the directed edges that reference that point. the
list of edges is sorted by angle, so the next edge around the
vertex can be found be looking forward or backward in the linked
list. Each directed edge also points to a facet structure, one
for each side of the edge.
Walking around a facet to draw it is far more complicated than usual
because the topology is embedded in a torus. There is a
valid tiling that contains only one point, two edges, and one square
facet! When walking around this facet to draw it, every corner of
the facet is the same point as far as the data structure is concerned,
so the program has to keep track of how many times it's wrapped around the
torus in each direction to figure out whether it's come back to the
starting point or not.
Constraints
Constraints are represented as rows in the matrix equation
Ax=b. The number of columns in A and rows in
x is the number of degrees of freedom in the topology.
Doing a singular value decomposition on A makes
it easy to find a state x0 that satisfies Ax=b
and a set of basis vectors that span the rest of the solution
space. Restricting the user to states that are in the given
space is quite easy given the basis vectors.
Forces
The sanity force is not as mathematically tractable as the linear
constraints. Since it can't be expressed in the constraint matrix,
a general purpose multivariate optimizer is used. Currently there
is a small Nelder-Mead simplex method solver that restrains the
interactive user or wandering force if it approaches a self-intersection.