Shape Computation Lab



01. Graph representation of shapes in GRAPE. (a) A shape; (b) One large square; (c) One smaller square; (d) Part-relation graph of two overlapping squares. (e) Embedding of a search pattern to find the large square; (f) Embedding of a search pattern to find the smaller square.

02. Input/output structure of GRAPE to work with different graph engines and geometry engines.

03. Stiny’s ice-ray checkerboard lattice grammar implemented in GRAPE; (a)-(b) Original rules; (c) New rules substituting the square motifs by new motifs with the same diagonal symmetry.

04. Stiny’s ice-ray checkerboard lattice grammar implemented in GRAPE.

05. Some new designs in the checkerboard lattice language implemented in GRAPE.

06. Sample rules from March’s nucleated and linear distributions implemented in GRAPE. (a) Binary division; to 4 squares (b) Tertiary division to 9 squares.

07. A production in the binary division grammar implemented in GRAPE.

08. Some new designs in alternative sequences of the binary and tertiary division rules implemented in GRAPE.

09. An Escheresque grammar implemented in GRAPE.

10. A production in the Escheresque grammar implemented in GRAPE.

11. Some fractal-like designs in the Escheresque grammar implemented in GRAPE.

12. The Dirksen grammar (James Park) implemented in GRAPE. Three types of representation of a shape rule: (a) axonometric projection; (b) orthographic projection; (c) Graph.

13. A sample derivation of a Miesian courthouse design from the software implementation of the Dirksen grammar in GRAPE.

14. Sectional models of six Miesian courthouse designs generated in GRAPE. All models are satisfying the requirement of having 24 courtrooms and appropriate volume of public, office and supporting spaces.

Thomas Grasl and Athanassios Economou



Keywords: Shape Grammar Interpreter; Shape Grammars; Computer-Aided Design; Design Automation; Visual Indexing; Algebras of Shape

The challenges for designing a general-purpose parametric shape grammar application are numerous. Several accounts in the literature focus on technical and/or expressive characteristics of interpreters including underlying computing language, subshape recognition, the dimensionality of shapes, and so forth, or the tasks for programs that implement shape grammars, for example, generation, parsing, and inference tasks and their interactions with CAD modelers. And still other accounts focus on usage in design, including general interpreters versus specific domain applications, schematic design versus design development, industrial strength interpreters versus proof-of-concept applications, and so forth.


The work here presents a new general parametric shape grammar interpreter, code-named GRAPE, that uses graph grammars to carry out computations on graphs that encode maximal representations of shapes. We argue that what distinguishes the application from other applications in the field is that emergent shapes and general parametric rules are both supported – while fully acknowledging that parametric subshape recognition is NP-hard.


Graphs are a popular choice for representing the structure of shape. Typically, graphs are seen as multidimensional data structures that, with an appropriate embedding, can formally structure and visually resemble the shapes they represent. Still, the encoding of shapes in terms of these alternative graph representations is not straightforward. Various approaches to representing shapes as graphs have been attempted in the past but none has managed to provide a viable and useful solution for a shape grammar interpreter. The resulting formalism here uses two parallel representations, a graph-theoretic one that is used for the subshape detection, and a visual one that illustrates the shape and which can be tested for intersections. The implementation presented here also maps the shape rules into graph rules. Once a rule has been selected, matching subgraphs are mapped back to shapes for further user interaction, such as picking a shape to which to apply the rule. The shape grammar library has been implemented in C# and it is code named GRAPE to affectionately recall the parallel representations of ‘GRAph’ and ‘shAPE.