[OpenJDK 2D-Dev] RFC: Fix for 7036754
Denis Lila
dlila at redhat.com
Tue Apr 19 18:11:49 UTC 2011
Hi Jim.
> As for this webrev, I'm going to have to wait until tomorrow to slog
> through the new math (I'm kind of foggy-minded today), but I would
> like
> to point out that the Java Coding style guidelines are to put a space
> between the cast and the expression - you might as well fix those
> missing spaces while you are playing with all those lines of code.
Sure.
> My main worry is if the solution can be fooled by reversing the curve
> so
> that the "problematic miter" is on one side or the other. If side A
> becomes degenerate then a first glance looks like you munge it so that
> both are straight lines, but it would be nice to have the other side
> correctly mitered even though we draw a short straw with the first
> side
> that was intersected...
I've addressed this in the webrev.
Basically, if the left path's computeIntersection fails, try
the same with the right path. If that fails too, then it's a
line.
This doesn't cost anything, because those if statements' bodies will
almost never execute.
> Oh, and you changed the length of the method name, but didn't change
> the
> indentation of some of the continuation lines.
>
> (Picky, picky, picky, ;=)
I fixed this too :-)
Jim, what do you think about completely removing this code:
final boolean p1eqp2 = within(x1,y1,x2,y2, 6 * ulp(y2));
final boolean p2eqp3 = within(x2,y2,x3,y3, 6 * ulp(y3));
if (p1eqp2 || p2eqp3) {
getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
return 4;
}
// if p2-p1 and p3-p2 are parallel, that must mean this curve is a line
float dotsq = (dx1 * dx3 + dy1 * dy3);
dotsq = dotsq * dotsq;
float l1sq = dx1 * dx1 + dy1 * dy1, l3sq = dx3 * dx3 + dy3 * dy3;
if (Helpers.within(dotsq, l1sq * l3sq, 4 * ulp(dotsq))) {
getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
return 4;
}
This sort of duplicates logic in the caller. I put it in anyway,
because I was afraid that the subdivision would introduce degenerate
curves, despite the checks in somethingTo passing. However, looking
at it again, I don't really think it's necessary. The parallel check
in particular was introduced because I was afraid that if a curve's
control vectors are close to parallel, computeIntersection would
return crazy, inaccurate values. But I tested that and it doesn't
seem to happen. The isNotFinite checks should be enough to deal
with quads that are actually lines.
If we just replaced that whole chunk above with
if ((x1 == x2 && y1 == y2) || (x2 == x3 && y2 == y3)) {
getLineOffsets(x1, y1, x3, y3, leftOff, rightOff);
return 4;
}
I think we could squeeze a fair bit of performance out of this.
I've updated the webrev.
Regards,
Denis.
----- Original Message -----
> Well, I'd like to see what you came up with if you want to just send
> it
> to me in private email.
>
> As for this webrev, I'm going to have to wait until tomorrow to slog
> through the new math (I'm kind of foggy-minded today), but I would
> like
> to point out that the Java Coding style guidelines are to put a space
> between the cast and the expression - you might as well fix those
> missing spaces while you are playing with all those lines of code.
>
>
> ...jim
>
> On 4/18/11 12:05 PM, Denis Lila wrote:
> > Hi Jim.
> >
> >> Hm. It turns out that if the parallel versions of the control
> >> lines are extended to infinity, their intersections form a
> >> rhombus whose centre is the second control point (i.e. of the
> >> centre curve). The control points we're trying to compute are
> >> two vertices of the rhombus that lie on the same diagonal. An
> >> equation for this diagonal would be c2 + t*( (c3-c2)/||c3-c2|| +
> >> (c1-c2)/||c1-c2|| )
> >> where c1, c2, c3 are the control points of the centre curve.
> >>
> >> To compute the points we want we would need to know their distance
> >> from c2.
> >
> > This is pretty easy to do, but it involves a few too many sqrt
> > calls.
> >
> >> Well, thanks for getting me thinking about this. This line of
> >> thinking seems promising.
> >> I'll try to code it up.
> >
> > This wasn't fruitless, however. It made me realize that
> > if we have the second control point for the left path
> > we can compute the second control point for the right
> > path with just two subtractions and 2 multiplications:
> >
> > http://icedtea.classpath.org/~dlila/webrevs/7036754/webrev/
> >
> > Is that good to go?
> >
> > PS: I made some other changes: one style fixup (a "{" was not
> > following our convention), removing "Math." from certain
> > calls using "include static", and fixing comments that didn't
> > make sense.
> >
> > Thank you,
> > Denis.
> >
> > ----- Original Message -----
> >>> For parallel quads, is there a relationship between any of the
> >>> following
> >>> points that could be exploited?
> >>>
> >>> original control point
> >>> left_curve and right_curve control points
> >>> center point on the original (and rt and lt) curve
> >>> perpendicular of center point on the curve(s)
> >>> center of line between endpoints
> >>
> >
> >>
> >> Regards,
> >> Denis.
> >>
> >> ----- Original Message -----
> >>> Here's an odd thought.
> >>>
> >>
> >>>
> >>> I'm just basing this on a "gut feel" of how quad curves behave,
> >>> not
> >>> on
> >>> any mathematical intuition, though. It also makes sense given that
> >>> you
> >>> are computing the intersection of parallel versions of the lines.
> >>> I'm
> >>> guessing that the intersections of all parallel lines equidistant
> >>> from
> >>> the original pair form a line themselves and that line might be
> >>> related
> >>> to other points we have access to.
> >>>
> >>> But, it might be some food for thought on how to make parallel
> >>> quads
> >>> go
> >>> a lot faster...
> >>>
> >>> ...jim
> >>>
> >>> On 4/15/2011 2:20 PM, Jim Graham wrote:
> >>>> Hi Denis,
> >>>>
> >>>> The strategy I took to work around this was to simply check for a
> >>>> zero
> >>>> denominator in the Miter method and return the average of the
> >>>> endpoints
> >>>> instead of the intersection points. That makes a straight line
> >>>> via
> >>>> a
> >>>> quad that has colinear points, but it greatly simplifies the
> >>>> impact
> >>>> of
> >>>> the fix.
> >>>>
> >>>> To be safe (performance-wise), I made a separate copy of the
> >>>> method
> >>>> called "safecomputeMiter()" and put the test only in that copy
> >>>> (which is
> >>>> only used from the quad function) until I have time to do some
> >>>> more
> >>>> exhaustive performance tests. To be honest, though, I don't
> >>>> imagine
> >>>> that
> >>>> single test could affect performance (given that "den" is already
> >>>> computed as the difference of two values, the subtract operation
> >>>> already
> >>>> sets condition codes so it is simply a matter of how fast the
> >>>> processor
> >>>> can take the branch or not, and this is likely a case where
> >>>> branch
> >>>> prediction would pay off a lot...)
> >>>>
> >>>> ...jim
> >>>>
> >>>> On 4/15/2011 10:38 AM, Denis Lila wrote:
> >>>>> Hi.
> >>>>>
> >>>>> Jim Graham pointed out this bug to me.
> >>>>>
> >>>>> A fix is here:
> >>>>> http://icedtea.classpath.org/~dlila/webrevs/7036754/webrev/
> >>>>>
> >>>>> It just checks for inf/nan and just emits a line joining
> >>>>> the endpoints in that case.
> >>>>>
> >>>>> The stroking is no longer symmetric with respect to right
> >>>>> and left polynomial degrees. This is a bit more general.
> >>>>>
> >>>>> I have a question:
> >>>>>
> >>>>> The "curve is a straight line" check I use is this:
> >>>>> 737 float dotsq = (dx1 * dx3 + dy1 * dy3);
> >>>>> 738 dotsq = dotsq * dotsq;
> >>>>> 739 float l1sq = dx1 * dx1 + dy1 * dy1, l3sq = dx3 * dx3 + dy3 *
> >>>>> dy3;
> >>>>> 740 if (Helpers.within(dotsq, l1sq * l3sq, 4 * Math.ulp(dotsq)))
> >>>>> {
> >>>>>
> >>>>> However, this isn't making much sense mathematically
> >>>>> right now. I would like to avoid redoing the math
> >>>>> so if someone can quickly confirm/deny that it works
> >>>>> that would be nice.
> >>>>>
> >>>>> Thank you,
> >>>>> Denis.
More information about the 2d-dev
mailing list