Computation -friendly shape grammars with application to determining the interior layout of buildings from image data.

摘要

A shape grammar is a formalism that has been widely applied, in many different fields, to analyzing designs. Computer implementation of a shape grammar interpreter is vital to both research and application. However, implementing a shape grammar interpreter is hard, especially for parametric shapes defined by open terms.;This dissertation explores the problem of implementing a shape grammar interpreter, which arose in the context of the AutoPILOT project, in which we were seeking an algorithm to determine the interior layout of a building given an input of building features and a shape grammar describing the building style. A general approach was adopted based on the fact that when applied exhaustively, a shape grammar can generate, as a tree, the entire layout space of the building style. The approach essentially requires a parametric shape grammar interpreter that caters to a variety of building types.;As extensions to the fact that shape grammars can simulate any Turing machine, three corollaries are found that significantly impact the implementation of a shape grammar interpreter. They are the following: a shape grammar may not ha the language space of a shape grammar may be exponentially large; and parsing of a configuration against a shape grammar is generally unsolvable. The problem of interpreting a general parametric shape grammar is thus in general intractable; even parametric subshape recognition of two-dimensional, rectilinear shapes may require a high-degree polynomial time.;In reality, there are distinct but large classes of shape grammars, with differing underlying characteristics, for which interpreters are known to be computationally tractable. In this dissertation, I present a practical, 'general' paradigm for ensuring the tractability of designed shape grammars and implementing such shape grammars.;Even these tractable shape grammars may significantly differ from one another. A further way of classifying these tractable shape grammars, optimally in my belief, is by the types of data structure capable of carrying out their rule application. There are, of course, other factors that influence the computation of shape grammars; these include the description language and all adopted underlying manipulations. As a consequence, the paradigm is augmented so that every interpreter is supported by an application programming interface-wise (API-wise) framework, which comprises an underlying data structure, basic manipulation algorithms, and a description meta-language. The paradigm specifies an overall framework comprising a series of sub-frameworks. The overall framework is capable of ensuring the computation for a specified shape grammar interpreter. Shape grammars, which follow such a framework, are termed as computation-friendly. .;The concept of the overall framework is detailed by examining three sub-frameworks. These include one over 2D rectangular shapes (Rectangular sub-framework), one over 2D polygonal shapes (Polygonal sub-framework), and one for shapes describable by a graph structure (Graph sub-framework). The issue of how to develop a computation-friendly shape grammar is explained and illustrated by using the Baltimore rowhouse grammar as the exemplar.;The rectangular sub-framework, which has direct application to the AutoPILOT project, is examined in detail. This includes an investigation of estimating an initial interior layout from the feature input by constraints solution, and the application of spatial constraints from an estimated initial layout to prune the layout tree and 'fix' the open terms of the intermediate configurations. The building feature input for the AutoPILOT project is typically difficult to obtain. The technical feasibility of automatically extracting building features from image data is examined by comparing two pipelines, an ideal pipeline and a realistic pipeline..;In summary, in this dissertation, I develop a general approach for determining building interior layouts from exterior features with the aid of shape grammars. Central to the general approach, issues of implementing a shape grammars interpreter are formally investigated by complexity analysis. Subsequently, a practical 'general' paradigm is developed and demonstrated by sub-framework examples. The paradigm facilitates the development of a practical shape grammar interpreter and is readily extensible to future development.