Polygon fill draws an extra line along left edge of image

[dmorissette]

Hi Steve, sorry to bug you with another one today...

Someone with a sharp eye has pointed to us that in some cases a blue line was 
appearing along the edge of the map produced by one of our MapServer apps.  I'll 
attach an sample map to this bug.

My first reaction was to think that what we saw was the IMAGECOLOR, but that's 
not the case: the IMAGECOLOR is beige in this mapfile.

After investigation, we found that it was a donut polygon that was flooding.  It 
turns out that the map contained an "oceans" layer which was a huge box with a 
hole in it representing the landmass of Canada, like a donut shape.  And when 
you look at a map that's mainly inside the hole then you get this blue line 
along the left edge.  I know this donut-shape for the ocean may not look like 
the best way to do things at first but they were forced to do so because of 
some data issues.

Anyway, this is a minor issue, and we implemented a workaround for this 
application, but we thought that it would be a good idea to raise this as a bug 
in case you want to review the polygon filling code and see if you can fix this.

[dmorissette]

Sample map showing the blue line along the left edge

[dmorissette]

Steve Lime wrote:
> 
> Can we verify the age of this bug? Does it predate recent changes to the
> polygon fill routine (3.6.1)? I assume so but want to make sure since
> that code is ancient.
> 


This was using MapServer 3.6.2.

Should we try to test this with an older version?

Daniel

[dmorissette]

Dean (or Dave/Jeff) can you please test this with MapServer 3.5 and report back 
to this bug whether the problem was present in 3.5 or not... we must have an old 
3.5 DLL around somewhere on our download site.  

The reason for this test is that there have been changes in the polygon fill 
algorithms between MapServer 3.5 and 3.6 and Steve wants to find out if the 
problem is related to those changes before looking any further.

Thanks.

[sdlime]

I'm wondering if the problem I fixed with an extra pixel at the corner of shaded
legends is related to this. It was a scanline issue that may well have
manifested itself in otherways with certain polygons. Does anyone have a
repeatable test case they could try with beta 2?

[mcilhagga@…]

Dean or Jeff might have that old map file with the ocean polygon that was
causing the problem?

[jmckenna@…]

I'm testing with mapserver 4.0 beta 2 (this morning's build).

The bug still exists, I found the donut polygon shapefile from that same
mapfile.  I made a small mapfile with just the donut oceans layer (deep blue
colour) and when I zoom into the donut (where there is no data) the resulting
gif has a blue line on the left edge.  I'm attaching a couple of screengrabs.

[jmckenna@…]

donut poly layer

[jmckenna@…]

phantom blue line on left

[sdlime]

I'm afraid I'll need the data and mapfile. Possible?

[jmckenna@…]

http://www2.dmsolutions.ca/netbin/phantom-line.zip

It's about 5 MB, and only contains the oceans shapefile and the mapfile.

[sdlime]

This one is still marked as open. I believe I fixed it a good while ago. There
was an error in the scanline conversion code. Still an issue?

Steve

[dmorissette]

Jeff, can you please check if this is still an issue with 4.1?

[jmckenna@…]

problem still exists..tested with a build from March 3rd.  Attaching screengrab.

[jmckenna@…]

still exists

[sdlime]

Will shoot for this summer.

[dmorissette]

Problem still present in latest MapServer and this is causing us problems for
some stuff we're doing. I'll reassign to Assefa to have a look.

I agree with Steve that it's probably a scanline problem in the polygon filling
routines, either that or a polygon clipping issue.

[assefa]

I think the problem is with the polygon clipping. Apparently the  Liang-Barsky 
Polygon clipping algorithm can produce degenarte polygons arround the clipping 
window. I have added some code to clean up degenarte polygons and It seemed to 
have corrected the problem seen in the test case. I am though a bit nerveous 
to commit this since It is in a sensible part of the code and I am not 100% 
sure of the solution (I have based this on 
http://orion.math.iastate.edu/burkardt/g_src/drawcgm/cgm_clip.c that explains 
the situation).

The code I added is basically the function "clean_degenerate_edges" found in 
the link.

I will make additional tests later on today. 

Any comments, advice on this ?

[dmorissette]

Only one question, but a very tricky one: Do you know if this new function has
much impact on performance?

With respect to committing to CVS, let's wait to hear from Steve to see if he
has any comments, but I think that the sooner we commit this the better to
increase the chances of catching any side-effects during the 4.6 beta period.

[sdlime]

Assefa, since it's not in CVS can you post the changes?

Steve

[assefa]

Here is the code :

diff -r1.51 mapprimitive.c
510c510
<   int i, j;
---
>   int i, j, changed, numpoints;
647c647,692
<       msAddLine(&tmp, &line);
---
> 
>       numpoints = line.numpoints;
>       /* clean_degenerate_edges */
>       /* this was necessary to correct Bug 179. This logic was taken from 
>          http://orion.math.iastate.edu/burkardt/g_src/drawcgm/cgm_clip.c */
> 
>       while (changed)
>       {
>           changed= 0;
> 
>           /* Check for not enough vertices */
>           if (numpoints <= 2) numpoints= 0;
> 
>           /* Check for colinear triples in x direction */
>           for (i=0; i<numpoints-2; i++)
>             if ( (line.point[i].x == line.point[i+1].x) && 
>                  (line.point[i+1].x == line.point[i+2].x) ) 
>             {
>                 for (j=i+1; j<numpoints-1; j++) 
>                 {
>                     line.point[j].x= line.point[j+1].x;
>                     line.point[j].y= line.point[j+1].y;
>                 }
>                 numpoints--;
>                 changed= 1;
>             }
> 
>           /* Check for colinear triples in y direction */
>           for (i=0; i<numpoints-2; i++)
>             if ( (line.point[i].y == line.point[i+1].y) && 
>                  (line.point[i+1].y == line.point[i+2].y) ) 
>             {
>                 for (j=i+1; j<numpoints-1; j++) 
>                 {
>                     line.point[j].x= line.point[j+1].x;
>                     line.point[j].y= line.point[j+1].y;
>                 }
>                 numpoints--;
>                 changed= 1;
>             }
>       }
>       if (numpoints > 2)
>       {
>           line.numpoints = numpoints;
>           msAddLine(&tmp, &line);
>       }

[sdlime]

Hmmm... MapServer has code elsewhere to remove colinear points, the goal being 
to simplify the shape as much as possible, although that checking is for lines 
of any orientation. I believe that processing happens as map coordinates are 
converted to image coordinates, then the shape is clipped. If that's the case 
then these tests would be appropriate. If done for every feature then this 
could get expensive cause your traversing the points array twice. 

Since the artifacts always appear on the left edge of the image I wonder if we 
could leave the clipper alone and instead adjust the clipping rectangle to the 
west one pixel so that any degenerate polygons fall outside the field of view. 
They don't seem to hurt the rendering code. Do we know exactly what a 
degenerate polygon looks like? I mean, is it consistent in any way (e.g. 3 
verts)?

I guess I wouldn't commit yet until some timings are run with and without the 
change and we look at the clipping extent.

Steve

[assefa]

Steve,

 I was doing testing with it today here and the changes I made created more
problems than solutions (lot of polygon flooding). So It is definiltly not
material to commit.

After discussing with Daniel, he suggested adding a 1 pixel buffer around the
clipping rectangle as you are suggesting and we tried this with the data and the
problem seem to have disapeard :). Here is the code I added in mapdraw.c just
before the call to msClipPolygonRect:

diff -r1.90 mapdraw.c
1290c1290
< 
---
>   double buffer;
1587a1588,1594
>       buffer = (map->extent.maxx -  map->extent.minx)/map->width;
>       buffer = buffer *2;
>       cliprect.minx -= buffer;
>       cliprect.miny -= buffer;
>       cliprect.maxx += buffer;
>       cliprect.maxy  += buffer;
> 

 You see that I have multiplied the buffer by 2 since just using the buffer did
not correct the problem on the test data that we were using.

 I need to do more testing with other data but I am more confident that this
would be less disruptive than the first patch.


Later,

[sdlime]

Any word on this one?

Steve

[dmorissette]

I believe Assefa fixed it. Can you please update the bug Assefa?

[sdlime]

I'm still seeing the effect, will make sure I'm up-to-date though...

Steve

[assefa]

I commited the fix as described in comment #22 (mapdraw.c).

We did not see any side effects with the changes and It seemed to have solved 
the problem.

Marking it as Fixed.

[dmorissette]

Steve, since the 4.6.0-beta2 has not been posted to the website yet, I have
re-tagged the CVS source as rel-4-6-0-beta2 to include this fix.