Example-Based Procedural Modeling Using Graph Grammars

Fig. 1. From an example shape (a), our method automatically generates a graph grammar (b) that produces shapes (c) that are locally similar to the example. The graph grammar consists of rules that transform graphs. The graphs are converted into a planar graph drawing to produce the final shape.

We present a method for automatically generating polygonal shapes from an example using a graph grammar. Most procedural modeling techniques use grammars with manually created rules, but our method can create them automatically from an example. Our graph grammars generate graphs that are locally similar to a given example. We disassemble the input into small pieces called primitives and then reassemble the primitives into new graphs. We organize all possible locally similar graphs into a hierarchy and find matching graphs within the hierarchy. These matches are used to create a graph grammar that can construct every locally similar graph. Our method generates graphs using the grammar and then converts them into a planar graph drawing to produce the final shape.