[OpenJDK 2D-Dev] CubicCurve2D.solveCubic and containment/intersection bugs.

[Denis Lila]

Hi Jim.

> Also, I'm not mathematically familiar with what the case of "D close to
> zero" means.  Generally, in floating point math, when you do a test and
> change the approach based on the results of that test I would hope that
> the answers returned by both approaches would be similar for cases near
> the decision point of the test.  So, for example, if a 3 root case of
> 5,10,15 yielded a D that was "strongly negative" and a 3 root case of
> 5,9.99999,10.00001 yielded a D that was "just barely negative" and the 2
> root case of "5,10" yielded a D that was "just barely positive" then I
> would have no problem with the fact that we classify the 2 vs. 3 root
> case on the sign of D.  The thing I haven't figured out, though, is
> whether that is indicative of the case where the 2 vs. 3 root switchover
> hapens?

I think so. I mean, we can't use the 3 root computations if D is positive,
so we're almost always computing as many roots as possible. If D should be
slightly negative but because of inaccuracy problems it is computed to be
slightly positive then we'll compute 2 roots instead of 3. I don't think
this is a problem because the difference between computing 5,9.99999,10.00001
and computing 5,10 is very fuzzy. In cases where there are 2 roots that are
very close together the function will be flat around the roots and if we
call solveEqn(eqn, 3, x) for all x near the root/roots it will fluctuate a
lot, and if we're assuming that it's a good approximation to the ideal
cubic, we'd end up with dozens of roots (one for every sign change).

> And I think there is an argument to be made if it is being used to make
> the "answers that came from transcendental trig functions" more accurate
> since those functions aren't necessarily as accurate as the math used
> elsewhere in the function.

This was my main motivation for the refinement. The accuracy is much
better than without the refinement. I don't think it's a good idea
to use solveCubic for intersections.

> There is another bug out there where I've indicated the need to beef
> up our documentation of the intersection methods (see 7003516).

I like the ideas in the evaluation, especially about the links to the
"Definition of insideness" in the Shape docs. What confused me
in the documentation, even after I had read the "Definition of
insideness", was that the wording is not very consistent. For example
contains(Point) says "...inside the boundary of the Shape." The 
"Definition of insideness" says "lie *inside a Shape* if and only if"
So we have "inside a Shape" and "inside the boundary of the Shape".
This creates the impression that they are referring to two different
things. That's why I was confused about whether "inside the boundary"
included the boundary or not.

What made it even more confusing was just the usage of the word "boundary"
itself, especially when combined with the usage of "interior" in the
intersects() docs. I'm used to "boundary" and "interior" being defined
like so: http://en.wikipedia.org/wiki/Boundary_%28topology%29, 
http://en.wikipedia.org/wiki/Interior_%28topology%29
but in Shape we use a different definition which classifies every
point in the plane as either inside or outside the shape, so in
some sense, the boundary doesn't even exist in our case. So I propose
that we remove every use of the word "boundary", and replace every
use of "interior" with "inside"+ a link to the "Definition of insideness"
in awt.Shape. That will make it perfectly clear what we mean by "inside"
and people who have studied a bit of topology won't be confused ;-)

What do you think?

Regards,
Denis.

----- Original Message -----
> Hi Denis,
> 

> 
> The Shape class comments give some helpful information that describes
> our boundary conditions. We basically use half open intervals where
> the
> upper/left boundaries are contained in the shape and the lower/right
> boundaries are not. The description is describing more specifically
> "which pixels are filled", but it is related to the philosophy behind
> the intersection methods as well (and we need to call that out). So,
> Shape.contains(point) follows those guidelines.
> 
> For the rect methods, I think we should also clarify that:
>
> intersects(rect)
>
> means there is some point that is contained in both the shape and also
> the rect (as per the Shape class comment), and:
>
> contains(rect)
>
> means that for any point that is contained in the rect, it is also
> contained in the Shape - again per the Shape class comment.
> 
> I agree with your comment about 4724556 - I just closed it as a dup of
> 4645692.
> 
> Also, note that Path2D now uses a very fast general intersection
> facility in the sun.awt.geom package that is based on the above rules.
> The containment methods of all of the various shapes could be switched
> over to this mechanism except that the may have faster ways of finding
> the answer in some cases. Certainly Rectangle2D can figure out the
> answer faster on its own, but I'm not sure if CubicCurve2D or
> QuadCurve2D are any faster than simply utilizing those methods,
> though...
> 
> ...jim
> 
> On 1/11/2011 1:06 PM, Denis Lila wrote:
> > Hi Jim.
> >
> > I'm starting a new thread about this, since "X11 uniform scaled
> > wide lines and dashed lines; STROKE_CONTROL in Pisces" has
> > absolutely nothing to do with what we were discussing :-)
> >
> >> You might want to submit it as a separate push and get credit for
> >> fixing
> >> 4645692 (solveCubic doesn't return all answers), and maybe even the
> >> following failures in the containment methods (which could be
> >> closed as
> >> dups if this fixes the problems) as well:
> >>
> >> 4724552
> >> 4493128
> >> 4074742
> >> 4724556
> >> (etc. Those were just the bugs I found on the first 2 pages of a
> >> bug
> >> database search)
> >
> > I've been thinking about these bugs, but I'm confused about what
> > the correct behaviour is supposed to be in many of these cases:
> > contain(double, double, double, double) says "Tests if the interior
> > of
> > the Shape entirely contains the specified rectangular area". I have
> > two questions on this. Does "interior of the Shape" mean the set of
> > points
> > that are inside the shape as per the "Definition of insideness" in
> > awt.Shape,
> > or does it mean everything inside *minus* the boundary? Also, I have
> > the
> > same question about the rectangle parameter: does "entirely
> > contain..."
> > include the points on the boundary of the rectangle or not?
> >
> > I'm also confused about contains(Point2D). What should be returned
> > if the
> > Point2D is on the boundary? Would this be decided using the
> > "Definition of
> > insideness"?
> >
> > I have similar questions about the intersect methods, but I'm
> > guessing those
> > can be extrapolated from any answers I might get about the contains
> > methods.
> >
> > Also, contains(double, double) is working properly in the given
> > reproducer
> > for 4724556. I'm guessing this is because "contains" used to use
> > solveCubic
> > but it's not anymore so it's behaving correctly (at least in this
> > case). This
> > bug report is a bit ambiguous since it's also referring to
> > solveCubic not
> > finding a root, so I think it should either be closed as fixed or
> > notabug
> > or it should be made a duplicate of 4645692.
> >
> > Thank you,
> > Denis.