Ticket #2734 (assigned enhancement)

Opened 6 years ago

Last modified 6 years ago

[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 lakes99ms84ms
North Europe coastline610ms399ms

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

-- Brage Førland

Attachments

mapgd.patch Download (9.9 KB) - added by brage 6 years ago.
Patch of mapgd.c with new implementation of imageFilledPolygon()
itasca-lakes-pathed.png Download (16.2 KB) - added by brage 6 years ago.
Itasca lakes theme, patched mapg.c
itasca-lakes-orig.png Download (18.5 KB) - added by brage 6 years ago.
Itasca lakes theme, unpatched mapg.c
northeurope-orig.png Download (10.3 KB) - added by brage 6 years ago.
North Europe coastline, unpatched mapgd.c
mapgd.c.diff Download (10.3 KB) - added by brage 6 years ago.
Updated patch
gd_poly_fill.map Download (0.6 KB) - added by brage 6 years ago.
Test demonstrating overlapping polygons
poly_original.png Download (2.9 KB) - added by brage 6 years ago.
Output from test with unpatched mapgd
poly_patched.png Download (2.3 KB) - added by brage 6 years ago.
Output from test with patched mapgd.c
northeurope-new.png Download (11.4 KB) - added by brage 6 years ago.
North Europe coastline, patched mapgd.c

Change History

Changed 6 years ago by brage

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

Changed 6 years ago by brage

Itasca lakes theme, patched mapg.c

Changed 6 years ago by brage

Itasca lakes theme, unpatched mapg.c

Changed 6 years ago by brage

North Europe coastline, unpatched mapgd.c

  Changed 6 years ago by brage

  • summary changed from Improved polygon scan conversion for imageFilledPolygon() to [PATCH] Improved polygon scan conversion for imageFilledPolygon()

follow-up: ↓ 5   Changed 6 years ago by sdlime

  • status changed from new to assigned
  • version changed from unspecified to svn-trunk (development)
  • milestone set to 5.4 release

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

  Changed 6 years ago by dmorissette

  • cc dmorissette added

  Changed 6 years ago by 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.

in reply to: ↑ 2   Changed 6 years ago by 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

Changed 6 years ago by brage

Updated patch

Changed 6 years ago by brage

Test demonstrating overlapping polygons

Changed 6 years ago by brage

Output from test with unpatched mapgd

  Changed 6 years ago by 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.

Changed 6 years ago by brage

Output from test with patched mapgd.c

  Changed 6 years ago by brage

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

Changed 6 years ago by brage

North Europe coastline, patched mapgd.c

  Changed 6 years ago by 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

Note: See TracTickets for help on using tickets.