[PATCH] Improved polygon scan conversion for imageFilledPolygon()

[brage]

The attached patch is a new implemetation of imageFilledPolygon() for mapgd.c.

With the current mapgd.c it is not really possible to make a polygon without an outline. If no outline is specified, the polygon will have a outline the same color as the fill. This results in loss of detail, and makes small polygons (for instance lakes and islands) look bigger than they should.

The problem is that imageFilledPolygon() uses a midpoint line algorithm, and includes points which are not strictly interior to the polygon. The patch replaces this with an interior extrema algorithm, based on Paul Heckbert's algorithm from from "Graphics Gems".

The attached examples should demonstrate how big difference this makes.

The patch is also eliminates the loop iterating over every point for every scanline, and is generally much faster than the old imageFilledPolygon. It should actually give mapsever appliactions using the gd backend a noticable performance improvement.

For example, the average runtime for shp2img when creating the example maps was

	Unpatched	Patched
Itasca lakes	99ms	84ms
North Europe coastline	610ms	399ms

And, at last, Mapserver should be able to render the coastline of Norway correctly!

-- Brage Førland

[brage]

Patch of mapgd.c with new implementation of imageFilledPolygon()

[brage]

Itasca lakes theme, patched mapg.c

[brage]

Itasca lakes theme, unpatched mapg.c

[brage]

North Europe coastline, unpatched mapgd.c

[sdlime]

Wow, excellent contribution. Does AGG suffer from the same problem or is this an GD only issue? Also, regarding the patch, since this is more than a one-liner, I need to make sure the code contributed in accordance with the MapServer committer guidelines:

​http://mapserver.gis.umn.edu/development/rfc/ms-rfc-7.1/

Steve

[brage]

I have done som further refinements to the patch to use bucket sort instead of qsort, which should give a slightly better performance than the original patch, especially for for complex polygons.

[brage]

Replying to sdlime:

Wow, excellent contribution. Does AGG suffer from the same problem or is this an GD only issue?

I haven't been using the AGG backend to any extent, so I do not know if this issue affects AGG to.

Also, regarding the patch, since this is more than a one-liner, I need to make sure the code contributed in accordance with the MapServer committer guidelines:

​http://mapserver.gis.umn.edu/development/rfc/ms-rfc-7.1/

As far as I can see the patch should not violate any of the guidelines. I have been looking at Heckbert's implementation at ​http://tog.acm.org/GraphicsGems/gems/ConcaveScan.c, but the code is quite different from his implementation. The license of the Graphic Gems examples is rather liberal anyway, see ​http://tog.acm.org/GraphicsGems/.

--Brage

[brage]

Updated patch

[brage]

Test demonstrating overlapping polygons

[brage]

Output from test with unpatched mapgd

[brage]

gd_poly_fill.map is a simple testcase based on the dataset in msautotest/misc. Overlap between rendered polygons will create lines/artifacts in a darker greeen.

[brage]

Output from test with patched mapgd.c

[brage]

The AGG renderer suffers from the same problem, but for a different reason. I have created a new issue (#2749) for AGG.

[brage]

North Europe coastline, patched mapgd.c

[sdlime]

I've applied the patch to the development branch. Let's see how it works! Brage, can you make one of the complex coastline shapefiles available for test development?

Steve