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.