Sign in to follow this  

Triangulation to a shrink wrap?

Recommended Posts

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]

Share this post

Link to post
Share on other sites
Actually, I think the boolean approach would probably be the best. You already have to deal with non-convex polygons, which is the only hard part. Given an island with a hole in it, find a vertex on the hole and a vertex on the border such that the line segment between them is entirely within the border and outside the hole. Then just add two edges there and merge the vertex lists of the border and the hole, making it from an O into a C with a zero-width cut. Continue for all the other holes.

Incidentally, though, with that low viewpoint there could be a significant amount of overdraw anyway. I haven't used the iPhone graphics libraries -- does the hardware do early Z testing? If so, sort from top layer to bottom layer and you may not have to worry about any of this crap.

[Edited by - Sneftel on September 26, 2010 9:02:36 AM]

Share this post

Link to post
Share on other sites
do u already render the terrain in a sorted way?
from the top most layer to the bottom layer the sea?

cause if not u would profit a lot of z-culling

Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this