flipCode - Tech File - Alex Champandard [an error occurred while processing this directive]
Alex Champandard
Click the name for some bio info

E-Mail: alex@base-sixteen.com

   09/20/2000, Engine prototypes, yet more landscape LOD and hard body physics

Shameful plug

The rest of the update is fairly technology oriented, so I'll tell you about the most important part first. I've just released a new prototype of Escape. As you can tell by the following shot, it looks fairly good. Read on a bit further to find out what's so wrong with the engine itself.

I was going to wait a bit longer before releasing the demo, but my computer at home has practically died on me, so I can't update it anymore. Since it's a technological dead end anyway, I thought I'd release it anyway. You can get it right here. The remaining sections of this update will briefly explain what's so bad about this demo, and where Escape will be going in the near future to remedy to all the problems I ran into.

You're On Your ROAM

It's taken me a bit longer than everyone else to realise this, but after spending quite a long time tweaking the algorithm, having huge email conversations with Phil about this, and talking to some coders at work, I've come to one conclusion: the world is not quite ready for ROAM. It seems to me like the algorithm spends its time making life difficult for the graphics card. I'm talking about breaking strips, and generally making the points appear in random positions in the vertex array. Of course, a few nifty tricks and small hacks can generally help, but this does cost you processor time. And in the end, you end up with an algorithm that is no where near as elegant (or sexy, for those of you that can find an algorithm sexy ;) as presented in the paper.

Just to put things into perspective, there are quite a few other things wrong with this demo (as you will find out in the following few paragraphs), and they are not only due to ROAM. There is a lot of room for improvement, as this engine prototype remains unoptimised. Given enough time and the right tools, I believe it possible to get at least 4x the FPS out of this thing, and maybe even 8x if the engine was to be redesigned a bit. So using a ROAM engine for a game is possible, but given the choice of having LOD, or being able to shift twice the amount of polies at the same FPS, I don't think there is any comparison. Not to mention the instability.

Procedural Data

To be honest, I'm starting to get sick of it. As you've noticed in the demo, the landscape is practically infinite. This means you'll get bored before you get to the end of the world :P Although it does exist... Everything is generated procedurally, and as it takes quite a lot of memory to store everything, I remove landscape nodes and trees when they exit the view frustrum. The draw back for this is that when you spin the camera round really quickly, everything needs to be recomputed. Hence the second reason for the major slowdown you notice when you turn the helicopter. A solution to this would be to have a sort of database management, which would remove nodes automatically when they're not visible for a certain amount of time.

Another major disadvantage is that no pre-processing is possible, so I had to tweak the ROAM algorithm to estimate the wedge size. This causes quite a bit of instability, when the algorithm realises that it's split a node that wasn't as important as it estimated it to me, and merges it back nearly straight away.

Texturing Schemes

Everyone else seemed to be working on texture synthesis, so being the stubborn programmer that you all know, I decided to try something different. I went for texture layers. The basic concept is to compute what layers are used for each vertex, based on altitude, normal and bit of perlin noise. Then all the triangles are bucketed and stripped in realtime according to their shaders. Finally, the generic shader is applied to all the vertices in the bucket, and the whole thing is rendered as a vertex array. That's the third reason why this demo is so slow.

This method looks very good as long as you have a landscape that is fairly highly tessellated. So for a ROAM based engine, this really doesn't really work well at all. Popping is awful, and the artefacts due to linear interpolation of the layers are horrible. I pretty much fixed the popping by snapping the vertices to a bigger grid, and interpolating the texture layers in between. But this is twice as slow, and that's the fourth reason why this demo crawls on pretty much any machine.

Canned Behaviour and Physics Simulators

I bet you're all wondering why exactly I made a playable demo out of such a terrible engine. Well to be honest, I got dragged into it :P I was so much fun coding up the helicopter's movement, and the 3D sounds that I just hacked the whole thing together without even having to put any effort into it. The down side is I've ended up with a huge main.cpp file, and lots of C like code based on a C++ engine.

Anyway, when I started coding the behaviour of the helicopter, I went for the simple option: canned behaviour. This worked great. The helicopter did exactly what I wanted it to do. But one thing was lacking. I wanted it to bounce around when it hit the floor. So I decided i needed proper physics, and worked through all Chris Hecker's tutorials. Wrote a very simple physics engine, had to recode most of my basic collision detection. It was nice actually learning the theory behind the physics, but getting down and implementing the simulator was quite a horrible process. It would go into an infinite loop in some very simple cases, and it generally took up way more processing time than I expected. Again, a few nifty tricks and hacks and I got the simulator working in a fairly stable manner. I suppose that was to be expected. However, getting the helicopter to manoeuvre at all was a nightmare. I found that physically modelling the helicopter properly lead it to be practically uncontrollable. It just makes me wonder how the real pilots do it :P I gave up half way. In the end, I've got some a helicopter that is partly controlled by canned behaviour, and partly by proper physics. This way, I find the helicopter can be flown, and it bounces off the floor like I want it to.

Integrating a physics simulator into an engine is fairly easy, given enough time. But making a small game with one is quite a challenge, and very time consuming. And if all you really want is collision response, I'm not sure the pros outweigh the cons in the end.

The Road Ahead

I'm not quite going to give up on binary trees just yet. I think I'll implement a top down only version of the standard ROAM, with pre-computation. Then try out the isolevel technique, which seems to me like it would be so much more stable than the priority queue based version. I'll also implement texture synthesis, since anything vertex based is bound to look appalling.

After that, I'm moving away from procedural data, away from CLOD algorithms where you have minute control over each polygon, and away from layer based texturing. Basically, I'll start again from scratch. I haven't done that for 3 months, so it's about time I did ;) I think I'll implement the perfect static landscape first, and then see how I can apply chunk based LOD, where I can discard polies by groups of 64 for example. I'll place the emphasis on maintaining ideal strips and perfectly ordered vertex arrays. Now all I need is a bit of time, and a working computer :P

Feel free to email me any comments you have on all of this, or start a thread under the IOTD.


  • 01/05/2002 - A.I., Websites and Voxels
  • 03/05/2001 - State Of The Art Character Animation
  • 01/24/2001 - Alternate Programming Languages
  • 01/11/2001 - The Sound Of Silence
  • 09/20/2000 - Engine prototypes, yet more landscape LOD and hard body physics
  • 07/13/2000 - Good Practice (TM)
  • 06/13/2000 - Revision Week Indeed
  • 04/11/2000 - Escape From Inactivity ;)
  • 01/05/2000 - Generic Shaders
  • 12/03/1999 - Start Of Term: Lots Of Good Intensions :)
  • 10/06/1999 - Dynamic LOD, Landscape Generation and much more...
  • 09/22/1999 - Water Contest Entry: Rendering Raytraced Refraction with 3D Hardware
  • 09/16/1999 - More About Bezier Patches And Fractals
  • 08/11/1999 - The Right Landscape Engine For You!
  • 07/12/1999 - Leftovers From The Contest: Fixing TP7's Runtime Error 200 bug
  • 07/01/1999 - Introduction

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]