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.