The input to **Lang's Universal Molecule Algorithm** is a topologically embedded metric tree
and a special kind of convex polygon we call a Lang Polygon. The output is a crease pattern for which there exists
a folded realization as a uniaxial base whose shadow tree is the input metric tree. The figure below illustrates
the input and output for the algorithm.

**The input/output of Lang's Universal Molecule Algorithm.**

The algorithm works by a **parallel sweep process** in which the edges of the Lang polygon are moved
inwards in a parallel fashion at constant speed. The interior sweeping polygon is called a contour.
The distance the edges have moved at any point in the sweep process is called the height of the
contour.

**The parallel sweep process.**

Edges of the crease pattern are created by tracing the paths of the vertices of the polygon (see figure below).

**The crease pattern edges (red and blue) are created by tracing the vertices of the Lang polygon during the sweep.**

As the contour sweeps inwards, an edge between two marker vertices maintains its length, while an edge between a marker and a corner shrinks. This corresponds to a shrinking of the tree by moving the leaves inwards. In the figure below, the pink tree (right) superimposed on the input tree corresponds to the contour (left) in the sweeping process. The distances between markers for b1 adn b2 along the contour do not change during the sweep, which is reflected in the shrinking tree.

**The crease pattern edges (red and blue) are created by tracing the vertices of the Lang polygon during the sweep.**

At certain discrete heights, one of two events occurs. A **contraction event**
occurs when an edge between a corner and a marker vertex shrinks to a single point. Note that all
leaves incident to the same node, shrink at once.

**A contraction event.**

In a **splitting event**, the distance between two corner vertices is equal
to the distance between the corresponding leaf nodes. At this point, if the sweeping process
proceeds, the contour would cease to be a Lang polygon. In the illustration
below, the distance between leaves a1 and a2 in the shrunken tree is equal to the distance
between vertices a1 and a2 in the contour.

**A branching event.**

The contour is therefore split by adding an edge between the two corner nodes. Marker nodes are added along this new edge so that the edge corresponds to the path in the tree between the two leaf nodes.

**Splitting the contour at a branching event.**

In the tree, this split corresponds to a splitting of the tree into two trees along the path between the two leaf nodes.

In 3D the sweeping contours correspond to a sweeping process of the shrinking tree upwards by the height of the contour.

**The sweep in 3D.**

Conceptually, the sweeping process is a continuous process with discrete events. The algorithm, however, works by identifying the height of the next event, and by recursing on the contour and sub-tree at that event. The base case is when the next event is a contraction of all edges to the same vertex. In the illustration below the gray lines represent the actual discrete event contours on which the algorithm is invoked. The intermediate sweep lines are generated for illustration purposes only.

**The gray lines indicate the actual contours that the algorithm recurses on.**

The **polygon editor** on the right allows you to drag the corner
points of the doubling cycle to turn it into a Lang polygon. Red dotted lines between
corner vertices represent vertices whose distance is less than their corresponding
distance in the tree, thus violating the definition of a Lang polygon. Once all of
these constraints are removed, you will see only the green polygon.

**Note:** In the current version it is possible to invert the ordering of the polygon
nodes such that the walk of the tree corresponds to a clockwise, rather than counter-clockwise
walk of the polygon. In this case the vertex labels will fall inside the polygon rather
than outside it and the output is undefined, since our implementation assumes that the
walk of the inner face is counter-clockwise. Future updates will address this limitation.

Once you have a polygon defined, drag the sweep slider above the the polygon editor to view the sweeping process as it generates the crease pattern. You can continue to edit the vertices of the polygon and see the crease pattern update live. If, however, you modify the tree, you will need to click on the "››" button to generate a new doubling cycle for the tree.

This version does not show the 3D uniaxial base for the crease pattern. We also have a live demo which visualizes the 3D base as well. This demo requires that Java's implementation of OpenGL be allowed to run on your computer and thus requires that you grant the applet special permissions when it is run. If you want to run that version, please click here, and accept whatever Java dialogs are presented.

In the polygon edit window (left), the scroll wheel (or two finger scroll on a Mac laptop) can be used to zoom in and out.

**Note: This applet requires Java 1.6 to run.
Also, we have experienced problems running the applet in Safari 5.1.2 (Safari 5.1.3 appears to
work fine). If you experience
any problems running the applet, please try a different browser (e.g. Google Chrome or Firefox). If this does not
work, please send an email jbowers "at" cs "dot" umass "dot" edu.**

Click on the section headings or arrows to open and close them. Java applets may load slowly the first time.

← back