Computer Graphics & Geometry
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
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.
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:
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]).
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
All of these steps are guided trough a grammar (Generation Grammar) comprising time specific rules.
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)
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)The rules from the generating grammar are processed by a specifically conceived parser (represented in Figure 2).
Figure. 2. Parser
All of the algorithms used in each of the steps are depicted in this section.
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
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
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,�}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.
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.
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 roomIn 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.
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.
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
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:
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.
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
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.
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
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]:
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)
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/.
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
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
[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.