Hi Denis,
One request on your code - please don't use the variable "lowercase
L".
On my screen with Courier font I cannot distinguish between the
number
1 and the lowercase L character and so I cannot verify if your code is
correct.
Also, by "inner loop" I meant the single loop. I use the term to mean
the "loop that does all the work at the innermost level" without
regard
to whether the case contains only 1 loop and is therefore a degenerate
application of the term.
My comment about the "major axis" stuff was an optimization that is no
longer needed. I though I saw calls to hypot() in the inner loop, but
I
just noticed that those were in deleted code and the new code has no
such calls, so you can ignore it. If it makes the comment clearer,
"major axis" is either the X or Y axis depending on whether the line
is
more horizontal or vertical, but you can ignore it now.
I will note that the 2 arrays you compute are simply scaled versions
of
the dash array and so we could eliminate the extra allocations by
simply
computing the values inside the loop at the cost of a multiply per
dash
segment to offset the cost of an allocation per incoming line segment.
Also, you would no longer need to compute the "dashesToCompute" value
and the setup code would be much, much simpler (basically you just
need
to compute the untransformed length and the cx and cy values and then
jump into the loop).
I'm leaning towards the multiplies in the loop to greatly simplify the
code...
(One last comment - have you checked what happens with the code in the
presence of a degenerate transform? A non-invertible transform may
run
the risk of an infinite loop if you assume that you can reverse
compute
the line length and end up with a finite value...)
...jim
Denis Lila 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.gra...@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.
