Project Description
It is well known to most of those in the field of computer graphics that mountainous
terrain can be generated programmatically. A good deal of research has been done
in this area, focused for the most part on the use of fractals to generate landscapes.
While these techniques produce some impressive results, they are restricted in the
kinds of terrain that they can generate. For example, these techniques are not
appropriate for the creation of urban terrain.
This is unfortunate, as there are many benefits to being able to programmatically
generate urban landscapes. Many recent video games, for example, feature very
large urban environments. Finding little research on the topic of urban terrain
generation, I decided to create my own utilities for that purpose.
Approach
In implementing the system, I chose to follow the UNIX tradition of
having each utility do one thing. As such, each of the three stages in the
creation of a cityscape is implemented in a separate utility.
The three major components of my project are:
|
Inputs |
Actions |
Output |
| StreetBuilder |
GraphThing file - contains a graph representation of the city to be generated.
Intersections are stored as nodes, and streets as edges |
Geometry creation |
AC3d file - contains the actual street geometry, ie vertices, polygons, etc.
Blocks file - contains information pertaining to the blocks in the city. Each block
is stored as a set of points defining the perimeter of the block itself. |
| BlockBuilder |
Blocks file - output from StreetBuilder
Lots file - contains a list of building models available to the system, as well as
the properties attached to those models
Channels file - defines the channels to be used with this city
|
Block division and population |
Scene file - contains references to models that are to be placed int the final scene,
as well as the transformation values for those models |
| ClutterBuilder |
GraphThing file - same file used by StreetBuilder
Clutter file - contains a list of street clutter models (street signs, lamp posts, etc)
available to the system, as well as the properties attached to those models
Channels file - defines the channels to be used with this city
|
Populating the city with the typical street clutter... the "icing on the cake", as it were |
Scene file - same format as above |
Justification
In this section, I'll attempt to explain some of the reasoning behind my design
choices.
Having the roads for a city defined in a 3dformat-independent
file structure means that:
-
Geometry data can be (re)generated at a later time, or by a separate utility.
(remember unix philosophy; "do one thing and do it well") If improvements
are made to the quality of the output generated by the 3d-data-generating-utility
(streetbuilder) (example: smoother, curved street corners),
then applying those improvements to ALL the roads in the city model
is as simple as re-executing streetbuilder.
Were the 3d data generated by hand (ie by a 3d modeler), sweeping improvements
like this would not be practical, as each road object would have to be
tweaked by hand.
-
It is possible to generate data that is not directly related
to graphical output. For example:
Once the roads have been laid out in this manner, it is very easy to
produce pathfinding information for use by a game's AI... automobiles
would already have a rigid node graph to tell them where they can and cannot
drive... AI-driven actors have a convenient node graph to aid them in finding
their way around the city... etc.
Storing the geometry data for the buildings separate from the geometry of
the streets, etc:
-
makes it easy to swap out models later on (think: turning a daylight-lit
city into a night scene simply by replacing the buildings models, or even just
their textures. Same goes for changing the weather [snow-topped buildings,
streets, etc].)
-
saves on memory *big-time*. Since the building models need to be stored in
memory in only one place, and are then re-used throughout the city scene graph
through pointers, lots of memory can be saved (allowing for bigger cities :)
Textures are re-used, too, but this is less of a concern, as most game engines
already do texture caching.
This last point, regarding memory consuption, deserves further comment. An
early, incomplete version of the scene-viewing program (the program based on the Tux game,
discussed below) did not consolidate multiple references to a model into
a single copy. This early version of the viewer retained a separate
copy of each building model in memory. Upon testing this version of the viewer
with a 40-block city, it ran out of memory on my workstation and was terminated
by the operating system. The same 40-block city, when viewed with the current version
of the viewer program, uses about 50MB of memory. The memory savings -- using prefabricated
models that are stored in memory once, rather than a custom, unique model for each building --
are substantial.
Implementation
Overall System Architecture
A diagram showing the flow of data through the system:
As shown in the above diagram, there are two points in the system that require
user intervention. The first is the graph-creation stage. The
GraphThing utility is used to create the street graphs.
The second point requiring user intervention is the post-production fine tuning of the
generated scene graph. While this stage is entirely optional, some user intervention is
inevitably required to help make the generated city look more natural. The KludgeBuilder
utility [not yet publically released] provides the user with the ability to manipulate
the scene graph file.
Here's a screen shot of KludgeBuilder in action:
The scene graph file can be viewed with the game engine implemented in the
Tux: A Quest For Herring game.
Some modifications to the engine were required in order to properly handle the
transformation matrices written by the BlockBuilder utility, and to implement a new
camera mode.
Overall Program Architecture
I won't cover the operation of the entire system, as that would take too long.
Instead, I will explain some of the more interesting algorithms from each part
of the system.
UPDATE : I'm not going to bother. The code is fairly well commented.
The algorithms likely of greatest interest are the following:
streetbuilder
edge mitering : streetbuilder/src/intersections.c
block (graph face) creation : streetbuilder/src/blocks.c
blockbuilder
heuristics-based block division : blockbuilder/src/blocks.c
channels : blockbuilder/src/channels.c
clutterbuilder
geometry used to place clutter : builder/src/street_pop.c
Data Structures
The input file formats:
GraphThing
The GraphThing file format consists of a list of graph nodes and their locations,
and a list of the edges connecting the nodes together. The graph-loading and
building code in streetbuilder and clutterbuilder is taken directly from GraphThing,
and hence the file formats are identical. (Note - version 0.5 of GraphThing was used
for this project. Newer versions of GraphThing use a slightly different file format.
Specifically, the latest GraphThing has support for edge weights, which is a highly
desirable feature that will be taken advantage of in future versions of this system.)
Lots files
Lots files specify a list of available building models, along with the dimensions
for each building lot (which may not match the actual dimensions of the model).
Included with each entry are the channel values for the lot. Channels may go unused,
but values must still be specified.
Example entry, with annotation following the #'s:
building0a.ac # model file name
4 # number of corners (must be 4, at this point)
0.0 0.0 # the four points defining the edges of the lot
36.0 0.0
36.0 36.0
0.0 36.0
1.0 # this lot's channel 0 value
1.0 # this lot's channel 1 value
0.0 # etc.
0.0
Clutter files
Clutter files are identical to lots files, except instead of specifying the geometry
of the model, the type is specified.
Example entry, with annotation following the #'s:
lamppost.ac # model name
2 # model type (2 = street lamp)
0.5 # this lot's channel 0 value
0.0 # etc.
0.0
0.0
Channels files
Channels are simply properties that the lot's model has.
There is no pre-defined meaning that the channels hold; their meaning is
determined by the user. Example: the user would like to differentiate
between models that depict buildings typically found "downtown" (like
skyscrapers) from buildings that would be found outside the city center
(like rowhomes). The user would assign, say, channel 1 to be the
degree-of-downtown-ness, and would give skyscraper lots a 1.0 for channel 1,
and rowhome lots a 0.0 for channel 1. The images (ordinary Targa files)
are used to give locations in the city channel values.
Channels may go unused, but values must still be specified.
Example file, with annotation following the #'s:
2 # number of channels used (4 max)
0.0 0.0 # minimum x, y for the city
800.0 650.0 # maximum x, y for the city
demo-channel0.tga # the image file to use for channel 0
demo-channel1.tga # etc.
The output file formats:
AC3d
The AC3d file format is a simple file format for storing polygonal 3d meshes.
It is documented elsewhere.
Scene file
The scene files (.dat) are roughly the same format used by Tux:AQFH, with the addition of
the 4x4 transformation matrix data. The transformation matrices are stored in row-major
format, all 16 values on the same line, and separated by commas.
Results
Screen shots
A shot of part of the demo city, showing the claustrophobic effect that
tall buildings can sometimes have. Note that all the street and sidewalk textures are
aligned perfectly, despite being placed on very skewed, non-orthogonal polygons.
A shot of a 5-way intersection. The maximum number of streets that can meet at a single
intersection is 6 (an arbitrary limitation in streetbuilder; anything more than 6 just doesn't
happen in real life). The minimum is 2 (dead ends are not allowed). The texture for the
intersection looks goofy because I didn't have time
to create a texture for 5-way intersections. Note the stopsigns in the background. Clutter
uses channels, just like lots, so having different models at different points in the city
(trafficlights for downtown, where traffic is dense, and stopsigns elsewhere) is easy.
An overhead shot of part of the demo city. Cities can be of arbitrary size. The only real
limitation to how big a city can get is the capacity of the hardware that the viewer program
is executed on.
User Documentation
Compiling
The utilities are all compiled using the autoconf system. The user must run the configure script,
then run make:
> ./configure
> make
Running
The run.sh script in the data directory does everything.
[info on running kludgebuilder]
[info on running viewer]
Future Enhancements
The following features are intended to eventually be implemented in the system:
- fix transform-matrix-generating code. Here is a description of the bug.
- move common code to a library
- automated creation of street graph. A fourth utility, to replace the "GraphThing" stage of the system.
- heightmap for city? would require pervasive changes to all 3 utilities...
- variable street widths. easy enough, but need convenient way to specify
widths when creating graph. may need to hack graphthing. current versions of graphthing
have the ability to set the edge weights.
- curved street corners
- more flexible way to specify street clutter?
- better blockbuilder algo :)
- trees, green stuff