Introduction

Improvements in computer hardware have made the reproduction of larger and more detailed urban environments possible and the users are demanding the full use of such capabilities. However, these environments are complex spaces, offering a wide variety of elements and modeling them, using traditional tools, may take several man years since every urban element must be modelled in detail. To cope with such request for greater detail, there has been a shift of focus to procedural modeling systems which, from a small set of rules and coupled with a controlled level of randomness, are capable of generating geometry and textures in an semi-automatic way, relieving the user from the burden of manually producing the models that represent the urban environment.

Take for example the recent title No Man's Sky that gives us an entirely procedural galaxy to explore. Creating all that content using traditional techniques would probably require thousands and thousands of hours to accomplish, since each and every element would have to be manually modelled. Also, budgets would be through the roof.

That is why we're seeing procedural content more often. Procedural modeling is a group of techniques that allow more content to be created with less effort, by encoding the content generation into rules or procedures. These rules often exploit some form of repetition or pattern and can be parameterised by random or user-defined values allowing the generation of a large variety of models.

The patterns in these environments often stem from urban planning rules and guidelines with which cities are built. City layouts, for instance, are conditioned by roads and it is common to see grid or radial patterns. Buildings also possess repeating elements in their structure, such as windows, doors or ornaments laid out according to some pattern. Without these patterns, cities would have a chaotic aspect.

As for parameters, one can, for instance, state the number of floors a building has or, even, based on the date of construction, create buildings with different architectural styles. Coupled with randomness it is possible to generate vast amounts of models and, thus, create entire urban environments with ease. This is the true power of procedural modeling.

In this article I chose to discuss shape grammars for two reasons:

1. They are a familiar and easy concept to understand even for newcomers to the procedural modeling field.
2. They are extremely easy to implement. The geometric operations are, by far, the most difficult part but they are present in almost every procedural modeling technique.

Although you can find some theory behind shape grammars in this article, I recommend reading the papers from Parish and Muller [1], Wonka et al. [2] and Muller et al. [3] for a deep understanding of this methodology. For an overview of the literature on urban procedural modeling I recommend the survey by Vanegas et al. [4].

Shape Grammars

One of the most typical ways of encoding procedural rules is to use a formal grammar, where symbols execute operations on the geometry, starting with an initial shape. The grammar derivation process, iteratively refines the geometry, adding more detail to the result by replacing one shape by a new set of shapes. This is similar to what happens in grammars in linguistics. So for example the following grammar:

Sentence -> Noun_Phrase Verb_Phrase Noun_Phrase 
	-> Pronoun | Noun Verb_Phrase 
		-> Verb Noun_Phrase Pronoun 
			-> "I" | "You" Verb -> "like" | "hate" Noun -> "cats" | "dogs" 

can be used to create the sentences "I like cats", "I like dogs", "You like cats" and so on, simply by collecting all terminal symbols.

In the case of procedural modelling of buildings we also have this type of grammatical rules. A rule has a labelled shape on the left hand side (which is often called the symbol) and commands on the right hand side which create new labelled shapes with the purpose of being further processed. Commands usually have parameters controlling how they affect the geometry.

A shape is considered terminal if there is no rule in the grammar that has its symbol in the right hand side and is non-terminal otherwise. Besides the geometry, a shape also has (typically) material information and an oriented bounding volume (called a scope) defining its position, a frame of coordinates and a size along each axis.

The most common commands in procedural modelling of buildings are presented next. Note that you will find these in almost any tool out there.

• Extrusion: The extrusion command simply extrudes a shape along its normal by a given amount. This is useful for creating the building volume given its floor plan and almost all examples I've seen start with an extrusion.
• Split: This command divides a shape into multiple shapes along one of the scope's axis by a given amount. Usually, procedural modelling tools allow you to define the amount as an absolute value or as a value relative to the scope's size and let you chain several subdivisions in the same operation.
• Repeat Split: As the name implies, this command allows you to repeatedly apply a split to a shape. This is useful to scale the split operation to shapes of unknown size (e.g., floors in a building).
• Face Split: This one allows you to access different faces of a shape. With this command you can, for example, create different geometry for the different fa?ades of a building. Typically this command allows you to select the resulting shape based on some condition such as the front, right or left faces.
• Insert: The insert command lets you load a pre modelled asset from file and put it in your procedural model so that you can end up with more complex buildings.

So now you know about rules, shapes and commands. How does it all come together to create buildings? There are (at least) two things you need:

1. An initial shape (the axiom) with a symbol
2. A shape grammar with all the rules

The axiom is, typically the building lot and it is often provided by some procedural method that is responsible for creating the city layout along with roads and building lots. However, you can also create it manually or import it from somewhere else such as a Geographic Information System. After you have the axiom your hard work is on the creation of the shape grammar.

When you have both, it's time to have generate the building geometry. Shape grammars work by replacing a shape with a new set of shapes created by applying a set of commands. So, from any given configurations of shapes, the system finds a non-terminal shape and the rule with such symbol on its left hand side. It then executes the set of commands on the right hand side creating new shapes from the original one which are added to configuration of shapes. This is repeated until there are only terminal shapes. To this point, all there is left for the system to do is collect all terminal shapes and either render them or export them to a file.

So now we're up to an example. Consider an axiom with the "Lot" symbol and the following grammar. Below you can see an image with the several steps in the derivation.

Lot -> extrude(10) Mass 
	Mass -> FaceSplit{ sides: Facade } 
		Facade -> Split("y"){ 3: FirstFloor, ~1: TopFloors } 
			TopFloors -> Repeat("y"){ 1 : Floor } 
				Floor -> Repeat("x"){ 1 : Window } 
					Window -> insert("window.obj") 

The first rule is applied to the axiom shape (top loft in the image) since it has the "Lot" symbol on the left hand side and simply extrudes the axiom by 10 units along its normal, resulting in the top middle image. The symbol "Mass" is associated to the resulting shape. Then, the Mass rule uses a face split to create a new shape for each of its faces and assigns the "Facade" symbol to the side faces.

The Facade rule splits each fa?ade along its y axis (top right image), creating a ground floor 3 units tall and leaving the rest to be repeatedly divided into floors (the TopFloors rule). The ~1 indicates a relative to the scope size which, in this case, takes up all of the remaining fa?ade space. The TopFloors rule uses the repeat split command to divide the shape vertically into floors 1 unit high (bottom left) and, similarly, the Floor rule divides each floor into a tile 1 unit wide (bottom middle image). Finally, the Window rule simply inserts a pre-modelled window asset into each tile as can be seen in the bottom right image.

Implementing shape grammars

Of course, I can't detail every aspect or write every line of code required to build a shape grammar system. Although simple to understand they are still complex systems mainly because of the geometric operations. That said, I can give you some pointers in how to implement them, specially in overall architecture.

The main components you need to implement a shape grammar are the following:

• Geometry and Material representation: This is how you represent the geometry and materials in your system and you can practically choose any representation you see fit. However, take into account that every type of geometry representation has its advantages and drawbacks. For example, and vertex indexed has a low memory profile and is usually very fast but doesn't allow you to know which faces are adjacent to a vertex. On the other hand, a half edge mesh allows you to do this, but is way more complex and limits you to two-manifold meshes. Although in practical scenarios I haven't had this issue with buildings but it might not be suitable for other things.
• Shape Tree: Possibly the best way to organise the shapes generated by your system is in a tree of shapes. You create this tree during the execution of a command by setting the created shapes as children of the previous shape. Leaf shapes are the next ones to be processed by the system. Moreover, if you later implement conditional execution in your shape grammar, you can do things such as selecting a shape based on its index number which is useful to create patters such as different even or odd floors.
• Geometry Operations: Here you implement all the operations that manipulate geometry or materials. You will typically need, among others, extrusions, clipping geometries to planes, scales, translations and rotations. Make sure that the operations execute as fast as possible as this can become a bottleneck. I believe it is best to separate geometry operations from the implementation of the shape grammar commands in order to improve reusability (e.g., both split and repeat split use the clipping operation).
• Shape Grammar: This is where you implement rules in your system. A rule has a symbol, a list of parametrisable commands that generate new shapes with different symbols. In this sub-system you should also implement the shape grammar execution algorithm. To do this, you can simply store all the rules indexed by their symbol (e.g., in a map). Then, you find a non terminal shape that hasn't been derived (a non-terminal leaf in the shape tree) and execute the rule with the same symbol, adding the resulting shapes as children of the previous shape. You do this until there are only terminal shapes.
• Shape Grammar Parser: You need to define a syntax for your shape grammar and create a parser for such syntax which creates the rules and respective commands with their arguments.
• Geometry exporter or renderer: Finally, in order to be useful, you have to either export the created geometry to file or render it. To do this, you simply collect all leaf shapes in the shape tree, apply some post processing if you wish, and write it to disk.

Conclusions

As you can see, procedural modeling is an extremely useful way to generate content for video games. It cuts down both on time and budget and allows you to create a wide amount of models with the same set of rules.

Shape grammars were one of the first methods proposed to generate buildings and they are currently used in both commercial applications and in the research field. Currently there are extensions that add layers [5], free-form deformation [6], non-cubic convex scopes [7], visual languages [8,9] or advanced programming concepts [10,11] among many others. Nonetheless, they still have drawbacks. The most obvious one is that the resulting buildings can be rather repetitive if care is not taken.

Another method, which is (probably) more user user friendly, is to use node based approaches where nodes define operations and edges define a flow of geometries and data between nodes. The field is relatively new and more approaches will definetly appear which will make procedural modeling even more powerful.

References

[1] Parish, Yoav I H, and Pascal Miller. 2001. "Procedural Modeling of Cities." In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '01, 301-8. SIGGRAPH '01.

[2] Wonka, Peter, Michael Wimmer, Fran?ois Sillion, and William Ribarsky. 2003. "Instant Architecture." ACM Trans. on Graphics, SIGGRAPH '03, 22 (3).

[3] M?ller, Pascal, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool. 2006. "Procedural Modeling of Buildings." ACM Transactions on Graphics 25 (3).

[4] Vanegas, Carlos A, Daniel G Aliaga, Peter Wonka, Pascal M?ller, Paul Waddell, and Benjamin Watson. 2010. "Modelling the Appearance and Behaviour of Urban Spaces." Computer Graphics Forum 29 (1).

[5] Jesus, Diego, Ant?nio Coelho, and Ant?nio Augusto Sousa. 2016. "Layered Shape Grammars for Procedural Modelling of Buildings." The Visual Computer 32 (6): 933-43.

[6] Zmugg, Rene, Wolfgang Thaller, Ulrich Krispel, Johannes Edelsbrunner, Sven Havemann, and Dieter W Fellner. 2013. "Deformation-Aware Split Grammars for Architectural Models." In 2013 International Conference on Cyberworlds, 4-11. IEEE.

[7] Thaller, Wolfgang, Ulrich Krispel, Ren? Zmugg, Sven Havemann, and Dieter W. Fellner. 2013. "Shape Grammars on Convex Polyhedra." Computers and Graphics 37 (6). Elsevier: 707-17.

[8] Patow, Gustavo. 2012. "User-Friendly Graph Editing for Procedural Modeling of Buildings." IEEE Computer Graphics and Applications 32 (2): 66-75.

[9] Silva, PB, Pascal M?ller, Rafael Bidarra, and A Coelho. 2013. "Node-Based Shape Grammar Representation and Editing." In Proceedings of PCG 2013 - Workshop on Procedural Content Generation for Games, Co-Located with the Eigth International Conference on the Foundations of Digital Games.

[10] Krecklau, Lars, Darko Pavic, and Leif Kobbelt. 2010. "Generalized Use of Non-Terminal Symbols for Procedural Modeling." Computer Graphics Forum 29 (8): 2291-2303.

[11] Schwarz, Michael, and Pascal Miller. 2015. "Advanced Procedural Modeling of Architecture." ACM Transactions on Graphics 34 (4): 107:1-107:12.