Shape Computation Lab

From Topologies to Shapes



From Topologies to Shapes: Parametric Shape Grammars Implemented by Graphs


Thomas Grasl and Athanassios Economou


Journal Environment and Planning B: Planning and Design









Publication date:

January 2013




Grammar interpreters, Shape grammars, Graph grammars, Subshape detection, Subsymmetry


A method for implementing parametric shape grammars is presented. Subgraph detection is used to find subshapes. Parametric shapes are described by restricting topologies. Shape grammars provide a powerful generative approach for the description, interpretation, and evaluation of existing designs as well as for new designs. Still, while the shape grammar formalism has produced a long and excellent series of formal studies, the corresponding efforts for automation of the tasks that shape grammars accomplish have not met with the same success. Two computational challenges of implementing shape grammars are detecting emergent shapes and enabling parametric rules. A general solution to both is presented here in terms of a graph theoretic model. 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 are described here and one of them is selected as the most useful for a shape grammar interpreter. The resulting formalism 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 playfully recall the parallel representations of ‘GRAphs’ and ‘shAPEs’.