On 20091128 16:100800 Alan W. Irwin wrote:
> On 20091127 11:190800 Alan W. Irwin wrote:
>
>> If you run
>>
>> examples/c/x16c dev xwin exclude nx 20 ny 20
>>
>> a smooth donut is excluded from the 5th page (as expected, since years ago
>> Rafael modified the defined algorithm for plshade(s) to give smooth edges
>> using some sort of iterative technique). However, if you use
>> coarser resolutions, e.g.,
>>
>> examples/c/x16c dev xwin exclude nx 10 ny 10
>>
>> Rafael's iteration sometimes still gives reasonably good results (some edges
>> of the donut are smooth) at coarser resolutions but also sometimes gives
>> horrible results (the edges of the donut are extremely misplaced or missing
>> altogether). I interpret these results as a numerical robustness issue (a
>> starting solution that is so bad that it cannot converge, or a convergence
>> criterion that stops the iteration before it has converged).
>
> I have looked into this further. Rafael's iteration technique (routine
> bisect in plshade.c) for finding the edge of defined regions is the
> bisection method. According to Numerical Recipes, Chapter 9.1, bracketing
> issues can be important for the bisection method (especially for our
> gradient use case where multiple solutions for finding the edge of
> complicated polygons can exist).
I have now (revision 10681) cleaned up and commented exfill and made the
logic more robust, but I have not yet made any fundamental changes to the
exfill algorithm. Currently that algorithm simply drops all undefined
vertices from the polygon and defines new vertex points on each side of the
undefined vertices (or vertex) with a bisection method right at the edges of
the undefined regions that intersect the polygon.
There are two fundamental bracketing issues with the current algorithm.
(1) For two consecutive vertices of the same type (say undefined), it is
assumed the entire region between the vertices is also of the same type.
This is the principal issue with the software fallback gradients where the
polygons tend to be long skinny rectangles for a gradient defined with 2x2
points. Assuming you have a defined region consisting of some shape in the
middle of the 2x2 area, all points of those 2x2 polygons are in undefined
regions so it is assumed the whole polygon is undefined and you get no
gradient result at all! To deal with this issue, you have to have some
criterion (probably based on distance between the vertices) to decide to
search between vertices of the same type for two transitions (one to
opposite type from the two vertices and one back again). This is analogous
to attempting to bracket two roots of a function between two independent
variables where the function is the same sign at the two independent
variables. You may be wasting your time because there are no roots there
or there may be two (or more) roots there; you just never know.
(2) Deal with the situation where there are two or more regions of the
polygon which are undefined. Right now the result is two regions are simply
spanned (as you can tell from the above description of the algorithm where
undefined regions are simply dropped from the polygon). That may be the best
approximation if the two undefined regions are unrelated, but if the two
undefined regions for the polygon are the two entrances for a "river" of
undefined area flowing through the polygon, then the best approximation
would be to split the polygon into the two defined pieces. This turns out
to be the issue when attempting to use the exclude option for example 16
for small nx, ny values. Some rectangles just completely span the range of
the excluded donut so become completely defined due to issue (1). But even
if issue (1) were fixed, then you still have to deal with the fact that
there are correlated undefined regions on opposite sides of the rectangle
corresponding to part of the donut cutting through the rectangle. Of
course, it rapidly gets even more complicated (with more chances of making a
completely incorrect interpretation) the more undefined regions of the
polygon that you have. Probably, the only way you can deal with this issue
directly is to split the polygon into tiny pieces so there is no ambiguity
about how the undefined regions on the polygon are connected internal to the
polygon.
Note, both issues (1) and (2) can be solved externally by using
sufficient resolution to thoroughly figure out where the defined regions are
located with no ambiguity. So unless somebody here can come up with good
internal algorithms to deal with issues (1) and (2), I think I will give up
on any internal solutions for these issues and recommend only an external
solution; that is, when using the defined capability of plshade(s), always
be sure to use a sufficient number of z points so there is no ambiguity
about finding the defined region.
As far as I know that recommendation affects just two use cases. I believe
the defined capability of plshade(s) is only accessible from C and not from
any of our other languages. So direct use of the capability must be fairly
rare, and such users probably have already figured out they need to use lots
of z points. That then just leaves the the second use case which is the
software fallback for gradient. For that case, I intend to take my own
recommendation and stick to using lots of z points (currently 20x20) and
abandon my dream of using just 2x2. After all, our best supported devices
have native support for plgradient so they don't use this code path at all.
In any case, I plan to give a warning whenever the sofware fallback for
plgradient must be used for drivers that don't have a native gradient, and
for users that need this capability a lot, that warning should nudge them
into using a device that natively supports plgradient.
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 equationofstate implementation
for stellar interiors (freeeos.sf.net); PLplot scientific plotting software
package (plplot.org); the libLASi project (unifont.org/lasi); the Loads of
Linux Links project (loll.sf.net); and the Linux Brochure Project
(lbproject.sf.net).
__________________________
Linuxpowered Science
__________________________
