Sandbox: Lime Drone

SketchUp

A few words about SketchUp would be appropriate now (I use Sketchup in my Genetic-house project for final processing and visualisation).

I consider SketchUp the best drawing software I've ever seen, period.

I have some 25 years of experience with computers and software. It started with the 8-bit Sinclair ZX-81, then came it's more powerful brother ZX-Spectrum, then Commodore 64, and then a countless armada of PCs... you can imagine I've tried and used lots of software of every kind.

From my personal experience I know that by far the most difficult thing in software is to make things simple but still powerful (that I call good abstraction). It's very easy to make complex things. To add features, to expand functionality. Anyone knows how to do that. But complex software can be either painful to use or even completely useless.

The other danger is to make things too simple. One of the Murphy's Laws, called Shaw's Principle, says: Build a system that even a fool can use, and only a fool will want to use it. That I call bad abstraction.


To keep powerful things simple to use, that's far from trivial. And SketchUp is both quite powerful as well as incredibly simple to use.

When discussing SketchUp with my colleagues, most of them point out, that SketchUp in not as powerful as the classic CAD software (e.g. AutoCAD). That's not a very good comparison; AutoCAD (a great software too, no doubt) is primarily a drafting tool, while SketchUp is used for - 3d sketching and modeling in the design conception phase.

But consider this: SketchUp can build up functionality and new features while it can remain simple to use; it's authors have demonstrated they master the good abstraction lore. On the other hand, it's virtually impossible for AutoCAD (or any other) to become much simpler - unless they start all over again, but then it wouldn't be the same software anymore.

"To boldly go where no man has gone before"

Today something funny happened. I mailed my first real "Voronoi Genetic-house" screenshots to some of my friends. In response, two of them suggested (independently of each other!), that I should bisect my last "Voronoi Genetic-house" laterally, throw one half away, mirror another half over the bisection plane in order to produce nothing less than a Star-Trek-fashion alien starship. One of them even suggested that I should offer my software to Sci-Fi production studios for alien ship structure generator. Well, that idea is somewhat of a long shot, but the fact that two people simultaneously came to the same idea, amuse me. That was a nice example that human minds think alike and that when you see something you invented, it is not necessery that that other guy stole it from you - he might just came across the idea by himself as well. If you need consolation - it happened to the greatest minds as well. Back to the subject, being a Sci-Fi fan myself (well, do you know any computer geek who is not?), they didn't have to tell me twice. In SketchUp, it took only a few minutes to complete the operation. It's not exactly a beauty, just a proof-of-concept. I'll try harder some other time.

My first Voronoi Genetic-house

This is the first example of all the stuff put together: my C# "interactive breeder" software, Qhull and Sketchup (for final eye-candy-type visualisation). As I pointed out in the previous post, some restrictions were made in deploying the input Voronoi sites. Most of them are derived using the interactive genetic algorithm; however, I sometimes force the grid distribution of the input sites, which can be nicely seen in this model - there are some areas of rectangular regularity. While this can be seen as a cheating the evolutionary process, it is important to me to get insight in the rules of morphogenesis (genotype -> phenotype conversion). To be an architecture, the "genetic-house" must exhibit some architectural features - leveled floor of internal spaces (or rooms), for example, is perhaps the most important feature. This "house" (I suppose you wouldn't like to live it it) is the major milestone in my project. I'll do a lot of them in the days ahead to get some feeling about what works and what doesn't. Then I have to refine the genotype definition as well as phenotype development - morphogenesis. I am somewhat sorry that I won't have the time to implement all the ideas continually emerging at every step of my research.

The Interactive Voronoi

Today I merged my "interactive breeder", previously working only with cubic prisms, with 3d Voronoi structures. Wow, it took a long time to come to this point, I'm getting somewhere... There are still some problems: 3d Voronoi structures don't look like architecture yet (see the first picture on the left). One would, um, imagine that a structure should have some horizontal planes in order to be an architecture. People expect to have some horizontal places to move, dwell, work... in their houses. I decided to merge two vocabularies to achieve that: the final structure would be generated by the Voronoi algorithm, but the points would be artificialy encouraged to take positions in cubic grids (see the last picture on the left). Was I cheating a bit here? Yes. The (politically?) correct way would be to define another fitness function which would favor the subjects with as many horizontal planes as possible. Maybe I'll do that some time. At this time, I'm exploring the interactive genetic algorithms (with a human selector). As you surely know, the concept of time exists because everything cannot happen at once :-) I think I'll explore the following question in one of the future posts: to what extent the traits of a subject are defined by the evolutionary process itself and to what extent by other forces; enviroment, for example. A shark and a lion are both predators, but they look quite different. The evolution process is crucial in species development, but the environment takes a part of paramount importance, too.

Spotted: Shape Evolution

Very interesting thesis of Oréstes Choúchoulas exploring the Genetic Algoritms (GA) in architecture. While the author concludes that "..the genetic algorithm is not working as efficiently as expected..." (well, nobody promised that it would be easy...), the paper gives lots of valuable insight in the field of GA and its usage in architecture.

The Interactive Approach to Genetic Architecture

As discussed in Evolutionary Computing Applications in Architecture design, the genetic algorithm's fitness function could take into consideration three different aspects of architecture (structural integrity, functionality and aesthetic). After I put a lot of thought into it, I made two important decisions. 1. In my research, I will limit the fitness function to only one of the aspects. While the ultimate genetic algorithm for architectural design could and should include all three aspects, I strongly believe that each aspect should be studied first in a partial experiment. Combining different (Vitruvius') aspects in GA before each of them would be fully studied and understood, would only mess things up. 2. I decided that I should choose the aesthetic value aspect. It's the key aspect which differentiates an architecture from a building. GA searching the optimal structure could proove very efficient, however, it falls more in the field of structural engineering. I wrote a program which displays 9 "subjects" in a 3x3 matrix. The subjects are simple cubic compositions, made of randomly sized and randomly positioned cubic prisms. The users selects some of those prisms in order to favor them in the evolutionary process (selection, recombination, mutation...). To emphasize the inheritance trace of specific genotype codes (and phenotype features), I colored the subjects at the begining of the evolution. After each new generation is produced, one may observe how the genotype-phenotype properties are passed to the subjects of the next generation. I was somewhat disapointed that I won't be able to demonstrate "real" genetic algorithm processing with huge populations (several thousands subjects) and lots of (thousands of) generations. I even risk that the evolutional principle won't be achieved in such a small population (only 9 subjects!) and within relatively small number of generations (limited to duration of user interaction). But at this moment this is the only solution. The two decisions described earlier in this post, are certainly the right ones and I should proceed in this way.

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.

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.

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.

More of Voronoi

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

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!

Spotted: Evolved Virtual Creatures

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

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.

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.

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.

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.

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.

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.

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 - 10⁹) 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 10¹³ to 10¹⁵ 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 :-)

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 :-)).

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.