Friday, August 10, 2012

Producing complex shapes

Architecture L-Systems deal with fairly simple shapes: boxes, tubes, cylinders, prisms, some times loft and revolution operations. They define the bounding volumes where you can instance actual geometry samples, like columns, windows, doors, bricks and tiles.

These basic shapes alone can get you far. The problem arises when you need these constructs to intersect each other. In most cases they produce complex shapes for which we don't even have names, let alone a unique mathematical formula. For instance, you can create a nice dome by doing a loft operation on a tube or a cylinder. Now, if you needed to blend two domes, you would be facing an increasingly difficult problem.

In other fields this is usually solved by "Constructive Solid Geometry" (CSG), which is about combining multiple shapes into bigger or smaller shapes by subtraction, addition, intersection and other similar operations. The problem with CSG is that it outputs a soup of triangles. The little boxes, cylinders, prisms we used to have disappear in this soup. This matters a lot for  architecture grammars. The rules you write are designed for these basic elements, not flat triangles.

I encountered this problem while building grammars for a Mosque. The base of the building is square, the top of the building is a dome which has a circular base. There is some kind of roof that transitions from the square into the circle. This is an element also found in Roman and Byzantine buildings.

In the next image you can see a red arrow pointing to it:


If you isolate this element, this is how it looks like:


It is some kind of curved square with a round hole in it. Not only this element is special. The side walls of the square base must be properly cut so it fits. Here you can see them:


These images, as usual, are the output of my architecture system. Which means these shapes entirely possible. They are quite easy to produce as well.

The trick again is in the occlusion rules. This time they can be combined with the recursive nature of L-Systems to great advantage.

The starting point is to define these shapes ignoring the weird cuts we will make later. This is what you get from a square base and a cone-shaped tube, both basic shapes:


Here comes the first trick. In reality, these shapes are made of smaller ones. I have reduced them just so you can see:


Using occlusion rules, we can hide the elements that are outside the box and above the roof. This produces a very coarse approximation to the shape we want:

Now comes the really important bit. The elements that are completely occluded will remain hidden, but those elements that are partially occluded we will subdivide them into smaller elements instead of just hiding them.

This produces a new set of elements. To this set we apply the same rule as before. Some will be entirely visible, some will be entirely occluded and some will be partially occluded. Once again, those that are partially occluded will be subdivided into a smaller set. Eventually the elements will be small to a point where it is not practical to subdivide again. This is where the process ends.

Here you can see the output of this method. Note that all the elements are boxes:



Obviously the cuts are not completely smooth. You still get these microscopic boxes. In my case this is not a problem at all. These volumes are sent to a voxelization phase. The tiny boxes are smaller than the voxel resolution so they are blended into straight features which later optimize very well.

I thought this was a nice technique. For sure you could use it to produce really bizarre objects. We may see some of that later.



19 comments:

  1. Wow, That was a very unexpected way to proceed and a very good use for voxels !
    I can't wait to see what weird shapes and buildings you will come up with. : )

    ReplyDelete
  2. Now that we are back to architecture. On a scale from 1 to 10, how difficult is it to procedurally generate the objects which you use pre-made models for? (Such as windows)

    ReplyDelete
    Replies
    1. 100

      At some point you start seeing diminishing returns. The generation becomes too difficult and the results are not aesthetically pleasing.

      Delete
  3. Wait, when the end output is voxels anyway, why bother with composite cones and spheres that are made of many smaller boxes instead of just using pure mathematical definitions of cones and spheres, like ray-tracers do?

    In ray-tracers, CSG shapes are rendered directly with arbitrary resolution without ever converting to polygons or dividing curved surfaces into small triangles or cubes. The same principle can be used to get voxel output directly from CSG shapes without ever needing any subdivision.

    Or is there are reason why your curved surfaces must be made up of many small boxes rather than just being defined mathematically?

    ReplyDelete
    Replies
    1. The reasons are practical. Rendering is the easy part so it has little weight on the solution. The real problem is how you encode what we could call the DNA of buildings. Defining buildings as pure functions is very difficult, to the point I don't think it has ever been done for a realistic building. Think of a house, you have doors, hallways, kitchens, chimneys, staircases, bathroom tiles. It is a problem that is best solved by a system that acknowledges and produces structure, like L-Systems.

      When you write L-System rules for a family of buildings you want to target manageable scopes like boxes and prisms. The rules determine how the scopes are placed, sized and most important, subdivided into other scopes. This is what gives the system the ability to grow, pretty much like an organism grows out of its DNA.

      Keeping the same basic DNA blocks at all scales makes the system more powerful. For instance it would be possible to turn some of these small blocks into larger features like gargoyles.

      Also you must know these boxes are not visible in the final output. Not only the small ones, the large ones are gone too. They are guidelines where custom geometry like bricks and roof tiles will be instanced. This geometry is hand made. You certainly don't want to create gargoyles out of mathematical functions.

      Delete
    2. If you are using building "DNA" it might be interesting to rig up a genetic algorithm to "breed buildings". Have a list of possible mutations to your building code, run it, and see what happens. This may not be as easy as it seems.

      It would be interesting to have a sort of open-world where buildings "fitness" was scored based on how long people spent near them, as a proxy for how interesting they are. But in practice that would probably just result in the evolution of buildings with hidden, inescapable pits.

      Delete
    3. In theory it is possible. As you noted, the challenge I see is how to discard the many absurd mutations this will produce even before the building is presented to people.

      Delete
    4. Well, I would say, just discard all the inaccessible designs and the ones with inescapable pits etc. but keep the rest. If people hate a building, regardless of how absurd it is, they will reject it XD. You might get really alien architecture, but people might like it, even if you would discard them yourself.

      Delete
  4. Good blog Miguel, but I'm wondering, for these sorts of problems (boolean results) would NURBS surfaces be more suitable? You could easily convert from polygons to NURBS (Autodesk Maya manages it) if you want to keep the current methods, but this discretisation and recursive subdivision wouldn't be a problem.

    ReplyDelete
    Replies
    1. Both NURBS and polygons are poor choices for defining architecture. The main reason is they are surfaces, not volumes. When writing rules for an architecture L-System you really want to operate on volumes.

      See the answer I gave above to Rune Skovbo Johansen. I applies to your question as well.

      Delete
  5. So could you use a similar technique to create, say, a sewer system? Dig out a blocky grid that gets rounded out and connected to the surface (manholes) by means of these recursive elements?

    ReplyDelete
    Replies
    1. I have not tried that, but looks doable.

      Delete
    2. OK, so I'm just thinking out loud here, but I guess a sewer system could be generated by finding a destination point (a pond or something outside of the city, or maybe a nearby river) and then running the main "veins" under the roads. Try and find a good angle that never quite intersects with the surface, periodically connect the veins to the surface by means of gutters and manholes, and you're in business.

      What do you think? How would you approach it?

      Delete
    3. Yes, that would work.

      You could also use a space colonization algorithm with some strict angle constraints. If you seed point below houses a network would naturally form.

      Delete
    4. Did you just make even sewers sound interesting? :)

      Delete
    5. Did we tell you about the giant alligators?

      Delete
  6. so, is the general idea behind the architectural work to have random buildings/ruins littering the landscape, or are you thinking of more formal town layouts? is it possible to have buildings placed in 'logical' places if they are procedurally generated? for example; watchtowers on mountain tops, housing on flat plains, roads curving/cutting into the sides of hills, etc? also, the buildings shown all seem very clean cut & shiny, do you have any intentions to make more 'ruined' forms of them? missing sections of ceiling, broken columns and such? or is this prematurely introducing unneeded complexity into the mix?

    ReplyDelete
    Replies
    1. This is needed complexity. I have already covered some of it:

      Ruins

      http://procworld.blogspot.ca/search/label/Ruins

      City layout and building placement:

      http://procworld.blogspot.ca/search/label/City

      Delete