Ideas for triangulation of polygons

Stainless 151 Feb 23, 2014 at 16:47

I’m extracting data from SHP files, they are used a lot in geographic apps. The particular set I’m having problems with show all the standing water in the Sudan.

Polygons end up being stored as a sequence of verts, when I draw these with System.Drawing.FillPolygon() it works fine, slow but fine. However I need them in a game and I don’t have System.Drawing.

I started out rendering each polygon into a bitmap, but they are too small and lacking in detail so I binned that.

Then I tried generating triangles by calculating a centre point and just running around the edge generating a triangle fan, didn’t work.

I looked at the data and I have lot’s of ‘bays’ and ‘crosses’ in the polygons. Yes I know, I should have looked more closely at the data before starting writing code, I’ll give myself an extreme face palm for that.

So I implemented a ear splitting triangulation algorithm. It took forever and failed on a lot of polygons.

So I’m asking if anyone knows how System.Drawing.FillRectangle works under the hood? Is it some kind of shitty flood fill?

I’m really pissed off, I really needed this done today…..

4 Replies

Please log in or register to post a reply.

TheNut 179 Feb 23, 2014 at 18:51

I’m not sure what Microsoft does with their API, but you can find out by using a .NET disassembler. It could be something as simple as the scanline algorithm and they cache the bitmap for quicker subsequent renderings.

If you’re interested in generating a permanent mesh, I would do that offline first and then rearrange how the assets are loaded and rendered in the app. Personally I use marching cubes or squares. It’s a fast, versatile algorithm that’s easy to understand and implement.

rouncer 104 Feb 24, 2014 at 07:45

well you could try a voxel attempt of some kind… but unless youve put a lot of thought into voxels before itll be months of theory, ive put years into it, nearly ready to do some photo to sculpture scanning.

Stainless 151 Feb 24, 2014 at 09:00

Since in the final app I need to be able to zoom the view, I am going to triangulate the data.

That’s why I tried the ear splitting algorithm.

Just pissed off it didn’t work. I’m going to have to try “Sweep-line algorithm for constrained Delaunay triangulation”

Looking at the bitmaps generated in my first attempt, I think TheNut is correct and they do a flood fill. It’s not a simple flood fill though. Some of the shapes it can handle make me think it’s a decent quality one.

Stainless 151 Feb 24, 2014 at 09:58

Well that has to count as another extreme face palm.

I grabbed a simple delauney triangulation library and dropped it in.

Not only was it thousands of times faster than the ear splitting algorithm, it handled every polygon perfectly.

The only problem now is I am drawing my rivers with a sprite draw and as you zoom in the lakes look beautiful, and the rivers are too big.

Now I have to go back and redo the lines…..

I never wanted to be a programmer, I wanted to be a Lumberjack swinging from tree to tree across the mighty rivers of British Columbia, with my best girl by my side, I’d sing…sing sing…