Thread: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c (Page 2)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

On 2016-09-12 21:39+0100 Phil Rosenberg wrote:

>>>> I'm still of the opinion that the notcrossed function should not use
>>>> the 2 pixel fuzziness. At this point in the drawing we are dealing in
>>>> integer pixels and we need only an epsilon test I think. I think the
>>>> best fix is to change this. There are some sticking plaster solutions
>>>> that would hide the problem but not really fix it in my opinion. I
>>>> would really like to change the notcrossed function unless anyone has
>>>> some really strong objections?
>>>
>>>
>>> My opinion is this is an extraordinarily tricky topic where all the
>>> currently active fill code (i.e., the part of the code not currently
>>> removed by the C preprocessor) needs to be completely reviewed and
>>> potentially rewritten. Also, I think the fuzziness logic (with all
>>> bugs fixed in that code) should stay just in the interests of
>>> providing some tolerance for numerical rounding errors.  For example,
>>> even the article <https://en.wikipedia.org/wiki/Point_in_polygon>
>>> talks of providing some numerical tolerance.  Note also, such
>>> tolerance is certainly required for the integer case since minute
>>> rounding errors in the floating point calculations that decide, for
>>> example, whether a point is inside or outside a polygon can shift
>>> integer results around by +/- 1.
>>>
>>> I have a topic branch where I have already taken some substantial
>>> steps along the above ideas (including at least one bug fix in our
>>> current fuzzy logic in notcrossed). I temporarily halted work on that
>>> topic some time ago, but assuming you can provide a test example that
>>> triggers fill bugs regardless of compiler or optimization level, I
>>> plan to take up that topic again where the first order of business
>>> will be to compare (using imagemagick image differences) updated fill
>>> algorithm results versus 5.11.1 results for all our standard examples
>>> that use fill in some way.  (That test should turn up any unusual fill
>>> artifacts in our examples that are generated by bugs in the original
>>> or revised fill algorithm, and once that test is implemented it should
>>> be done for any fill change from now on.) In addition, of course, I
>>> will look carefully at your example to make sure the revised fill
>>> algorithm produces the correct result for it.
>>>
>>> Assuming you are able to provide the requested example which triggers
>>> the fill bug regardless of rounding issues, and the above
>>> plan meets with your approval, I would plan to start working on this
>>> topic again just after the current release is out the door.
>>>
>>> Note also there are still a number of relatively small issues I would
>>> like to address for this release, but because of the break I mentioned
>>> above, I made little progress on those this summer so that release
>>> deadline is still indefinite and at least a month or two away.
>>>
> I agree that this is tricky, but feel this is something we can deal
> with without being too troublesome. Algorithms and code already exist
> to do this consistently - we're not the first to have to deal with it.
> In fact here is a 7 line C implementation that deals with the ray
> hitting a vertex correctly, but doesn't give any warning about if the
> point is close to or on a segment.
>
> I still don't understand why we need two whole plplot units of
> fuzziness. I understand that we round and that can give us up to two
> pixels of error. But surely we just accept that and work with the
> rounded polygons as if they were exact - in fact they are exact
> because they use integers.
>
> for example we wish to plot two rectangles which end up with internal
> coordinates of the opposite corners of (200,400.2),(600,600.4) and
> (200,600.4),(600,800.1). We round these to give (200,400),(600,600)
> and (200,600),(600,800). Now there is absolutely no count that the
> point (350,600.2) is in the second rectangle. Of course if we were
> using the original coordinates this point would have been in the first
> rectangle. But we are not plotting the original coordinates, we are
> plotting the rounded coordinates and that is what matters - the
> coordinates we are plotting.

We shouldn't care about 1-pixel rounding shifts in results.  But we do
need to care about logic screwups caused by such shifts.  Of course,
you are also demonstrating the current fuzzy logic sucks, i.e., the
cure is currently worse than the disease.  But let's fix that fuzzy
logic rather than throwing it out completely.

>
> I would clearly like to get this fixed properly, but in the meantime
> would anyone object if I apply a sticking plaster fix for this as it
> is something I have hit about half a dozen times over the last six
> months - I presume this is because I've been plotting some really high
> resolution data. So I do really need to avoid the issue for now.

There is a substantial testing requirement for fill changes. The
reason for that is we have had years of mostly good user experience
with the present fill algorithm so I feel it is important that anybody
that changes the fill algorithm in any further way needs to
demonstrate with substantial testing that their change does not
introduce fill regressions.

I have alluded previously to automated fill regression testing (for
all our standard examples that directly or indirectly use fill and all
our file devices).  The core of the idea is to compare old and updated
plot file results using imagemagick image differences.  Do you agree
this general approach (supplemented by actually looking at the "fill"
subset of our examples for each of our interactive devices) is the way
forward to insure that our further fill changes do not introduce more
issues than they fix?

Assuming you like this idea, please implement it if you are in a hurry
or else wait for me to implement it post-release.  Then once our fill
regression testing scheme is in place, you should test any proposed
fill change with that scheme before you merge that fill change to the
master branch.

Of course, while waiting for one of us to implement such a fill
testing scheme, there is still the problem about what to do for the
fill problems that have recently been bugging you?  I suggest you
should simply solve those issues locally in any convenient way that
you find that works for your particular needs, and circulate that
patch on this list to be referred to when we finally start working on
the definitive fix.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state
implementation for stellar interiors (freeeos.sf.net); the Time
Ephemerides project (timeephem.sf.net); PLplot scientific plotting
software package (plplot.sf.net); the libLASi project
(unifont.org/lasi); the Loads of Linux Links project (loll.sf.net);
and the Linux Brochure Project (lbproject.sf.net).
__________________________

Linux-powered Science
__________________________

Thread: Re: [Plplot-devel] Bug in notcrossed() function of plfill.c (Page 2)

Cross-platform, scientific graphics plotting library

plplot-devel