Shape grammar

Shape grammars, deutsch Figur-Grammatiken, sind eine Art von Produktionssystem in der Informatik zur Generierung von geometrischen Figuren. Üblicherweise werden Shape grammars zur Erzeugung von zwei- bzw. dreidimensionalen Figuren eingesetzt, heutzutage vor allem in den Bereichen der Architektur und Computergrafik. Die Grundlage für Shape grammars wurde in einem Seminar-Artikel von George Stiny und James Gips im Jahr 1971 geschaffen.

Definition

Eine Shape grammar ist formal definiert als ein 4-Tupel $G=(V_{T},V_{M},R,I)$.

• $V_{T}$ ist eine endliche Menge von Figuren,
• $V_{M}$ ist eine endliche Menge von Figuren, sodass $V_{T}*\Cap V_{M}=\Sigma$,
• $R$ ist eine endliche Menge von Produktionsregeln
• $I$ ist die Startfigur bestehend aus Elementen von $V_{T}*$ und $V_{M}$.

Elemente der Menge $V_{T}*$ sind eine endliche Anordnung von beliebig vielen Elementen aus $V_{T}$ mit beliebiger Skalierung oder Orientierung.

Elemente aus $V_{T}*$, die in einer Regel $(u,v)$ aus $R$, oder in $I$ vorkommen werden Terminale Figuren genannt.

Elemente aus $V_{T}$ sind sogenannte Nonterminale Figuren oder Marker. Elemente $(u,v)$ aus $R$ werden Shape-rules bzw. Produktionsregeln genannt und werden in der Form $u->v$ notiert.

Die linke Seite $u$ ist eine Figur bestehend aus einem Element aus $V_{T}*$ kombiniert mit einem Elementen aus $V_{T}$.

Die rechte Seite $v$ ist eine Figur und besteht entweder aus demselben Element aus $V_{T}*$ das in $u$ vorkommt, demselben Element aus $V_{T}*$ in $u$, kombiniert mit einem Element aus $V_{M}$, oder demselben Element aus $V_{T}*$ in $u$, mit einem zusätzlichen Element aus $V_{T}*$ kombiniert mit einem Element aus $V_{M}$.

$I$ ist die Startfigur, bestehend aus Elementen von $V_{T}*$ und $V_{M}$. Sie besteht normalerweise aus zumindest einem Element, dass als $u$ in einer Regel $(u,v)$ in $R$ vorkommt.

Beschreibung

Eine Shape grammar besteht aus Regeln sowie einer Generierungs-Engine, welche die Regeln auswählt und verarbeitet bzw. berechnet. Eine Regel definiert wie eine existierende Figur (bzw. ein Teil davon) im Geometrischen Raum transformiert werden kann. Die Definition einer Shape grammar folgt der Standarddefinition einer Phrasenstrukturgrammatik von Chomsky, wobei statt Symbolen, Figuren („shapes“) verwendet werden.

Eine Shape grammar generiert eine Figur durch rekursives Anwenden der Shape rules, beginnend mit der Startfigur. Das Ergebnis der angewendeten Regel auf eine vorhandene Figur, ist immer eine neue Figur, die aus der vorhandenen Figur besteht, wobei ein Vorkommnis der linken Seite der Regel in der neuen Figur durch die Figur auf der rechten Seite der Regel ersetzt wurde.

Eine Shape grammar besteht minimal aus drei Produktionsregeln (=Shape rules). Einer Anfangsregel, zumindest einer Transformationsregel und einer Terminierungsregel. Die Startregel ist erforderlich um den Generierungsprozess zu starten, während die Terminierungsregel notwendig ist um die Generierung abzuschließen. Der einfachste Weg den Prozess zu stoppen, ist es den Marker (=Nonterminale) zu entfernen. Im Gegensatz zu Chomsky-Grammatiken können Produktionsregeln in Shape grammars nicht nur seriell, sondern auch parallel angewendet werden, ähnlich dem Ablauf von L-Systemen.

Ein Shape grammar System hat meist einen bestimmten Arbeitsbereich in der die erzeugten Formen angezeigt werden. Die Generierungs-Engine überprüft die bestehende Figur nach Übereinstimmungen mit den Bedingungen auf der linken Seite der Shape rules. Wird mehr als eine geeignete Regel gefunden, entscheidet die Engine, welche angewendet werden soll. Eine Alternative Methode ist es, zuerst eine Regel auszuwählen, und dann alle Übereinstimmungen der Linken Seite mit der aktuellen Figur zu suchen. Gibt es mehrere Übereinstimmungen, wird je nach Implementierung entweder

• die Regel auf alle Übereinstimmungen parallel angewendet,
• die Regel auf alle Übereinstimmungen seriell angewendet (könnte zu Inkonsistenzen führen) oder
• eine der Übereinstimmungen ausgewählt und die Regel nur auf diesen Bereich angewendet.

Parametrische shape grammars sind eine Erweiterung von Shape grammars. An Stelle der Produktionsregeln werden Shape rule schema ($\alpha ->\beta$) verwendet, die aus parametrisierten Figuren bestehen. Durch das Einsetzen von konkreten Werten in die Variablen von $\alpha$ und $\beta$ werde neue Shape rules definiert, welche dann in der üblichen Art und Weise verwendet werden um neue Figuren zu erzeugen. Durch diese Generalisierung kann eine größere Variation von Figuren generiert werden.

Anwendung

Shape grammars wurden ursprünglich für Gemälde und Skulpturen präsentiert, haben seither jedoch vor allem in der Architektur (Computer-aided architectural design) Anwendung gefunden. Shape grammars eignen sich dabei vor allem für kleine, klar definierte Probleme, wie etwa Struktur und Layout von Innenräumen oder Fassaden von Gebäuden. Shape grammars bestehen dabei sehr oft aus einer großen Anzahl an Regeln. So besteht die von William Mitchell präsentierte Shape grammar zur Generierung einer Villa im Stile des italienischen Architekten Andrea Palladio aus 69 Regeln, die in acht Durchführungsschritten angewendet werden.

Ähnlich zur Anwendung in der Architektur haben Shape grammars auch in der Computergrafik in den letzten Jahrzehnten an Bedeutung gewonnen. Shape grammars werden dabei vor allem bei der prozeduralen Modellierung von Gebäuden oder Städten eingesetzt (z. B.: für Filme oder Videospiele). Shape Grammars bilden dabei die Grundlage für zahlreiche entwickelter Systeme die anhand von Produktionsregeln eine Variation von unterschiedlichen 3D-Modellen generieren. Sowohl realistisch aussehende Straßenplänen, als auch Fassaden oder Innenräume von Gebäuden können dabei mit Hilfe von Shape Grammars prozedural erstellt werden.

Zu weiteren Bereichen, in denen Shape grammars angewendet wurden, zählen Industriedesign und Ingenieurwissenschaften.

Software Prototypen

Hier eine Liste von im Internet verfügbaren Software Prototypen von Shape grammar Systemen.

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

Siehe auch

• Formale Grammatik
• Graphersetzungssystem
• Lindenmayer-System
• Produktionssystem (Informatik)
• Prozedurale Synthese

Literatur

• G. Stiny, J. Gips: Shape grammars and the generative specification of painting and sculpture. In: Information Processing, 71, 1972, S. 1460–1465. North-Holland Publishing.
• G. Stiny: Introduction to shape and shape grammars. In: Environment and Planning B: Planning and Design, 7(3), 1980, S. 343–351.
• T.W. 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.

Weblinks

• www.shapegrammar.org
• Shape Grammar and Style Simulation (Liste von Referenzen)
• Shape grammar implementation: from theory to useable software (Übersicht über aktuelle Implementierungen)