Generating tractable designs by transforming shape grammars to graph grammars

Shape grammars are powerful in specifying and generating an infinite number of designs by repeatedly applying predefined transformation rules to initial shapes. However, the intractable nature of shape grammars limits its wide use in many applications. Moreover, shape grammars lack a parsing method to automatically validate generated designs. In this paper, we present an approach capable of generating tractable designs and validating generated designs. Our approach transforms polygonal shapes and shape rules in shape grammars to graphs and then uses the spatial graph grammar (SGG) formalism to generate and parse designs. We have evaluated our approach by transforming shapes and shape rules originally specified in a shape grammar for Turkish houses to our graph representation and validating designs with the transformed graph rules on VEGGIE, a graph grammar specification and induction tool. Other shape grammars can be potentially integrated with our approach to extend their capability in generating and validating designs.