Converting 2D Tile based shapes to simplified Polygons

Question

As seen in the image above, I have a 2D array of tiles, each with 4 points in my game world. I'm looking for a method to convert these shapes constructed from individual tiles into simplified (no unnecessary vertices, only those needed to form the outline) polygon shapes.

I have been looking around, here and elsewhere and have had very little luck. But maybe I don't know the correct terminology to search for. Any help is appreciated.

Extra Info: I'm looking to use this to optimize dynamic lighting. If someone has a different approach for accomplishing fast dynamic shadows in a tile based world, that will also answer the question.

Waterfall

Nice images. How did you create those? – Largescale

I created them by hand in photoshop :) – Waterfall

Answer 1

I suggest next algorithm:

1. Storing all edge positions into 2D array (edge position is center of edge).
2. Counting duplicate edges in this array (1 is no duplicates, 2 is intersecting with another edge. Other values are implossible).
3. Picking first unmarked edge from array with duplicating count 1 (no duplicates) and applying simple recursive fill algorithm in certaing direction (Clockwise for example) until first edge reaching. All this edges will form one simplified polygon. If unmarked edge has not been founded, then GOTO 5.
4. Marking all this edges from step 3 as used. GOTO to step 3.
5. End.

For more intuitive representation of algorithm, I posted an image below.

Nectarous

I'm trying to implement your algorithm in JS, but I have a hard time grasping the exact details of the implementation. For step 1 (storing edge positions into 2D array), I stored the edges as follow: [ [ '0:0' '1:0' ] [ '1:0' '1:1' ] [ '1:1' '0:1' ] [ '0:1' '0:0' ] [ '1:0' '2:0' ] [ '2:0' '2:1' ] [ '2:1' '1:1' ] [ '1:1' '1:0' ] [ '0:1' '1:1' ] [ '1:1' '1:2' ] [ '1:2' '0:2' ] [ '0:2' '0:1' ] ] Do I misunderstand how to store all edge positions into 2D array? – Aegisthus

What do you mean by "edge position is center of edge"? – Aegisthus

Answer 2

The naive approach would be to simply step through every single tile and mark any transition edges into a polygon but you could reuse a common edge detection routine for better performance.

After that you'd probably be interested in tessellating those polygons so as to convert them into collections of triangles (making the later shadow/lighting/intersection math a lot simpler), the only problem in this case is if you end up with a concave polygon, but a decent tessellator should allow you to break it up into convex polygons. I don't think XNA has anything built in for tessellation so you might need to find a utility library to do it for you.

Phenetidine