I have a computational problem - I have an arbitrary polygon chain, which I wish to triangulate, but I wish to triangulate it in such a way that the inside of the polygon is divided over my terrain grid, the resulting triangle mesh should be decomposed so that there are vertices at each grid point within the polygon. Example:

[attachment=13697:PolygonRegion.png] => [attachment=13698:PolygonRegionDecomposed.png]

I'm thinking that a scan-line algorithm could work well, as per seidels trapizoidation algorithm - though modified so that extra internal points are generated as I traverse across the polygon.

Otherwise, a multi-phase approach could work where I first clip the polygon into vertical strips, inserting extra edge points at grid locations on those new vertical edges, and then triangulating each resulting polygon using one of my existing triangulation routines - but that feels awkward and in-efficient.

I also had another hairbrained idea where I start of with the polygon earclipped, and then detect and insert points from prominant terrain features into the mesh, splitting triangles as I go - but without a round of triangle improvement, the triangulation could get nasty.

[attachment=13700:PolygonRegionEarThenSplit.png]

Ultimately the number of points involved is not going to be insanely high, so I could be crude, but I'd like to 'do-it-right'.

You can assume that all polygons are concave, non-intersecting, and without holes. Any suggestions, and any approaches are welcome

Cheers,

Alex

Just an idea - maybe useful, maybe not:

I assume you can say which grid cell is interior and which one is on boundary - interiors just spawn 2 triangles to form regular grid (from top view on terrain), just the cells on boundary are problem, but why couldn't you just use simple triangle-plane clipping (I mean doing it by hand and spawn N triangles instead of the processed one) - analogically in 2D it'd be even simplier, just line vs triangle clipping. Of course this will generate you new triangles, but the clipping code isn't that ugly (it's actually quite simple if you think about line-plane or (in 2D) line-line intersection), and you can actually write it in bunch of hours from scratch.

EDIT: Basically you don't even need to tell which grid cell is interior or boundary - but it'd be like ton of redundant operations.

Vilem,

This was largely what I was intending to do, I was just trying to think of an approach that reduced the complexity from test everything against everything else. Probably still the top on the list.

irreversible,

'Ear-clipping, then split by grid' would not generate a particularly nice triangulation as a pair of adjacent ears that completely contain a grid square can actually end up bisecting it into more triangles, especially if any of the ears were 'thin' (see below). Though as you suggest, its probably fairly easy to get that scheme working. Already have the ear clipping code in there for one.

Delaunay could be nice, hadn't thought of just triangulating the contour and the grid points from a single point set.

[attachment=13701:PolygonRegionEarThenClipBadTriangles.png]

Alex

Yeah, no worries about z-fighting - Generically, the tessellated area forms the cap of a 'terrain following vertical extrusion' - in the first case I'm using it for the top of a region of trees, with a terrain-following strip around the outside with appropriate textures for trunks, possibly another strip around the edge for foliage, the top will be textured, probably displaced slightly on top of following the terrain, with a bit of paralax mapping for relief. Should look pretty effective for what I want to achieve.

I've got some other ideas for using the functionality it once I have it in the toolbox :)

Alex