Shape grammar

Shape grammars in computation are a specific class of production systems that generate geometric shapes. Typically, shapes are 2- or 3-dimensional, thus shape grammars are a way to study 2- and 3-dimensional languages. The foundation of shape grammars has been defined in a seminal article by George Stiny and James Gips in 1971.

Definition
A shape grammar consists of shape rules and a generation engine that selects and processes rules. A shape rule defines how an existing (part of a) shape can be transformed. A shape rule consists of two parts separated by an arrow pointing from left to right. The part left of the arrow is termed the Left-Hand Side (LHS). It depicts a condition in terms of a shape and a marker. The part right of the arrow is termed the Right-Hand Side (RHS). It depicts how the LHS shape should be transformed and where the marker is positioned. The marker helps to locate and orient the new shape.

A shape grammar minimally consists of three shape rules: a start rule, at least one transformation rule, and a termination rule. The start rule is necessary to start the shape generation process. The termination rule is necessary to make the shape generation process stop. The simplest way to stop the process is by a shape rule that removes the marker. Shape grammars differ from Chomsky grammars a major respect: the production rules may be applied serially (as with Chomsky grammars) or in parallel (not allowed in Chomsky grammars), similar to the way “productions” are done in L-Systems.

A shape grammar system additionally has a working area where the created geometry is displayed. The generation engine checks the existing geometry, often referred to as Current Working Shape (CWS), for conditions that match the LHS of the shape rules. Shape rules with matching LHS are eligible for use. If more than one rule applies, the generation engine has to choose which rule to apply. In the alternative scenario, the engine first chooses one of the grammar rules and then tries to find all matches of the LHS of this rule in the CWS. If there are several matches, the engine can (depending on its configuration/implementation)

A shape grammar is formally defined as a 4- tuple  ,

  •  is a finite set of characters,
  •  is a finite set of characters, so  .
  •   is a finite set of production rules
  •  is the starting figure consisting of elements of   and   ,

Elements of the crowd   are a finite arrangement of any number of elements   with any scaling or orientation.

Elements off   that in a rule   out   , or in   occurrences are called terminal figures.

Elements off   are so-called non – terminal figures or markers. elements   out   are called shape rules or production rules and are in the form   written down.

The left side   is a figure consisting of an element   combined with one elements   ,

The right side   is a figure and consists of either the same element   this in   occurs, the same element   in   , combined with an element   , or the same element   in   , with an additional element   combined with an element  ,

 is the starting figure, consisting of elements of   and   , It usually consists of at least one element that as   in a rule  in   occurs.

Apply the rule to all matches in parallel,
apply the rule to all matches serially (which might lead to inconsistencies) or
choose one of the detected matches and apply the rule to only this match.
Shape grammars are most useful when confined to a small, well-defined generation problem such as housing layouts and structure refinement. Because shape rules typically are defined on small shapes, a shape grammar can quickly contain a lot of rules. The palladian villas shape grammar presented by William Mitchell for example contains 69 rules, that are applied throughout eight stages.

Parametric shape grammars are an extension of shape grammars. The new shape in the RHS of the shape rule is defined by parameters so that it can take into account more of the context of the already existing shapes. This typically affects internal proportions of the new shape so that a greater variety of forms can be created. In this way, attempts are made to make shape grammars respond to structural conditions, for example the width of beams in roof structures which depends on span.

Despite their popularity and applicability in academic circles, shape grammars have not found widespread use in generic Computer Aided Design applications.
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 part of it) can be transformed in Geometric space. The definition of a shape grammar follows the standard definition of a phrase structure grammar of Chomsky, using shapes instead of symbols.

A shape grammar generates a figure by recursively applying the shape rules, starting with the starting figure. The result of applying the rule to an existing figure is always a new figure consisting of the existing figure, with an occurrence of 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 is minimally composed of three production rules (= shape rules). An initial rule, at least one transformation rule and a termination rule. The start rule is required to start the generation process, while the scheduling rule is necessary to complete the generation. The easiest way to stop the process is to remove the marker (= nonterminals). In contrast to Chomsky grammars, production rules in Shape grammars can be applied not only serially but also in parallel, similar to the sequence of L-systems .

A shape grammar system usually has a specific workspace in which the generated shapes are displayed. The generation engine checks the existing figure for matches to the conditions on the left side of the shape rules. If more than one suitable rule is found, the engine decides which one to apply. An alternative method is to first select a rule and then search all the matches of the left side with the current figure. There are several matches, depending on the implementation either

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

Parametric shape grammars are an extension of shape grammars. Instead of the production rules, Shape rule schema (  ), which consist of parametric figures. By inserting concrete values ​​into the variables of   and   new shape rules are defined, which are then used in the usual way to create new figures. Through this generalization, a larger variation of figures can be generated.

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

Similar to architecture, shape grammars have become increasingly important in computer graphics in recent decades. Shape grammars are used primarily for the procedural modeling of buildings or cities (eg for films or video games). Shape Grammars form the basis for numerous developed systems that use production rules to generate a variety of different 3D models. Both realistic-looking street plans, as well as facades or interiors of buildings can be created procedurally using Shape Grammars.

Other areas in which Shape grammars have been applied include industrial design and engineering.

Software Prototypes
This is a list of software prototypes that are available on the web (several of them are strictly speaking rather set grammar systems):

Grammar Environment
GRAPE
SD2
Shape Grammar Interpreter
Shaper2D
spapper
SubShapeDetector
Yingzao fashi building generator

Source From Wikipedia