Computer Graphics & Geometry

 

Rule-based Generation of Houses

N. Rodrigues, M. Dionísio and A. Gonçalves
DEI/ESTG-IPL, Portugal

, ,

L. G. Magalhães
UTAD, Portugal

J. P. Moura
UTAD, Portugal
Knowledge Engineering and Decision Support Research Group, Porto, Portugal

A. Chalmers
Warwick Digital Laboratory
University of Warwick, UK


Contents


 

Abstract:

The manual creation of virtual environments is a demanding and costly task. With the increasing demand for more complex models in different areas, such as the design of virtual cities, video games and computer animated movies, the need to generate them automatically has become more necessary than ever. This paper presents a method for the automatic generation of traversable houses, using architectural rules and an L-System to generate the rooms. The method has some innovating features, including the implementation of rules coded in a grammar, to produce 2D floor plans as well as complete 3D models with a high level of detail, in just a few seconds. The generation grammar was tested with legal rules from RGEU (Regulamento Geral das Edificações Urbanas) for Portuguese modern houses as well as heritage rules referring to the Roman civilization. A framework was also developed, and two different applications to evaluate it, which allow for the generation of multiple houses and interactive navigation.

1. Introduction

In the past few years, the use of algorithms to automatically generate virtual environments has become an area of growing interest for researchers all over the world. In fact, the idea of automatically creating environments is a fascinating idea that can lead to several benefits in different areas, such as Architecture, video games and movies. The goal is to place all, or most of the effort of creating an environment in computer software. In the context of the examples presented (i.e. Architecture, video games and movies), the effort required by human resources, could be greatly reduced and applied to more useful tasks, thereby leading to the creation of more realistic models. This paper presents a complete method for house models generation, including the interior and exterior geometry. The main case study of this method is centred on single, one floor, Portuguese homes and took into consideration strict legal rules provided by RGEU (Regulamento Geral das Edificações Urbanas, General Regulations for Urban Buildings). This is one of the main documents by which all Portuguese Architecture projects have to comply with. Other considerations were also taken into account, with the analysis of authentic floor plans, to obtain rules referring to features found in real houses, thereby complementing RGEU rules. Such is the example of separating a house into public areas and private areas.

The proposed method presents the following features, as follows:

This work also complements previous work from the same authors [1] and, although the method is mainly demonstrated with the case study of modern Portuguese houses, a generation grammar is introduced to encode time specific rules and tested (beside RGEU rules) with the example of heritage rules derived from Vitruvius (Marcus Vitruvius Pollio � Roman architect and engineer who lived in the 1st century BC, author of �De architectura�). Alongside a specific parser specially conceived to process these rules is also presented. Likewise the L-System was also tested against heritage rules.

A framework which implements the current method is also described to demonstrate that computer algorithms for house generation can be used, even on areas where there are strict legal rules to be respected. This framework implements an algorithmic approach for the automatic creation of a multitude of different house geometries in just a few seconds. This includes external geometry as well as interior geometry, with a high level of detail. At the time this document was written only single one floor family houses could be generated. This was our initial focus since these represent the types of houses normally chosen and personalized by the average person. Many features present in typical houses are created, including doors, windows, roofs and baseboards. At the same time, the features generated for the different rooms of the house reflect the characteristics of a real house. This stems from the results, where the final models present tiles, both in kitchens and bathrooms, and where different kinds of materials are represented for the floors of different rooms (e.g. mosaic for kitchens and bathrooms and wood floors for bedrooms).

1.1 Related work

The reconstruction of urban environments has been a focus of previous work from different areas, spanning several types of data sources (e.g. aerial images, laser scanning data) [2, 3] as well as different applications. There are also approaches that attempt to model a particular town or city [4], to those that create purely artificial environments [5], as stated by R. G. Laycock and A. M. Day in [6]. A different method of modelling (often referred to as Procedural Modelling) relies on algorithms to automatically generate buildings. These algorithms usually aim for the generation of new worlds, rather than the reconstruction of existing ones. They may also be used for the reconstruction of non existing worlds for which some kind of knowledge is available (e.g. floor plans, photographs) to support the reconstruction of realistic environments (e.g. reconstruction of archaeological sites where only some features about construction techniques related with the site are known).

Several methods have been presented in the recent past based on procedural techniques to generate urban environments. Parish and Müller, in [7] presented an approach based on shape grammars (L-System) to generate large urban environments. Wonka, in [8], also used shape grammars, but putting the main effort on creating detailed geometric façades on individual buildings. Later, in [9], the knowledge from the previous mentioned work was used by Müller and Wonka to propose a new method based on a mass model technique.

Greuter, followed a different approach in [10] based on optimization techniques to present a framework capable of generating real time virtual worlds and Finkenzeller, in [11], presented a technique for generating floor plans and resulting 3D Geometry based on a decomposition technique.

One common feature among these authors� techniques is that the main effort is placed on generating the exterior of the structures. This means that the structures are not traversable and thereby they may not be adequate to some fields of application (e.g. architectural applications and some video games).

In [12] the author addressed this problem by presenting two different approaches to generate both outer and inner characteristics of houses. Even though the presented work lacks some realism, some architectural issues were taken into account as the author makes the distinction between public and private parts of a house, as laid out by Christopher Alexander architectural patterns described in 1977 (�A Pattern Language� [13]). Indeed, in most of the related literature it is common to find references that acknowledge Alexander�s contribution, which may serve as a basis to several architectural applications. Nevertheless, a similar distinction has already been made in more ancient civilizations (though in different terms). One example is the Roman civilization where the literature adapted from Vitruvius �De Architectura� refers to the function of a room [14].

There is also an extensive literature based on the construction and analysis of architectural design, using the shape grammars presented in [15], which have become the foundation for many applications comprising different architectural styles (e.g. [16-19]).


1.2 Overview

This paper is structured as follows: Section 2 provides a general description of the proposed method for procedural house generation. Section 3 presents the L-System used to generate the list of rooms which define the interior of the house and the generation grammar which follows the whole method. Algorithms for floor plan generation are described in Section 4, and in Section 5 we discuss algorithms for 3D geometry generation. In Section 6, some results achieved with the proposed method are discussed, and in Section 7 some conclusions and plans for future work are presented.


2. Procedural House Generation

The proposed method is composed by three different major steps: Organization, Floor Plan and 3D Model (represented in Figure 1).


Figure. 1. Method components

Organization comprises two different sub-steps: first a list of rooms is automatically generated by an L-System and then the list is organized into a graph defining the connections between those rooms. In the Floor Plan step, the information from Organization is used to create a Floor Plan and in the 3D Model step 3D geometry is raised from the floor plan and mapped to X3D for the final representation onto the screen.

All of these steps are guided trough a grammar (Generation Grammar) comprising time specific rules.


2.1 Generation grammar

The first feature of the method described in this paper is the generation grammar which guides all of the steps in the generation of a virtual house. The grammar used in this method allows for the definition and transformation of shapes but it has a more general purpose than a proper shape grammar, reason why the authors decide to call it generation grammar. In fact, the grammar encodes several other features to ensure a proper control over the whole generation process (from the initial organization step until the generation of the 3D Geometry). The features of the grammar include: mathematic operations, definition of shape attributes, relations between shapes and nested rules.

The rules of the grammar are available to the user in a very simple form, which is similar to the one found in common spreadsheets, i.e. as a function. The following example corresponds to the simple definition of a bedroom which is 5 m long and 3 m wide.

defineShape(bedroom)
setProperty(length; bedroom; 5)
setProperty(width; bedroom; 3)

With this grammar it is possible to encode a whole set of time-specific rules and it was proofed with two different sets: a set corresponding to modern Portuguese houses (with RGEU rules) and a set with Roman houses (with Vitruvius rules). Additionally, the grammar also comprises most rules obtained from observation, mostly through the observation of real floor plans, and may also include expert rules inferred from experts based on their knowledge about time specific construction rules.

Taking into account the example of modern houses, it is possible to define links between rooms either at a higher level, i.e. defining the room types (e.g. public, private) which can be linked together or at a lower level, i.e. defining the specific rooms (e.g. kitchen, living room) which can link to each other.

setHighLevelLink(PublicRoom; PrivateRoom)

The first kind of rules (in the example above) define links by referring to the room type, instead of specifically referring to each room. Thereby it is possible with just a few rules to prevent links which do not represent the reality of modern houses (e.g. a private room never serves as a link between two public rooms, meaning that in the present context a bedroom could not be used as a passage from a dining room to a kitchen). This prevents the definition of all the possible links between each room, while also serves the purpose of separating the house in a public and in a private part.

With the second type of rules, it is possible to establish more detailed links by specifying which rooms can link to each other. One possible rule is presented is presented below:

setLowLevelLink(LivingRoom; Kitchen)

The grammar offers enough extensibility to incorporate different sets of rules, which is demonstrated with a few rules referring to Roman houses:

SetProp(TypeDim)
Atrium.TypeDim = 1
If(Atrium.TypeDim == 1; Atrium.Width = (Atrium.Length / 5) * 3)

The example above refers to the dimensioning of a Roman atrium, where there are three types of dimensioning according to Vitruvius� �De architectura�. In the example, the type chosen was the first one, which states that the atrium length is divided into five equal parts and then three parts are given to its width.

Parser

The rules from the generating grammar are processed by a specifically conceived parser (represented in Figure 2).


Figure. 2. Parser

A text file with all the defined rules serves as the starting point for the parser, where a lexical analysis is performed, splitting the file into meaningful symbols (tokens), defined by a grammar of regular expressions. Then a syntactic analysis is performed, where the tokens are checked to see if they form an allowable expression, in reference to the defined grammar. Type validity is also performed in this stage and a tree with all the validated tokens is returned. Finally (Interpreter), the tree is traversed and the appropriate actions taken for each validated expression.

3. Organization

This step presents some similarities to the method, presented by Jess Martin in [12], where the author employed a context free grammar and user defined ruleset, to generate a graph representing the rooms in a house and the connections between them. Though, in our method a grammar was used, containing legal rules (on the specific example of modern houses) and several observation rules. Conversely to the previous approach we also present a context free L-System in which terminal symbols represent different rooms of a house. All of the subsequent steps differ from the previous approaches, in which only the ultimate goals are similar, i.e. the generation of a house floor plan where the interior structure dictates the exterior of the house. The organization is sub-divided into two major steps: the L-System (responsible for the room generation) and the connection graph (responsible for the connections between rooms).

All of the algorithms used in each of the steps are depicted in this section.


3.1 L-System

To generate the list of rooms a stochastic L-System was used, therefore, there are several rules which may be chosen with a certain probability in each iteration. This means that for a certain house type (e.g. T0, T1, T2, etc. where the �T� stands for the number of bedrooms in the house. The house type determines most of the legal rules from RGEU in Portuguese architectural projects) several room configurations may be achieved, making it possible to control the derivations of the L-System. Thereby with the L-System it is possible to ensure that only valid configurations are produced and to control the derivations in such a way that some more frequent topologies are achieved.

The specified alphabet and production rules of the L-System are codified according to the legal rules, ensuring that some rooms must exist for different house types (e.g. in houses equalling three or more bedrooms, at least two bathrooms must exist). However the L-System is conceived to allow some extensibility so it can be used in very different situations with total control over their productions.

The use of the L-System is demonstrated with the example presented in Figure 3, where the productions for a T3 house are shown.


Figure. 3. L-System productions for a single floor T3 house

In Figure 3, when the first rule is applied, the initial symbol or axiom (Lot) is replaced by the house type. Then, in the next iteration, the house type is replaced with a proper list of rooms. After that, each room may be replaced by a more specific room (e.g. bedroom replaced by bedroom with private closet) and so on.

The process proceeds until only terminal symbols are reached.

The method is specific enough to ensure that only valid productions are generated, but also generic enough to extend to different house types. This is demonstrated by giving an example of extending the grammar to multi-floor houses. In this case a new level of abstraction could be added, represented by the symbols T32F, T3F0 and T3F1 in Figure 4.


Figure. 4. L-System productions for a two floor T3 house

The use of the L-System is further demonstrated with the example of extending it to other type of houses such as ancient Roman houses where an alphabet is formed by the symbols corresponding to the different parts of the house.

Considering the example of a classic Roman house, a typical organization is shown in Figure 5, where the house is divided in two parts: the area around the atrium (1) and the area around the peristylium (2).


Figure. 5. Classic Roman house organization [20]

Assuming that the axiom (ω) corresponds to the symbol RomanStructure, from the V alphabet and the productions (p0, p1,�, pn) correspond to the possible replacements between the symbols, then an example of a Roman house may be represented as:

V = {RomanStructure, RomanHouse, AtriumArea, Atrium, Ala, Cubiculum, �, PeristyliumArea, Peristylium,�}
ω = RomanStructure
p0: RomanStructure → RomanHouse
p1: RomanHouse → AtriumArea, PeristyliumArea
p2: AtriumArea → Atrium, Ala, Cubiculum, �
p3: PeristyliumArea → Peristylium, Cucina, Bathroom, �
p4: Cubiculum → Cubiculum, Cubiculum

In the present example the process may be interpreted as a decomposition system, where every symbol is iteratively replaced until only terminal symbols, corresponding to different parts of the house, are reached. This is demonstrated in Figure 6.



Figure. 6: L-System generations

Initially, the axiom RomanStructure is replaced by the symbol RomanHouse, in the first generation (g1). Then in the second generation (g2), the symbol RomanHouse is divided in two major areas: the area around the atrium and the area around the peristylum. Finally in the third generation (g3) the two major areas are divided into the corresponding parts of the house.


3.2 Connection Graph

The second step in Organization is the creation of a graph formed by the list of rooms created by the L-System. The consequent algorithm starts by adding the first room to the graph of rooms. Then corridors are created and added to the list of house rooms. After that, all the other rooms from the list are added to the graph and finally circular connections between rooms are created.


Creating corridors

Before the actual creation of the graph an initial step consists in determining the necessary number of corridors to link all the rooms of the house. Corridors are a predominant feature of Portuguese houses and were emphasized in the algorithm, although this does not necessarily means that corridors must exist. Indeed there are some rooms which may link directly to each other (e.g. living room linked to kitchen) and there are also other rooms which may be used to serve as a link between rooms (e.g. hall, atrium).

The number of necessary corridors is estimated following the ad hoc formula:

In the formula, the variable number_rooms represents the number of rooms which can be linked to a corridor and max_corridor_rooms the maximum number of rooms which a corridor can link to. This calculation determines the necessary number of corridors which are created and added to the list of rooms.

Adding the first room

In this step, the list of rooms is searched to find a room which can be linked to the front door. This is defined in the generation grammar, where only public rooms may link to the front door. This is due to the fact that it does not make much sense linking a private room, such as a bedroom, to an exterior door.


Adding remaining rooms

Once the starting point of the graph is established with the first node, the next step consists of iteratively removing each of the rooms from the list, including the previously created corridors, and adding them to the graph until the list is empty. This process starts by picking, from the room list, a room to be added to the graph. Then the graph is searched for all rooms which may serve as a source room to the current room to be added and one of those rooms is randomly chosen, thereby the corresponding link between the source room and the current room is defined. Finally the room to be added is removed from the list of rooms and the process repeats itself for the next room from the list. The whole process is performed following the rules defined in the generation grammar.


Adding circular connections

The last step of the algorithm is the creation of circular connections, i.e. connections between rooms which have the same origin (e.g. a corridor which links to a living room and to a dinning room that are also linked between each other). Only the rooms which are set to allow for circular connections in the generation grammar are considered. This step is the reason why the connections are stored in a graph form instead of a tree.

Figure 7 represents a graph, generated by the graph generation algorithm, for a T2 house.


Figure. 7. Algorithm generated graph

The output of this step is the list of rooms that will constitute the house as well as the corresponding connections between the rooms.

4. Floor Plan

The previous steps of the proposed method provide all the necessary data for the generation of the house floor plan which occurs in two sub steps. In the first one, area distribution, the total area available for the house is distributed through each room. In the second, room placement and sizing, the rooms are geometrically placed and properly dimensioned to their previously given size. In both cases several specific rules (e.g. RGEU rules) as well as observation-based rules were accounted for, to assure the realism of the final floor plans.

4.1 Area distribution

Before the placement of rooms and proper sizing a first approach to the house dimensioning is performed, where there are three possible ways to define the area of a house:

  1. Specify particular dimensions for each room of the house (e.g. living room dimensions: 3 m (width) x 5 m (length)).
  2. Specify a particular area for each room of the house (e.g. kitchen area: 16 m2).
  3. Specify the total area of the house.

This first approach does not conflict with the room placement and sizing step, where even though some further sizing may occur, due to spatial restrictions the ultimate goal is the room placement.

The third possibility of defining the area of a house is more explicitly described since if only a total area is specified, an algorithm to distribute this area through all the rooms of the house is necessary. In this alternative, an initial size is set for each room, corresponding to the minimum allowed according to legal rules. Then the difference between the total desired area and the sum of the current areas of the rooms is distributed proportionally, according to a weight previously set for each room of the house. For example, a living room usually has a greater priority than a bedroom, implying that it will receive a bigger portion. This is due to its public and social function, which means that it normally has a bigger area (this observation was obtained from authentic floor plans).

The last step in area distribution is to verify if any of the rooms exceed their maximum size. When this happens the excess area is removed and distributed through the other rooms that have not yet exceeded their limit. This last step is repeated until the total desired area is distributed through all of the rooms or until all the rooms have achieved their maximum area.


4.2 Room placement and sizing

The placement and further sizing of the rooms is done using a greedy algorithm (technique to solve problems where at each step of the algorithm the locally optimum choice is made with the hope of finding the global optimum). With this kind of algorithms there are two issues to be taken into account. One is that they may fail to find the best solution or a solution may not even be found (even if one exists). The other is that the algorithm is not complete (meaning that not all of the search space is contemplated in the search for a solution).

When generating a floor plan, the search space (i.e. all possible configurations for a certain connections graph between rooms of the house) is too vast to be taken into consideration. This is one of the reasons why the algorithm may fail to find a solution, since the solutions may be in the search space that was not analyzed. However, when this happens the presented method simply starts from the beginning, and in some cases the final user will not even be aware of the additional time taken by running more than once the algorithm. Hence, although the greedy algorithm is not complete, this feature contributes to enhance the performance of the algorithm by incorporating a grid to deal with room placement and sizing. This makes the number of possible solutions (positions and dimensions) for each room finite and also makes possible to control the performance of the algorithm by changing the parameters of the grid.

The general idea of the algorithm is to navigate through each node of the graph, and for each room represented by that node, create the corresponding polygon, ensuring the polygons are placed according to the links dictated by the graph branches. After all the rooms have been placed, algorithms for door placement (taking also into account for opening directions, to avoid conflicting doors, i.e. doors which intersect each other when opened) and window placement are also used to create the final floor plan.

All the steps of the algorithm are guided through RGEU rules (in the present case study), as well as several observation-based rules. For example, in door placement, in common rooms (e.g. living rooms, kitchens, bedrooms) doors are usually located near one of the extremities. On other kind of rooms (e.g. corridors) they are usually placed in the centre.

There are also more complex aspects of underlying sub algorithms necessary to generate the final floor plan. These include several metrics and formulas necessary to enforce the achievement of the desired results. There are also some rooms which need some special consideration, such as corridors which are created depending on the characteristics (e.g. size, geometry) of the rooms linking to it.

To achieve better results further algorithms were also implemented, such as an algorithm for edge smoothing to avoid sharp edges, i.e. rooms with many edges. Other aspect under consideration was wall thickness, where different wall thicknesses were used for inner and outer walls.

Figure 8 shows a generated floor plan for a T2 house.


Figure. 8. T2 Floor Plan

5. 3D Model

The floor plan is the source for the generation of 3D Geometry, which is achieved in three steps. In the first step, walls are raised from the floor plan. Then, in the second step, doors and windows are created and in the third step roofs are created and added to the final model. Each of these steps is further detailed in the next sections.

5.1 Walls

The wall creation accounts for two types of walls: exterior walls and interior walls. In both, the algorithm is relatively similar where for each edge of the floor plan a 2D polygon is created with a length equalling the edge length and a height equalling the height defined for the walls. The difference, between exterior and interior walls, is only that in interior walls the algorithm follows a room approach (i.e. each room of the house is browsed and for each one, all edges are accounted for to create the polygons that compose the house) as for in exterior walls the algorithm simply traverse the boundary of the floor plan. Floor and roof planes are also created in this stage.

Inner tiles (e.g. kitchens, bathrooms) are also added in this step, where for each previously created wall (configured to use tiles) a polygon is created based on the polygon length and mosaic height parameters and then extruded a proper thickness into a 3D volume. After this step, baseboards are created in a similar way where the only difference resides in the height parameter.


5.2 Doors and windows

After creating all the walls, doors and windows are integrated in the house by subtracting their geometry from the inner and outer walls, thereby creating holes, and filling these holes with the corresponding doors and windows. This subtraction process accounts for baseboards and tiles too.

Two types of windows were considered in this process: surrounding frame windows and bottom frame windows (represented in Figure 9).


Figure. 9. Window types (left: surrounding frame window, right: bottom frame window)

The door creation process is similar to the creation of windows, differing only in the geometrical variation between these two elements. Though there is also a difference between interior and exterior doors: conversely to interior doors, exterior doors usually do not have similar frames, i.e. the outer frames (usually in stone) are different from the inner frames (usually in wood). An exterior door is represented in Figure 10.


Figure. 10. Exterior door

5.3 Roofs

The generation of the 3D model is completed with the creation of the roof structure. In a first stage, all edges of the roof are created according to the floor plan. Then, the remaining roof is created using the �Straight Skeleton Implementation� proposed by Felkel and Obdrzálek in [21]. With this method, a hip roof may be created following four major steps which receive as input the building floor plan, as stated by Laycock and Day in [6]:

  1. Construct the Straight Skeleton.
  2. Determine the distance, d, from each vertex to its supporting edge.
  3. Perform a boundary walk, using the least interior angle, to determine the roof planes.
  4. Raise the vertices according to their distance from the supporting edge.

Figure 11 illustrates this process.


Figure. 11. Hip roof modelling [6]

After completing the Straight Skeleton, 3D half-cylinders are placed in each of the Straight Skeleton edges, to represent the roof spines and adequate textures are used to represent the roof planes.

Figure 12 presents a house roof created by this method.


Figure. 12. Hipped roof

The final geometry is modelled into X3D allowing the visualization of all the elements of the house through a 3D perspective, where the user can navigate through the exterior and interior of the created house. The generated models also feature collision detection and proximity sensors, for turning on lights and opening/closing doors, to increase the realism of the scene.

Figure 13 shows screenshots of a generated model representing the house exterior and interior.

     
Figure. 13. House exterior (left), house interior (right)

6. Results

To test the proposed method a framework � ArchHouseGenerator � was developed which implements all the algorithms presented in this paper. Two different applications were also developed to demonstrate the framework: HouseGen and WebHouseGen. Both applications have the same general goals, i.e. allowing the user to generate floor plans of houses and their respective 3D models. However the specific goal of each is somewhat the converse. On one hand, HouseGen runs on a Windows operating system and was developed to exploit all of the features of our framework. On the other hand, WebHouseGen was developed to allow the widespread divulgation of our framework over the Internet and, as such, offers a smaller bundle of functionalities. The first application � HouseGen � was developed in C# and exploits all the available features of the framework. It includes a wide collection of options available to the user ranging from the initial specifications (e.g. house type, rooms, areas) to some more specific customizations of the final models (e.g. materials selection, colours and textures, window linings, light source positioning).
Even though HouseGen is not a complete production-ready application but merely a prototype, there is still a great deal of options available to the user. Tasks such as defining the total area for the house or for specific rooms, configuring the rooms that will make up the house, generating floor plans which can be exported to some common formats (e.g. dwg, wmf, bmp, jpeg) and specifying new types of houses can be performed in the application.
It is also possible to generate environments composed of multiple houses (whose types can also be selected).

A screenshot of HouseGen may be observed in Figure 14.


Figure. 14. HouseGen

The second application � WebHouseGen � developed in ASP.NET, has a smaller range of options available to the user and was conceived with two different goals: demonstrate the simplicity associated with the generation of a new house and allow the widespread dissemination of the framework over the Internet. In this application only a few features of the framework were exploited and the output for the user is the floor plans as well as the 3D models. This application is available at: http://www.dei.estg.ipleiria.pt/projectosOnline/geradorEdificios/.


6.1 Performance tests

The efficiency of the framework was tested by running numerous tests involving the generation of virtual environments. One of the tests involved the random generation of different house types (ranging between T0 and T6), measuring the performance from 10 to 100 houses, considering intervals of 10 (Intel P4, running at 3.2 GHz with 1 GB of RAM). The results are shown in Figure 15.


Figure. 15. House generation times

In Figure 16 a diferent test involved the creation of a simple virtual city, that may be explored from a first person perspective, and which was created with different house types (the house types were chosen by the user and ranged from T0 to T3 houses). Using the same hardware than the previous test, the city has 60 different houses, made of about 170940 polygons, which were generated in about 18 seconds. Note that no performance issues were taken into consideration.


Figure. 16. Generated city with 60 houses


7. Conclusion and Future Work

The method presented in this paper was conceived for the procedural modelling of architectural structures. The main case study focused modern Portuguese houses, for which the method may represent a first step into the creation of architectural applications that may produce legal floor plans.
Moreover the method was also though to be extended to other areas, which is revealed by the flexibility provided by the L-System and the generation grammar. The created framework revealed to be capable of generating several distinct house types, with different characteristics (e.g. rooms, areas, paths), which seem adequate for the creation of virtual environments. Figure 17 shows different houses types representing the variety which may be achieved with the proposed framework.

The results achieved lead us to believe that the presented method is suitable for generating virtual environments in some areas of application, being the most obvious one Architecture. Nevertheless it may also be used, in the near future, in other areas where some level of realism is required such as virtual cities or even video games. Though the framework was initially conceived for the Architecture field, it can be easily extended to some other fields where a high degree of realism is required (e.g. virtual cities, reconstruction of virtual heritage sites, video games).

For Architecture, specifically, there are some features which need improvement, and new features which involve further work and the development of new algorithms. These are a few:

These represent a fraction of the identified future work topics involving the field of Architecture. In a near future, the aim is to extend this work to other areas, namely to the generation of time specific sites where there is some knowledge about the types of buildings and their architectural features. In this field there is still further work to be done exploiting new spatial techniques and testing them with real examples.


Fig. 17. House variety

References

[1] N. Rodrigues, L. Magalhães, J. Moura and A. Chalmers. Geração Automática de Estruturas Romanas. In Proceedings of CAAP2007, Leiria (Portugal). 2007.

[2] L. Martinez-Fonte, S. Gautama and W. Philips. An Empirical Study on Corner Detection to Extract Buildings in Very High Resolution Satellite Images. In Proceedings of ProRisc, IEEEProRisc, 25-26, Veldhoven, The Netherlands. 288-293. 2004.

[3] U. Weidner. An Approach to Building Extraction from Digital Surface Models. In Proceedings of the 18th ISPRS Congress, Comm. III, WG 2, Vienna, Austria, pp. 924-929. 1996.

[4] R. Ingram, S. Benford and J. Bowers. Building Virtual Cities: applying urban planning principles to the design of virtual environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST96), 83-91. 1996.

[5] Urban Simulation Team, http://www.ust.ucla.edu/ustweb/ust.html.

[6] R. G. Laycock and A. M. Day. Automatically Generating Roof Models from Building Footprints. In Proceedings of WSCG, Poster Presentation. 2003.

[7] Y. I. H. Parish and P. Müller. Procedural modeling of cities. In Proceedings of ACM SIGGRAPH 2001, ACM Press / ACM SIGGRAPH, New York, 301-308. 2001.

[8] P. Wonka, M. Wimmer, F. Sillion and W. Ribarsky. Instant architecture. ACM Transactions on Graphics 22, 3, 669�677. 2003.

[9] P. Müller, P. Wonka, S. Hägler, A. Ulmer and L. Gool. Procedural modeling of buildings. ACM Transactions on Graphics 25, 3. 2006.

[10] S. Greuter, J. Parker, N. Stewart and J. Leach. Undiscovered Worlds � Towards a Framework for Real-Time Procedural World Generation. Fifth International Digital Arts and Culture Conference, Melbourne, Australia. 2003.

[11] D. Finkenzeller, J. Bender and A. Schmitt. Feature based Decomposition of Façades. In Proceedings of Virtual Concept, Biarritz, France. 2005.

[12] J. Martin. The Algorithmic Beauty of Buildings: Methods for Procedural Building Generation. Honors Thesis, Trinity University. 2005.

[13] C. Alexander, S. Ishikawa and M. Silverstein. A Pattern Language. Oxford University Press. 1977.

[14] M. J. Maciel. Vitrúvio � Tratado de Arquitectura. IST Press. 2006.

[15] G. Stiny. Pictorial and Formal Aspects of Shape and Shape Grammars.Birkhauser Verlag, Basel. 1975.

[16] H. Koning and J. Eisenberg. The language of the prairie: Frank Lloyd Wright�s prairie houses. Environment and Planning B 8 (1981): 295-323. 1981.

[17] T. Knight. The forty-one steps. Environment and Planning B 8 (1981): 97-114. 1981.

[18] U. Flemming. More than the sum of its parts: the grammar of Queen Anne houses. Envi-ronment and Planning B: Planning and De-sign 14 (1987): 323-350. 1987.

[19] J. Duarte. Malagueira Grammar � towards a tool for customizing Alvaro Siza�s mass houses at Malagueira. PhD thesis, MIT School of Architecture and Planning. 2002.

[20] The Roman Empire, http://www.roman-empire.net/society/soc-house.html.

[21] P. Felkel and S. Obdrzálek. Straight Skeleton Implementation. In Proceedings of the 14th Spring Conference on Computer Graphics, Budmerice, Slovakia, 210-218. 1998.