A Grammatical Framework for the Generation and Verification of Tractable Designs

Automatically generating designs with given requirements have been widely studied in computer science. Researchers either propose approaches to generate designs by given rules or develop computer-aided software helping designers to semi-automatically design products. The shape grammar has been investigated in recent decades by researchers from different domains, since Stiny and Gips proposed this rule-based approach to automatically generate paintings and sculptures. The shape grammar methodology then rapidly expanded to other fields, such as architectural designs, pattern designs, and industrial designs. A shape grammar takes shapes and shape transformation rules to generate designs by recursively applying rules to shapes. However, the bottleneck of shape grammar approaches is intractability and uncontrollability. Most shapes grammars either only handle special shapes or have exponential time complexities for generating designs. Moreover, shape grammar approaches iteratively apply transformation rules to expand designs, generating designs of uncontrollable sizes. To ease the process of design generation and make the generated designs tractable, we represent a framework that can generate and verify designs automatically by combining the generation power of shape grammars and the reduction power of graph grammars. Graph grammar, as a specification, generation and parsing tool, is well studied in the field of computer science, particularly in Visual Programming Languages (VPLs). It is capable of validating a given design by parsing it with given grammatical rules. We have developed a shape grammar interpreter with enhanced features, such as image import, polygon import and polygon filling. The interpreter provides a graphical interface for users to design and draw initial shapes and shape transformation rules. The designs can then be generated automatically by performing these transformation rules. To generate tractable designs meeting various design requirements, we discuss two different methods. One generates designs directly by analyzing the composition of shapes of designs. The other separate shapes into different classes based on their attributes, such as size, function or angle. It then analyzes the adjacency among classes of shapes and automatically generates adjacency graphs of shapes. The final design can then be generated through a shape placing algorithm. The first method can generate designs directly. Since the shapes in transformation rules are fixed, the generated designs are constrained in a limited range. The second method, however, generates adjacency graphs and then places random shapes based on the graphs, which makes the generated designs varied. Floor plan, as a fundamental architectural diagram, is one of the various representation tools used by architects to design buildings. Since architects may take days or even weeks to manually draw a floor plan, it is highly desired to automate the design process. It is, however, a challenging task to generate floor plans fulfilling design requirements. To testify the feasibility of our framework, we implement both aforementioned approaches in generating and validating floor plan designs. We demonstrate that both methods can generate/validate different plans consisting of varied rooms based on user-specified constraints within a reasonable time. Therefore, the framework is capable of generating designs that greatly reduce the designers’ effort.