Oops, I forgot the attachment.
I'm sorry.
----- "Denis Lila" <[email protected]> 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" <[email protected]> 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.
> > >
exporting patch:
# HG changeset patch
# User Denis Lila <[email protected]>
# Date 1277131744 14400
# Node ID 61f354c51110bf62b1e9b4da1cc0089000e10897
# Parent 83c7768292d783709a1cdb7ddd3d68df65e23148
Patch that fixes the drawing of uniformly scaled dashed lines, and improves the performace of dashing.
diff --git a/src/share/classes/sun/java2d/pisces/Dasher.java b/src/share/classes/sun/java2d/pisces/Dasher.java
--- a/src/share/classes/sun/java2d/pisces/Dasher.java
+++ b/src/share/classes/sun/java2d/pisces/Dasher.java
@@ -56,7 +56,6 @@
Transform4 transform;
- boolean symmetric;
long ldet;
boolean firstDashOn;
@@ -143,7 +142,6 @@
this.m10 = transform.m10;
this.m11 = transform.m11;
this.ldet = ((long)m00*m11 - (long)m01*m10) >> 16;
- this.symmetric = (m00 == m11 && m10 == -m01);
}
public void moveTo(int x0, int y0) {
@@ -181,51 +179,77 @@
}
public void lineTo(int x1, int y1) {
+ int lx = x1 - x0;
+ int ly = y1 - y0;
+
+ // Compute segment length in the untransformed
+ // coordinate system
+ // IMPL NOTE - use fixed point
+
+ int l;
+ long la = ((long)ly*m00 - (long)lx*m10)/ldet;
+ long lb = ((long)ly*m01 - (long)lx*m11)/ldet;
+ l = (int)PiscesMath.hypot(la, lb);
+
+ // Compute the number of transformed dash lengths that will
+ // be needed in the while(true) loop. We carry out the first
+ // iteration outside the loop so we can take into account phase.
+ int lenAcc = dash[idx] - phase;
+ int dashesToCompute = (lenAcc > l) ? 0 : 1;
+ for (int i = 1; i < dash.length; i++) {
+ lenAcc += dash[(i + idx) % dash.length];
+ if (lenAcc > l) break;
+ dashesToCompute += 1;
+ }
+
+ long t;
+ int[] dxsplit = new int[dash.length];
+ int[] dysplit = new int[dash.length];
+
+ // In this comment, let (x,y), di, dxi, dyi, t be, respectively, the
+ // untransformed line, dash[i], the x and y component of dash i
+ // for line (x,y), and the angle of line (x,y). Let (x', y'), di',
+ // dxi', dyi', t' be the transformed counterparts of the above.
+ // We are trying to find the dxi' and the dyi'.
+ // dxi' = cos(t')*di' = (x' / <x',y'>) * di' and we know that the
+ // ratio of untransformed and transformed lengths depends only on
+ // the angle of the line, so di'/di = <x',y'>/<x,y> which means:
+ // di' = (di * <x',y'>)/<x,y>
+ // So: dxi' = ((di * <x',y'>)/<x,y>) * (x' / <x',y'>) which simplifies
+ // to dxi' = (di * x') / <x, y>. dyi' is similar.
+ // x' / <x, y> is constant, so we compute it outside of the loop.
+ //
+ // Note: in the code: dxsplit[i] = dxi'; dysplit[i] = dyi'; dash[i] = di
+ // lx = x', ly = y', and <x,y> = l.
+ long cx = ((long) lx << 16) / l;
+ long cy = ((long) ly << 16) / l;
+ for (int i = 0; i < dashesToCompute; i++) {
+ int j = (i + idx) % dash.length;
+ dxsplit[j] = (int) ((dash[j] * cx) >> 16);
+ dysplit[j] = (int) ((dash[j] * cy) >> 16);
+ }
+
while (true) {
- int d = dash[idx] - phase;
- int lx = x1 - x0;
- int ly = y1 - y0;
-
- // Compute segment length in the untransformed
- // coordinate system
- // IMPL NOTE - use fixed point
-
- int l;
- if (symmetric) {
- l = (int)((PiscesMath.hypot(lx, ly)*65536L)/ldet);
- } else{
- long la = ((long)ly*m00 - (long)lx*m10)/ldet;
- long lb = ((long)ly*m01 - (long)lx*m11)/ldet;
- l = (int)PiscesMath.hypot(la, lb);
- }
-
- if (l < d) {
+ if (l < dash[idx] - phase) {
goTo(x1, y1);
// Advance phase within current dash segment
phase += l;
return;
}
- long t;
int xsplit, ysplit;
-// // For zero length dashses, SE appears to move 1/8 unit
-// // in device space
-// if (d == 0) {
-// double dlx = lx/65536.0;
-// double dly = ly/65536.0;
-// len = PiscesMath.hypot(dlx, dly);
-// double dt = 1.0/(8*len);
-// double dxsplit = (x0/65536.0) + dt*dlx;
-// double dysplit = (y0/65536.0) + dt*dly;
-// xsplit = (int)(dxsplit*65536.0);
-// ysplit = (int)(dysplit*65536.0);
-// } else {
- t = ((long)d << 16)/l;
- xsplit = x0 + (int)(t*(x1 - x0) >> 16);
- ysplit = y0 + (int)(t*(y1 - y0) >> 16);
-// }
+ if (phase == 0) {
+ xsplit = x0 + dxsplit[idx];
+ ysplit = y0 + dysplit[idx];
+ } else {
+ long p = (((long)dash[idx] - phase)<<16) / dash[idx];
+ xsplit = x0 + (int)((p * dxsplit[idx]) >> 16);
+ ysplit = y0 + (int)((p * dysplit[idx]) >> 16);
+ }
+
goTo(xsplit, ysplit);
+ l -= (dash[idx] - phase);
// Advance to next dash segment
idx = (idx + 1) % dash.length;
dashOn = !dashOn;
