Please see the pic below that is clearly a level from my in-development game.

Apologies this is a bit long, but I want to make sure you understand the problem space.

That mesh is generated purely in code from a hexagonal 2D tile editor. To make a mesh, I dived up the 2D hex tiles into groups "islands" and then run a simple algorithm to find the edge of each Island as a list of points, then extrude that downwards with some edge faces. And it all works ok.

The problem is overdraw. The "Sea" for example is pretty much a screen filler, then this is overdrawn by all the islands from height 1. Which in turn is overdrawn by all the islands from height 2, etc.

On iPAD this is killing the FPS due to the amount of wasted overdraw. What I really need to do us a boolean cut of whatever is below the current island, but that sounds like a real nightmare.

So what I've been thinking about is how to start again from the top and triangulate all the point lists from my islands in one hit to make a shape that looks like a shrink-wrap of the surface.

In other words, given every point in my level, would something like a delaunay triangulation give me a mesh that looks like the one in the pic below, or would it just give me a nasty convex hull etc.? I can't quite make up my mind from reading up on delaunay as it seems that keyword describes a result, not a solution iyswim.

Anyone have any useful ideas on where I should go from here? Many thanks...



[Edited by - Rubicon on September 26, 2010 6:23:20 PM]

I think there is some sort of Hi-Z thing going on, but it's fill rate that's the problem, not shader execution. Therefore just doing a depth filling pass will take too long as its extra iyswim.

Also, that's a "nice" camera angle. The game view is much straighter down for the most part.

I guess I could use a tiling system and stitch the bits together, but that would then make geometry with many more vertices in it. Not sure what the knock on of that would be vs the saved fill-rate, but it sounds like a lot of work just to find out the answer is "yes, it's just as slow" :(

Given the planar nature of there the height comes from, I reckon I could get away with solving the core problem in 2D slices, kinda like what I'm doing now, only with an extra layer of code.

How about, if I mesh up each plane (ignoring the cliffs for now) using a routine that meshes up around holes? Is there something online I can look at for this? I guess it's like ear-clipping++ or something?

EDIT: I just realised you said sort from top to bottom. I just checked and actually I'm sorting bottom to top because that's how I first got it working. I'll change that and see if it makes a difference, but I'd still like to get this mesh optimised better also. Thanks.