# Triangulating a polygon region over terrain

This topic is 2065 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites

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.

Edited by Vilem Otte

##### Share on other sites

I'd use something like ear clipping to decompose the concave polygon (because that's the biggest problem you have) into as few triangles as possible and then split those along the grid lines. You'll end up with triangles and quads, which are trivial to unify into either triangle lists or strips. Ear clipping is easy to implement if you don't have to worry about winding and if the concave polygon doesn't fold back in on itself (eg touches itself (no pun intended); anyway - if it does, then this is important to handle, because it complexifies ear clipping considerably).

Overall, ear clipping is easy if you can trust the input data. If you want a robust triangulator that you can just spit data at, then you'll be in for a small ride.

##### Share on other sites

Or if you're up for a bigger challenge, then Delaunay triangulation should give you want you want directly if you place your points on grid intersections inside the polygon.

##### Share on other sites

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.

Alex

##### Share on other sites

What are you going to use it for?

If you're actually placing it on a terrain then you probably want the triangles to match the terrain triangulation exactly, as a quad can be triangulated by splitting by either of its diagonals, and the two triangulations are not equivalent unless all the 4 vertices lie in a plane.

I would start with the triangulated grid and simply clip it to the polygons you place on top. Should be rather simple as only those triangles of a cell that are intersected by a boundary edge need to  be changed, and all the interior cells are already done. It should yield a nice triangulation, and reduces the problem to the clipping of a single triangle to inside the shape, for each edge-intersecting triangle.

Edited by Erik Rufelt

##### Share on other sites

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

1. 1
2. 2
3. 3
Rutin
16
4. 4
5. 5

• 14
• 9
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
632912
• Total Posts
3009182
• ### Who's Online (See full list)

There are no registered users currently online

×