Thursday, May 15, 2008

Spotted: Digital Origami

Today, when everything is so digital and virtual, I am really both amazed and amused when I see something folded from actual paper at such a large scale (I wouldn't be so amused if I'd have to do the folding myself, though). Being something Voronoi-like is just a bonus.

Saturday, April 26, 2008

Spotted: VoronoiTom

It's not exaclty a surprise to me that many people are exploring Voronoi diagrams. Today, I came across a really cool site - VoronoiTom.

Tom explored countless variantions of the Voronoi diagrams, based on a set of points, arranged in different regular patterns. If you're interested in Voronoi, you must see this. The 3d vizualisations are really nice, but I like his extensive analysis of various 2d Voronoi configurations even more.

Thursday, April 24, 2008

Voronoi 3d Explorations

While most of the time Voronoi diagrams are based on (at least seemingly) random set of point, I started to explore some regular patterns.

If you place input points in a regular square grid, the Voronoi diagram is a grid as well. Well, that's not a huge surprise.

If you slide each row of points in a grid for half a distance between the points, you get a honeycomb pattern. That's interesting.

What's the purpose of these games? To understand the relation between input (set of points) and output (Voronoi diagram) better. In my applications, to put it very simply, the former would represent genotype and latter phenotype. Of course, in the evolutionary process I would not control the input points directly, but I somehow sense that it would be beneficial if I understood the Voronoi diagrams as much as possible.

Tuesday, April 22, 2008

More of Voronoi

I played with "my" Voronoi generator (2d and 3d); here are some screenshots.

Saturday, April 19, 2008

Qhull solution

Hmmm... it turned out that the construction of Voronoi diagrams is far from trivial. There are some serious papers out there, and they involved quite a bit of mathematics, to put it mildly.

I started to study the 2d methods first.

The sweep method (java required for demo) seemed so not elegant to me. "Wave front", come on, what's that? :-) There must be a better way.

I found the divide-and-conquer approach, presented by Shamos and Hoey, much more elegant. It can be easily attacked with the object-oriented programming language.

But after some hours of intensive work some concernes began to arise. The algorithm was pretty complex, but I was still in 2d. What would happen in 3d? The complexity would go over the roof. After all, the Voronoi construction itself is not the topic of my research; it's merely a tool and I should spend as little time as possible for it.

I stopped the work with the divide-and-conquer construction of Voronoi and headed for the web again; let's find some more info about 3d Voronoi construction.

My fears that 3d Voronoi construciton is far from trivial were confirmed, when I discovered that two first-class mathematical tools, Mathematica and Mathlab, both use external library Qhull for Voronoi (and related) computations.

Qhull is a powerful software put together by nice people who seemingly allow us to use it freely. It can do convex-hull, Voronoi diagrams and Delaunay triangualtion (which is the dual of Voronoi) in not only 2d and 3d, but even in higher dimensions, at least up to 8d; so there was really no point in competing with it :-)

After a few hours crunching numbers and fighting with academic-style documentation, almost all of my Voronoi computation problems were solved. As a bonus, it turned out that Qhull was lightning fast as well. Happy ending!

Thursday, April 10, 2008

Spotted: Evolved Virtual Creatures

This is a must-see for anyone interested in Evolutional Computing (EC). Actually, it's a must-see for everyone.

Wednesday, April 9, 2008

The Voronoi Addiction

Wow, I found a real jewel. Voronoi graphs were discovered by Mr. - not surprisingly - Voronoi, over a hundred years ago.

While the Voronoi graph is defined by very simple rules, it usually takes more than one sentence to explain it to someone. Let me try in my own words:

The Voronoi diagram divides the space into cells based on the input set of points. Each point defines one cell. Cell borders are drawn so that they divide the space equidistantly among the points. As a result, each location within a cell has the closest input point in the same cell.

For more info, see the Wikipedia's article on Voronoi.

Or try this interactive presentation (click in diagram to create new points!).

(if you have java installed, you may also try this, this or this)

There's something mesmerizing about Voronoi diagram. It is very similar to the patterns in nature. Soap bubbles, tissue cells...

It's also very appropriate for my "genotype-phenotype" requirements: a simple set of points can define complex spatial forms, which look natural as well.

Monday, April 7, 2008

Mission: Increase Density

While my first experiments with Genetic Algorithms (GA) and floor plan optimization didn't exactly pass with flying colors, I decided to try with simpler problems first.

The most simple problem I could think of, was: each subject is represented with a randomly distributed set of points in space. Fitness funcion: the subjects with more points nearer to the center of the space are more fit.

After running GA several thousand times, the "density" of points was increased as expected. But even then, the local optimum problem stopped the process short of compressing the cloud of points into single point at the center of space (which would give the subject best fitness assessment).

I experimented a lot with different stategies, trying to overcome obstacles in the GA. As the theory suggested, proper mutations are the key weapon in fighting the local optimum problem. I added several "complications" in my mutation system: parametrization and randomization of when, where and how the mutations occur.

The results were improved, however, I must admit that my GA can't achieve the destined goals yet.

Tuesday, March 25, 2008

Spotted: eVolo

eVolo Architecture holds the annual architectural competition for the skyscrapers of the future. You'll find some wild stuff there, just look at some of the entries: 1 2 3 4 5 etc.

Monday, March 24, 2008

Lessons in Genetic Algorithms

Easy in theory, hard in practice :-)

While Evolutionary Computing and it's most popular "flavour" - Genetic Algorithms - can be easily explained, it turns out that producing usable results with real-world problems can be a daunting task.

I quickly put together a light framework for the manipulation of populations, generations, subjects... and tested the system with kd-trees.

The aim was the optimization of 2d floor plans - for example, the fitness function would define whether more desirable subject would rather have rooms of equal size or maybe rooms of greater variety in size...

While the experiment moved in the right direction, it turned out that the problem of the local optimum quicky moves in place. After a plato in the population fitness is reached, the algorithm cannot find new ways to better subjects, if all new subjects are less fit than the "local optimum".

The local optimum problem is very well known and explored in the theory of Evolutionary Computing, so I wasn't very surprised that I encountered it in my first attempts.

Sunday, March 23, 2008

Kd-trees and De Stijl

In the search for the vocabulary (the means of defining the genotype and rules of morphogenesis - growth of phenotype) for my genetic houses, I came across the kd-trees.

It's a method of space partitioning, or, as architects would say, "organizing the space". It can be applied in 2-d space (e.g. floorplans) or 3-d space (e.g. complex spatial plans).

Nice thing about kd-trees is that space is organized with a very simple set of input parameters - set of points. Each point divides the space (in witch it's put) in two partitions; then new points are put in those partitions and so on.

I don't know whether Piet Mondrian (one of the founders of De Stijl) was familiar with kd-trees, but, at least to me, it looks fishy! :-)

I'm a bit reluctant about using the kd-trees as a driving vechile for my genetic house. While the Gerrit Rietveld's Schroeder house certainly looks good, I'm afraid that all of my houses would look the same - infinity variety of cubic forms. Very far from examples from nature.

If I'm dealing with the evolutionary computing, it would be far more appropriate to explore more organic forms and not to limit myself by the cubic partitioning of space.

Thursday, March 20, 2008

Evolutionary Computing Applications in Architecture design

While evolutionary computing (EC) is nothing more than a search for the optimum, so is every (and thus also architectural) design. How can EC be applied for usage in architecture?

As Vitruvius pointed out some two thousand years ago, a well designed architecture has to match three standards: firmness (structural integrity), commodity (functionality) and delight (aesthetic value).

So, in the search for optimal architecture, it is very logical to map each of the Vitruvius' standards to evolutionary computing's fitness function.

When asssessing the structural fitness of a subject (a building), the fittest are those capable of carrying more static stress (burden), preferably with less material used for the construction.

In a similar way, the functionality can be assessed based on the set of conditions. It is certanly better if the drawing room is bigger than the hall; and it's better that master bedrom is closer to the bathroom than to the kitchen.

The hardest thing to process for the computer is the aesthetic. While one could struggle to automate the aesthetic assessment process with certain mathematic rules (symetry, proportions, rythm....), I remain sceptic about such an approach - aesthetic is a highly subjective category.

But even if the fitness function for aesthetic cannot be calculated, that does not mean evolutionary computing cannot be applied in that field.

If aesthetic is a subjective quality, something in the eye of the beholder - the human being, then a real human being must perform the assessment of the subjects. Selection by fitness function still exists, but it is not automated nor calculated. A human being, artist/architect in our case, would make selections in the manner of a horse breeder. Some subjects in population would look better and would be favored for passing their properties to the next generations.

One might argue that human intervention would render EC unusable. Well, it might slow down the process (few seconds instead of few miliseconds - that's 1000x slower), but all the key elements of the EC remain. Only the fitness function for the aesthetic is admitted to be what it actually is - inevitably a human's judgement.

Monday, March 17, 2008

Evolutionary Computing (EC)

Evolutionary Computing (EC) is a method in the field of Artificial Intelligence. EC provides methods of search for the optimium by the means of randomization, mutation, recombination and selection. It mimics and learns from the biological evolution.

Similarities (compared to the biological evolution):

  • each subject is defined by a highly abstract code (genotype),

  • each subject is grown from genotype into phenotype (morphogenesis),

  • the probability for each subject to survive depends on its fitness; environment plays a large role in that,

  • the variety of the genetic pool of the population is ensured by recombination, providing offspring a new genotype, derived from genotypes of its ancestors,

  • further variety is achieved by random mutation of genotype.


Differences (comapred to the biological evolution):

  • generation turnover rate can be much higher - instead of hours, days or years, sequences of generations can be developed in miliseconds, evolution can run faster,

  • flexibility in the rules of inheritance - for example, in nature a subject typically inherits genetic material from 2 ancestors; these limitations can be easily overcome (e.g. a subject can have 5 ancestors),
  • it is not possible to simluate the complexity of natural systems in an artificial enviroment (for example, the human brain has at least 10-100 billion (short scale - 109) neurons; each of them is capable of "parallel processing" and is connected to others through about 1.000-10.000 synapses; these estimates compute to 1013 to 1015 number of synapses...); and we're not talking just about data storing, but (parallel) information processing as well.


So, how to apply that stuff in architecture? The plan is to grow a population of "houses"; each house would be based on its encoded genotype (blueprint), from which a real house would be grown. The houses would mate and produce offspring, which would be assessed; the subject with the greatest fitness (most appropriate house) would survive and pass its genetic material to the next generation. After many generations, best designs should emerge. Huh. I admit it's a long shot, but certainly worth a try :-)

Monday, March 10, 2008

First steps

Before evolutionary computing can be applied, I have to develop a vocabulary for the representation and manipulation of three-dimensional forms. Such a vocabulary is needed for the construction of the genotype and growth of the fenotype.

Here I used the approach with "particle agents". Each particle/agent holds a set of properties - spatial position, direction, speed, color etc. When time passes, the properties are manipulated according to a set of simple rules. Changing the rules, you get something completely different each time the simluation is run.

Is it "just a random development"? Of course it is, but don't underestimate the power of "random". The eyes and brain you're using to read this are the result of random events, together with a little natrual selection, of course (we'll discuss the intelligent design hopefully some other time :-)).


Wednesday, March 5, 2008

Genetichouse

I decided to explore a field connecting two disciplines: architecture and evolutionary computing, specifically genetic algorithms.

This project - codenamed Genetichouse - is a part of completing my bachelor's degree in architecture at the University of Ljubljana under the mentorship of professor, Ph.D. Igor Kalčič.

The goal of the project is to devise new ways of designing architectural forms.