Computer Graphics World

October 2008 10 Formal Modeling Grammars T he sheer complexity of trees, plants, or cities makes it im- possible to model those structures manually for computer graphics applications. To reproduce the rich structure of such formations, procedural techniques are used, most of which are based on a set of very simple rewriting rules. ese systems (such as the L-system) are based on formal grammars, a funda- mental concept first introduced in linguistics and now studied in a branch of mathematics, the formal language theory. Formal Languages Formal and natural languages (such as English) generally have two main aspects: syntax and semantics. e first is what the language "looks like," in so far as what are valid and what are invalid words or sentences; the latter refers to the meaning of various utterances. Formal language theory is only concerned with the syntax of a language and completely ignores meaning. e precise description of a language is called the grammar (or formation rules). When thinking about the uses of grammars, our first idea usu- ally is the recognition of error—for instance, not spelling a word properly or using wrong punctuation. However, grammars are also regarded as a means to generate valid strings of a language. When learning a foreign language, we not only memorize basic words but also a set of rules on how to inflect them or form sentences with them. e rules of grammar help us to create valid utterances of which we may never have even heard. A formal generative grammar is essentially a set of rules that we can apply to strings (sequences of symbols) to transform them. Triggering an applicable rule one after the other, we can generate any valid com- bination of words in the language. Generative grammar originates in the work of an American linguist, Noam Chomsky, beginning in the late 1950s. It is considered to be one of the most significant contribu- tions to the field of linguistics made in the 20th century. But why would it be significant to other fields of science, like computer graphics? While in linguistics the alphabet is the set of letters or set of words of a particular language, in other applica- tions of formal grammars we can define an arbitrary alphabet: a set of algae cells, commands of a programming language, or 3D modeling operations. Using such symbols as the building blocks of the language, we have a powerful tool to express very complex structures and patterns. Formal grammars are used to detect erro- neous HTML (or XML) code of Web pages, identify syntax prob- lems in computer programs, or to simulate biological formations, such as realistic neural cells. Non-linguistic Application As mentioned earlier, a grammar consists of a set of re-write rules. e synthesis of valid strings begins with only a single start symbol, Modeling By GerGeLy VAss Gergely Vass is a software developer in the Image Science Team of Autodesk Media and Entertainment, where his research focus includes image process- ing and computer vision. Located in Budapest, Hungary, Vass can be reached at gergely.vass@autodesk.com. Above is an image showing iterations of the construction of the Serpinksi triangle using L-system rules.

• Cover