Tuesday, November 18, 2008

stand back, I'm going to try biology



(notes from a 1994 copy of Molecular Biology of the Cell, a cheeky Russian has posted all images (and russian text) from the textbook here.

Geometric Strcture in the Early Vertebrate Embryo

The head to tail axis (anteroposterior)is already defined in the un-fertilized egg, however the back to stomach (dorsoventral) axis of the fertilized egg are only defined by where the sperm enters the cell. Roughly the sperm enters the egg around about your belly button (or rather causes your belly button to appear there). This is a clear data point in the nature/nurture debate - which way up you are is defined by the point where a sperm first touches the egg, a very chaotic event.



After a while we have a bunch of cells packed into a membraney sack. The shape they make is an interesting one - basically packed spheres within a larger spherical shell. Space subdivision based on membrane tension, rather than distance-to-a-point.This is very similar to soap bubble patterns. There are equations defining their shape at their boundaries, (the link is worth following for the pretty renders of bubbles). Something similar shows up up in weighted Voronoi tesselations as well.

Sodium is pumped into space between the cells, and via osmosis water follows. This forms a single cavity with a cruchy shell of cells. This leaves room for the wonderfully titled gastrulation, a process, it seems, whereby an arse appears and grows into a mouth. (This explains a lot about what comes out of people's mouths). Seriously - an indentation grows that forms the anus, then continues up to create a mouth. This shapes the cell into a torus around the nascent digestive system.


But where does this indentation come from and how is it controlled? A homogeneous structure suddenly creates this balstopore lip that becomes a digestive system. If you splice a second lip into a developing creature, both digestive systems grow and you end up with something non too pretty:-

This lip was one of the original organizer features documented and has the name Spearmann's Organizer. It's initial formation seems to be a result of regulative development (several cell movements in combination with morphogenic fields) and it goes on to control a lot of important growth functions in early embryos.

Regulative Development

The two extremes that define development.
  • Mosaic development - pattern of the body determined by features of the egg
  • Regulative development - body determined by cell-cell interactions after fertilization
Once again these are the ongoing nature/nurture (compiletime/runtime; creationism/evolution) principles. I don't think I can really study mosaic development, it seems to be fairly unknown (and as the output of an evolutionary system, messily complicated), a more productive line of research is Regulative development. Trying to understand genes is hard, trying to understand the physical properties exploited by the gene is much easier (and I have a very low tolerance for comprehending TLA chemicals). Various principles from this field follow:

  • When certain types of cells are adjacent, new cell-division behaviours can be turned on. This induction can happen several times to build up layers of different cells as the adjacency changes. Based on the concentrations of morphogens, cells can develop in different directions. Cell age also has an effect, older cells can behave in different ways to new cells.

cell induction
i) two adjacent regions of cells
ii) new cell type induced by adjacency
iii) strata of cells via induction



  • The concept of function calls appears- "in this way the final specification of how a limb cell should behave is built up combinatorially; first it is supplied with information as whether it is to be a leg or wing then signals within the growing limb bud specify more fine-grained components of positional value, reflecting the precise position within the limb". So a programmer might say that values have been curried into the code for each part of the limb. You can see this in an experiment - if the tip of a embryonic chicken's foot is transplanted onto the end of the wing, you get a wing with a toe on the end; that is the tissue has already been curried (fated) as part of a leg, but doesn't know which part it is yet. (I wish computer science involved experiments like that - I mean just to spend the afternoon splicing bits between embryos is more excitement than the entire cs dept gets in a year, perhaps I should start a wet-lab in one of the terminal rooms that people never use, how about this one mixing up cells in an embryo, just to see what happens!).


  • Cockroaches show another pattern - the parts of their legs seem to know where they are in the sequence, somehow they know their positional values. Through a process called intercalation any missing (ie a mid-portion of leg removed in an experiment) parts are eventually grown back. There's an idea for geometry deformation here - if you have a house, and stretch out a wall sensible house-parts should grow to fill in the space (much like mueller's 2006 paper) .

Linear animals - built end to end, easiest thing to encode for & follows digestive system. makes HOX etc... genes feasible?

  • "Programmed death A C. elegans hermaphrodite generates 1030 somatic cell nuclei in the course of its development, but 131 die" - programmed cell deaths, cells that are "fated" to die. Is it possible for a system to have anti-features? features that cause something to disapear?

  • Cells use a system of morphogenic fields to control features:

sausage cell

For example if you want a feature in the middle of an organism, cells should be programmed to transform in that way if the concentration of red and blue (in the above diagram) are identical. Most of these morphogens are unutterable TLAs, but their production and effects are quite relevant. Experiments that showed these principles included taking a fly egg (Drosphila) and removing some of the fluid containing the morphogens from the head end leading to a fly without a head. If you stick some arse-morphogentm in place of the head field, you get a fly with two sets of abdominal segments.

These fields would be rather robust when dealing with geometric features (if disrupted the system can re-organize itself) and may well prove to be well suited to procedural geometry that adapts to new features. The field effects could also be simulated using Voronoi-like arangements (I'm a bit hooked up on V. diagrams if you haven't noticed).

These fields can be seen as giving input to the growth-algorithm. They certainly solve the problems of symmetry in simple grammars (since diffusion is equal in all directions). There are several techniques that seem to be used - differentiating features by field strength or using a combination of fields, each producing another one -

curves

Note how similar this is to the concept of induction outlined above. It is interesting to note how these fields develop and are used (above) by excreting morphogens based on certain criteria, you can build up harmonic patterns to control feature development. Some of these criteria are:
  • A function of another field strength.
  • Equal strength of a number of other fields
  • Orientation of the field (use the local field gradient for some function).
So each of the harmonic divisions in 4) above can be used as the starting point for a feature/another technique along the length of an animals body.

  • Another technique is shown by the evaluation of "pair -rule" genes. A number of genes(hairy, even-skipped, paired, fushi-tarazu) of different lengths, are activated at intervals of two "segments". Different start-locations for the genes are apparent, and in combination (boolean operations - and, or, not, xor etc...) they can build more patterns.

pair-rule

This is really the idea expressed in Muller's 01 paper, that is used in 2D to positions windows on a façade (a boolean union of 2D pulse functions).
  • If we suddently drop down to later in the development cycle (biologists don't seem to know what goes on between), there is a technqiue for producing occasional features called Lateral inhibition.

differentiation via inhibition

As in i) above all the cells start of with the same concentration of signal. Cells near those with a larger signal stop signalling, the result iii) is that we end up interspersed pattern. In this example each of the selected cells then becomes a mother cell to a clutch of hair-cells, while the remaining cells carry on as normal to become skin. The more complex patterns of stimulation/inhibition using morphogens are best described by Turing (free via the Turing institute).

Final thoughts: how much of this is suitable for algorithmic control? for artist control? the design certainly feels like it comes from the transcend, and is totally uncontrollable, unplannable. If any technique proves to be too complicated for an artist, then morphogenic fields become as good as any? However my first attempt at creating cell membrane using morphogenic fields had positive results in 3 hours -


Monday, November 17, 2008

a841 north of sannox

a841 north of sannox


Fantastic camp & ride around Arran last weekend. This photo was taken in the empty & hilly north of the island; you can just see Ben powering off into the distance. The south of the island was very up-and-down, but none of the large hills from the north. The whole place was so nice and quiet (and sunny) it made it worthwhile despite being shagged by the end of the day.

Thursday, November 13, 2008

engineered emergent behaviour

More morphogenic field playing, using this matrix


{-1f,  0f, 0f},
{10f,-.1f, 0f},
{-2f,  3f,20f}};


(horizontal = cell type, vertical = attraction to field)
(red, green, blue)




We can get double-walled cells! (almost) The white field is the red cell morphogen.


I'm considering that more rules are needed to make the cell-wall continuous and unbreakable. Maybe adding springs between the cells once they've been next to another cell of a certain type for a set period.

[edit] these people have been playing these games since 94.

[edit] this file will run the simulation on your computer if you've got Java 1.6 and webstart enabled. The referenced files contains the source code. Thanks Phys2D!

Monday, November 10, 2008

physics2d games

Still playing with cellular automota in phys2d -

Take some gravity-less balls. (Colours don't mean anything)





Now imagine each gives off a chemical trace-




Make the cells move towards the field. This is kinda-like gravity simulation (but gravity with history). There's also some jiggle in there - "brownian motion" to keep things moving. The cells look about 3x their radius in each of the 4 compass directions to figure out where to go. If they look less than their diameter away, they don't really do much :(




Adding some field decay back in and tweaking some values, gives us patterns that build themselves a potential hole to stay in and start spinning (gravity! there's even a cog arrangement in there). These guys are good at chasing one another, but can just follow their own track again and again (ants?). Notice they also often just join pairs and go for a spin. There's no friction on the movement (just bounds) so they keep going once they start (I think it's a property of the physics system)




The patterns that they stop in are nicely organic and might be useful in the future...

This is more fun than game of life stuff :) Apologies for youtube's awful video compression...Code here, (tis messy & you'll need phys2d)


The balls in this one can only see blue





Here's coloured gravity ;) each cell emits a field that is 3x more attractive to cells of the same colour than different colours:





Code here (still messy)
(this has 200 circles, and is reaching the limits of what Phy2D can do in real time). This next one switches of the red's attraction to it's own field, and increases blue and green's atrraction. And we get some really nice emergent behaviour - the reds form a cell wall around blue and green :)


some ponderings on nature and nurture

This post sketches out some fuzzy concepts about Nature and Nurture with respect to form. The directions are not coherent. Most are not even sensible.

Is form predetermined at conception/compile time (nature) or is it determined by the environment/runtime (nurture)? This is very similar to questions about free will. Here are some touchy-feely topics I've been pondering:

Environmental:

  • Growth (eg housing estates grow into each other to use all space, embryos develop into emus)Our system going at the world - the way our form responds to the outside world.
  • Decay (eg bits fall from houses, old women start shrinking) Similar to growth, the changes that the outside world has on our form,
Conception:
  • Evolution (eg the nicest houses or the fastest cheatas survive)
  • Design (eg "let's shove a gargoyle on it", "buildings are often L-shaped"). Form that comes from an intellegence.


So we have the temporal/evalutation/run-time phenomina growth and decay. And the morphospace search algorithms of "design" and evolution.

Aren't growth and decay both the same "environmental" or "evaulative" factors? It's sensible to draw a line between them because growth patterns tend to be dictated by the conceptive mechanism (genes or blueprints).



Evolution has been a mechanism for growth between generations of grown animals, allowing life to become more complex over the aeons.

A design will often involve previous ideas, and the designer's knowledge of previous generations of buildings. Evolution is a simpler (purer?) process, where only the effectiveness of the phenotype (and not the perception of effectiveness) is taken into account. The two concepts are very connected - design itself can evolve - good designs persist (bricks) and bad designs (green bikes) disappear. Given that most designs are copied, an evolutionary system occurs. (better stop on this track before it becomes a lecture on creationism vs evolution.)



Design is able to leap over many iterations of evolution to create more extreme forms. Because design's evaluation function is cheaper (and it has a better memory) it can create bigger leaps in form. Would it be possible for nature to evolve spaceships? Would nature have evolved vaccination?


Is design is just another word searching the space of all forms (morphospace)? - So very similar to evolution, except the genotype-ideas are not evaluated as phenotypes, they are evaluated as designs the architect's mind. In natural morphology the growth of an organism reacts little to it's environment and when it does it reacts in a pre-determined (at conception) way. However as a city grows, it is different to animals because it is constantly re-designed. It is re-thought out (by different minds seeing different problems). These minds did not exist when the city was founded.




Does this mean that applying natural algorithms to man made systems is hopeless? Imagine my washing machine where one person designed what they saw as the optimal drum, another their opinion of the greatest engine, and another their best powder draw. Even worse each manager will control the cost/value of the product based on their on evaluation of what's correct. It would be a very hard system for natural methods to arrive at because even if each person applied an evolutionary approach to whittle down their ideas, different evaluation criterion are applied by each person. It is almost certainly suboptimal.



Or is it that there are different levels of control and environmental interaction in creating form? Are different method appropriate for different circumstances? Does this mean that for an omni-procedural toolkit it'd be necessary to have simulate the range of possible design and environment interactions? Or that this has degenerated into masturbation and now I have a rough consensus I should concentrate on running code?



Natural forms seem be defined in terms of evolution and growth, while man made structures are mainly defined by design and decay. Is this because man made forms are constructed faster - design takes very little time and isn't visible, the growth takes a little longer, but is still short in comparison to the object's lifespan, and so they spend most of their visible time decaying? Wheras evolution slowly designs through evaluation of sucessive generations and each individual spends much of their existence growing. When an organic form stops growing, it is only a matter of time before it starts to quickly decay.

So what about the other two quadrants - designed growth and decaying evolution?

We have to be careful by what we mean by growth:
  • the evolutionary scale of growth - man growing from apes
  • the act of physical growth - a plant growing from a seed
  • the act of constructive growth - was my washing machine's grown? We take a bit of metal and add in an engine, some ballast & wire in some circuits. So people are just a catalyst in the creation of washing machines? Similarly for a city's growth of road networks (same as 2?)




meta-level-up: While I was thinking through this chain of thoughts I found myself writing: "So, we can write a coherent paragraph, but not be able to recall it's argument a minute later. There is something messy about the state of my mind." and now (a couple of days later) my answer is "But in hindsight the concepts are not clear, so i wouldn't expect it to make sense. The ideas I had where valid, just not complete." perhaps anyone (anyone?) who reads this should just absorb each example rather than take it as a framework.

The videos on this page where made with Blender (I'm learning how it works) and rendered with Yafray. The nice softness (is reasonable time) came from using low lighting and a skydome global illumination model (since I'm modelling cubes, it's a good approximation).

Sunday, November 09, 2008

How the Leopard Changed It's Spots

How the Leopard Changed It's Spots has just introduced me to the word morphospace - "The conceptual array of all possible morphologies". This is a fantastic word for describing the design space of a procedural object. This means that you can say that "the morphospace of the stools is a strict subset of the morphospace of the chairs" with a straight face. Equally morphogen to mean a chemical that creates morphological changes...

On another tack HTLCIS makes an argument that genes just guide stable physical principles to form creatures**. That life is as much a product of natural("mathematical') patterns as the genes that guide it. I think this is slightly stating the obvious, evolution will tend to take the path of least resistance, and exploiting physical patterns is an expected trick. These physical patterns should be taken as part of the input to the evolutionary algorithm, just as much as the geographic environment of the creature.

When people build buildings, they use the most practical materials. Building a geodesic house of carbon fibre and titanium would put it in a different league to other houses, but would cost too much, be hard to design, and likely to have weaknesses we don't know about. So we stick with the thousand year old tradition of wood joists in a brick frame(our "stable maxima" in evolutionary terms) . "If genes where people and houses where cells..."

The point of the book is that just studying genes is hopeless, that understanding the paths of least resistance through the physical world ("stable physical maxima") is just as important.

But how did we settle on this set of physical patterns? are we using the complete set? or a subset defined by our environment? or our genes?

Growth and Form is going on about laws that govern at different scales in the universe (briefey mentioning sagging breasts as an example of gravity on a human scale). So at different scales different physical laws prevail. But similar geometric properties arise out of these systems at different scales - spirals etc.... Should i be looking at these different common geometric patterns and finding ways of combining them into a procedural framework? As last weeks post described, the distance-from-point partition of space (weighted Voronoi) is very common, perhaps there are others, or was that a one off common-pattern? (it's a fairly trivial property of space...). There are examples at slightly more abstract level, the legs on a table are (from a design perspective) similar to...erm...legs on a tetropod.


But we must be careful of going too far down this route. I have several books on my desk (from the Fine Arts floor of the library) about architectural theory, so far these have been descriptive rather than generative. That is they define a solution space rather than detailing how to build an actual house.

Perhaps we should be designing compuational systems in which the desired forms are stable and easily achievable. As an example, here is a complete accident that occurred while playing around with Phys2D for a side project. It is a version** of one of the bundled demos that I added a generator for three balls connected by springs (with the intention of later modelling simple cells), but note how with enough energy in the system these simple cells start joining up into chains - one ball stuck inside another cell. The was fantastic to see because it was an unintended form occurring in a complex system.


More fun from HTLCIS for my project is the idea that if genes are an undecipherable mess of information*, then the repeated physical patterns present an opportunity to understand biological life. Rather than try and evaluate the functions of genetic sequences, perhaps I should try and build a set of patterns that can build any animal with someany control mechanism standing in for genes.

Some of the chapters towards the end of the book present that argument that has always been my defn of evolution:-
phenomena that are good at existing continue to exist
so phenomena can mean:
  • parasite and the symbiote,
  • the brick
  • planets
good at existing can mean:
  • good at reproducing
  • being hard to destroy
and continues to exist can mean:
  • isn't destroyed
  • can replicate itself
  • is replicated by a symbiote (the brick)


* There are lots of fun stories of people trying to understand the output of computational evolutionary systems (section 5 here). Have you seen the size of biology textbooks? There's no way we can pretend to understand that.
** http://twakered.googlepages.com/Demo8.java

Saturday, November 08, 2008

Paper notes: Procedural Modeling of Buildings

Procedural Modeling of Cities by Parish and Muller (2001 SIGGRAPH) (apologies this has zero coherence)

Interesting areas of background reading:

Mentions L-Systems as being good for "pattern amplification". Tis an interesting phrase, much like texture synthesis. But it turns out the referenced paper is talking about properties inherent to the grammars themselves:
"The complexity is gained with little human effort by the exploitation of the database amplification property of formal languages, generalized from strings to graphs."
But the idea of grammar-synthesis - creation of a grammar from a bunch of examples may be a fantastic way to avoid teaching artists how to use complex grammars*.

It's not explicitly said, but I think the highways are grown first, then the city-streets fill in the details. So the overview looks like*:

muller_01


This is an example of choosing the correct tools for the job. The streets are best defined by a network controlled by a growth L-system, while the buildings are most easily defined by a shape grammar that divides space. The different techniques have different properties (ease of implementing self sensitivity, ease of creating Level of Detail hierarchies, ability to produce symmetry). While it is tempting when looking at the above figure to suggest that the entire system could be reproduced as a singe grammar & L-system, breaking the process up allows the best tool to be used for the job.

Breaking it up into these chunks does, however, loose self-sensitivity between the different systems. For example, while the roads are self sensitive to each other, they're not sensitive to the buildings, meaning that overhanging buildings cannot encroach on the street. This forces limits on what can be created (no overhanging buildings) at the price of usability (compartmentalized systems for each stage).

An interesting question is what the primitives at each stage of the L-System are, with the goal of finding a common set that can form the basis for a framework. The above graphic shows that the main primitive is the polygon ("building faces" should also read "polygon").

It looks like for the pictures in the paper the building L-system/shape grammar wasn't used, instead they extruded a shape based on the floor plan. The generation of buildings using shape grammars features in the 2006 paper (and a nice job they make of it too).

Procedural Modeling of Cities, talks about self-sensitive L-Systems at the Street-plan level, by growing a mesh of roads. The roads check for other roads and merge into them if close enough. A similar approach wasn't taken to buildings tho, they where left as independent objects. This is the best and worst thing about shape grammars - they divide space early. This stops any possible interactions, but also simplifies the problem nicely.

A reoccurring theme in the study of procedural design is the need to create form that adapts to it's local environment. For the problem of road generation, this paper breaks the problem down into global goals (i.e. population density) and local constraints (i.e. location of other roads, the self sensitivity discussed above). After the L-system states it's desired outcome, parameters of that outcome are edited wrt these constrains. This implementation of the road generator feels a little messy (middle-endian) because it is different to the order of scale. The scale order would be global-goals (population) then L-system output, and local constraints (self-sensitivity). But evaluating the geometrically concrete L-system first is a necessary step to be able to fold in the values from the global-goals, and then nudge the output for the local constraints.

The street L systems demonstrates how we can use one of different types of growth to simulate another type of growth. Growing a street network from the nodes outward to fill in the remaining gaps isn't the natural pattern, but is an effective iterative algorithm. From a historical context roads really grow in a different way - starting from the centre of a city and spreading outwards, connecting, being bombed in the wars, areas redeveloped, remade to current themes. There are many themes when you start studying growth...enough for their own blog post.

Frankly textures are cheating ;) Although using boolean operation on square pulses against a façade is a solid idea, we should really be creating the geometry and baking it down to a texture. Something is niggling at the back of my mind, thinking that someone is pushing an agenda. He is creating a system for real time graphics, with the interest def from the SimCity approach.
"the main design goal for the system is easy extensibility. We want to be able to add new subsystems, such as different transportation networks (underground, train) and alternative land uses."
During my research it has been startling how hard it is to get away from comparisons with game technology, games are the most natural application (esp since they are set to outsell music and video in the uk).

It looks like this commercialization of this work is doing well for the authors, each copy going for $7000 dollars. Compared to the puny $5000 for Maya it's showing the problems that stopped me thinking about this as commercial work. For this to be successful you would have to spend huge amounts of time chasing each individual customer in each individual niche for the production graphics market, as well as horribly splinter your dev and marketing teams to sell to very fractured market:
  • Holywood
  • Videogames (realtime and otherwise)
  • Architects
  • Transport modellers
  • Education

Winner of the "not-so-insightful sentence" award: "Roads are the transportation medium for the urban population distributed over the area."

* For comparision, a similar graph of Sity (one of my old projects):
sity_overview

Saturday, November 01, 2008

scriptage

My first python script! An animation I was working on was too short. It would have taken a lot of time to go in and scale all the ipo curves, so here's a script* to make an animation 3 times longer.


import Blender, bpy;
from Blender import Ipo;

for x in bpy.data.ipos:
for y in x.curves:
for z in y.bezierPoints:
z.pt = [z.pt[0]*3,z.pt[1]];
y.recalc();


If you're very clever you can find the value 3 and change it...but only if you're really clever ok?. I'll try and add a ui to it sometime!

*Your computer may be repossessed if you run this script or other scripts provided by me