More terrain rendering musings...

So, I finally caved in and decided to get a next-gen console. Yes, so I do have a Wii, but I really don't think that counts (you go Hecker!). So the question really was Xbox 360, or the Playstation 3. Now both Sony and Microsoft get on my nerves with their ad campaign and hype machine so I tried real hard to ignore things that have been said in the past (which are so absurd I won't even bother to post them here). The question then was, which console offers the most for me, a self-proclaimed casual hardcore gamer. As far as game selection, the 360 wins hands down. I'm not just talking about the much hyped Gears of War or Halo 3, but other worthwhile titles like Just Cause and the soon to arrive Mass Effect. The PS3 is definitely lacking here. On the other hand, things are looking up with games like LittleBigPlanet and Eye of Judgment coming out (which is reason enough to buy a PS3 imo). Oh and Civilization Revolution of course. :-)

Now the nice thing about the PS3 is that it doubles as a Blu-ray player, which appears to be winning the Hi-Def disc wars. Right now (until stock runs out), the PS3 60GB version is selling at $500, which is not too shabby considering it still maintains hardware backwards compatibility with PS1/PS2 via the emotion engine and vector units (and costs Sony $800 to manufacture. Ha, do the math!). To buy an equivalent Xbox (w/ HDMI) you'd have to get the $450 Xbox 360 Elite. For next-gen video, i.e. HD-DVD (instead of Blu-ray, which the 360 does not support), that's an additional $100 (I should mention MS has mandated this drive can never be used for games either, whereas PS3 Blu-ray can). Oh, and you want wi-fi internet access? That's another $100. So for an equivalent Xbox that can compete (feature wise) with the PS3, you're talking about spending $150 more!! To exacerbate the cost, the reported 30-60% failure rate is insane. I think you can already guess which console I went with.

Now I think for a while the naive approach most developers have taken towards games for the PS3 will result in a slight win for the 360 (thanks to great development tools, more on-die cache on the (same) PowerPC processor, unified (instead of segmented) video memory, predicated tiling with "free" MSAA, etc...), but once people start using the SPU's as they should be, things are bound to change. I give it two years time. Until then, I'm very happy with my new Blu-ray player. ;-)

The only problem I've run into so far is heat due to my keeping the thing in an enclosed cabinet. I'm not willing to sacrifice aesthetics (what can I say, I'm shallow), so I devised a plan to improve air flow and found a cute little usb fan that looks like it will work just nice. So after coming up with all this I decided to run it through my "this has to have been done before" filter and found someone who did the exact same thing (same fan even)! Props to you Mick, I'm sure this will work now!

So to change the subject a bit, I'm nearly done with a major overhaul to my new terrain system. I tried to come up with a good real-time continous LOD algorithm but I ran into a few initial problems. My first approach involved implementing a simple Binary Triangle Tree for polygon simplification (basically split a triangle at it's hypotenuse recursively until a max error level is met), which resulted in improved frame rates in high density terrains in the millions of polygons, but due to the triangle formation not being trivial I had to switch from using triangle strips to triangle lists which resulted in a HUGE performance hit, even with less polygons! I thought about using a 3rd party strippifier (like nvTriStrip) but it will most certainly add a lot of time to the precomputation (which is already somewhat long). I may investigate this in the future, but for now I decided to approach the problem slightly differently.

In addition to the terrain simplification I planned to incorporate a quadtree to split the terrain up. As I was doing this , I suddenly remembed a paper I had read a good number of years back by Thatcher Ulrich on something he calls Chunked LOD. The basic premise is so simple it's brilliant. The purpose of the algorithm is to be able to render massive terrains that could not possibly be rendered on modern hardware. To do this, you take your massive terrain heightmap and subdivide using a quadtree (a recursive structure that divides a 2D field into 4 sub-area's until some condition is met). Each sub-level however may still result in too large chunks (quadtree nodes), so some kind of simplification must occur.

For the simplification I merely resample the heightmap grid using a bicubic filter I coded up a while back (which looks just as good as photoshop's). I also map the height resolutions to some pre-determined max (for sanity's sake). As an example, a 8092x8092 terrain is WAY too large to display on modern hardware in real-time (it would be in the millions of triangles). If I was to decompose the quadtree to the 4th level, I end up with chunks sized 4096, 2048, and 1024. All of those sizes are still pretty massive, but lets say 1024 was acceptable as a max. Now instead of 8092 for the base chunk, we get 1024. For the next 4 sub-chunks we _could_ half the parent chunk's resolution, but this would result in a uniform distribution of points (not giving us better detail as the tree subdivides). By substituting the max for this number, I still maintain something close to my max from before, but increase the fidelity of the terrain mesh. So each level (including base) becomes 1024, 1024, 1024, and 1024 (the original high resolution version). In this case the lower levels (0, 1, and 2) lose some visual fidelity, but the highest level (3) maintains all of the original detail. This is important since this is the level the viewer will view closest.

Thats pretty much how my pre-processing algorithm works. In real-time I recursively render the tree and at each node, check to see if an LOD error metric for that chunk has been met. If not, I continue down the tree until there are no more nodes (leaf node) or we're at a tolerable error level.

The results so far are excellent, I'm very happy with it. The only problem so far is the seems at the edge's are still not acceptable even after implementing the terrain skirts like Ulrich mentions in his paper. I think this might have something to do with me not using enough levels so I'll hold off on trying to fix that further for now. The textures (dif/spec and normal map) are split in a similar fashion so I may be doing something wrong there as well to be causing the seems. The last thing I need to do is get terrain morphing working between levels to get rid of the unseemly pop when the LOD level is changed. I plan on doing something very similar to how I did the GPU vertex morphing for the Mona Sax facial animation demo. I'll have more on this later. Until then, here are some screenshots and a short video to demonstrate how it works!













One last thing! I tried to put into words what I thought of the movie 1408 which I finally got a chance to see last weekend as well as the Unreal Tournament 3 demo which I somehow found time to play. Unfortunately I just wasn't able to, so I leave you with this:



Phantom Hourglass on the other hand gets an A+.

l8r meeples!