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

Denis Lila dlila at redhat.com
Mon Jun 21 15:07:12 UTC 2010

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,

----- "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.
> >

More information about the 2d-dev mailing list