Terrain ... ONNA SPHERE!!!111

So, lots of work on a clever algorithm which reconstructs a triangle strip for every frame, cleverly including / excluding vertices on an individual basis, clever clever clever. I did an awfully clever implementation of this (well, ignoring the view fustrum culling bit), and the whole thing was looking jolly clever.

Possibly too clever.

I decided it was overkill for a game, taking up precious CPU every frame which would be better dedicated to AI or graphical effects or physics processing or whatever. So I've shelved it, probably for good.

Not one to make life simple for myself, however, I've turned instead to spherical terrain, or "planets" if you like, Super Mario Galaxy-style. I'm going for a geodesic dome-style division of a sphere. Turns out these are pretty simple to construct - you start with (say) an octagon, and then recursively divide each triangle into four smaller ones, pushing the new vertices out onto the surface of the sphere you're trying to approximate.

This is a really rough drawing ... but you can follow the subdivisions by colour, red then green then blue then pink:

I'm doing my subdivision in two stages - two or three iterations to get me a set of "patches". With two iterations, that's 8x4x4=128 patches. Then I further subdivide in each patch, creating perhaps 32 rows of triangles. This arrangement allows me to test distance / visibility etc against each patch, and then render the patch (or not) accordingly, so 128 checks instead of a brazillion (see below).

That framerate's not looking too good though (7 frames per second!). Let's count up how many triangles we're talking about (let's ignore the fact that we've got a count up there already - 38656. For boring reasons, this isn't what we're going to get to anyway).

Start with an octagon (so, 8 triangles).

Split each triangle into 4, twice (so 8*4*4=128).

So we'll have 128 patches.

Then for each patch, we'll have 32 triangles per side. That's 32*33/2=528 triangles per patch.

That's 128*528=67,584 triangles total.

BUT:

We don't need to see patches on the far side of the planet, in fact, we'll probably only be able to see about 32 patches maximum.

And, of those, we'll probably view roughly a third (let's say 12) at full resolution. The rest, we'll have at 8 triangles per side.

But we need the patches to join up nicely, and in general they won't. If we have a patch at 32 triangles per side next to one at 8 triangles per side, we're going to get gaps. So we "fill up" the edges of the low-res patches so that they're full resolution along each side. So each patch will have:

3 corners with 7 triangles = 21 triangles

18 edges with 4 triangles = 72 triangles

36-21=15 remaining triangles = 15 triangles

(this picture is with four triangles per side, but you get the idea!)

Total: 108 triangles

So the grand total once we've done all this is:

12*528 + 20*108 = 8496

That's not so much, is it?!

Now, is a 67k polygon planet going to be detailed enough? Some VERY rough sums: A planet with 0.5km radius (roughly what I'm aiming for), has a surface area of about 1.5km squared. That's 2.25 million square metres of territory. So our triangles will be about 33 square metres in size (say, 6m x 6m).

Hmm, not bad, but I'd like to get it better than that. Still, I've satisfied myself that a scheme along these lines will work - I can afford to have more than 8.5k polys in my terrain I reckon, plus I was conservative in a few places with this estimate. And I can consider (for example) three different levels of detail for each patch. With some tweaking, we should end up with a rather good environment to play in!