Shape grammar

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.[1]

Definition[Bearbeiten | Quelltext bearbeiten]

Eine Shape grammar ist formal definiert als ein 4-Tupel .

  • ist eine endliche Menge von Figuren,
  • ist eine endliche Menge von Figuren, sodass ,
  • ist eine endlichen Menge von Produktionsregeln
  • ist die Startfigur bestehend aus Elementen von und .

Elemente der Menge sind eine endliche Anordnung von beliebig vielen Elementen aus mit beliebiger Skalierung oder Orientierung.

Elemente aus , die in einer Regel aus , oder in vorkommen werden Terminale Figuren genannt.

Elemente aus sind sogenannte Nonterminale Figuren oder Marker. Elemente aus werden Shape-rules bzw. Produktionsregeln genannt und werden in der Form notiert.

Die linke Seite ist eine Figur bestehend aus einem Element aus kombiniert mit einem Elementen aus .

Die rechte Seite ist eine Figur und besteht entweder aus demselben Element aus das in vorkommt, demselben Element aus in , kombiniert mit einem Element aus , oder demselben Element aus in , mit einem Zusätzlichen Element aus kombiniert mit einem Element aus .

ist die Startfigur, bestehend aus Elementen von und . Sie beinhaltet normalerweise aus zumindest einem Element, dass als in einer Regel in vorkommt.

Beschreibung[Bearbeiten | Quelltext bearbeiten]

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 () verwendet, die aus parametrisierten Figuren bestehen. Durch das Einsetzen von konkreten Werten in die Variablen von und 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[Bearbeiten | Quelltext bearbeiten]

Shape grammars wurden ursprünglich für Gemälde und Skulpturen präsentiert,[1] 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[2] 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.[3][4][5]

Zu weiteren Bereichen in denen Shape grammars angewendet wurden, zählen Industriedesign und Ingenieurswissenschaften.[6]

Software Prototypen[Bearbeiten | Quelltext bearbeiten]

Hier eine Liste von im Internet verfügbaren Software Prototypen von Shape grammar Systemen.[7][8]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b 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. (deutsch Figur-Grammatiken und die generative Spezifikation von Gemälden und Skulpturen)
  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), S. 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: E. K. Antonsson, J. Cagan (Hrsg.): Formal Engineering Design Synthesis. Cambridge University Press, Cambridge UK 2001.
  7. A. McKay, S. C. Chase, K. Shea, H. H. Chau: Spatial grammar implementation: From theory to useable software. In: Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI EDAM), 26(02), 2012, S. 143–159.
  8. G. Stiny: Spatial relations and grammars. In: Environment and Planning B: Planning and Design, 9(1), 1982, S. 113–114.