Procedural Virtual Worlds

16

Chapter 2

Procedural Virtual Worlds Nuno Rodrigues Polytechnic Institute of Leiria, Portugal

Alan Chalmers University of Warwick, United Kingdom

Luís Magalhães University of Trás-os-Montes e Alto Douro, Portugal

Filipe Santos Polytechnic Institute of Leiria, Portugal

João Paulo Moura University of Trás-os-Montes e Alto Douro, Portugal

Leonel Morgado University of Trás-os-Montes e Alto Douro, Portugal

ABSTRACT With the increasing demand for more complex and larger models in different fields, such as the design of virtual worlds, video games, and computer animated movies, the need to generate them automatically has become more necessary than ever. Manual tools are no longer sufficient to match this rising need, and the impact that automatic tools may have within these fields is essential and may lead to an adoption of virtual worlds in a growing number of applications. Indeed, it is possible to eliminate most of the effort associated with the creation of such environments, by providing tools that may generate “massive” 3D content automatically. In consequence these tools may lead to an exponential growth of virtual environments and represent an important turn into the design of realistic virtual cities, which may have a huge impact on virtual world users. This chapter discusses the very complex issue of where and when procedural modelling may be used and presents some solutions and methods that have been successfully used in the aforementioned fields of application.

INTRODUCTION The continuous trend to use virtual worlds coming from several different domains, such as education and private sectors, leads to the need to efficiently create virtual environments. Indeed, in virtual DOI: 10.4018/978-1-60960-854-5.ch002

worlds as well as in the competitive markets of film, video games and several other applications, there is a trend to rapidly produce digital content at low costs. Manually designing virtual environments, during long periods of time, is not a cost effective solution with limited valuable human resources in many situations.

Procedural Virtual Worlds

Within the present context, procedural modelling represents an effective solution to produce digital content which is, in numerous virtual worlds, often characterized by urban environments. In order to assure the realism of the final models there is the need to account for many architectural concerns. These are essential aspects when dealing with different applications, such as heritage worlds amongst others. The increasing number of virtual world users from diverse areas creates the need to provide tools, able to efficiently produce realistic urban environments featuring traversable structures (e.g. houses), which achieve architectural coherence. Traditionally procedural modelling have been used mostly in film and games and is not, yet, a mainstream solution for the design of 3D content for virtual worlds, such as Second Life, Activeworlds or Croquet. It is a fact that some virtual worlds (e.g. Second Life) have well known native modelling tools, but these are not yet procedural. Some small procedural plug-ins do exist, often designed only to fulfil small specific requirements, such as the creation of textures. For these reasons, the next sections describe in which worlds may these procedural techniques and tools may be adopted and when and how it may be done. This chapter is mostly centred on the creation of urban environments, one of the targets of procedural modelling. Most virtual worlds, such as virtual worlds for socialization purposes, are often characterized by these type of models. The automatic content creation that can be achieved with such tools may deal with different features, such as the generation of clouds and textures, streets and roads, vegetation, houses and many other objects. These content generation have been used mainly in film and game industry but most of this features are often present in virtual worlds and may used in these in a similar way. This chapter starts by presenting an overview of procedural modelling. Then the dilemma behind where, when and how should procedural modelling be used in virtual worlds is addressed. This

is followed by a discussion of two possible targets of procedural modelling: reconstruction and generation. After that, some tools and techniques are described and finally some conclusions and future trends presented.

“GOING PROCEDURAL” In the last few years, the use of algorithms to automatically generate virtual reality environments has become an effective solution for the production of digital content. In fact, the idea of automatically recreating environments with very little modelling effort is a fascinating idea that can lead to several benefits in different areas including virtual worlds (a few other examples include architecture, video games and movies). The goal is to place all, or most of the effort, of creating an environment in computer software. This means that the time spent by human resources, such as computer modellers or even a plain virtual world user who wants to create their own models, would be significantly reduced and their time may be used on more useful tasks. The creation of virtual environments via an algorithm (instead of manually) is often identified as “generation” of virtual environments. Similarly, the set of techniques which rely on algorithms to generate these environments are often referred to as “procedural modelling” techniques. Although there are diverse techniques used in procedural modelling, such as grammar based techniques (e.g. L-systems1), fractals2 and generative modelling3, the general purpose of these is similar: apply parameterised algorithms to produce 3D virtual scenes. The result is to create 3D models or textures from user choices rather than manually modelling each of the environment features. Procedural modelling techniques embody essential tools, in situations where it would be cumbersome to create 3D models manually, or where current software does not provide efficient means to produce those models. One particular

17

Procedural Virtual Worlds

situation, which reveals the huge advantages of such techniques, is their use in computer animations where one can easily imagine the amount of effort necessary to perform some manual tasks, such as perform characters movement including their hair and clothing. For these reasons recent animation movies use algorithmic simulations to perform characters animation. It is also easy to imagine several situations where procedural modelling may be useful such as the generation of “massive” 3D models to quickly populate a virtual world (e.g. traversable buildings for a whole city). As such there is an increase demand for tools that can produce 3D content, which in some situations requires automatic solutions as manual creation methods are no longer sufficient. The generation of urban structures seems to be a very appealing target for the use of procedural techniques, since urban models embody most of the computer graphics environments in several areas. For this reason there has already been a number of papers produced concerning urban procedural modelling such as the work presented in “Procedural Modeling of Cities” (Parish & Müller, 2001), in “Real-time Procedural Generation of ‘Pseudo Infinite’ Cities” (Greuter, Parker, Stewart, & Leach, 2003), in “Instant Architecture” (Wonka, Wimmer, Sillion, & Ribarsky, 2003) and in “Procedural Modeling of Buildings” (Müller, Wonka, Haegler, Ulmer, & Gool, 2006). One common characteristic amongst most of the existing methods within the field of urban procedural modelling, e.g. (Coelho, Bessa, Sousa, & Ferreira, 2007; Pascal Müller, et al., 2006; Parish & Müller, 2001; Wonka, et al., 2003), is the use of some kind of grammar (e.g. shape grammars: L-systems, split grammars4, etc.), although the purpose may be very diverse (e.g. generate roads, determine building locations, generate building facades, etc.). Indeed, even within recent techniques ranging photogrammetry and/or LIDAR, grammars are also applied, e.g. (Aliaga, Rosen, & Bekins, 2007; Hohmann, Krispel, Havemann, & Fellner, 2009; Müller, Zeng, Wonka, & Gool,

18

2007). It is a fact that grammar approaches require many rules to generate the models but if, at first, this seems a clear disadvantage, compared to other approaches, the flexibility provided by grammars makes them a powerful tool for the generation of urban models. Furthermore, it is also possible to avoid the text-based complexity of grammars by designing efficient interactive visual editing systems for shape grammars, such as the one presented by Lipp et al. (Lipp, Wonka, & Wimmer, 2008). Figure 1 presents a procedural generated virtual environment including algorithm generated objects (houses and roads) and manually designed objects (fences, trees and lightning poles). All of the houses in the picture are completely traversable and although some objects were manually designed they were algorithmically placed (via an L-system).

WHICH WORLDS? The first question concerning the use of procedural modelling techniques in virtual worlds is where, i.e. in which virtual worlds may they be used? This raises another question, which types of virtual worlds exist? The most popular virtual worlds are used for entertainment purposes. Most of them belong to the category of the so called Massively Multiplayer Online Role Playing Games (MMORPG) (Woodcock, 2008) and are games in their real sense as they have an inbuilt narrative or meta-narrative for the users which have in that game a specific purpose or goal to achieve. Some of the most played MMORPGs today are World of Warcraft (Warcraft, 2010), Lineage (Lineage, 2010) and RunEscape (RunEscape, 2008). One other popular use of virtual worlds is for socialization purposes. The so called Massively Multiplayer Online Social Games (MMOSG) which, without necessarily imposing a narrative to the user, focuses on the social aspect of it as

Procedural Virtual Worlds

Figure 1. Procedural generated environment

the main purpose, are expanding. Second Life (SecondLife, 2009) is currently the most well known virtual world of this kind, and the most open to content development by users, but many others have similar or greater popularity, e.g. IMVU (IMVU, 2010), particularly within the age groups of children and teenagers, e.g. Habbo Hotel (Hotel, 2010), Club Penguin (Penguin, 2010). The “Universe chart” in Kzero (KZero, 2010) shows the variety and popularity of virtual worlds universe. One interesting aspect of some virtual worlds, MMOSGs in particular, is that as they don’t have a goal to achieve or narrative to follow but rather they give the users the tools to make them. Second Life is well known by its 3D modelling tools (not procedural), which allow users the ability to program and control the behaviour of the world’s objects. Other MMOSGs have lesser degrees of freedom in the level of control they give their users for creating content, but several provide tools that are adequate within the scope of this chapter (e.g. Activeworlds and Croquet). Virtual Worlds that have these two features give its users tremendous possibilities as worlds can be created and programmed for certain activities

as education, scientific research and collaborative work, amongst others. These two perspectives see virtual worlds as pre-existing entities upon which one wishes to create content. A third perspective is that one may decide to create a virtual world from scratch, and provide the content from the start. This can be done using either a set of traditional programming tools or a special-purpose development library, such as Unity3D (Unity3D, 2010). The potential of virtual worlds is very rich but has yet to be fully realised (Prentice, 2007). Still, there are already a great number of projects that take virtual worlds for education purposes (Ching-Song, Yan, & Jiann-Gwo, 2009; Dickey, 2005; Dreher, Reiners, Dreher, & Dreher, 2009; Natho & Pfeiffer, 2010) and training (Heinrichs, Youngblood, Harter, & Dev, 2008). These two uses of virtual worlds take advantage of, very often, virtual worlds as a simulating platform. Simulation may be seen as a technique “to replace or amplify real experiences with guided experiences, often immersive in nature, that evoke or replicate substantial aspects of the real world in a fully interactive fashion” (Gaba, 2004). Virtual worlds, as simulators, have some advantages over other types of simulators as high-fidelity simulators are

19

Procedural Virtual Worlds

expensive and students may be geographical far apart in virtual worlds (Heinrichs, et al., 2008), and in that virtual worlds can be more flexible in the range of educational activities, by leveraging the ability for students/trainees to create or modify content. Other purposes for virtual worlds that are worth mentioning are the ones used for collaborative work (Back, et al., 2010; Bouras, Tegos, Triglianos, & Tsiatsos, 2007; Snowdon, Churchill, & Munro, 2001), scientific research (Bainbridge, 2007), virtual tourism (Bellotti, Berta, Gloria, Panizza, & Primavera, 2009) and military applications (3DSolve, 2010; Benford, Greenhalgh, Rodden, & Pycock, 2001). The commercial potential of virtual worlds is also subject of much research (Fang & Cai, 2009; Seidel & Berger, 2007). Now, that a brief overview of has been presented the initial question persists. The fact is that independent of the type of virtual world there is a common feature amongst them, which is they all use 3D models, that represent nature, urban structures or even other human-made objects. Indeed it is easy to foresee a set of contexts where automatic 3D modelling mechanisms based on user parameters are useful. For example, a virtual city with hundreds or thousands of buildings can be implemented for real life simulations (e.g. earthquake damages scenarios) as virtual worlds may also have powerful physics engines integrated. These can also be useful for games and movies as new scenarios could easily be seen and tested since it would only be needed to change the preprogrammed rules for building creation. These features makes procedural modelling a suitable tool for mostly all of the presented virtual worlds presented, since it ranges several different features ranging the simple generation of a texture, performing real objects animations (e.g. smoke, fire) to the complete generation of urban environments.

20

WHEN? Once it is established the different types of virtual worlds which may benefit from procedural modelling it is also essential to determine when these techniques might be applied. This question does not have a straightforward answer since it is dependent of several aspects. For example, it depends of the availability of efficient methods/ tools to produce the models. Most likely a common virtual world user who does not have any programming skills will not be willing to develop an algorithm to create virtual models. Another example is the purpose for which the models are intended. It is not the same generating models for a pure imaginary world than for a world where the purpose is to represent real world structures. In fact, in procedural modelling techniques, the quality of the 3D models is closely related with the quality of the algorithm used to generate them, whereas in manual techniques the quality of the models is directly related to the skills of the human modeller. Furthermore the choice of when to use a procedural technique is always dependent on the person who will design the world, either this is a computer graphics modeller or a common virtual world user. Most likely it is possible that, even when considering a procedural approach, the user would like to manually create some features or make some customizations thus producing a hybrid model. After all, as previously stated, the goal of procedural techniques is not to replace human resources or creativity but instead to provide efficient tools aiding the sometimes arduous and tedious task of producing complex 3D content. These are just a few examples since there may be many other aspects constraining the use of procedural techniques. So, as may be understood there is not a unique answer of when to “go procedural”. Though, one may say at the very least that procedural techniques are very likely the prime resort for the generation of virtual worlds, in present days, where it would be cumbersome

Procedural Virtual Worlds

to create 3D models manually or where current software does not provide efficient means to produce those models.

HOW? The previous sections described where and when procedural modelling techniques may be used but did not described exactly the features of the different virtual worlds. This section presents how they may be used. Most procedural modelling techniques address the generation of different features which may refer either to generation of static models or animated ones, allowing for the generation of models representing many of the physical objects present in our world. In (Watson, et al., 2008) the authors present a briefing of some of the vast quantity of procedural modelling “targets” and the corresponding techniques commonly used by several authors to generate or simulate each of them. L-systems are identified for the generation of plants (Prusinkiewicz, Lindenmayer, & Hanan, 1988), agent-based methods to model and animate different types of objects – e.g. particle systems to model fuzzy objects such as fire and smoke (Reeves, 1983) and Reynolds’ boids to animate flocks, schools and herds (Reynolds, 1987), Perlin’s noise to simulate clouds and natural textures (Perlin, 1985), and fractal techniques to synthesise natural landscapes (Fournier, Fussell, & Carpenter, 1982) or even simulate erosion effects on them (Musgrave, Kolb, & Mace, 1989). All of these features make it possible to use procedural modelling in a large diversity of applications where different techniques may be used to couple with different aspects. For example, they may centre the attention on the generation of individual houses (Martin, 2005; Rodrigues, Dionísio, et al., 2008a, 2008b; Rodrigues, et al., 2009), on tall buildings and skyscrapers (Greuter, et al., 2003; Parish & Müller, 2001; Park, 2005), or on large urban environments (Bostrom, et al.,

2004; Willmott, Wright, Arnold, & Day, 2001), applying urban planning principles to the design of virtual environments (Ingram, Benford, Rd, & Bowers, 1996), modelling from architectural rules (Fuchs, 2006; Luca, Véron, & Florenzano, 2007; Rodrigues, Dionísio, et al., 2008a, 2008b; Rodrigues, Magalhães, Moura, & Chalmers, 2008), dealing with specific features as the generation of streets and roads (Chen, Esch, Wonka, Müller, & Zhang, 2008; Parish & Müller, 2001), or on house specific house features such as windows (Charbonneau, Boulerice, Booth, & Tidafi, 2006). Likewise, they may focus on modern architecture (Bessa, et al., 2005; Coelho, et al., 2007; Martin, 2005; Rodrigues, Dionísio, et al., 2008a, 2008b) or on heritage architecture, such as Roman (Müller, Vereenooghe, Ulmer, & Gool, 2005; Rodrigues, Magalhães, Moura, & Chalmers, 2007; Rodrigues, Magalhães, et al., 2008) or Mayan architecture (Müller, Vereenooghe, Wonka, Paap, & Gool, 2006). In another perspective, they may emphasise optimisation techniques, deal with real-time issues (M. Carrozzino, Tecchia, & Bergamasco, 2009; Döllner & Buchholz, 2005; Willmott, et al., 2001; Wonka, et al., 2006), or even address photorealism (Müller, Vereenooghe, Vergauwen, Gool, & Waelkens, 2004) or high-fidelity (Sundstedt, Chalmers, & Martinez, 2004) concerns. From all of the above it is clear that the requisites are not the same for each of the different applications where procedural techniques may be employed. The next section addresses the use of procedural techniques for two of their main purposes: reconstruction and generation.

RECONSTRUCTION/GENERATION? At the beginning of this chapter some features of procedural modelling techniques were uncovered showing their undeniable advantages for the generation of new worlds. Indeed, often procedural modelling is the tool of choice when generation is in order. Additionally it may also prove to

21

Procedural Virtual Worlds

be useful to create virtual models representing structures lost in time, or even to create virtual models of existing structures. For these reasons it is important to first establish the significance of the terms reconstruction and generation within the present context, presented below: •

•

Reconstruction – creation of models using automatic techniques representing existing structures or creation of models representing structures no longer existing but for each there is enough evidences (i.e. ruins, floor plans, photographs, etc.) to faithfully reconstruct them. Generation – generation of new worlds, i.e. automatic creation of fictional structures not intended to represent any ever-existing structure.

Throughout the rest of this section the use of procedural techniques to perform the reconstruction and generation of structures is discussed, exemplified with heritage structures one of the main targets for “procedural reconstruction”. If the use of procedural techniques which produce fictional structures it is somewhat simple to realize in some areas (e.g. games), their use on areas such as archaeology where the general idea is to record historical fact it is not. Indeed, although these techniques should be carefully be thought out before they are employed in such area, since depending of the case study and purpose of the virtual models there may are more efficient methods (manual modelling), when realism is the main concern. Some literature concerning procedural techniques has been used to create heritage models representing ancient structures. For example, in (Müller, et al., 2005) the authors wrote a set of rules to generate a virtual model of Pompei using CityEngine, a system introduced by Parish and Müller (Parish & Müller, 2001). Later, using the same system, the authors of “Procedural 3D Reconstruction of Puuc Buildings in Xkipche” (P.

22

Müller, et al., 2006), generated Puuc-style buildings similar to the ones that may be found in the ancient Mayan site of Xkipché, in Mexico. Without disregarding the efficiency of such techniques and tools the fact is that generation produces fictional structures, although in the present cases these are based upon known heritage construction rules or tries to reproduce features found in existing structures. However, in structures showing more complex geometric harmony, the process used, i.e. the set of rules necessary to describe the physical geometry of the buildings may prove to be, in several cases, harder to achieve (or take more time) than when using traditional methods (manual modelling) or even impossible. Indeed, an experienced modeller may produce 3D models very efficiently when given adequate data (e.g. measurements, photographs, etc.) about a physical structure. Unfortunately, manual modelling does not allow the efficient reproduction of large virtual environments showing diversity (e.g. creation of different houses corresponding to a similar architectural style). For the above reasons and although the generation of models representing ancient structures may prove to have some interest or applications within archaeology and several other areas, when trying to faithfully reproduce an existing structure it does not always is a better solution. Therefore sometimes it is not desirable to use only algorithmically generated structures. The next section describes a way of using procedural modelling and yet maintaining realism in the models, by using a hybrid approach.

Realism When addressing reconstruction or even considering a procedural technique for reconstruction it is important to think in which areas it may be applied. So, one may think at most obvious areas such as archaeology, architecture, etc. This raises some questions concerning the ability to represent or reconstruct structures using procedural methods

Procedural Virtual Worlds

since, for example, areas such as archaeology are highly driven by proof and realism. Most known methods and tools for the automatic generation of models representing man-made structures usually rely on procedural techniques, which often produce models through the means of simple shape composition (or decomposition – depending on the technique). As previously mentioned these techniques sometimes do not allow the use of more complex objects. In areas such as archaeology, one main key point to recreate the past is the realism, which means that it is crucial do create features with a higher level of detail. Therefore, it is advisable to use manually modelled objects rather than to try to use some algorithm which would resemble the real structures that are pretended to be represented. Producing these realistic models may be achieved either by designing them from known similar objects (e.g. artefacts, columns, windows, etc.) or even by replicating existing ones. This last option, however, does allow using faster reproductions, since there is the possibility of using automatic techniques such as laser scanning, to create the objects. Independently of how the models are created, the fact is that often there is evidence which indicate that most probably, within a certain architectural style, similar structures use identical features. This is what led Rodrigues et al. in (Rodrigues, Magalhães, et al., 2008) to define a hybrid approach, i.e. an approach which joins both manual

and procedural modelling, to meet the demanding concerns behind the reconstruction of heritage structures, but also providing most of the features brought by procedural techniques. Thus, the authors used an object database which may be used to represent some more specific house features. An example of this is the House of the Skeletons, a Roman heritage house of Conimbriga, Portugal. For the creation of the house several manual objects (e.g. triclinium window, impluvium, tuscan columns), modelled in an external application (3D Studio Max) were used, represented in Figure 2, and placed accordingly to grammar rules. Integrating these objects into the final geometry is simply a matter of placing it in the desired place (e.g. impluvium, columns) or by subtracting the corresponding object geometry from the wall where they are to be placed (e.g. windows). The grammar rules used in the approach were based on the knowledge left by Marcus Vitruvius Pollio – Roman architect and engineer who lived in the first century BC, author of “De architectura”. Moreover the same authors also provided a means to describe the whole geometry of a house through textual specifications (using a grammar) allowing both the generation of new houses but also the reconstruction of existing ones. This feature is particularly useful, because it allows a user with no knowledge or experience with modelling tools, to construct his/her own models through a set of textual specifications. These specifications were used to perform the reconstruction of the House

Figure 2. External objects; From left to right: triclinium window, impluvium, tuscan columns (Silva, Rodrigues, & Gonçalves, 2004)

23

Procedural Virtual Worlds

of the Skeletons which was then compared to a manual model showing very similar features. Figure 3 shows both of these models. This approach may be considered a hybrid one, since it combines procedural techniques together with manually modelled objects. This allows a more realistic appearance of the final models and uses the best of both approaches: the efficiency of procedural techniques and the realism of manually modelling.

Automatic Reconstruction? The previous section described how realism may be achieved using procedural modelling but one question still persists: how may procedural modelling techniques/tools be useful for areas such as archaeology? The first answer to this question is to efficiently produce models of non-existing worlds for which there is some kind of knowledge (e.g. floor plans, photographs) to support the reconstruction of realistic environments. Projects such as “Rome Reborn”, “an international initiative whose goal is the creation of 3D digital models illustrating the urban development of ancient Rome from the first settlement in the late Bronze Age (ca. 1000 B.C.) to the depopulation of the city in the early Middle Ages (ca. A.D. 550)” (Rome, 2010), use both reconstruction, which

currently is done manually, and generation. The buildings present in the digital model are divided into two kinds: “Class I” and “Class II” buildings. “Class I” buildings are manually modelled based on archaeological evidence (such as excavations, studies and ancient literary sources). “Class II” buildings are procedurally modelled from a digitization of the Plastico di Roma Antica, “a large plaster-of-Paris model of imperial Rome (16x17 meters) created in the last century” (Guidi, et al., 2005). The process consists of replacing the scan data from the digitization with geometrically simplified forms and the modelling of these simplified form faces with detailed architectural features (e.g. doors, windows, balconies). The process also included the correction of known errors present in the Plastico di Roma Antica. Another interesting feature about “Rome Reborn” is that CityEngine, an urban modelling software from Procedural Inc. described in section “Tools and Techniques”, was used in “Class II” buildings. Rome Reborn is also published in the Internet as “Ancient Rome 3D” in Google Earth (A. Rome, 2010). The second answer to the question presented is to support the generation of distinct possibilities to allow experts to draw some conclusions or conceive different hypotheses about lost worlds. For example in several Roman heritage sites (e.g. Conimbriga, Portugal) some parts of the city are yet uncovered or may even be lost. By taking as

Figure 3. House of the Skeletons; Left: manual model, Right: grammar model

24

Procedural Virtual Worlds

an example similar Roman cities it is possible to determine what may exist in most of the site. For this reason, Rodrigues et al. in (Rodrigues, Magalhães, et al., 2008) have designed an grammar approach which allows the specification of several features of a house, including incomplete specifications which allows the generation of several resembling models within an architectural style. The presented approach is demonstrated with the generation of several Conimbriga’s Roman houses showing some dissimilarity amongst them. The idea of generating structures similar to existing ones is not something new and not even confined to heritage. In fact, it is something that is pursued by several authors and may be referred as inverse procedural modelling. For example, (Aliaga, et al., 2007) describes an interactive system for the creation of new buildings in the style of others or for the modification of existing buildings. The idea is to create geometric models from photographs, divide the building into their basic external features (e.g. floors, windows, etc.) and create a grammar that captures the repetition patterns of these features. Then it allows the user to design building configurations from building blocks and finally to divide these building configurations into the several features, using the repetition patterns from the grammar. One of the most interesting aspects of this approach is the idea itself and its potential use in architecture. Nevertheless, there is still a great deal of interaction needed from the user, starting from the initial photograph mapping until the design of the final building blocks (nevertheless the interaction in this last step does make a lot of sense if the idea is for the user to provide new geometries). Another aspect to notice about this approach is that only facades are created.

TOOLS AND TECHNIQUES Although recently procedural modelling is becoming mainstream in other applications, it has already been applied for a number of years in several applications such as games. The initial motivation for this relied in the fact that earliest computer games were limited by memory constraints of existing hardware and software. For example, “The Sentinel”, a video game featuring 3D graphics allowed the generation of 10,000 different levels, which would be stored in about 64 KB of memory (another is “Elite”, a space video game, which was initially planned to contain approximately 282 trillion galaxies with 256 solar systems each). Nowadays the motivation is not exclusively related to hardware/software resources but also on the human resources necessary to produce large 3D environments. For this reason the trend to use procedural techniques to produce 3D models remains in modern games. Such is the example of “.kkrieger” and “Will Wright’s Spore” which use procedural synthesis to generate the graphics (the first, “.kkrieger” has the particularity of packing video effects in less than 97 KB). Many more examples exist, such as the first-person shooter video games “Left 4 Dead” and “Left 4 Dead 2”, released in 2008 and 2009 respectively. Another example in a different area is the competitive movie industry where every year new movies rich in digital content, produced through procedural techniques, appear. In the field of applications there is also some tools specific for the generation of different features, for example, to generate terrains there are tools available such as Terragen or Acropora; for trees, Speedtree; for urban structures, CityEngine (further described shortly) and Cityscape; for textures, Art of Illusion; to perform animations, Houdini, etc. Beside these applications there are also procedural plug-ins for existing applications, for example, Filter Forge is a plug-in for Adobe

25

Procedural Virtual Worlds

Photoshop for designing procedural textures. These represent only a fraction of the available tools and most of these tools are not exclusively to one type of content. For example, some tools for the generation of urban environments may also allow the generation of terrains and trees. Furthermore, although some of these tools are available for free others are very expensive. So, it is really up to the user to choose the software which best fits their purpose. (M. Carrozzino, et al., 2009), presented the City Modelling Procedural Engine (CMPE), a system for the automatic/semi-automatic reconstruction of virtual models of cities integrated in the XVR framework (Marcello Carrozzino, Tecchia, Bacinelli, Cappelletti, & Bergamasco, 2005), a framework for the development of Virtual Reality (VR) applications developed by some of the same authors. Indeed, mostly built with XVR, it uses 3D urban models and may include vehicle simulators, crowd behaviour simulators, according to the Pecchioli, Carrozzino et al. (Pecchioli, Carrozzino, & Mohamed, 2008), which also present a methodology to deal with the access to information related to Cultural Heritage. In (CGV, 2010) several ongoing projects are also presented featuring High-Quality Urban Reconstructions by Fitting Shape Grammars to Images and derived Textured Point Clouds and also the generation of 3D city models, using existing data such as aerial photos and laser scans. Indeed such examples, e.g. (Hohmann, et al., 2009) proof that even procedural modelling approaches may also incorporate data and techniques used in photogrammetry and laser scanning. One of the most remarkable tools, in the field of the procedural urban environments, is City Engine, a commercial software produced by Procedural Inc. (Procedural, 2009). City Engine is a 3D modelling software especially conceived for the generation of urban environments, using procedural techniques, which allows the generation of street networks which take into account the topography of the terrain. Furthermore, real

26

city networks may be imported into this software, from several other programs such as OpenStreetMap (OpenStreetMap, 2010). The software also includes a scripting language to develop architectural 3D content and an interface to parameterize specific building features (e.g. height, age). CityEngine also allows batch exports of 3D models for several file formats such as: Wavefront OBJ, Autodesk FBX, Autodesk 3DS, COLLADA DAE, MentalRay MI and Renderman RIB. Some virtual worlds provide tools to develop 3D content (with scripts for behaviours if desired) but others rely on 3rd party tools for this task, as Blender or 3D Studio Max, giving the user “import content” tools. As this may be desirable, giving the users the liberty to use their favourite modelling tool, the lack of a common 3D modelling format, for the several virtual worlds, could also be a challenge as some problems of conversion between formats still exist. Presently, virtual world users may implement their own procedural techniques and tools for content generation, within the constraints of each platform (e.g., scripting languages, automated client software, etc.). Some 3rd party tools are available, with varying degrees of power and applicability, such as the ones described in this section, albeit its use is not widespread. The dilemma behind using 3rd party tools is that these are not integrated in virtual worlds meaning the models have to be exported from 3rd party tools and imported to the virtual world. Beside conversion problems that may arise there is another aspect to take into consideration, which is the fact that 3rd party tools often produce dummy models, i.e. generic models which may not suit the virtual world. Indeed, although some virtual worlds allow the import of several formats, most of the time not all of the features of the format are supported due to constraints related with the virtual world. Furthermore, the models may be suitable for some applications but sometimes they are not appropriate for virtual worlds, which have to maintain some minimum performance. Additionally, the lack of a common format amongst

Procedural Virtual Worlds

virtual worlds sometimes constrains the use of certain application to produce the models. The above reasons led Rodrigues et al., in (Rodrigues, et al., 2009) to present a framework prototype – ArchHouseGenerator – for the development of virtual models which integrates an “dedicated exporter”, i.e. an exporter which takes into consideration the type of format being produced and the type of virtual world. Although this tool is not yet available to virtual world users some initial tests allow to produce models which were imported into a virtual world. The models were tested in a virtual world developed with virtual World SDK, OpenCroquet, a tool that “can be used by experienced software developers to create and deploy deeply collaborative multiuser online virtual world applications on and across multiple operating systems and devices” (OpenCroquet, 2009). Figure 4 shows an OpenCroquet virtual world where a house produced with ArchHouseGenerator was imported and where its multi-user capabilities were also tested. As it can be seen the world was rendered in two different machines synchronously – allowing the simultaneous presence of two users (here represented by rabbits – each one is seeing the other).

CONCLUSION AND FUTURE TRENDS This chapter has presented the advantages, as well as disadvantages of using procedural modelling tools in the several types of virtual worlds. In addition, where, when and which tools are available to generate virtual models have been described. It is clear that, the purpose of procedural modelling in virtual worlds, is not to prevent virtual world users from designing their own worlds, but instead to provide an efficient tools to do so. Indeed, procedural modelling has been extensively used in several other areas and there is no reason to believe it will not be used the same way in virtual worlds. The different types of existing virtual worlds determine where and when should procedural techniques be employed. When dealing with urban structures, the starting point for defining the way to create the physical models is to determine if the purpose of the models are the representation of existing structures or the generation of new ones. Procedural modelling is a very powerful tool but that does not mean that it is always the better solution. As described in this chapter many aspects determine the possible use of such techniques (e.g. type of virtual world, reconstruction/

Figure 4. Procedural generated traversable house (in an OpenCroquet multiuser world)

27

Procedural Virtual Worlds

generation, number of models to create, etc.) and a conscientious choice has to be made in each case. In this busy and competitive world the rush to generate digital 3D content may determine the overall adoption of procedural tools. This may also be a great opportunity to propel a virtual world to a new status as providing features not yet supported by all the others. It is likely 3rd party generation tools would be integrated with virtual worlds’ engines or, at the very least, would perform exports that are mode “virtual world friendly”. In addition, it is even more likely that future virtual worlds would have integrated their 3D modelling tools, as they currently have (e.g. Second Life), but also featuring procedural features, either natively supported or provided via plug-ins.

REFERENCES Aliaga, D. G., Rosen, P. A., & Bekins, D. R. (2007). Style grammars for interactive visualization of architecture. IEEE Transactions on Visualization and Computer Graphics, 13(4), 786–797. doi:10.1109/TVCG.2007.1024 Ancient Rome. (2010). Ancient Rome. Retrieved on June 13, 2010, from http://earth.google.com/ rome/ Back, M., Childs, T., Dunnigan, A., Foote, J., Gattepally, S., Liew, B., et al. (2010). The virtual factory: Exploring 3D worlds as industrial collaboration and control environments. Paper presented at the Virtual Reality Conference (VR). Bainbridge, W. S. (2007). The scientific research potential of virtual worlds. Science, 317(5837), 472–476. doi:10.1126/science.1146930

28

Bellotti, F., Berta, R., Gloria, A. D., Panizza, G., & Primavera, L. (2009). Designing cultural heritage contents for serious virtual worlds. Paper presented at the Proceedings of the 2009 15th International Conference on Virtual Systems and Multimedia. Benford, S., Greenhalgh, C., Rodden, T., & Pycock, J. (2001). Collaborative virtual environments. Communications of the ACM, 44(7), 79–85. doi:10.1145/379300.379322 Bessa, M., Coelho, A. F. V. C. C., Moura, J. P., Ferreira, F. N., Cruz, J. B., & Sousa, A. A. d. (2005). Modelação expedita de ambientes virtuais urbanos para utilização em dispositivos móveis. Paper presented at the 13º Encontro Português de Computação Gráfica. Bostrom, G., Fiocco, M., Puig, D., Rossini, A., Goncalves, J. G. M., & Sequeira, V. (2004). Acquisition, modelling and rendering of very large urban environments. Paper presented at the 3D Data Processing, Visualization, and Transmission (3DPVT), 2nd International Symposium. Bouras, C., Tegos, C., Triglianos, V., & Tsiatsos, T. (2007). X3D multi-user virtual environment Platform for collaborative spatial design. Paper presented at the 27th International Conference on Distributed Computing Systems Workshops. Carrozzino, M., Tecchia, F., Bacinelli, S., Cappelletti, C., & Bergamasco, M. (2005). Lowering the development time of multimodal interactive application: The real-life experience of the XVR project. Paper presented at the ACM SIGCHI International Conference on Advances in Computer Entertainment Technology, ACE 2005. Carrozzino, M., Tecchia, F., & Bergamasco, M. (2009). Urban procedural modeling for real-time rendering. Paper presented at the 3rd ISPRS International Workshop 3D-ARCH 2009: 3D Virtual Reconstruction and Visualization of Complex Architectures.

Procedural Virtual Worlds

CGV. (2010). Computer graphics and knowledge visualization. Retrieved on May 31, 2010, from http://www.cgv.tugraz.at/CGV/Research/Projects Charbonneau, N., Boulerice, D., Booth, D. W., & Tidafi, T. (2006). Understanding gothic rose windows with computer-aided technologies. Paper presented at the 24th eCAADe Conference. Chen, G., Esch, G., Wonka, P., Müller, P., & Zhang, E. (2008). Interactive procedural street modeling. ACM Transactions on Graphics, 27(3), 1–10. doi:10.1145/1360612.1360702 Ching-Song, W., Yan, C., & Jiann-Gwo, D. (2009). A 3D virtual world teaching and learning platform for computer science courses in Second Life. Paper presented at the Computational Intelligence and Software Engineering. Club Penguin. (2010). Club Penguin. Retrieved on June 14, 2010, from http://www.clubpenguin.com/ Coelho, A., Bessa, M., Sousa, A. A. d., & Ferreira, F. N. (2007). Expeditious modelling of virtual urban environments with geospatial L-systems. Computer Graphics Forum, 26(4), 769–782. Dickey, M. D. (2005). Three-dimensional virtual worlds and distance learning: Two case studies of Active Worlds as a medium for distance education. British Journal of Educational Technology, 36(3), 439–451. doi:10.1111/j.1467-8535.2005.00477.x Döllner, J., & Buchholz, H. (2005). Continuous level-of-detail modeling of buildings in 3D city models. Paper presented at the 13th Annual ACM International Workshop on Geographic Information Systems. Dreher, C., Reiners, T., Dreher, N., & Dreher, H. (2009). 3D virtual worlds as collaborative communities enriching human endeavours: Innovative applications in e-learning. Paper presented at the Digital Ecosystems and Technologies.

Fang, Z.-C., & Cai, H. (2009). Designing social commerce experience in 3D virtual world. Paper presented at the 2009 IEEE Conference on Commerce and Enterprise Computing. Fournier, A., Fussell, D., & Carpenter, L. (1982). Computer rendering of stochastic models. Communications of the ACM, 25(6), 371–384. doi:10.1145/358523.358553 Fuchs, A. (2006). Outils numériques pour le relevé architectural et la restitution archéologique. Nancy, France: Université Henri Poincaré. Gaba, D. M. (2004). The future vision of simulation in health care. Quality & Safety in Health Care, 13(suppl 1), i2. doi:10.1136/qshc.2004.009878 Greuter, S., Parker, J., Stewart, N., & Leach, G. (2003). Real-time procedural generation of `pseudo infinite’ cities. Paper presented at the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia. Guidi, G., Micoli, L., Russo, M., Frischer, B., Simone, M. D., Spinetti, A., et al. (2005). 3D digitization of a large model of imperial Rome. Paper presented at the Proceedings of the Fifth International Conference on 3-D Digital Imaging and Modeling. Habbo Hotel. (2010). Habbo Hotel. Retrieved on June 14, 2010, from http://www.habbo.com/ Heinrichs, W. L. R., Youngblood, P., Harter, P. M., & Dev, P. (2008). Simulation for team training and assessment: case studies of online training with virtual worlds. World Journal of Surgery, 32(2), 161–170. doi:10.1007/s00268-007-9354-2

3DSolve. (2010). 3DSolve. Retrieved on January 5, 2010, from http://www.3dsolve.com/ov3d.html

29

Procedural Virtual Worlds

Hohmann, B., Krispel, U., Havemann, S., & Fellner, D. (2009). CityFit: High-quality urban reconstructions by fitting shape grammars to images and derived textured point clouds. Paper presented at the 3rd ISPRS International Workshop 3D-ARCH 2009: 3D Virtual Reconstruction and Visualization of Complex Architectures.

Müller, P., Vereenooghe, T., Vergauwen, M., Gool, L. V., & Waelkens, M. (2004). Photo-realistic and detailed 3D modeling: The Antonine Nymphaeum at Sagalassos (Turkey). Paper presented at the Computer Applications and Quantitative Methods in Archaeology (CAA2004): Beyond the artifact - Digital interpretation of the past.

IMVU. (2010). IMVU. Retrieved on June 14, 2010, from http://www.imvu.com/

Müller, P., Vereenooghe, T., Wonka, P., Paap, I., & Gool, L. V. (2006). Procedural 3D reconstruction of Puuc buildings in Xkipche. Paper presented at the Symposium on Virtual Reality, Archaeology and Cultural Heritage (VAST).

Ingram, R., Benford, S., & Bowers, J. (1996). Building virtual cities: Applying urban planning principles to the design of virtual environments. Paper presented at the ACM Symposium on Virtual Reality Software and Technology (VRST’96) KZero. (2010). KZero chart. Retrieved on June 14, 2010, from http://www.kzero.co.uk/universe.php Lineage. (2010). Lineage. Retrieved on May 1, 2010, from http://www.lineage.com Lipp, M., Wonka, P., & Wimmer, M. (2008). Interactive visual editing of grammars for procedural architecture. Paper presented at the ACM SIGGRAPH. Luca, L. D., Véron, P., & Florenzano, M. (2007). A generic formalism for the semantic modeling and representation of architectural elements. The Visual Computer, 23(3), 181–205. doi:10.1007/ s00371-006-0092-5

Müller, P., Wonka, P., Haegler, S., Ulmer, A., & Gool, L. V. (2006). Procedural modeling of buildings. ACM Transactions on Graphics, 25(3), 614–623. doi:10.1145/1141911.1141931 Müller, P., Zeng, G., Wonka, P., & Gool, L. V. (2007). Image-based procedural modeling of facades. ACM Transactions on Graphics, 26(3). doi:10.1145/1276377.1276484 Musgrave, F. K., Kolb, C. E., & Mace, R. S. (1989). The synthesis and rendering of eroded fractal terrains. Paper presented at the 16th Annual Conference on Computer Graphics and Interactive Techniques.

Mandelbrot, B. B. (1982). The fractal geometry of nature. W. H. Freeman.

Natho, N., & Pfeiffer, O. (2010). A knowledge management system for educational scenarios in 3D virtual worlds. Paper presented at the Second International Conference on Mobile, Hybrid, and On-Line Learning.

Martin, J. (2005). The algorithmic beauty of buildings: Methods for procedural building generation. Unpublished Honors Thesis, Trinity University.

OpenStreetMap. (2010). OpenStreetMap. Retrieved on May 31, 2010, from http://www. openstreetmap.org/

Müller, P., Vereenooghe, T., Ulmer, A., & Gool, L. V. (2005). Automatic reconstruction of Roman housing architecture. Paper presented at the International Workshop on Recording, Modeling and Visualization of Cultural Heritage.

Parish, Y. I. H., & Müller, P. (2001). Procedural modeling of cities. Paper presented at the 28th Annual Conference on Computer Graphics and Interactive Techniques.

30

Procedural Virtual Worlds

Park, S. M. (2005). Tall building form generation by parametric design process. Chicago, IL, USA: Illinois Institute of Technology. Pecchioli, L., Carrozzino, M., & Mohamed, F. (2008). ISEE: Accessing relevant information by navigating 3D interactive virtual environments. Paper presented at the 14th International Conference on Virtual Systems and Multimedia, IEEE VSMM. Perlin, K. (1985). An image synthesizer. SIGGRAPH Computer Graphics, 19(3), 287–296. doi:10.1145/325165.325247 Prentice, S. (2007). The five laws of virtual worlds. Stamford, CT: Gartner Research, Gartner Inc. Publication ID: G00148019. Procedural Inc. (2009). Procedural Inc. Retrieved on June 24, 2009, from http://www.procedural. com/ Prusinkiewicz, P., Lindenmayer, A., & Hanan, J. (1988). Development models of herbaceous plants for computer imagery purposes. ACM SIGGRAPH Computer Graphics, 22(4), 141–150. doi:10.1145/378456.378503 Reeves, W. T. (1983). Particle systems - A technique for modeling a class of fuzzy objects. ACM Transactions on Graphics, 2(2), 91–108. doi:10.1145/357318.357320 Reynolds, C. W. (1987). Flocks, herds and schools: A distributed behavioral model. Paper presented at the 14th Annual Conference on Computer Graphics and Interactive Techniques. Rodrigues, N., Dionísio, M., Gonçalves, A., Magalhães, L., Moura, J. P., & Chalmers, A. (2008a). Incorporating legal rules on procedural house generation. Paper presented at the Spring Conference on Computer Graphics.

Rodrigues, N., Dionísio, M., Gonçalves, A., Magalhães, L., Moura, J. P., & Chalmers, A. (2008b). Rule-based generation of houses. Computer Graphics & Geometry, 10(2), 49–65. Rodrigues, N., Magalhães, L., Moura, J. P., & Chalmers, A. (2007). Geração automática de estruturas Romanas. Paper presented at the CAA Portugal. Rodrigues, N., Magalhães, L., Moura, J. P., & Chalmers, A. (2008). Automatic reconstruction of virtual heritage sites. Paper presented at the Symposium on Virtual Reality, Archaeology and Cultural Heritage (VAST 08). Rodrigues, N., Magalhães, L., Moura, J. P., Chalmers, A., Santos, F., & Morgado, L. (2009, 24-25 September). ArchHouseGenerator - A framework for house generation. Paper presented at the Slactions 2009 International Conference: Life, imagination, and work using metaverse platforms, Babbage Amphiteatre, NMC Conference Center, Second Life. Rome Reborn. (2010). Rome Reborn. Retrieved on June 13, 2010, from http://www.romereborn. virginia.edu/ RunEscape. (2008). RunEscape. Retrieved on May 1, 2008, from http://www.runescape.com SecondLife. (2009). Second Life. Retrieved on July 29, 2009, from http://secondlife.com/ Seidel, I., & Berger, H. (2007). Integrating electronic institutions with 3D virtual worlds. Paper presented at the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology. Silva, F., Rodrigues, D., & Gonçalves, A. (2004). House of the skeletons - A virtual way. Paper presented at the XXXII CAA - Computer Applications and Quantitative Methods to Archaeology Conference.

31

Procedural Virtual Worlds

Snowdon, D., Churchill, E. F., & Munro, A. J. (2001). Collaborative virtual environments: Digital spaces and places for CSCW: An introduction . In Churchill, E. F., Snowdon, D. N., & Munro, A. J. (Eds.), Collaborative virtual environments: Digital places and spaces for interaction (pp. 3–17). London, UK: Springer-Verlag. Sundstedt, V., Chalmers, A., & Martinez, P. (2004). High fidelity reconstruction of the ancient Egyptian temple of Kalabsha. Paper presented at the 3rd International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa. Unity3D. (2010). UNITY: Game development tool. Retrieved on June 14, 2010, from http:// unity3d.com/ Watson, B., Müller, P., Wonka, P., Sexton, C., Veryovka, O., & Fuller, A. (2008). Procedural urban modeling in practice. IEEE Computer Graphics and Applications, 28(3), 18–26. doi:10.1109/ MCG.2008.58 Willmott, J., Wright, L. I., Arnold, D. B., & Day, A. M. (2001). Rendering of large and complex urban environments for real time heritage reconstructions. Paper presented at the conference on Virtual reality, archaeology, and cultural heritage. Wonka, P., Wimmer, M., Sillion, F., & Ribarsky, W. (2003). Instant architecture. ACM Transactions on Graphics, 22(3), 669–677. doi:10.1145/882262.882324

32

Wonka, P., Wimmer, M., Zhou, K., Maierhofer, S., Hesina, G., & Reshetov, A. (2006). Guided visibility sampling. Paper presented at the ACM SIGGRAPH. Woodcock, B. (2008). MMOG chart. Retrieved on April 21, 2008, from http://www.mmogchart. com/Chart8.html World of Warcraft. (2010). World of Warcraft. Retrieved on May 1, 2010, from http://www. worldofwarcraft.com

ENDNOTES 1



2



3



4



L-systems or Lindenmayer systems (named after their creator) consist of formal grammars and were introduced in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer. A fractal is “a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reducedsize copy of the whole” (Mandelbrot, 1982). Generative modelling, in computer graphics, is a procedural modelling technique where a shape is described by a sequence of processing steps. “Split grammars” were introduced by (Wonka, et al., 2003) and are three-dimensional design grammars based on the concept of a shape.