TopoSynth: Incorporating Cosm

Posted on August 26, 2010 by moniker

I’ve finally completed all of the basic topological operations for TopoSynth and am now moving on to treating the dynamics of the system.  This last rule involved figuring out how to connect two extended vertices together when they collide.

For example, in the above image, there are 2 vertices that have been progressively extended, leaving a tail behind.  The vertices being extended are at the tip.  If these vertices happen to collide (or any other vertices for that matter), I want a way to merge them in such a way as to create a handle and thus preserve the 2-manifold nature of the mesh.  Simply connecting them with an edge isn’t a solution since that would either break the 2-manifold or create an extremely awkward face.  Instead, what I do is a multi-step process of deleting each vertex, which leaves 2 faces behind.  This is a kind of reversestellate operation.  Then, I join the 2 faces together with a pipe creating a seamless connection between the previously disjoint sections of the mesh.

As an illustration of the delete-vertex operation, imagine the mesh on the left and we want to delete vertex 93 in the middle.  When the operation is done, vertex 93 will be gone and a new face consisting of all of the vertices connected to vertex 93 by an edge will be left behind.  This operation is easily carried out by circulating around all of the face vertices of vertex 93 and successively adding the face vertices not connected by and edgeto vertex 93 to the new face.  To finish, simply delete the vertex, all of its face vertices as well as the edges and the face vertices they link to vertex 93. The face vertices in dark blue circles are the ones that will be deleted in addition to the vertex 93 face vertices.

Cosm

One of the problems that came up when testing this out was how to direct the vertices near enough to each other to connect them in a nice way.  There’s the typical procedural methods using splines to model the transition, but in TopoSynth, mesh vertices are more like a kind of super-particle that contain their own ways of interacting with the environment.  Eventually, I’m going to be incorporating fields and other forces into the system, so I decided to integrate some previous particle dynamics work we’ve done in Cosm.  Cosm already incorporates basic dynamics and most importantly collision detection.  This allows me to direct the topological operations based on particle movements and collision events.

I incorporated Cosm into TopoSynth by replacing the notion of a vertex with a particle aka a cosm.nav (with nav being a directed point in space).

A cosm.nav consists of a position in world space and an orientation defined by a quaternion.  This is why vertices are not drawn as points, but instead as circles with a perpendicular line.  The line depicts the direction the nav is facing while the circle indicates xy-plane of the local coordinate system.

Right now, I’m trying to get more control over the dynamics (e.g. how one vertex meets another while both are moving), thinking over how rule definitions for dynamics and behavior will be described, and what the overall control flow of the system needs to be to make sure the mesh stays valid as do the elements rules are operating on.  For example, if a rule deletes two vertices, that rule gets killed, but what happens to other rules that might refer to the vertex in some way?  Another big challenge is figuring out how to provide a high-level interface to placing rules on the mesh without having to assign them individually by hand.  There’s a lot of approaches to play around with, and now that the nitty-gritty of the topological operations is taken care of, the fun part of figuring out how to compose with the system begins.  Here’s a first render of an example, perhaps a little hard to read, but I’ll post it anyway.  Expect more soon…

Posted in Computational Composition, Computational Technique, Software Engineering | Tagged , , , | Leave a comment

TopoSynth: Topological Structure

Posted on August 23, 2010 by moniker

DLFL Background

As I had mentioned in the last post, the topological inspiration for TopoSynth is derived from TopMod and particularly the doubly-linked face list (DLFL) data structure.  The DLFL makes it particularly straightforward to always maintain a 2-manifold mesh structure as mesh transformation operations can all be expressed in terms of 4 primitive operations:

  1. Insert vertex
  2. Remove vertex
  3. Insert edge
  4. Remove edge

Any other operation can be constructed in terms of these primitive operations.

A lot of mesh representation structures maintain double representations of edges, which are typically called half-edges, where each half-edge is opposite in direction to its other half (e.g. v1->v2 and v2->v1).  The idea here is that each half-edge belongs to a different face.  To get to the other face, one simply uses moves from one half-edge to the other.  In contrast, the DLFL maintains a single edge for any pair of connected vertices, saving memory.  The difference compared to the half-edge representation is that the vertices on either edge belong to different faces.  In fact, the trickiest conceptual leap to make in understanding the DLFL is that there are actually two different types of vertices: actual vertices and face vertices that shadow the actual vertices.  When I say that an edge connects vertices on different faces, I mean face vertices not actual vertices since actual vertices effectively belong to many faces whereas face vertices belong to a single face.  Face vertices are basically a per-face proxy for actual vertices.  Thus, if a mesh is made of quadrilaterals, each vertex will belong to 4 faces and have 4 face vertices.

Here, each actual vertex is given a unique number and the black face vertices are clustered together.  Edges are the dotted blue lines.  Notice how they connect face vertices across faces.  This is the key attribute of the DLFL.  Each face in the DLFL also maintains a doubly-linked list of its boundary face vertices.  The direction of the pink and grey arrows indices the sense of the face boundary.  Pink arrows are in the direction of the blue edges while grey arrows are not.

For the DLFL to work properly, the mesh must always be a 2-manifold geometric complex.  This means that not only must every edge belong to two faces, but the orientations of edge-abutting faces must be opposite in direction.  One way to think about it is that when circulating a face, if traversing from v1->v2 is given a value +1, then when traversing another face that goes from v2->v1 the value -1 is given and v1->v2 + v2->v1 will sum to 0.  If all such traversals sum to 0, then the mesh is a geometric complex.  Effectively this means that face normals must all face either outward or inward.  There can’t be a mixture.  The four primitive operations listed above are implemented such that these conditions always hold.

TopoSynth Operations

TopoSynth operations, as in TopMod, are implemented over the primitive operations such that the 2-manifold condition is always maintained.  Unlike in TopMod, however, the operations are not simply applied as mesh sculpting events one at a time, but instead are micro programs attached to mesh elements such as vertices, faces, and edges.  In this sense, they are akin to rules in StructureSynth with the addition of a more elaborate context sensitivity.  StructureSynth is context sensitive in the sense that rules terminate under certain global conditions related to primitive size (is the rule producing visible shapes) and total number of primitives (has the max number of shapes been generated).  TopoSynth rules have an additional context sensitivity related to their immediate spatial neighborhood.  For example, a rule can be written such that a face is pulled in a particular direction, but when it approaches another face, it attaches itself, creating a handle.

The more involved TopoSynth operations are built on a combination of spatial partitioning and standard mesh operations.  The basic operations include face extrude, vertex extend, stellate, etc.  How these are built into TopoSynth operations is the subject for another post.  Below are the basic extension and extrusion operations.  Extend pulls a vertex in a direction, splitting each edge in half that links to the vertex and forming a ring of edges to connect the new midpoints.  Extrude pulls a face out in a direction, creating a new ring of faces.

Posted in Computational Composition, Computational Technique, Software Engineering | Tagged , , , , , | Leave a comment

TopoSynth

Posted on August 16, 2010 by moniker

Ever since I found out about the excellent Structure Synth program, I wondered what it would be like to apply the same concept to topological operations.  Structure Synth works by writing rules that describe a pattern of transformations.  The transformations can be spatial or they can operate on the colors.  When the interpreter processes a rule, it applies the transformations to a terminal node, which can be a primitive shape like a box or sphere, or more interestingly, another rule.

The beauty of Structure Synth, and similar systems like Context Free, is that a simple rules can end up building complex and surprising forms by virtue of how they are connected.

scout

While these structure can be quite stunning, there are quite a number of reasons why one would want to move beyond a haphazard collection of objects in space to something more reified such as 2-manifold meshes or a at least a guarantee of non-intersecting objects.  Instead of just repeating primitive shapes under transformation, I’d like to see how this could work by operating on mesh vertices themselves.

As a paradigm for operating on the mesh, topological operations are going to be both the most interesting and generally applicable.  One need only look at what the topological meshing software TopMod is capable of to imagine the power of topological processes.

Whishboneahedron

After doing some research about this, it seems I’m not the only one with this ideas.  In a paper on grammar-based approaches to pattern making, the author of Structure Synth mentions as much when speculating about possible directions it could go in the future.

I’ve been working on TopoSynth for about a week now and have a pretty good handle on how it’s going to work.  The most difficult part was finally coming to a clear understanding of how TopMod works and getting to the point where I know enough to easily write my own topological operations.  For background research, there’s the sill-in-draft TopMod book, but truth be told, nothing is better than stepping through the source code or better yet, writing your own version.  I ended up writing my own take on TopMod in Lua, which is what I’m using to prototype TopoSynth.  I’ll be posting my findings shortly, but first here’s a teaser rendered with PBRT:

Posted in Computational Composition, Computational Technique | Tagged , , , , , | Leave a comment

Facing Autotools

Posted on July 29, 2010 by moniker

One of the essential features of a good software package is that it is both portable and straightforward to build.  When working on a system (Linux or even OS X) with a UNIX shell, the most common build tools are the dreaded Autotools.  I say dreaded from a developer’s perspective.  From a user’s perspective, it’s usually only takes invoking

./configure && make

to build a well-designed software package.

On the developer’s end, there’s the seemingly Byzantine world of autoconf, automake, auto-whatever and the unfamiliar world of M4 macros and under the hood magic. At first, when faced with setting up a portable build system, I tried to roll my own using Lua scripts. It worked quite well … until other people needed to use it. When that happened, things started to fall apart under the weight of all of the contingencies I had to keep track of, so I dove into the world of Autotools.

Going through the manuals and trying to understand the terminology with no reference points is incredibly frustrating. I managed to get a decent understanding of how things works, but I still wasn’t able to setup a build system to handle the complicated structure of LuaAV. Fortunately, John Calcote has just published a book called Autotools: A Practitioner’s Guide to GNU Autoconf, Automake, and Libtool. I highly recommend it. It’s clear, explains the terminology well, and is as much of a pleasure to read as such things can be.

Posted in Software Engineering | Tagged , , , | Leave a comment

Fast Multipole Method

Posted on July 20, 2010 by moniker

To get a better intuition for how the Fast Multipole Method (FMM) approximates n-body interactions, I implemented the equations in Mathematica along with the exact solution. Below are some plots for different situations.  The thing to keep in mind is that the FMM is valid only a certain distance from the center of the particle cluster, so it’s expected that the approximation will not be accurate in that region.

The first row shows contour plots of clusters of 3 and 40 points and a difference between them.  With the difference plot, I was trying to get a sense of how the potential field varies under differing conditions.

The second row is again for 3 and 40 points with a difference.  The cutoff spike in the difference surface is an artifact of numerical evaluation.  Since the potential in 2D is logarithmic, near the particles it tends to blow up.  The coloring of the surfaces follows the phase of the potential.  With 3 particles, there potential wave has 3 clear periods while with 40 particles, it starts to get noisier (an artifact of sampling), but there are likewise 40 periods.  The reason the number of particles matches the number of cycles is from the linear summing of the phase term.

The last row shows the electrical field as derived from the complex potential.  The two images are for 3 particles with the one on the left being exact and on the right calculated from the FMM method.  These plots only show the calculation of the multipole expansion.  To actually implement the FMM as a solution of the n-body problem, someadditional techniques for manipulating the multipole expansion are required.

The FMM simplifies the n-body problem by relating clusters of particles to other clusters of particles.  As the multipole expansion shows, the affect on the potential field a cluster of particles generates can be easily calculated.  The trick now is to figure out how to incorporate the multipole expansion into a hierarchical data structure without having to recalculate it at every single level.  Instead, what we’d like to do is calculate the multipole expansion at the lowest level and accumulate the expansions up the hierarchy through a simple summing of terms.  The problem is that each low-level expansion is centered at a different point, so we need to be able to translate the expansions to the center of higher-level (parent) cells.

The translation lemma shows how to accumulate the multipole expansion into coarser clusters, which can dramatically speed up the calculation for faraway clusters.  This is the bottom up step of the FMM technique.  As has been emphasized a number of times, however, the multipole expansion is only valid for well-separated clusters that are a certain distance from each other.  This means that only clusters that are faraway can be treated this way or, alternatively, we can reduce the size of the clusters in order to apply the technique to closer in clusters.  In order to do this, each box in the hierarchy is given an interaction list..  The interaction list says which boxes interact with each other.  The interaction list consists of all of the child nodes of the neighbors of a box’s parent node not bordering it.

At each level, the interaction list covers a smaller and more refined area of the space.  Any area not covered by the interaction list, which is essentially those boxes at the finest level bordering the box under consideration, are calculated using the O(N^2) n-body method directly, but these calculations should be quite minimal.

In the diagram above, the pink box affects affects the blue boxes.  In order to make use of the multipole expansion, the expansion within the blue boxes has to be recentered on the pink box since expansions can only be summed in a simple way if they are centered on the same location.  This process is described as converting a multipole expansion into a local expansion where local is the pink box.

Once this calculation is done, we have a description for the effects of every particle outside the box, except for those nearest neighbors, and can evaluate their effects simply by plugging in the locations of the particles in the box into the sum of all of the multipole expansions.  This sounds like a lot of work compared to the O(N^2) formulation, but for thousands or millions of particles, it’s vastly more scalable.  The trickiest part is all of the bookkeeping that has to be done to shift the multipole expansions around the space and up and down the spatial hierarchy.  The payoff though, once it’s encoded in a easy to use software package should be significant and we won’t have to think about the hairy details so much anymore and can get to figuring out what massively detailed particle simulations can be used for in terms of spatial composition.

Note: The lemmas posted above were taken from Greengard and Beatson, A Short Course in Fast Multipole Methods.

Download: FMM Mathematica Files

Posted in Computational Technique, Research Literature | Tagged , , , | Leave a comment

N-Body Problems

Posted on July 8, 2010 by moniker

N-Body problems inevitably come up when doing any most any kind of physical simulation work, particularly when particles are involved.  N-Body problems appear whenever the particles in a system construct a field that in turn determines their dynamics.  The classic examples are typically gravitational, but the n-body problem equally applies to electrostatic, electromagnetic, fluid dynamics, and even acoustic scattering problems.  All can be formulated in essentially the same way just with different constants.

At first sight, n-body problems have a runtime complexity of O(N^2) since every particle interacts with every other particle.  While this is not a big deal for small numbers of particles on the order of a few hundred, the amount of calculations required quickly exceeds what even the speediest of computers can handle.  The challenge is to somehow reduce the complexity to something like O(N log N), which is actually tractable for millions or even billions of particles, making something like the Millenium Simulation Project possible.

Fortunately, there has been a lot of work done in this area since the late 80′s and 90′s for cosmological and electrostatic simulations, particularly by Greengard and Rokhlin.  Together, they developed the Fast Multipole Method (FMM), which makes use of the math of complex analysis of harmonic functions to reformulate the n-body problem as O(N log N).

While this might sound complicated, the essential insight is straightforward and rather enlightening.  The simplification the FMM is based on recognizes that the field a clusters of particles generates, when viewed from a certain distance, can be simplified to a single point that approximates the actual field.  It’s akin to performing a simulation of the earth and sun where the mass of each body is taken to be at a point located the center of mass instead of spread out in space in a sphere.

FMM

The above images were generated using the FMM technique.  The red points in the middle are the particles, each with an equal charge.  The surface represents the potential generated by the points withe the coloring representing the phase.  With one particle, there’s one cycle of a wave around the place.  With 7 particles, there are more cycles as the waves generated by each particle interfere.  The FMM approximation is akin to a spatial wavelet transform.  This is the 2D case.  In 3D, the FMM method uses spherical harmonics to approximate the potential.

While the above surfaces represent electrical potential, what we actually want is the electric field.  The electric field gives the forces acting on the particles and is used to update the simulation.  Fortunately, the electric field can be derived directly from the potential by taking its derivative.  This works because we’re working with complex numbers.  With purely real numbers, the phase information is missing, and the electric field cannot be determined without phase.

One useful way to think about simulations is in terms of Lagrangian and Eulerian paradigms.  The Lagrangian perspective is essentially that of the particle.  Information moves through space according to the dynamics involved.  The Eulerian perspective is of a lattice or field, where fixed discrete points in space sample the dynamics.

In the case of the FMM, the n-body problem is simplified by converting the usual Lagrangian formulation into a hybrid Lagrangian-Eulerian algorithm where clusters of particles become instead waves in space.  This conversion only holds a certain distance away from the cluster, so nearby particles must be treated in an purely Lagrangian manner.

This technique is of course not new.  Spectral methods are used in all kinds of ways to quickly process point-wise spatial information, but such techniques have yet to be placed in the context of spatial composition where there is a continuum between field and particle.  FMM lies at the boundary between the two, and it will be interesting to see how working with the diametrically opposed conceptualization of spatial information can be brought together in a rigorous yet intuitive manner.

References:

Posted in Computational Technique, Research Literature | Tagged , , , , , , | Leave a comment

Chemical Automata

Posted on July 5, 2010 by moniker

I first came across Chemoton (Chemical Automaton) Theory a few months ago when reading a paper entitled Software Replica of Minimal Living Processes, and ever since it has been an inspiration.  At the time, I was trying to figure out how I could possibly build a system that spanned the range of complexity from Chemistry to a minimal Biology.  I was going off of Walter Fontana’s incredible Algorithmic Chemistry work, trying to find a way that his Lambda Calculus approach could become spatial.  It was Ganti’s Chemoton Theory that finally got me there.

Incredibly, the publication of Chemoton Theory in 1971 and subsequent refinement in the early 70′s was practically simultaneous with Maturana and Varela’s Autopoiesis work and Manfred Eigen’s RNA Hypercycles Theory.  Chemoton Theory, unlike Autopoiesis, is based on a very precise model, though simplified, model of chemistry.  In recent years, Ganti has even gone so far as to detail what actual chemical reactions could possibly realize a Chemoton.  Autopoiesis provides no such precision although the work of Pier Luigi Luisi has taken it much further in that direction.

A Chemoton is a network of 3 autocatalytic cycles: the metabolic (energy), template replication (information), and membrane (boundary/dynamics).  Together, they model a minimal living entity as they meet Ganti’s basic criteria of a living system:

  • it’s an individual unit
  • it performs metabolism
  • it’s inherently stable despite constant transformation
  • it has an information subsystem that programs the whole
  • it’s processes are regulated and controlled

I’m, of course, leaving out a lot of the details so this may not seem like a full definition of a living system.  For the complete explanation, see Ganti’s paper Biogenesis Itself or even better his book The Principles of Life.

What’s most intriguing about the Chemoton from a worldmaking standpoint is it’s fluid nature.  Chemical reactions function best in a fluid environment where spatiality is subsumed by chemical concentrations and statistical tendencies.  There doesn’t need to be a strict spatial ordering for Chemotons to function, just the appropriate chemical concentrations bounded inside a membrane.

Chemoton Theory shows in precise detail how to go from chemistry to a minimal biological unit, but it doesn’t say much about the structure of the membrane or how networks of membranes might form into more complex biological structures.  In the end of Chemoton Theory vol. 1, Ganti speculates about how computers might be built from such objects, but doesn’t link it to Morphogenesis or Topobiology.

Posted in Research Literature | Tagged , , | Leave a comment

worldmaking

Posted on June 27, 2010 by moniker

worldmaking is a site dedicated to exploring how to make worlds: spaces and systems that accumulate complexity.  The site weaves together the spaces of computation, cybernetics, poetics, mathematics, biology, among others, through observations, musings, and, above all, software experiments and techniques.  The best way of knowing is making.

Posted in General | Leave a comment