Algorithmic Creation

Algorithmic solutions for creating 3D content are often used for vegetation and similar organic objects. For example the Lindenmayer systems can be used to generate plants and trees. As the need for large 3D scenarios has increased drastically for movie productions and video games, manual modeling would take much too long. The solution is to give a machine the ability to create variations of equivalent models itself. For example building a detailed city model leads to a lot of cloning and individual modeling for a huge amount of very similar objects. This process can be automated using an algorithmic approach.

The most common approaches use shape grammars [WWSR03], [MWH^∗06] or scripting languages [SK92], [Hav05]. Using these techniques urban modeling has become manageable [PM01], [WW08]. All approaches base on shape templates, which are a representation of a construction process. Therefore, they are similar to algorithms. A shape template does not rep-resent a single object but a family of objects. Various modeling frameworks offer the possibility to define shape templates easily [PPV95], [GK07] [LN03], [MPB05].

If the structure follows a set of rules, an algorithmic approach is able to create a large variety of 3D models. For example the creation of Gothic windows using the Generative Modeling Language (GML) is described in detail in the PhD thesis of Sven Havemann [Hav05] (see also Section2.1.3).

Fig. 2.13 A successful reconstruction of a building ends up in a consistent and accurate CAD plan.

The GML is based on concepts of Adobe Postscript and is designed to describe geometric shapes in 3D. It uses polygonal meshes and subdivision surfaces and provides data types such as numbers, strings, vertices, edges, faces, etc. as well as methods to create and modify these data types.

A commented, exemplary method call to create stairs is

% push base vertices of base polygon

% on the GML stack

[ (0,0,0) (10,0,0) (10,1,0) (0,1,0) ]

% push additional parameters on stack 0.2 1 5

% call library function to create stairs Lib.stairs

The function to create stairs takes the vertices of a base polygon (and an implicit half-edge), the length of the riser, the length of tread, and the number of steps.

tread riser

A simplified implementation of the stairs function (without any error or reasonability checks) is listed beneath:

% pop parameters from stack and use them by names usereg

!nSteps !nTread !nRiser !polyBase

% create base polygon from array of vertices :polyBase 3 poly2doubleface

% initialize first step 0 :nRiser 3 vector3 extrude

dup faceCW edgedirection length !nDepth

% create following steps with a for-loop 1 1 :nSteps

{

pop edgemate

0 :nRiser 3 vector3 extrude edgemate

0 :nTread 3 vector3 extrude 0 :nRiser 3 vector3 extrude edgemate

0 :nDepth 3 vector3 extrude edgemate

} for pop

Further information about the Generative Modeling Language, interpreters for various plat-forms and examples can be found at:

http://www.generative-modeling.org

Havemann shows that it is important to understand the original construction rules to derive a general shape template. He has studied the construction of buildings and windows of the

Gothic era to understand the development of the shapes. After that he was able to transfer this knowledge to the GML. Now all variations of Gothic windows are available and can be used in any GML scene [HF04].

Although powerful in the hands of experts, the GML is a complex programming language, which needs to be learnt even by computer scientists with common knowledge of algorithms.

This is a significant hurdle for designers and other non-expert users who want to express their shape ideas in GML. Schinko et al. introduce an alternative for programming GML directly, a code translator [SSUF11]. It is included in the generative modeling framework called Eu-clides⁸ [SST10]. It is a JavaScript translator allowing users to define shape descriptions in the easy-to-use scripting language. The code is then converted to one of the supported target plat-forms, for example GML or the XML-based documentation target. The meta-modeller concept of Euclides offers a more general idea of procedural modeling. Shapes can be translated to a target platform while keeping the generative representation. It gives non-expert users a valuable tool for procedural modeling.

The creation process can also be supported by some clever software tools and made available to an even larger group of users. The Castle Construction Kit by Ren´e Berndt is a tool built on top of GML [BGHF05]. It supports the user on creating Medieval castles and fortress systems by defining many building blocks. For example, castle walls are created automatically from a polyline which is created by clicking onto a floor surface. Parameters of the wall like height and shape variations are modified with a graphical user interface. Still the resulting content is stored as GML code. Changes and variations to the 3D model are easily implemented by experts and added to the editor. Also, as mentioned before, the algorithmic description is much smaller than the resulting content.

Many classical 3D modeling tools support some kind of scripting language to add algorith-mic creation methods. For the production of the 2005 King Kong movie a digital version of New York City of 1933 was created. A large variation in buildings and facades was realized using the scripting language Mel in Autodesk Maya [Whi06]. Natural variations of shapes and compositions of shapes can be added with random parameter changes. This is done not only for the creation of cities but also for landscapes, plants and trees. Even for a large crowd of animated characters a similar approach can be used for the appearance as well as for variations in the animations. The results should be reproducible for example by using the same random seed or pseudo random numbers from a look up table. In this way it is possible to store such scenes in the procedural code also create them again and again with the same result.