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

Regular expression Sequence of characters that forms a search pattern

A regular expression is a sequence of characters that specifies a search pattern. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. It is a technique developed in theoretical computer science and formal language theory.

L-system 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. The method is commonly associated with American linguist Noam Chomsky.

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.

Data model model that organizes elements of data and how they relate to one another and to real-world entities.

A data model is an abstract model that organizes elements of data and standardizes how they relate to one another and to the properties of real-world entities. For instance, a data model may specify that the data element representing a car be composed of a number of other elements which, in turn, represent the color and size of the car and define its owner.

Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development involves writing and maintaining the source code, but in a broader sense, it includes all processes from the conception of the desired software through to the final manifestation of the software, typically in a planned and structured process. Software development also includes research, new development, prototyping, modification, reuse, re-engineering, maintenance, or any other activities that result in software products.

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.

A production system is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior but it also includes the mechanism necessary to follow those rules as the system responds to states of the world. Those rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection.

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.

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.

In formal language theory, a grammar describes how to form strings from a language's alphabet that 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 Dr. Eldon G. Lytle (1936–2010).

<i>Aspects of the Theory of Syntax</i>

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.

CityEngine 3D modelling software

ArcGIS CityEngine is a commercial three-dimensional (3D) modeling software application 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.

Peter Boatwright is Allan D. Shocker Professor of Marketing and New Product Development at the Tepper School of Business and also Director of the Integrated Innovation Institute at Carnegie Mellon University. He is co-author of The Design of Things to Come: How Ordinary People Create Extraordinary Products and Built to Love – Creating Products that Captivate Customers, September 2010.

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 the concept of shape grammars with James Gips.

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.

Kinematic synthesis, also known as mechanism 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.