Jump to content

  • Log In with Google      Sign In   
  • Create Account


Triangulating a polygon region over terrain


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 CaffeinePwrdAl   Members   -  Reputation: 178

Like
0Likes
Like

Posted 18 February 2013 - 08:03 AM

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:

 

PolygonRegion.png => 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.

 

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 smile.png

 

Cheers,

 

Alex


Twitter: @CaffinePwrdAl

Website: (Closed for maintainance and god knows what else)


Sponsor:

#2 Vilem Otte   Crossbones+   -  Reputation: 1391

Like
0Likes
Like

Posted 18 February 2013 - 08:17 AM

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, 18 February 2013 - 08:18 AM.

My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com


#3 irreversible   Crossbones+   -  Reputation: 1304

Like
0Likes
Like

Posted 18 February 2013 - 08:18 AM

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.



#4 irreversible   Crossbones+   -  Reputation: 1304

Like
0Likes
Like

Posted 18 February 2013 - 08:46 AM

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.



#5 CaffeinePwrdAl   Members   -  Reputation: 178

Like
0Likes
Like

Posted 18 February 2013 - 09:15 AM

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.

 

PolygonRegionEarThenClipBadTriangles.png

 

Alex


Twitter: @CaffinePwrdAl

Website: (Closed for maintainance and god knows what else)


#6 Erik Rufelt   Crossbones+   -  Reputation: 3344

Like
1Likes
Like

Posted 18 February 2013 - 10:13 AM

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, 18 February 2013 - 10:16 AM.


#7 CaffeinePwrdAl   Members   -  Reputation: 178

Like
0Likes
Like

Posted 18 February 2013 - 01:10 PM

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


Twitter: @CaffinePwrdAl

Website: (Closed for maintainance and god knows what else)





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS