grappling with 3d graphs: terrain in papervision

Recently, I airily told my colleagues that building a 3D graph in Flash would be no trouble at all. I knew Papervision was capable of it, and I’d be fine, I thought.

An overconfident assumption, it turns out. While the API docs for Great White are available, a lot of methods are uncommented, assuming you know your way around 3D. I had almost zero understanding of the basic geometry concepts needed to actually build what was required. As far as 3D goes, I am almost totally ignorant (a little less so after getting the 3D graph licked, but only enough to realise the scale of the huge amount I don’t know). I knew what it should look like, but I had no idea how to get there.

After googling extensively, I found no tutorials or explanations of what I needed. There is, no doubt, plenty of such information embedded in 3D basic concepts and mathematics courses, but I had a deadline looming and no time to be giving myself a full education in 3D. I just needed to get this damn graph built! The closest I found on the web was this example on overset.com – almost exactly what I wanted – but no detailed explanation or source code, just a tantalising glimpse of the result.

Luckily a friendly developer, Douglas Thompson, answered my cries for help on #papervision and came to the rescue with some code examples to study. The example he showed me was for building the terrain for a game.

I thought I would share this knowledge and write a semi-tutorial of sorts to describe how I came to a working solution. I say semi-tutorial because it’s a description of how I came to a solution in the real world, with mistakes and dead ends and all (personally I find this more enlightening than a neat set of steps – showing why as well as how).

This is not intended to be normative or definitive, just an account of my bumbling first footsteps in 3D, in the hope that someone else can learn from my mistakes without having to make them him/herself. If anyone wants to correct the ideas here, please do so in the comments.

OK, then …

The problem

I needed to build a 3D graph, with data arranged regularly on the X and Z axes, but the Y variable fluctuating arbitrarily: a terrain, essentially, like a big blanket covering random lumps (to paraphrase the detectives in I Heart Huckabees). This is what I got from the designer (rendered into Photoshop from a random data pattern in Cinema 4D):

So I knew what I should end up with … the question was: how?

The data

The data that the graph needed to represent showed energy usage levels (it’s an installation for Energy Australia’s Energy Efficiency Centre, going live very soon) over time – with time actually taking up two axes of the graph, X (half-hours per day) and Z (days per year). The Y (vertical) axis represents the usage level.

The brief suggested I load in the data from XML (it was supplied by the client in Excel format – that hammer with which clients always seem to delight to use on screws, bolts and light sockets …) With such a large volume of data (48 half-hours per day, 365 days per year = 17520 records), I decided this was a non-starter. Parsing all that XML would just be silly. So I decided to build the 3D graph as an AIR app, and house the data in a denormalised SQLite database table, one record per row (denormalisation was acceptable because I would basically be doing a SELECT *, reading everything in, nothing fancy). I coaxed the Excel data into INSERT statements by exporting to plain text and then using some sed and some gnarly regexps, but that’s another story. All you really need to know here is that we had lots of data, that when loaded, is arranged in a three-dimensional object model. Something like:

interface GridData {
function get numRows():uint;
function get numColumns():uint;
function get maxHeight():Number;
function get minHeight():Number;
function getHeightAt(column:uint, row:uint):Number;
}

3D space

First of all you have to understand the idea of 3D space and coordinates within it. I suggest you read this wikipedia article, it helped me.

To get an idea of how Papervision works with these concepts, have a browse of the Papervision wiki. Beware though – a lot of the info is out of date if you’re using the latest version (Great White).

The shape of terrain

I had a close look at the graph. There were certain given factors. The whole 3D grid could be divided into squares, with different heights at each corner of the square. Apparently, to render a shape in 3D, you need to break it down into triangles: these form the faces of the shape. I guess that’s because the triangle is the simplest 2D shape.

So – I would need to iterate through X (columns) and Z (rows) and find Y (the height) for each point. Apparently in 3D jargon, these points are called “vertices“. I decided to use a TriangleMesh3D object as the basis of my grid, because, well, it’s a mesh made up of triangles.

So, I tried to work out what vertices I would need to add to my TriangleMesh3D object, and what faces (triangles). I guessed I would need a vertex for every X,Z position on my graph (because my graph is basically a lumpy 2D shape, there will only be one Y for every X,Z coordinate, just at varying heights – otherwise the graph would be a flat grid).

But where to put the triangles? After looking at some examples of 3D wireframes to see how they are built, I discovered that they look a bit like this (viewed from above):

I have numbered the first six points just for ease of reference. From the looks of things (again, this is just me working intutively here, I have no background in 3D), you need to slice each square into two triangles – but, you use different diagonal lines, alternating top-right-to-bottom-left, top-left-to-bottom-right. If they all go the same way, it would look weird and wrong.

So to draw the grid. I nested two loops: one iterating over columns, the other over rows. That way I could refer to (for instance) points 1 and 2, as gridData.getHeightAt(i, j) and gridData.getHeightAt(i + 1, j). For each iteration of the inner loop, I added in the four corners of the current square, as Vertex3D objects. These would be the little points in space that Papervision would need to calculate where to put my triangles (this page helped me get the concepts clear).

I thought I would be clever here, and make sure I never put in duplicate vertices. Warning! This totally stuffed everything up. It worked fine when I just added all vertices, without caring if they were already added or not, and used mergeVertices() to get rid of the dupes at the end. I wasted a lot of time on that one.

Then I needed to add the actual triangles. At this point, Douglas’ help was invaluable, because trignometry is just a distant school memory to me. Basically, for each triangle, you need the vertices it will lie on (already created these, so that’s no problem – just make sure you alternate diagonal lines, as per my little diagram above), a material to display (I was just making a wireframe-style graph, so I just used a WireframeMaterial for the whole TriangleMesh3D, and null for each triangle – I suppose it inherits the material if none is given), and an array of NumberUV objects.

What is NumberUV, I hear you ask? Or at least, I did. Basically these are the coordinates of the three points of the triangle in relation to each other. The numbers are known as U and V to distinguish that we are talking about a localised 2D plane rather than the X,Y,Z of the 3D world.

Now, I have no idea why Papervision needs these U and V coordinates. Surely, since I’ve given it the damn vertices, couldn’t it just work it out itself? Apparently not. You have to spoon-feed it this data. So at this point I used Douglas’ trignometry, basically copying and pasting. Assume v0, v1 and v2 are the three vertices. This code calculates two values: the distances between v0 and v1, and the distance between v0 and v2, respectively (apparently we don’t need to know the distance between v1 and v2, don’t ask me why) …

var v0v1dist:Number = Math.sqrt((v1.x - v0.x) * (v2.x - v0.x) +
(v1.y - v0.y) * (v1.y - v0.y) +
(v1.z - v0.z) * (v1.z - v0.z));

var v0v2dist:Number = Math.sqrt((v2.x - v1.x) * (v2.x - v1.x) +
(v2.y - v1.y) * (v2.y - v1.y) +
(v2.z - v1.z) * (v2.z - v1.z));

Now that we have these numbers, we can built the array of three NumberUV objects that we need to instantiate our Triangle3D. However, remember that we are drawing the triangles differently, on alternating diagonals of our squares (stay with me). So, you need to use the numbers in slightly different ways. If we are on an even number (i.e. where, for our nested loops with iterators i and j, i % 2 == j % 2), then we do this:

uvArray = [
new NumberUV(0, 0),
new NumberUV(v0v1dist, 0),
new NumberUV(v0v1dist, v0v2dist)
];

… whereas if we’re on an odd number, we do this:

uvArray = [
new NumberUV(v0v1dist, v0v2dist),
new NumberUV(0, v0v2dist),
new NumberUV(0,0)
];

Clear as mud?

Now, after the two loops are complete, render your scene and you should have a 3D graph!

I also needed to put in the “furniture” for the graph – labels on the X and Y axes, for which I just got bitmaps from the designer, turned them into library symbols in Flash, and used Plane objects with the appropriate MovieAssetMaterial), and tweaked their x, y, z and rotation along axis. I made a little utility class called PapervisionCameraController that lets you move the Papervision camera around using three sets of directional keys that handle movement, tilting, pitching, etc; that came in very useful. You can download it as part of my open source utility library, Almirun Common Lib.

2D interactivity

Another thing I needed was to show highlighted “points of interest” on the graph, clickable by the user that would bring up a little info panel next to them. This needed to work regardless of the current camera angle – I used lots of dramatic camera sweeps to show off the 3D-ness of the graph. I spent a lot of time trying to work out how to get the 2D coordinates of 3D shapes (see my earlier post on this topic), getting answers on the mailing list saying that DisplayObject3D.screen should have the x and y coords I needed. However, these values were always zero, for me.

I think (and I might well be wrong here) that this is a recently introduced bug. Such is the danger of working from the bleeding edge of a project’s svn. I ended up just changing the visibility of method DisplayObject3D.calculateScreenCoords() from private to public, and calling it manually. This propograted the correct values.

I hope at least one person finds my ramblings useful … again, if anyone spots errors in what I’ve said, please feel free to correct me.

[ Edit: I have put an example with source online. ]