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

[Jim Graham]

Hi Denis,

Saving the arrays depends on both the original value of the array and 
also the transform being used.  Can a given Dasher be used by more than 
one rendering thread at a time?  (I forget if this is possible.)  Even 
if we currently cannot use them from more than one thread, I prefer 
re-entrant code to non-re-entrant code in general unless there is a big 
performance savings, and then the reuse of data should really be 
carefully planned and accounted for in the interfaces.

Also, scale and shear are both potentially non-invertible.  Scale(0,0) 
is non-invertible and I believe that something like Shear(1,1) is also 
non-invertible.  Also some combinations including rotate can become 
non-invertible even though the rest of the chain of transforms looks 
benign.  Just because the transform is affine does not mean it is 
invertible (witness the fact that we have to throw non-invertible 
exceptions from some methods)...

			...jim

Denis Lila wrote:
> Hello Jim.
> 
> Sorry about the l. It was already there, and I wanted to change as
> little as possible.
> 
> As for whether to compute the transformed dashes inside the while(true)
> or not... the main point of this patch was to fix a bug where zooming 
> transforms weren't handled properly. The efficiency improvements were
> just something I threw in because a bunch of stuff was being computed
> too many times, so I can go either way. I should note that the allocations
> can be easily removed by just turning the arrays into fields, and allocating
> them at setParameters, since for any one Dasher object their length is 
> constant. So the choice is between clearer and slower code and mine. I
> have 2 patches ready, one for each way of doing it. Just tell me which
> to send.
> 
> As for degenerate inputs: I did think about non-invertible transforms, but
> since they weren't being handled in the original Dasher and Stroker, and
> since the API provides no way of using non-invertible transforms (the only
> possible ones are shear, rotate, translate, and scale, all of which are
> invertible), I didn't think it was necessary to check for them.
> How do you think they should be handled? I think we should just throw
> an InvalidInputException if the determinant is 0.
> One more thing: it turns out that by computing dashes outside of the while(true)
> I introduced the possibility for divide by zero errors. I fixed this.
> 
> Thanks,
> Denis.
> ----- "Jim Graham" <james.graham at oracle.com> wrote:
> 
>> 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.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.
>>>>>