This paper introduces the special issue “Advances in Implemented Shape Grammars: Solutions and Applications” and frames the topic of computer implementations of shape grammars, both with a theoretical and an applied focus. This special issue focuses on the current state of the art regarding computer implementations of shape grammars and brings a discussion about how those systems can evolve in the coming years so that they can be used in real life design scenarios. This paper presents a brief state of the art of shape grammars implementation and an overview of the papers included in the current special issue categorized under technical design, interpreters and interface design, and uses cases. The paper ends with a comprehensive outlook into the future of shape grammars implementations.

Computer-based shape grammar implementations aim to support creative design exploration by automating rule-application. This paper reviews existing shape grammar implementations in terms of their algorithmic complexity, extends the definition of shape grammars with sets of transformations for rule application, categorizes (parametric and non-parametric) sets of transformations, and analyses these categories in terms of the resulting algorithmic complexity. Specifically, it describes how different sets of transformations admit different numbers of targets (i.e., potential inputs) for rule application. In the non-parametric case, this number is quadratic or cubic, while in the parametric case, it can be non-polynomial, depending on the size of the target shape. The analysis thus yields lower bounds for the algorithmic complexity of shape grammar implementations that hold independently of the employed algorithm or data structure. Based on these bounds, we propose novel matching algorithms for non-parametric and parametric shape grammar implementation and analyze their complexity. The results provide guidance for future, general-purpose shape grammar implementations for design exploration.

The ability to work with ambiguity and compute new designs based on both defined and emergent shapes are unique advantages of shape grammars. Realizing these benefits in design practice requires the implementation of general purpose shape grammar interpreters that support: (a) the detection of arbitrary subshapes in arbitrary shapes and (b) the application of shape rules that use these subshapes to create new shapes. The complexity of currently available interpreters results from their combination of shape computation (for subshape detection and the application of rules) with computational geometry (for the geometric operations need to generate new shapes). This paper proposes a shape grammar implementation method for three-dimensional circular arcs represented as rational quadratic Bézier curves based on lattice theory that reduces this complexity by separating steps in a shape computation process from the geometrical operations associated with specific grammars and shapes. The method is demonstrated through application to two well-known shape grammars: Stiny's triangles grammar and Jowers and Earl's trefoil grammar. A prototype computer implementation of an interpreter kernel has been built and its application to both grammars is presented. The use of Bézier curves in three dimensions opens the possibility to extend shape grammar implementations to cover the wider range of applications that are needed before practical implementations for use in real life product design and development processes become feasible.

Shape grammars come in a variety of forms. Algebras of shapes have been defined for spatial elements of different kinds, as well as for shapes augmented with varying attributes, allowing for grammar forms to be expressed in terms of a direct product of basic algebras. This algebraic approach is extended here to the algebraic derivation of combinations of basic shape algebras with attribute algebras. This algebraic abstraction at the same time serves as a procedural abstraction, giving insights into the modular implementation of a general shape grammar interpreter for different grammar forms. In addition, we consider practical limitations on algebraic compositions of basic shape algebras with attribute algebras and identify a complication with respect to solving the matching problem for parallel and compound shape grammars, suggesting a way to address this complication.

The use of grammars in design and analysis has been set back by the lack of automated ways to induce them from arbitrarily structured datasets. Machine translation methods provide a construct for inducing grammars from coded data which have been extended to be used for design through pre-coded design data. This work introduces a four-step process for inducing grammars from un-coded structured datasets which can constitute a wide variety of data types, including many used in the design. The method includes: (1) extracting objects from the data, (2) forming structures from objects, (3) expanding structures into rules based on frequency, and (4) finding rule similarities that lead to consolidation or abstraction. To evaluate this method, grammars are induced from generated data, architectural layouts and three-dimensional design models to demonstrate that this method offers usable grammars automatically which are functionally similar to grammars produced by hand.

Since the introduction of spatial grammars 45 years ago, numerous grammars have been developed in a variety of fields from architecture to engineering design. Their benefits for solution space exploration when computationally implemented and combined with optimization have been demonstrated. However, there has been limited adoption of spatial grammars in engineering applications for various reasons. One main reason is the missing, automated, generalized link between the designs generated by the spatial grammar and their evaluation through finite-element analysis (FEA). However, the combination of spatial grammars with optimization and simulation has the advantage over continuous structural topology optimization in that explicit constraints, for example, modeling style and fabrication processes, can be included in the spatial grammar. This paper discusses the challenges in providing a generalized approach by demonstrating the implementation of a framework that combines a three-dimensional spatial grammar interpreter with automated FEA and stochastic optimization using simulated annealing (SA). Guidelines are provided for users to design spatial grammars in conjunction with FEA and integrate automatic application of boundary conditions. A simulated annealing method for use with spatial grammars is also presented including a new method to select rules through a neighborhood definition. To demonstrate the benefits of the framework, it is applied to the automated design and optimization of spokes for inline skate wheels. This example highlights the advantage of spatial grammars for modeling style and additive manufacturing (AM) constraints within the generative system combined with FEA and optimization to carry out topology and shape optimization. The results verify that the framework can generate structurally optimized designs within the style and AM constraints defined in the spatial grammar, and produce a set of topologically diverse, yet valid design solutions.

I present an implementation of shape grammars that is aimed at supporting designers. It has two parts: a grammar editor and a stand-alone interpreter. The editor is the modeling application Rhinoceros3d using Python scripts. The interpreter is general, is three-dimensional, and supports subshape detection. A grammar is a Rhinoceros3d model; thus users can manipulate all its parts directly and immediately. That is, they can modify any shape without selecting or invoking an editor, and they can lay out the parts of the grammar in any way they find meaningful. Using this approach, which I call a whole-grammar approach, users are shielded from most subdomain tasks, like typing text files or specifying transformations. Informal observations suggest that users of this implementation can work effectively.

The shape grammar formalism has been discussed theoretically extensively. Recently there has been increased activity in implementing shape grammar interpreters, yet there is a lack of implementations that support parametric rules and emergence. Here the structure of a general parametric shape grammar interpreter is discussed in detail. The interpreter is based on graph grammars. It supports emergence, parametric rules, and numerous types of geometric objects. The shape grammar engine, an agent-based rule selection system and several implementations based on the engine are discussed.

Shape grammars have been developed to codify a specific type of artifact – Queen Anne houses, Buffalo bungalows – or the style of a particular designer – Andrea Palladio, Frank Lloyd Wright, or Álvaro Siza Vieira. However, these specific grammars fail to encode recurrent design moves or features that are above the particularities of a specific design style or the idiosyncrasies of a specific designer and, therefore, are common to a larger category of designs and maybe reutilized and incorporated in the definition of new, specific design languages. To overcome these limitations, the notion of generic grammars for defining design domains is introduced. Its application to the urban design domain is illustrated by showing a generic grammar implementation resulting in a City Information Modeling platform composed of a parametric design interface connected to a geographic database.

This paper presents a multipurpose chair grammar and its implementation in the design tool ChairDNA. This tool is oriented for the exploration of design alternatives in the early concept phase of the chair design process. This work addresses two shortcomings within the research area of shape grammars (SGs), namely, the lack of implementation of SGs applied to design domains, and the lack of practical applications in real-life design scenarios. To address these problems, a methodology is proposed for the implementation of a SG (more specifically, a set grammar) into a tool, comprising the translation of the grammar into user-interface elements oriented for design practitioners. By using the proposed tool, the user can add/delete chair components and edit shape parameters, while visualizing the effects on a three-dimensional digital model presented in a variety of CAD applications. Compared with other SG implementations, ChairDNA uses an approach that keeps under control the combinatorial explosion of rule applications, which simplifies the use of the tool by designers that do not have experience in SGs. The generative potential of the tool is demonstrated by generating chairs of different types, and its usability and utility in aiding the designer are evaluated by design students and design practitioners.