[OpenJDK 2D-Dev] Fix for uniformly scaled dashed lines.
dlila at redhat.com
Mon Jun 21 16:06:49 UTC 2010
Oops, I forgot the attachment.
----- "Denis Lila" <dlila at redhat.com> wrote:
> Hello Jim.
> Thank you for your reply. It seems my code did not fully take into
> account your second point after all.
> The dx's of the transformed dashes are di*newx/<x,y> (where
> di is the untransformed dash length, newx is the transformed x
> coordinate, and <x,y> is the untransformed line length). Obviously,
> newx/<x,y> is constant for all dash segments, so it can be computed
> outside of the loop, but I was computing t=di/<x,y> inside the loop,
> and then t*newx also inside the loop.
> I have fixed this and I included an improved version of the patch.
> However, I do not understand the second part of your e-mail
> ("One more optimization ..."). I am not sure what you mean by
> "major axis", how one would loop along it, and what the "inner loop"
> is. There are no nested loops in this method.
> Also, the computation of the dxi and dyi of the transformed dash
> dash[i] involves just 1 multiplication and 1 bit shift (along with an
> overhead of 2 divisions and 2 bit shifts).
> The computation of the actual endpoint of the dashes (done in the
> loop) most of the time involves just 2 additions.
> I am not sure how this can be made any simpler.
> Thank you,
> ----- "Jim Graham" <james.graham at oracle.com> wrote:
> > Hi Denis,
> > Here are my thoughts on it:
> > - Lines are affinely transformed into lines. The slope may be
> > different
> > before and after the transform, but both have a single slope.
> > - The ratio of a line length to its transformed line length is a
> > factor that depends solely on the angle of the line. Thus, for
> > determining dashing you can simply compute this scale factor once
> > a
> > given line and then that single scale factor can be applied to every
> > dash segment.
> > It appears that your setup code takes these factors into account,
> > though
> > I haven't done a grueling line by line analysis as to whether you
> > the math right.
> > One more optimization is that once you know the angle of the line
> > you have a factor for how the length of a segment of that line
> > to its dx and dy. Note that for horizontal and vertical lines one
> > those factors may be Infinity, but every line will have a non-zero
> > non-infinity factor for one of those two dimensions.
> > This means that you can calculate the dashing by simply looping
> > the major axis of the line and comparing either the dx, or the dy to
> > scaled "lengths" that represent the lengths of the transformed
> > projected onto the major axis.
> > Finally, the other dx,dy can be computed from the dx,dy of the major
> > axis with another scale. I am pretty sure that this dx=>dy or
> > scale factor might be zero, but it would never be infinite if you
> > calculating along the major axis of the transformed line, but I
> > write out a proof for it.
> > Taking both of these concepts into account - can that make the inner
> > loop even simpler?
> > ...jim
> > Denis Lila wrote:
> > > Hello.
> > >
> > > I think I have a fix for this bug:
> > http://icedtea.classpath.org/bugzilla/show_bug.cgi?id=504
> > >
> > > The problem is caused by the "symmetric" variable in
> > pisces/Dasher.java.
> > > symmetric is set to (m00 == m11 && m10 == -m01), and never
> > >
> > > It is only used in one place (in lineTo) to simplify the
> > of
> > > the length of the line before an affine transformation A was
> > to it.
> > >
> > > This is why it causes a problem:
> > > If A = [[a00, a01], [a10, a11]] and (x,y) is a point obtained by
> > applying
> > > A to some other point (x',y'), then what we want is the length of
> > the vector
> > > (x',y'), which is ||Ainv*(x,y)||. Ainv = (1/det(A)) * [[a11,
> > -a01],[-a10, a00]],
> > > so, after some calculations, ||Ainv*(x,y)|| ends up being equal
> > > sqrt(x^2*(a11^2 + a10^2) + y^2*(a00^2 + a01^2) - x*y*(a11*a01 +
> > a00*a10)) * 1/|det(A)|.
> > > If symmetric==true, this simplifies to:
> > > sqrt((a11^2 + a01^2) * (x^2 + y^2)) * 1/|det(A)|, and
> > > |det(A)| = a11^2 + a01^2, so, the final answer is:
> > > sqrt((x^2 + y^2)) / sqrt(det(A)). Therefore the problem in
> > Dasher.java
> > > is that it divides by det(A), not sqrt(det(A)).
> > >
> > > My fix for this was to remove the "symmetric" special case.
> > possible fix
> > > would have been to introduce an instance "sqrtldet" and set it to
> > sqrt(det(A)),
> > > and divide by that instead of det(A). This didn't seem worth it,
> > because the only
> > > benefit we gain by having the "symmetric" variable is to save 3
> > multiplications
> > > and 1 division per iteration of the while(true) loop, at the
> > of making the
> > > code more complex, harder to read, introducing more opportunity
> > bugs, and adding
> > > hundreds of operations of overhead (since PiscesMath.sqrt would
> > to be called to
> > > initialize sqrtldet).
> > >
> > > To make up for this slight performance loss I have moved the code
> > that computes
> > > the transformed dash vectors outside of the while loop, since
> > are constant
> > > and they only need to be computed once for any one line.
> > > Moreover, computing the constant dash vectors inside the loop
> > causes
> > > them to not really be constant (since they're computed by
> > numbers that
> > > aren't constant). This can cause irregularities in dashes (see
> > comment 14 in
> > > http://icedtea.classpath.org/bugzilla/show_bug.cgi?id=197).
> > >
> > > I would very much appreciate any comments/suggestions.
> > >
> > > Thank you,
> > > Denis Lila.
> > >
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5410 bytes
Desc: not available
More information about the 2d-dev