Shape grammar

Shape grammars , German figure grammars , are a type of production system in computer science for generating geometric figures. Shape grammars are usually used to create two- or three-dimensional figures, nowadays mainly in the fields of architecture and computer graphics . The basis for Shape grammars was laid in a 1971 seminar article by George Stiny and James Gips.

definition

A shape grammar is formally defined as a 4- tuple . ${\ displaystyle G = (V_ {T}, V_ {M}, R, I)}$

${\ displaystyle V_ {T}}$ is a finite set of figures,
${\ displaystyle V_ {M}}$ is a finite set of figures such that , ${\ displaystyle V_ {T} * \ Cap V_ {M} = \ Sigma}$
${\ displaystyle R}$ is a finite set of production rules
${\ displaystyle I}$ is the starting figure consisting of elements from and . ${\ displaystyle V_ {T} *}$ ${\ displaystyle V_ {M}}$

Elements of the set are a finite arrangement of any number of elements with any scale or orientation. ${\ displaystyle V_ {T} *}$ ${\ displaystyle V_ {T}}$

Elements from that in a control of , or happen to be terminals figures mentioned. ${\ displaystyle V_ {T} *}$ ${\ displaystyle (u, v)}$ ${\ displaystyle R}$ ${\ displaystyle I}$

Elements from are so-called non - terminal figures or markers. Elements from are called shape rules or production rules and are noted in the form . ${\ displaystyle V_ {T}}$ ${\ displaystyle (u, v)}$ ${\ displaystyle R}$ ${\ displaystyle u-> v}$

The left side is a figure consisting of one element from combined with one element from . ${\ displaystyle u}$ ${\ displaystyle V_ {T} *}$ ${\ displaystyle V_ {T}}$

The right-hand side is a figure and consists either of the same element from that appears in, the same element from in , combined with an element from , or the same element from in , with an additional element from combined with an element from . ${\ displaystyle v}$ ${\ displaystyle V_ {T} *}$ ${\ displaystyle u}$ ${\ displaystyle V_ {T} *}$ ${\ displaystyle u}$ ${\ displaystyle V_ {M}}$ ${\ displaystyle V_ {T} *}$ ${\ displaystyle u}$ ${\ displaystyle V_ {T} *}$ ${\ displaystyle V_ {M}}$

${\ displaystyle I}$ is the starting figure, consisting of elements from and . It usually consists of at least one element that occurs as a rule in . ${\ displaystyle V_ {T} *}$ ${\ displaystyle V_ {M}}$ ${\ displaystyle u}$ ${\ displaystyle (u, v)}$ ${\ displaystyle R}$

description

A shape grammar consists of rules and a generation engine which selects and processes or calculates the rules. A rule defines how an existing figure (or a part of it) can be transformed in geometric space. The definition of a shape grammar follows the standard definition of a phrase structure grammar by Chomsky, with figures ("shapes") being used instead of symbols.

A shape grammar generates a figure by recursively applying the shape rules, starting with the starting figure. The result of the rule applied to an existing figure is always a new figure consisting of the existing figure, with an occurrence on the left side of the rule in the new figure being replaced by the figure on the right side of the rule.

A shape grammar consists of at least three production rules (= shape rules). An initial rule, at least a transformation rule and a termination rule. The start rule is required to start the generation process, while the termination rule is required to complete the generation. The easiest way to stop the process is to remove the marker (= non-terminal). In contrast to Chomsky grammars, production rules in Shape grammars can not only be applied serially, but also in parallel, similar to the sequence of L-systems .

A shape grammar system usually has a specific work area in which the created shapes are displayed. The generation engine checks the existing figure for compliance with the conditions on the left side of the shape rules. If more than one suitable rule is found, the engine decides which one should be used. An alternative method is to first select a rule and then find all matches on the left side of the current figure. If there are multiple matches, either

the rule is applied to all matches in parallel,
the rule applied serially to all matches (could lead to inconsistencies) or
one of the matches is selected and the rule is only applied to that area.

Parametric shape grammars are an extension of Shape grammars. Shape rule schema ( ), which consist of parameterized figures, are used instead of the production rules . By inserting specific values into the variables of and , new shape rules are defined, which are then used in the usual way to create new shapes. This generalization allows a larger variation of figures to be generated. ${\ displaystyle \ alpha -> \ beta}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ beta}$

application

Shape grammars were originally presented for paintings and sculptures, but have since found application mainly in architecture ( computer-aided architectural design ). Shape grammars are particularly suitable for small, clearly defined problems, such as the structure and layout of interiors or facades of buildings. Shape grammars very often consist of a large number of rules. The Shape grammar presented by William Mitchell for generating a villa in the style of the Italian architect Andrea Palladio consists of 69 rules that are applied in eight implementation steps.

Similar to their application in architecture, shape grammars have also gained in importance in computer graphics in recent decades. Shape grammars are mainly used for the procedural modeling of buildings or cities (e.g. for films or video games). Shape grammars form the basis for numerous developed systems that generate a variation of different 3D models based on production rules. Both realistic-looking street plans and facades or interiors of buildings can be procedurally created with the help of Shape Grammars.

Other areas in which shape grammars have been used include industrial design and engineering.

Software prototypes

Here is a list of software prototypes of Shape grammar systems available on the Internet.

literature

G. Stiny, J. Gips: Shape grammars and the generative specification of painting and sculpture . In: Information Processing , 71, 1972, pp. 1460-1465. North-Holland Publishing.
G. Stiny: Introduction to shape and shape grammars . In: Environment and Planning B: Planning and Design , 7 (3), 1980, pp. 343-351.
TW Knight: Transformations in Design: A Formal Approach to Stylistic Change and Innovation in the Visual Arts . Cambridge University Press, 1994.
G. Stiny: Shape: Talking about Seeing and Doing . MIT Press, Cambridge MA 2006.

Web links

www.shapegrammar.org
Shape Grammar and Style Simulation (list of references)
Shape grammar implementation: from theory to useable software (overview of current implementations)

Individual evidence

↑ ^a ^b G. Stiny, J. Gips: Shape grammars and the generative specification of painting and sculpture . In: Information Processing , 71, 1972, pp. 1460-1465. North-Holland Publishing. (German figure grammars and the generative specification of paintings and sculptures )
^ W. Mitchell: The Logic of Architecture . MIT Press, London 1990.
^ Yoav Parish, Pascal Mueller: Procedural Modeling of Cities . (PDF)
^ Jan Halatsch, Antje Kunze, Gerhard Schmitt: Using Shape Grammars for Master Planning . Design Computing and Cognition '08 (2008), pp. 655-673
^ Pascal Müller et al .: Procedural Modeling of Buildings . (PDF)
^ J. Cagan: Engineering Shape Grammars: Where Have We Been and Where are We Going? In: EK Antonsson, J. Cagan (Ed.): Formal Engineering Design Synthesis . Cambridge University Press, Cambridge UK 2001.
^ A. McKay, SC Chase, K. Shea, HH Chau: Spatial grammar implementation: From theory to useable software . In: Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM), 26 (02), 2012, pp. 143-159.
↑ G. Stiny: Spatial relations and grammars . In: Environment and Planning B: Planning and Design , 9 (1), 1982, pp. 113-114.

[stiny1972-1] G. Stiny, J. Gips: Shape grammars and the generative specification of painting and sculpture . In: Information Processing , 71, 1972, pp. 1460-1465. North-Holland Publishing. (German figure grammars and the generative specification of paintings and sculptures )

[2] W. Mitchell: The Logic of Architecture . MIT Press, London 1990.

[3] Yoav Parish, Pascal Mueller: Procedural Modeling of Cities . (PDF)

[4] Jan Halatsch, Antje Kunze, Gerhard Schmitt: Using Shape Grammars for Master Planning . Design Computing and Cognition '08 (2008), pp. 655-673

[5] Pascal Müller et al .: Procedural Modeling of Buildings . (PDF)

[6] J. Cagan: Engineering Shape Grammars: Where Have We Been and Where are We Going? In: EK Antonsson, J. Cagan (Ed.): Formal Engineering Design Synthesis . Cambridge University Press, Cambridge UK 2001.

[7] A. McKay, SC Chase, K. Shea, HH Chau: Spatial grammar implementation: From theory to useable software . In: Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM), 26 (02), 2012, pp. 143-159.

[8] G. Stiny: Spatial relations and grammars . In: Environment and Planning B: Planning and Design , 9 (1), 1982, pp. 113-114.