[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openjdk-2d-dev
Subject:    [OpenJDK 2D-Dev] Fix for uniformly scaled dashed lines.
From:       james.graham () oracle ! com (Jim Graham)
Date:       2010-07-08 1:38:19
Message-ID: 4C352C0B.6040707 () oracle ! com
[Download RAW message or body]

This looks good, but don't assert that the transform is non-singular. 
Transforms can frequently be singular and that isn't an exception.

Actually, a singular transform simply means that the entire coordinate 
space has collapsed to a line or a point and so nothing need be 
rendered.  If there is a way to shortcut the rendering to a NOP that 
would be the right reaction to a singular transform...

			...jim

Denis Lila wrote:
> Hello Jim.
> 
> Here is a webrev for the patch: 
> http://icedtea.classpath.org/~dlila/webrevs/dasherFix/webrev/
> I have eliminated most of the setup code, like you suggested.
> 
> This is both more efficient, and far clearer than the original code
> (and especially my version of the patch. It is also correct in cases 
> where the transform is [[n,0],[0,n]]).
> 
> I still have my version of the patch (the one with "dashesToCompute"),
> and as I mentioned in another e-mail, the allocation of the array
> can be eliminated, since it can be turned into a field. So it should
> have better performance in pretty much all cases.
> If you would like me to send a webrev for that too, e-mail me.
> 
> Thank you,
> 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.
>>>>>

[prev in list] [next in list] [prev in thread] [next in thread]