[OpenJDK 2D-Dev] Fix for uniformly scaled dashed lines.

[Denis Lila]

Oops, I forgot the attachment.
I'm sorry.

----- "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
> segment
> 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
> while(true)
> loop) most of the time involves just 2 additions.
> I am not sure how this can be made any simpler.
> 
> Thank you,
> Denis.
> 
> ----- "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
> scale
> > 
> > factor that depends solely on the angle of the line.  Thus, for 
> > determining dashing you can simply compute this scale factor once
> for
> > 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
> got
> > 
> > the math right.
> > 
> > One more optimization is that once you know the angle of the line
> then
> > 
> > you have a factor for how the length of a segment of that line
> relates
> > 
> > to its dx and dy.  Note that for horizontal and vertical lines one
> of
> > 
> > those factors may be Infinity, but every line will have a non-zero
> and
> > 
> > non-infinity factor for one of those two dimensions.
> > 
> > This means that you can calculate the dashing by simply looping
> along
> > 
> > the major axis of the line and comparing either the dx, or the dy to
> 
> > scaled "lengths" that represent the lengths of the transformed
> dashes
> > 
> > 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
> dy=>dx
> > 
> > scale factor might be zero, but it would never be infinite if you
> are
> > 
> > calculating along the major axis of the transformed line, but I
> didn't
> > 
> > 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
> changed.
> > > 
> > > It is only used in one place (in lineTo) to simplify the
> computation
> > of
> > > the length of the line before an affine transformation A was
> applied
> > 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
> to
> > > 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.
> Another
> > 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
> expense
> > of making the 
> > > code more complex, harder to read, introducing more opportunity
> for
> > bugs, and adding
> > > hundreds of operations of overhead (since PiscesMath.sqrt would
> have
> > 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
> they
> > 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
> dividing
> > 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...
Name: dasherPerformanceAndUnifScalingv2.patch
Type: text/x-patch
Size: 5410 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/2d-dev/attachments/20100621/a73952ae/dasherPerformanceAndUnifScalingv2.patch>