In this paper we explore the theoretical basis for a concept of ‘computation-friendly’ shape grammars, through a formal examination of tractability of the grammar formalism. Although a variety of shape grammar definitions have evolved over time, it is possible to unify these to be backwards compatible. Under this unified definition, a shape grammar can be constructed to simulate any Turing machine from which it follows that: A shape grammar may not halt; its language space can be exponentially large; and in general, its membership problem is unsolvable. Moreover, parametric subshape recognition is shown to be NP. This implies that it is unlikely, in general, to find a polynomial-time algorithm to interpret parametric shape grammars, and that more pragmatic approaches need to be sought. Factors that influence the tractability of shape grammars are identified and discussed.
CarlsonCMcKelveyRWoodburyR, 1991, “An introduction to structure and structure grammars”Environment and Planning B: Planning and Design18417–426
3.
ChauH-H, 2002Preserving Brand Identity in Engineering Design Using a Grammatical Approach PhD thesis, School of Mechanical Engineering and Keyworth Institute of Manufacturing and Information Systems, The University of Leeds
4.
ChauH HChenXMcKayAPenningtonA, 2004, “Evaluation of a 3D shape grammar implementation”, in Design Computing and Cognition '04 Ed. GeroJ S, (Kluwer, Dordrecht) pp 357–376
HarryR LChristosH P, 1997Elements of the Theory of Computation (Prentice-Hall, Englewood Cliffs, NJ)
10.
HurSOhM-JKimT-W, 2009, “Approximation of surface-to-surface intersection curves within a prescribed error bound satisfying G2 continuity”Computer-Aided Design4137–46
11.
JowersI, 2006Computation with Curved Shapes: Towards Freeform Shape Generation in Design PhD thesis, Department of Design and Innovation, The Open University, Milton Keynes, Bucks
12.
JowersIEarlC, 2010, “The construction of curved shapes”Environment and Planning B: Planning and Design3742–58
13.
JowersIEarlC, 2011, “Implementation of curved shape grammars”Environment and Planning B: Planning and Design38616–635
14.
JowersIPratsMEarlCGarnerS, 2004, “On curves and computation with shapes”, in Generative CAD Systems Symposium: G-CAD 2004 Eds AkinOKrishnamurtiRLamK P, (Carnegie Mellon University, Pittsburgh, PA)
15.
KatzSSederbergT W, 1988, “Genus of the intersection curve of two rational surface patches”Computer Aided Geometric Design5253–258
16.
KelesH YOzkarMTariS, 2010, “Embedding shapes without predefined parts”Environment and Planning B: Planning and Design37664–681
17.
KnightT W, 1983, “Transformations of languages of designs”Environment and Planning B: Planning and Design10125–177
18.
KnightT W, 1989, “Color grammars: Designing with lines and colors”Environment and Planning B: Planning and Design16417–449
19.
KrishnamurtiR, 1981, “The construction of shapes”Environment and Planning B: Planning and Design85–40
KrishnamurtiR, 1992a, “The arithmetic of maximal planes”Environment and Planning B: Planning and Design19431–464
22.
KrishnamurtiR, 1992b, “The maximal representation of a shape”Environment and Planning B: Planning and Design19267–288
23.
KrishnamurtiREarlC F, 1992, “Shape recognition in three dimensions”Environment and Planning B: Planning and Design19585–603
24.
KrishnamurtiRStouffsR, 1997, “Spatial change: Continuity, reversibility and emergent shapes”Environment and Planning B: Planning and Design24359–384
25.
KrishnamurtiRStouffsR, 2004, “The boundary of a shape and its classification”The Journal of Design Research4(1)
26.
McCormackJ PCaganJ, 2003, “Increasing the scope of implemented shape grammars: A shape grammar interpreter for curved shapes”, in Proceedings of the ASME 2003 International Design Engineering Technical Conferences and Information in Engineering ConferenceChicago, IL
27.
MüllerPWonkaPHaeglerSUlmerAGoolL V, 2006, “Procedural modeling of buildings”ACM Transactions on Graphics25614–623
28.
MüllerPZengGWonkaPGoolL V, 2007, “Image-based procedural modeling of facades”ACM Transactions on Graphics2685
29.
PatrikalakisN MMaekawaTKoK HMukundanH, 2004, “Surface to surface intersections”Computer-Aided Design and Applications1449–458
30.
PiazzalungaUFitzhornP, 1998, “Note on a three-dimensional shape grammar interpreter”Environment and Planning B: Planning and Design2511–30
31.
PratsMJowersIEarlCGarnerS, 2004, “Generative curves in product design”, in Design Computing and Cognition DCC '04 Ed. GeroJ S, (Kluwer, Dordrecht)
32.
PressW HTeukolskyS AVetterlingW TFlanneryB P, 2007Numerical Recipes: The Art of Scientific Computing3rd edition (Cambridge University Press, Cambridge)
33.
StinyG, 1975Pictorial and Formal Aspects of Shape and Shape Grammars and Aesthetic Systems PhD thesis, System Science, University of California, Los Angeles, CA
34.
StinyG, 1977, “Ice-ray: A note on Chinese lattice designs”Environment and Planning B489–98
35.
StinyG, 1980a, “Introduction to shape and shape grammars”Environment and Planning B: Planning and Design7343–351
36.
StinyG, 1980b, “Kindergarten grammars: Designing with Froebel's building gifts”Environment and Planning B7409–462
37.
StinyG, 1991, “The algebras of design”Research in Engineering Design2171–181
38.
StinyG, 1992, “Weights”Environment and Planning B: Planning and Design19413–430
39.
StinyG, 2004, “How to calculate with shapes”, in Formal Engineering Design Synthesis Eds AntonssonE KCaganJ, (Cambridge University Press, Cambridge) pp 20–64
40.
StinyG, 2006Shape: Talking About Seeing and Doing (MIT Press, Cambridge, MA)
41.
StinyG, 2011, “What rule(s) should I use?”Nexus Network Journal1315–47
42.
StinyGGipsJ, 1971, “Shape grammars and the generative specification of painting and sculpture”, in Information Processing 71 Ed. FreimanC V, (North-Holland, Amsterdam) pp 1460–1465
43.
StouffsR, 1994The Algebra of Shapes PhD thesis, Department of Architecture, Carnegie Mellon University, Pittsburgh, PA
44.
StouffsRKrishnamurtiR, 1993, “The complexity of the maximal representations of shapes”, in Proceedings of the IFIP WG 5.2 Workshop on Formal Design Methods for CAD Ed. GeroJ S, (Kluwer, Dordrecht) pp 53–66
45.
StouffsRKrishnamurtiR, 2006, “Algorithms for the classification and construction of the boundary of a shapes”Journal of Design Research554–95
46.
WatsonBMüllerPVeryovkaOFullerAWonkaPSextonC, 2008, “Procedural urban modeling in practice”IEEE Computer Graphics Applications2818–26
47.
WeberBMüllerPWonkaPGrossM, 2009, “Interactive geometric simulation of 4D cities”Computer Graphics Forum28481–492
