Opened 16 years ago
Last modified 16 years ago
#2734 assigned enhancement
[PATCH] Improved polygon scan conversion for imageFilledPolygon()
Reported by: | brage | Owned by: | sdlime |
---|---|---|---|
Priority: | normal | Milestone: | 5.6 release |
Component: | MapServer C Library | Version: | svn-trunk (development) |
Severity: | normal | Keywords: | |
Cc: | dmorissette |
Description
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
Attachments (9)
Change History (17)
by , 16 years ago
Attachment: | mapgd.patch added |
---|
comment:1 by , 16 years ago
Summary: | Improved polygon scan conversion for imageFilledPolygon() → [PATCH] Improved polygon scan conversion for imageFilledPolygon() |
---|
follow-up: 5 comment:2 by , 16 years ago
Milestone: | → 5.4 release |
---|---|
Status: | new → assigned |
Version: | unspecified → svn-trunk (development) |
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:
Steve
comment:3 by , 16 years ago
Cc: | added |
---|
comment:4 by , 16 years ago
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.
comment:5 by , 16 years ago
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:
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
comment:6 by , 16 years ago
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.
comment:7 by , 16 years ago
The AGG renderer suffers from the same problem, but for a different reason. I have created a new issue (#2749) for AGG.
comment:8 by , 16 years ago
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
Patch of mapgd.c with new implementation of imageFilledPolygon()