Computer Graphics World

October 2008 12 n n n n Viewpoint and then we successively apply the rules (any number of times, in any order) to transform this string. By definition, the correspond- ing language consists of all the strings that can be generated in this manner. Let's consider a simple example of a "sandwich grammar," where we attempt to generate a proper breakfast. Our symbols are not letters, but ingredients. Let the start symbol be [sandwich], and the production rules (the grammar) be: 1. [sandwich] ➧ bread, [inside], bread 2. [inside] ➧ salad, [meat], cheese 3. [meat] ➧ ham 4. [meat] ➧ sausage 5. [meat] ➧ [meat], [meat] I indicated the so-called non-terminal symbols by [ ], which are abstract elements—to be replaced at some point with a "real" symbol—expressing structure in the language. e production of the breakfast in this case should start with rule one, and then with rule two. [sandwich] ➧ bread, [inside], bread ➧ bread, salad, [meat], cheese, bread As this example is a non-deterministic grammar, we can gener- ate different sandwiches. Choosing a certain order of generation rules we can produce: bread, salad, ham, cheese, bread bread, salad, ham, sausage, cheese, bread bread, salad, sausage, sausage, sausage, sausage, cheese, bread It would be easy to prove, as well, that vegetarian sandwiches are not part of the language (sorry) and the top and the bottom of a sandwich is always bread. My intention for using this simple example is to illustrate that a grammar of basic re-writing rules can express extremely complex formations. L-system In 1968, not much after Chomsky published his concepts of for- mal grammars, Aristid Lindenmayer (a Hungarian biologist) in- troduced a slightly modified production mechanism. He attempt- ed to model the growth patterns of multicellular organisms, like algae, and created the Lindenmayer system. In the L-system (as it is mostly referred to), multiple rules are applied simultaneously in each iteration step. is parallel string-rewriting mechanism of the production procedure makes it possible to realistically describe the development of branching structures. e resulting strings can be interpreted geometrically and visualized using computer graph- ics techniques to create realistic renderings of the modeled plants, trees, or other complex structures. An L-system, just like our sandwich grammar, is also defined by a set of symbols and production rules. For computer graphics ap- plications, these symbols are mostly geometrical primitives, and the generated strings represent buildings, cities, trees, or flowers. It is often desirable to reproduce the natural randomness in the growing process, such as leaves or branches, thus non-deterministic rules are used. By assigning probability percentages to the individual rules, we create a stochastic L-system. To avoid artificial regularity of the variations, which may be striking when synthesized and real plants are displayed side by side, the L-systems randomize the rules and their interpretation at the same time. e first technique affects the topology of the plant, while the latter—randomizing the stem lengths and branching angles—varies the geometric aspects. e computing power of modern game consoles and PCs make it possible to use huge and detailed virtual environments in com- puter games. Creating these assets manually takes a lot of effort, a growing obstacle for game development studios. To address this issue, L-systems often are used to generate random yet control- lable virtual objects. Building and city generation has been one of the first applications of the Lindenmayer system. By analyzing the statistical properties of the architecture of well-known and unique buildings or city layouts, new variations resembling the original can be produced. e L-system is a great example of how innovations of a very distant field, like linguistics, can be utilized in computer graphics. It should not be surprising, though. Capturing and reproducing the complexity of nature is a fundamental task in all areas of sci- ence. And there is still great room for improvement. n This CG plant with tiny hairs was generated with an L-system.

• Cover