Glambient: animating tilings with symmetry constraints

Glambient is a computer program for exploring periodic tilings. This page describes the internals of the software.

Basic Notions

The topology describes which points are connected to each other, and by which edges. The actual positions of the points are not included in the topology. The topology allows a certain number of degrees of freedom, or dofs for short. If there are more points in the topology, there are more different ways that it can wiggle, and more degrees of freedom. The number of dofs is roughly twice the number of points.

The state assigns a position to each point in the topology. A state allows you to actually draw the topology on the screen.

A space is a continuous range of possible states, but with fewer degrees of freedom than the entire topology. The space is restricted by constraints that determine which states are part of the space and which are not: each constraint removes a degree of freedom from the topology. If the constraints are visually obvious, then any state within the space will look symmetrical in some way. A space with zero degrees of freedom contains exactly one state.

In addition to the symmetry constraints, the sanity force restricts the current state to one that makes sense for a tiling - it resists entering states in which two edges of the tiling would cross each other, for example. It is a force rather than a constraint because it doesn't reduce the number of degrees of freedom in the current space, it just sets some limits on them.

User Interface

The glambient application allows a user to edit tilings by performing a number of operations on topologies, states, and spaces.

Dragging a point changes the current state. The application will try to find a state in the current space that allows the point to follow the user. The current space may not contain any states that exactly match what the user is asking for, in which case the point will not follow the user exactly. The sanity force will also stop the user from creating self-intersecting tilings.

Wandering through the current space. This animates the current state, moving it through the current space. The state is also subject to sanity forces.

Splitting an edge, by creating a new point in the topology and adding two degrees of freedom to the current topology and space.

Deleting a point, modifying the topology and removing two degrees of freedom from the current topology and space.

Creating a symmetry by finding a likely relationship between two edges in the current state. This removes two degrees of freedom from the current space (the topology is unchanged).

Releasing a symmetry, which restores two degrees of freedom to the current space (the topology is unchanged).

Opening a tiling file.

Saving the current state, space, and topology to a tiling file.

Known Major Bugs

At this time there is at least one bug that trashes memory, probably related to freeing constraints.

Freeing / releasing constraints often picks the wrong constraint to release and may screw things up completely. Avoid if possible.

Deleting vertices may crash because it takes the tiling through a temporarily inconsistent state.

Memory management is simply not dealt with: the model for using the program is to save your work and restart the program every now and then. Without a programming language that supports garbage collection, releasing memory is very hard to deal with.

Internal data structures

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.

This page is part of Nixweb.com.
All content © 1996-2008 Nick Thompson unless noted otherwise.