• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
aleks_1661

Triangulating a polygon region over terrain

6 posts in this topic

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

 

Cheers,

 

Alex

0

Share this post


Link to post
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
0

Share this post


Link to post
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.

0

Share this post


Link to post
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.

 

[attachment=13701:PolygonRegionEarThenClipBadTriangles.png]

 

Alex

0

Share this post


Link to post
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
1

Share this post


Link to post
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

0

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  
Followers 0