Talkin' 'bout my generation

Most of the mini-milestones I set myself in my last entry have gone pretty well:

Collision detection is one thing, collision handling is another

• I decided against switching matrix libraries. The boost one doesn't have a constructor, and that's the bit that's most iffy about my own matrix class. Once I'd implemented Gauss-Jordan elimination, pretty bloody well if I may say so myself, I had everything I needed. I also discovered that the uniform matrix functions in OpenGL have a built-in transpose flag, which is useful for overcoming the row-major/column-major issue.
• Quaternions - not very intuitive, but dead easy once you get the hang of them. A single "orientation" quaternion can be directly translated into the model matrix, or can be multiplied by an arbitrary vector on the model to find where that vector lies in the current orientation. For example, if vertical thrust is in the Y direction in the model, multiply that by the orientation quaternion and you've got the new direction of thrust.
• Mouse input seemed simple at first as I used WM_MOUSEMOVE, but the problem with that is it's bounded by the window or screen. It took me a while to find the right solution, many people seem to advocate moving the cursor back to the centre of the window, but I reckon the best way is to use raw input. Once you know how it's pretty simple and works beautifully.
• A chase camera, as expected, was very easy once I had the stuff above in place. However it caused a lot of grief as I forgot to give it an object to chase, and I started getting some very weird errors - unhandled exceptions in crtexe.c. Turns out that's Visual Studio's special way of saying "segmenation fault" or "uninitialised pointer". Still, I got to the bottom of it fairly quickly and learned a lot about VS's heap debug features in the process.
• Vertex buffers were again much easier than I thought. You just have to be careful to unbind the buffer when you're done or it'll confuse any subsequent OpenGL code which doesn't use buffer objects, and careful not to do out-of-bounds memory accesses or it can crash the video driver. I'm also using index buffers, they make my code a lot simpler and take up less memory. All in all I'm now able to have many more triangles on-screen without any creaking at the seams.
• Collision detection is really quite hard. I'm just doing the most basic test - player collisions with terrain based on the player's "bounding sphere" intersecting with the terrain tile. Once again the coding isn't the problem - it's remembering all of the maths. How do you find the distance between a plane and a point again? Oh yeah... find the plane normal, scalar projection, Bob's your uncle. There's a lot more work to do here - I'll eventually have to do BSP trees I guess - but it's usable for now.

I still don't have much, but all the pieces are gradually coming together now, and it means I can go into more depth on specific things...

At the moment, the thing I'm getting most excited about is the terrain. Initially I thought I'd have a terrain map, wrapping at the edges as Lander did. But say I have a terrain map made up of 1024x1024 tiles, and only have one byte of terrain data per tile - that's a megabyte straight off the bat. For height and colour it's going to be at least 5 bytes per tile, and if I have multiple maps it could build up to quite a lot of data. I'd also like the possibility of large, open spaces where you can really build up some speed and not wrap too quickly,  which probably means much bigger maps than that.

Wireframe terrain maps: an 80s sci-fi staple

Big terrain maps mean lots of storage, potentially a large memory footprint to cache it, and a lot of design too, so I'm drawn to the idea of procedural generation. Here terrain is generated algorithmically from a pseudo-random sequence. Rescue on Fractalus! used this idea, but that was a bit too craggy and random. I could have a mix of designed levels dotted over the world, with generated terrain covering the gaps - much like Frontier, where core systems were scientifically accurate but the rest of the galaxy was procedurally generated. This is gradually turning into a homage to David Braben...

But back in the real world, the terrain doesn't warp around existing sites - structures are located in suitable sites in the existing terrain. So I think that's probably the way to go - generate large amounts of terrain randomly with procedural generation, then scout for suitable sites to put the levels and apply some "terraforming". I'm not sure how easy that would be in practise, and if I changed the generation algorithm then everything would have to be re-done. So for now I want to concentrate on the algorithm itself and get that nailed down.

A commonly-used method for generating terrain is the diamond-square algorithm. It's a pretty simple iterative method which is described very well on this page, so I won't repeat the explanation here. To generate pseudorandom numbers I'm using a Linear Congruential Generator, with the same parameters Donald Knuth himself uses for MMIX and an "X_n" formed by combining the x and z co-ordinates.

A mountain floating in the air kinda ruins the illusion of realism

The results are vaguely realistic-looking. I've applied some stock textures with transitions based on bands of height, and some very crude blending between them - it doesn't look brilliant but it's good enough for now, and it showed up a bug in my depth buffering which I hadn't noticed with wireframes or flat colouring.

The next thing to look at is what to do at the edges. The weedy solution would be to wrap, but because I can use use procedural generation to map out an essentially infinite area it'd be better if I generated more terrain. The problem is that I don't really want to have to draw an infinite area every frame, so I need to find some intelligent way of only storing the terrain for the local area and generating more terrain on-the-fly as the camera moves. Easier said than done, and it's going to get worse when I add diffuse lighting and need to calculate vertex normals for every triangle. but an advantage of the diamond-square algorithm is that because it's iterative you can easily generate some terrain in the distance at a low level of detail and apply more iterations to increase the detail as it gets closer.

Ideally I'd map out an entire planet. That'd be fantastic, but it's going to be tricky. The tiles that make up the terrain will no longer be relative to a horizontal plane, but the curved surface of the planet. The horizon will naturally limit the required draw distance at low altitude, but it'll need to increase at higher altitudes to the point where I can fit the entire planet on screen. This'll probably mean I'll have issues with depth buffer precision, which can lead to z-fighting, so at the very least I'll have to change the clipping planes as I zoom out, but I'll probably have to do multiple passes.

Still no physics, still no lighting, still using a placeholder for the UFO, still no sound whatsoever. Then I'm getting crazy ideas for little touches, like using GLSL shaders to model atmospheric refraction. And one day I'll port it back to the Raspberry Pi again. Plenty of stuff to do, so little time.

Crash! Boom! Bang!

The aforementioned freezes are back and getting a bit ridiculous now. The problem's not limited to OpenGL, it sometimes happens shortly after boot before I've run anything. Fortunately I now occasionally get useful error messages, so I've been able to do better Google/forum searches and apparently this is quite a widespread issue. Setting the USB speed to 1.0 seems to help quite a bit, performance still seems acceptable, but it's making the whole Raspberry Pi experience a bit frustrating at the moment.

I don't see any point in working with the Raspberry Pi in this state, definitely not any hardware project where there are likely to be power issues obscured by the USB problem. So it's with heavy heart that I'm moving my OpenGL coding over to Windows, which is a crying shame. I'll come back to the Raspberry Pi one day, hopefully soon, but for now I'm left feeling that I got mine a bit too early, more so now there's a rev 2 board and more recently it's being shipped with 512MB as standard. Maybe I'll blow mine up with a hardware project and have an excuse to buy a new one?

OpenGL is intended to be cross-platform, and in past projects I've had it up and running on Windows and Linux very quickly. The first problem with OpenGL in Windows is that the maximum version supported is OpenGL 1.1, which was released way back in January 1997 when the likes of the 3dfx Voodoo, Matrox Mystique and PowerVR series 1 were all the rage, as indeed was the Rage. v1.1 has been fine for me in the past, but if I want to use the same features that are mandatory for OpenGL ES 2.0 (primarily shaders, introduced to desktop OpenGL in v2.0) then I need something more up to date.

You can't upgrade Windows to a newer version of OpenGL as far as I can tell, to get more up-to-date feature support you have to add individual features as extensions. Thankfully this can be handled by the GL Extension Wrangler Library (GLEW). It's a bit of a pain to set up, and when I thought I'd managed it both the static and the dynamic library refused to link no matter what I did, so I ended up importing the GLEW source into my project.

And then I think I found a bug in Visual C++. I've got a square matrix class template which takes a value type and a dimension. Its only member variable is an array which contains the elements, and there are member functions to assign values, do multiplication of two matrices, etc. The default constructor does nothing and, as I'm not ready for the brave new world of C++11 yet (given that VC++ has enough trouble getting C++98 right), I assign values with a redefined operator= which copies data out of an array, or another constructor which takes an array. When I created some arrays to do this, and then declared the matrices, I found some really weird stuff going on. If I just did the matrix declarations, no copying, all of the matrices had the same pointer. If I passed the arrays to the matrix constructors, or assigned them with operator=, then each matrix would have the same pointer as one of the arrays, but not the array that was assigned to it. If I made the arrays static (which is perhaps the right thing to do anyway) then everything was fine. What on earth could cause this? Just my own incompetence? The same code worked OK in g++. As soon as I've found a minimal example of this going wrong I'll submit it to MS.

After I'd worked around that, and remembered to actually call the function which initialised my OpenGL shaders (took me two days to work that one out), worked out how to use a class method as a custom message handler, tried GDI+, failed to get it working and reverted to OLE (about a month on that, admittedly much of it spent being too frustrated to progress and playing Skyrim instead) I was back to where I'd got to on the Raspberry Pi. I was doing a simple rotation about the X-axis, but when I set up the perspective projection matrix properly I got oscillation in the Y direction in time with the rotation. This didn't happen with orthographic projection, so surely I'd done something wrong with the projection matrix? Turns out it was fine, but GLSL stores matrices in column-major format whereas C arrays are effectively row-major. Transpose the final Modelview-Projection matrix and hey presto... everything working beautifully.

Sorry Chloe, Little Teddy turned out to be an intergalactic
criminal mastermind so we had to send him to the Phantom Zone

I've now moved away from "yayy, it works!" and started structuring things a little better for Offender (still need a better name). Rather than continuously drawing a load of triangles, I've got object classes with drawing and moving methods, and separate drawing routines for terrain. Now I can build up a list of objects, it's actually starting to look like the beginnings of a game. However, now I'm putting in more stuff I've found that it bellies-up and dies at around 17,000 triangles. At 60Hz that's about a million a second, which seems a bit low. Admittedly there's still a lot of room for improvement - I'm not using vertex buffers for example - but sorting that out is secondary as I don't need huge numbers of triangles on-screen (yet). All I really need is a single object and some terrain for context, hence the rather psychadelic effort shown here.

In spite of being a lot more complex under the hood, on the surface it's still a bit "Hello Triangle!". Next steps:

• Maybe use someone else's matrix library, for all the usual reasons people use standard libraries. Why go to the trouble of implementing a matrix inverse when someone's got a tried-and-tested implementation already? The ever-dependable Boost has a matrix library, but I don't think it's quite what I want.
• Do object positions by coordinate and rotations by quaternion, rather than matrix, so it's easier to move things around. I've already got much of the code for this in my OpenGL screensaver.
• Add mouse input and player control. Easy for Windows, I'll leave Linux to another day.
• Add a chase camera to follow the player object. Should be dead easy once I've done all of the above.
• Add collision detection. Though it's not hard to knock together a crude algorithm, it's difficult to do collision detection accurately and not slaughter your CPU in the process. I've had loads of ideas about this, found a guide on the subject and looks like I was definitely thinking along the right lines. I'll start with something pretty crude though - if I could just make the terrain solid so I can't fly through it, that'd be a start.
• Switch to using vertex buffer objects, maybe use index buffers too, as I'm going to need more triangles sooner or later. I'll probably want texture buffers too.

Once I've done all that, I think I'll have all of the major boilerplate in place and can actually start building up the interesting stuff.

And finally, you may have noticed that I'm a bit of a David Braben fanboy, so please support Elite: Dangerous. 'Tis a worthy project.