Shape grammar

Last updated

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. Shape grammars were first introduced in a seminal article by George Stiny and James Gips in 1971. [1] The mathematical and algorithmic foundations of shape grammars (in particular, for linear elements in two-dimensions) were developed in "Pictorial and Formal Aspects of Shapes and Shape Grammars" (Birkhäuser Basel, 1975) by George Stiny. Applications of shape grammars were first considered in "Shape Grammars and their Uses" (Birkhäuser Basel, 1975) by James Gips. These publications also contain two independent, though equivalent, constructions showing that shape grammars can simulate Turing machines.

Contents

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 in 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)

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 [2] for example contains 69 rules, that are applied throughout eight stages.

Parametric shape grammars are an extension of shape grammars. [3] 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.

Applications

Shape grammars were originally presented for painting and sculpture [1] but have been studied in particular in architecture (computer-aided architectural design), as they provide a formalism to create new designs. Other important domains shape grammars have been applied in are decorative arts, industrial design and engineering. [4]

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 [5] [6] ):

Literature

See also

Related Research Articles

<span class="mw-page-title-main">L-system</span> Rewriting system and type of formal grammar

An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures. L-systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist at the University of Utrecht. Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development. L-systems have also been used to model the morphology of a variety of organisms and can be used to generate self-similar fractals.

In linguistics, transformational grammar (TG) or transformational-generative grammar (TGG) is part of the theory of generative grammar, especially of natural languages. It considers grammar to be a system of rules that generate exactly those combinations of words that form grammatical sentences in a given language and involves the use of defined operations to produce new sentences from existing ones.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

In computer science, extended Backus–Naur form (EBNF) is a family of metasyntax notations, any of which can be used to express a context-free grammar. EBNF is used to make a formal description of a formal language such as a computer programming language. They are extensions of the basic Backus–Naur form (BNF) metasyntax notation.

In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering to layout algorithms and picture generation.

In computer science, an operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN).

<span class="mw-page-title-main">Syntax (programming languages)</span> Set of rules defining correctly structured programs

In computer science, the syntax of a computer language is the rules that define the combinations of symbols that are considered to be correctly structured statements or expressions in that language. This applies both to programming languages, where the document represents source code, and to markup languages, where the document represents data.

Generative Modelling Language (GML) in computer graphics and generative computer programming is a very simple programming language for the concise description of complex 3D shapes. It follows the "Generative Modelling" paradigm, where complex datasets are represented by "lists of operations" rather than by lists of objects, which is for instance the case in a relational database.

An adaptive grammar is a formal grammar that explicitly provides mechanisms within the formalism to allow its own production rules to be manipulated.

<span class="mw-page-title-main">Terminal and nonterminal symbols</span> Categories of symbols in formal grammars

In formal languages, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. Terminal symbols are the elementary symbols of the language defined as part of a formal grammar. Nonterminal symbols are replaced by groups of terminal symbols according to the production rules.

The DMS Software Reengineering Toolkit is a proprietary set of program transformation tools available for automating custom source program analysis, modification, translation or generation of software systems for arbitrary mixtures of source languages for large scale software systems. DMS was originally motivated by a theory for maintaining designs of software called Design Maintenance Systems. DMS and "Design Maintenance System" are registered trademarks of Semantic Designs.

<span class="mw-page-title-main">Formal grammar</span> Structure of a formal language

A formal grammar describes which strings from an alphabet of a formal language are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for such strings in a formal language.

Junction grammar is a descriptive model of language developed during the 1960s by Eldon G. Lytle (1936–2010).

<i>Aspects of the Theory of Syntax</i> 1965 book by Noam Chomsky

Aspects of the Theory of Syntax is a book on linguistics written by American linguist Noam Chomsky, first published in 1965. In Aspects, Chomsky presented a deeper, more extensive reformulation of transformational generative grammar (TGG), a new kind of syntactic theory that he had introduced in the 1950s with the publication of his first book, Syntactic Structures. Aspects is widely considered to be the foundational document and a proper book-length articulation of Chomskyan theoretical framework of linguistics. It presented Chomsky's epistemological assumptions with a view to establishing linguistic theory-making as a formal discipline comparable to physical sciences, i.e. a domain of inquiry well-defined in its nature and scope. From a philosophical perspective, it directed mainstream linguistic research away from behaviorism, constructivism, empiricism and structuralism and towards mentalism, nativism, rationalism and generativism, respectively, taking as its main object of study the abstract, inner workings of the human mind related to language acquisition and production.

<span class="mw-page-title-main">CityEngine</span> 3D modelling software

ArcGIS CityEngine is a commercial three-dimensional (3D) modeling program developed by Esri R&D Center Zurich and specialises in the generation of 3D urban environments. Using a procedural modeling approach, it supports the creation of detailed large-scale 3D city models. CityEngine works with architectural object placement and arrangement in the same manner that software like VUE manages terrain, ecosystems and atmosphere mapping. Unlike the traditional 3D modeling methodology which uses Computer-Aided Design (CAD) tools and techniques, CityEngine takes a different approach to shape generation via a rule-based system. It can also use Geographic Information System (GIS) datasets due to its integration with the wider Esri/ArcGIS platform. Due to this unique feature set, CityEngine has been used in academic research and built environment professions, e.g., urban planning, architecture, visualization, game development, entertainment, archeology, military and cultural heritage. CityEngine can be used within Building Information Model (BIM) workflows as well as visualizing the data of buildings in a larger urban context, enhancing its working scenario toward real construction projects.

In information technology a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction. Reasoning systems play an important role in the implementation of artificial intelligence and knowledge-based systems.

George Stiny is an American design and computation theorist. He co-created shape grammars with James Gips.

The following outline is provided as an overview of and topical guide to natural-language processing:

James Gips was an American technologist, academic, and author based in Boston. He was the John R. and Pamela Egan Professor of computer science and professor of information systems at Boston College.

In mechanical engineering, kinematic synthesis determines the size and configuration of mechanisms that shape the flow of power through a mechanical system, or machine, to achieve a desired performance. The word synthesis refers to combining parts to form a whole. Hartenberg and Denavit describe kinematic synthesis as

...it is design, the creation of something new. Kinematically, it is the conversion of a motion idea into hardware.

References

  1. 1 2 Stiny, G. & Gips, J. (1972). Shape grammars and the generative specification of painting and sculpture. In Information Processing 71, 1460–1465. North-Holland Publishing Company.
  2. ↑ Mitchell, W. (1990). The Logic of Architecture. MIT Press, London.
  3. ↑ Stiny, G. (1980). Introduction to shape and shape grammars. Environment and Planning B: Planning and Design 7(3), 343-351.
  4. ↑ Cagan, J. (2001). Engineering Shape Grammars: Where Have We Been and Where are We Going?. In: Antonsson, E. K. & Cagan, J. (eds). Formal Engineering Design Synthesis. Cambridge University Press, Cambridge, UK.
  5. ↑ McKay, A.; Chase, S. C.; Shea, K.; Chau, H. H. (2012). Spatial grammar implementation: From theory to useable (sic) software. AI EDAM (Artificial Intelligence for Engineering Design, Analysis and Manufacturing) 26(02), 143-159.
  6. ↑ Stiny, G. (1982). Spatial relations and grammars. Environment and Planning B: Planning and Design 9(1), 113–114.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.