Specification

The full specification and reasoning behind the simulator can now be found here. This gives the full background on the simulator and an idea of whats to come. It also contains discussions and reasoning behind the technologies in use, as well as being a status update on the progress of the simulator.

Videos

Here a couple of videos of the simulator in action. The first shows the rain system working as well as the basics of the simulator, roads, the ground plane and the skybox as well as a few trees (whose leaves now point in the right direction). It also shows the rain being blown around during 'gusts' of virtual wind. The second shows the user moving around the virtual world, controlling the direction with the mouse (follow the cursor and watch how it turns). These were generated using the Windows Media 9 SDK and hence require Windows Media Player to watch.

They can be obtained here and here.

Road Signs

To make things look more like a real road system, I have begun to implement a road sign system. It's still in it's infancy, but it currently uses road nodes to generate a list of all the roads meeting at that node and create a texture for the sign showing the road names. Te texture is created in a similar way to the sprite font, however this time it copies pixels from a font bitmap into the target bitmap in memory, then binds this to a texture name and so on.

Some work needs doing to remove duplicates and put arrows on the sign so that it makes more sense, but it's a start. I could probably do with some higher resolution fonts as well, since the signs can be quite large on the screen, but that should be easy enough.

The main issue, however, will be positioning the signs in useful places. Roads often have nodes even if they only join two sections of the same road. Obviously there is no need to put a sign down that confirms you are still on the same road. On the other hand, when a junction is met, where should the sign be placed? This can be calculated by taking the direction the road is coming away from the node in, and placing the sign on the left-hand side of the road. Finding a vector perpendicular to the road is easy in two dimensions, and only slightly harder in three (take the cross product of the direction of the road and the global 'up' vector, that is (0, 1, 0)).

Road Markings

After much thinking and fiddling with code, the first semblance of road markings have appeared. To get this working, I have used the road link data which has a list of coordinates for each road showing the lay of said road. By lining up quads along this string of coordinates, pretty convincing road markings can easily be created.

Unfortunately, the markings are in sections of straight lines, which can be seen in this screenshot. The next step is to interpolate between the points on said line to make a curve, and align the markings tangentially along this curve.

Point Sprites and Leafy Trees

I finally managed to get point sprites working to a decent state, thanks to the magic of the Alpha Test, as can be seen in the latest screen shot. Only problem now is that the leaves displayed are all standing on end, rather than in a sensible direction...

One solution is to create a 3D texture with multiple rotations of the sprite, and then specify an r texture coordinate during calls display points. While this would undoubtedly work, a more sensible solution is to use a textured quad instead. Takes a little more programming, but ultimately it's a lot more flexible. And thanks to the geometry of the tree generated by Arbaro being a set of eight vertices making six trianges, I can get the direction the leaf is in, cross it with the camera vector and get the relevant vectors to displaying a textured quad.

I'll post a screen shot when I've done this...

Rain

Today I added a particle-based rain system, which you can see in the latest screen-shots. Currently it generates one thousand particles which are updated every frame based on their velocity. The system itself introduces gusts of wind at random intervals for random lengths of time, and this affects the movement of the particles.

Because rain tends to be at terminal velocity by the time we see it, the particles are given a starting velocity that only changes in the x- and z-dimensions (i.e. horizontal plane). Each frame, before gust influence is calculated, these values are decreased so that the particles will go back to straight downward motion, to simulate air resistance and to give a smooth reduction when a gust stops.

Trees

In the interest of making the simulator more realistic, I have started adding trees to the scene. Initially, I looked at implementing Weber and Penn's algorithm described in Creation and Rendering of Realistic Trees, however it became apparent after reading through and starting to implement a generator that this was not going to be easy, or fast. However, I came across a wonderful application called Arbaro, which is a java implementation of said algorithm for creating trees for POV-Ray.

Arbaro generates POV-Ray inclue files (.inc) which are text descriptions of the vertex, normal, and face data of the tree created. While this makes POV-Ray very portable, it also means it's not the simplest of files to read (binary files are easier, read a header, allocate some memory, read the rest...). So, after a bit of work deciphering the file, and trying to ignore unimportant sections, the simulator now reads in trees generated with Arbaro.

Since Arbaro is generating for a raytracer, it creates leaves for it's trees. Each leaf is comprised of six triangles. I decided that, in order to conserve precious rendering time, I would render leaves as either points, or point-sprites (i.e. particles). That meant I had to average the vertex positions of each triangle, and then average the averages for each leaf to leave me with one vector for each leaf.

The result is this:

Which looks pretty good, so far. Currently the leaves are rendered as anti-aliased points, and with blending enabled this makes them rougly circular. Since the number of leaves is constant, point sizes increase exponentially as the camera approaches the tree, so that gaps aren't left, and foliage appears thicker.

Constant point size:

Variable point size:

The only problem with this is that it makes the trees look a little cartoony close up:

However, I plan to implement point sprites in an effort to rememdy this.

Sprite Fonts

I decided it was time to add text capabilites to the application. Initially, I looked into it and thought that rather than writing my own sprite font class, it would be easier to use the free library glFont2. However, after failing to get it to work correctly (It was just displaying coloured squares on the screen...) I decided to write my own handler.

The result is this:

The font colour can be changed by simply using glColor3f, and is written with a function DrawString(char *, int, int) which allows you to specify a string, and x ad y coordinates on the screen.

It is currently in use to display the camera location within the field in the upper-left corner of the screen, like so:

Implementing this was actually suprisingly easy. ASCII values for the characters needed are in the range 32 to 127, so converting from a char* to a set of ints was easy. With the value for each character, texture coordinates are calculated on a base "font" bitmap file, and drawn to the screen as a textured quad. Simple!

Lights, Camera, Action...

I have now added video recording to the application. There is now a video button on the button bar at the bottom that initiates capture when clicked, and finishes capture when clicked again.

The application uses the Windows Media Encoder 9 SDK to add this functionality, and captures an area of the screen using this API. Unfortunately, the framerate is pretty low at the moment, so I am now going to try using the glReadPixels function to feed frames into a stream that WME9 can then encode.

Road Overlay

Added a new screenshot here of the 3D view with the road overlay turned on. It's just for debugging purposes at the moment, but it helps me see where roads are when the topographic data hasn't been loaded correctly. Thankfully, not much of an issue any more!

Dynamic loading, again

I created another table, ta_grid, for the same reason as the roadnodes and roadlinks, but this time for topographic areas. It processed 9789 topographic areas, created a total of 553518 records, and took about two and a half hours to run.

Sad thing is, it actually runs worse now, and doesn't seem to load some data at all. Probably just slowed down a lot (that's a lof of records to get through, however you look at it), but for now I'm taking it out again.

Might look at it again later.

Triangles. Lots of triangles

I realised today that all of the polygons triangulated gives me a total of 533940 triangles in the total dataset. That's over five hundred and thirty thousand triangles. Goes some way to explaining the 344MB memory usage.

It also goes to show that frustum culling really is a necessity, not just a nicety...

Update: Dynamic loading

In the previous system, one roadlink may be referenced in several nodes of the quadtree. This is to make sure that the road is loaded, whatever angle you come at it from. However, this means that if a roadlink is referenced in fifteen nodes it could get loaded fifteen times. Not only does this slow down loading, but it slows down rendering (even with the appropriate culling, it still draws the same object several times)

I updated this process so that the loading thread calls a function isTALoaded on the graphics object, which returns true if the topographic data for a roadlink or roadnode has already been loaded. This has decreased both loading and rendering times significantly.

Dynamic loading of roads

The program now dynamically loads roads, rather than loading all of the topographic data at the start of the program. This has reduced the initial loading time of the program from just over six minutes to a mere four and a half seconds. A slight improvement...

The system works currently with another program which is run before trying to use the simulator and creates a couple of extra tables in the database. The roadlink and roadnode data is loaded into memory. For the roadnodes, the coordinates are converted to a figure relative to the centre of the data (the map area in the database) and then converted to a grid reference on a grid of size 50 (that is, grid lines are 50 metres apart). This is then put back into the database in a table rn_grid. Similarly, the roadlinks are loaded only this time the conversion and associated data entry is performed on all of the coordinate pairs in the list, and data is entered into a table rl_grid.

When the simulator loads, this information is put into a quadtree, each node representing a list of id's of roadnodes and roadlinks that pass through it. When the simulator is running, the Update function calculates the direction the camera is facing and, using data in the quadtree, pushes items onto the stack of topographic areas to be loaded. The extra threads initiated for loading topographic data pop items off the stack and load them while the simulator is running.

When I get the chance, I'll upload a video.

EDIT: I should point out that the other program only needs to be run once. This in itself takes about four minutes, so would be pointless if it were run every time.

Mutual Exclusion

Had a few thoughts about making the program thread-safe, and this involves ensuring mutual exclusion on a couple of functions.

First is the pop function for the stack containing all of the fid's of the topographic areas to be loaded. The function works like this:

string s = stack.top

stack.pop

Now, if two threads call it simultaneously, they could end up with the same reference, but pop two items off the stack. The following trace shows how:

Not only does this mean that one item gets loaded twice (waste of resources) but it means that one gets missed (b is not in the stack, nor in s1 or s2).

The other problem is adding these new items to the list to render. The process goes like this:

last.next = item

last = item

where last is a pointer to the last item in the list. This is a problem if last.next gets set by a different process before last, for instance:

item1 mysteriously disappears. This causes a memory leak, and incorrect rendering.

Using the built in Mutex structure in windows, these routines run in whole before another process is allowed to run them by being forced to wait until the mutex is available, for instance:

WaitForSingleObject(mutex)

critical section

ReleaseMutex(mutex)

At the moment, these are the only functions the extra threads are calling, so this makes the program safe.

Multi-threading

In an attempt to make things load in a more sensible time-frame (six minutes is too long for anyone to wait) I have begun to implement a multi-threaded approach to database access. Thanks to MySQL being able to handle multiple concurrent connections, this becomes all the more possible.

How does it work?

Upon loading the program a minimal set of data will be loaded, that is the road data of the immediate vicinity. As the camera moves through the world, data is loaded dynamically by these extra threads depending on where the camera goes.

So how does it know what to load?

In the initial loading stages basic information about each section of road is loaded including, but not limited to, a list of coordinates describing a line that the road follows. By dividing the world up into a grid, and noting which road sections pass through each square in the grid, you can use where the camera is and the direction it is facing to determine which grid squares are in view, or will be soon, and load as appropriate.

How does this get stored?

A quadtree (not unlike a binary tree, but with four children per node) seems ideal in this situation. The space can be sub-divided until each node holds a reference to only one road. This works especially well since the lines are stored as a list of coordinates, and not a continuous function.

What about the rest?

The reference id's of every topographic area are loaded at the start of the program into a stack. While the program runs, they are popped off the stack and loaded, one by one. By using a stack this also gives the opportunity to push any priority items onto the top of the stack, which can then be ignored later when they are repeated (repetitions are certain in this case, since we start with references to every item in the database)

Texture Filtering

OpenGL provides an interface for loading two-dimensional textures into memory via a function glTexImage2D. However, since this does not provide any filtering, it looks blocky and is rather slow to render. Using the function gluBuild2DMipmaps, mipmaps are generated down to a size of 1x1, which not only makes things look better, it also makes rendering much faster.

glTexImage2D

gluBuild2DMipmaps

Frustum Culling

Rendering sets of several thousand (20,000 +) triangles thirty times a second can slow the rendering process down, so it's important to have a fast and efficient way of culling items that don't need to be drawn.

Trivially, we can ignore anything that is behind the camera. While this helps, there are still items forward of the camera that are not visible, items that are too high above the camera or too far below for instance.

The viewing volume described by a rectangular screen is in the shape of a rectangular based frustum (that is, a pyramid with the top cut off). By drawing only items that appear in this volume, we can render scenes in a fraction of the time. Initially, culling can be constrained to items that do not intersect the viewing volume, although this can be extended to handle individual triangles for elements which do. The diagram below shows the camera and view frustum (intersecting the ground plane) and three objects. The yellow is outside the frustum, and is culled. The blue is entirely within and is drawn in whole. The green is partially within, so further culling is used to draw only the relevant triangles.

The fastest way of culling an object is by using a bounding sphere, which is calculated as a centre and a radius, both of which can be found using the maximum and minimum values for vertex data in each dimension. We need only test the distance of the centre of the element to be drawn from each of the six planes which make up the frustum. If this point is behind any of the planes, and further than the radius, we can cull the object. Using the Hessian normal form of plane notation for the frustum's six planes, we can quickly calculate whether a sphere is behind a plane using the inequality

n.v - p < -r

where n is the plane normal, v the centre of the sphere to be tested, r the radius of the sphere and p the distance of the plane to the origin. If the above inequality is true, the sphere is behind the plane. If the inequality is false for all six planes, the sphere is within the frustum (this includes cases where the sphere intersects the frustum)

Triangulation of complex polygons

The topographical data provided in the form of complex polygons, some of which have as many as two thousand vertices. Unfortunately OpenGL does not like this kind of data, preferring instead to display the closest possible convex polygon, so triangulation is necessary.

By starting at one end of a polygon and recursively clipping "ear" triangles (that is, triangles which have at least two edges on the outside of the polygon) we can convert a complex polygon into a set of triangles.

This also means that rendering will be much faster, submitting an array of triangles instead of one large polygon and expecting OpenGL to do all the work.