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

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.
**dofs**

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.