Re: [OpenJDK 2D-Dev] Fix for uniformly scaled dashed lines.
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" 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/ (where
di is the untransformed dash length, newx is the transformed x
coordinate, and is the untransformed line length). Obviously,
newx/ is constant for all dash segments, so it can be computed
outside of the loop, but I was computing t=di/ 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" 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.
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
The first part means that if the scale is uniform in X and Y (AffineTransform has some logic to determine this property in its getType() method) then we can use X11 to do line widening by just giving it a scaled line width. Also, X11 is limited to integer line widths so we would only want to do this if the SPEED hint is specified (not QUALITY) or if the scaled line width was close to an integer. If we are going to use a software rasterizer to widen the line and then send over spans to render, it may be faster to just give X11 the original path and a scaled line width and ask it to widen the line. Even if it uses a software renderer the reduction in protocol traffic is a win, and their rasterizer is probably optimized for integer polygons and may likely be faster than our more general curve-handling code. But, I would rank this low on optimizations at this point... ...jim Clemens Eisserer wrote: Hi Denis, In sun.java2d.x11.X11Renderer, line 340, it says: // REMIND: X11 can handle uniform scaled wide lines // and dashed lines itself if we set the appropriate // XGC attributes (TBD). Also, it is a known issue that Pisces does not support the STROKE_CONTROL hint. I have been wanting to implement these two features, and I have a few questions: Has anything been decided on the first issue? Do we still want to implement it? If yes, can anyone give me some rough suggestions as to how I can get started? Its just my personal opinion, but I would recommend not implementing it. Xorg falls back to software anyway for anything more complex than solid rectangles and blits and those code-paths will only be triggered for non-antialised rendering with solid colors. Implementing it in Pisces would help every backend OpenJDK supports :) Just checked and I also ignore the STROKE_CONTROL stuff completly in the cairo based Jules rasterizer. Curious how that could be mapped to Cairo, do you know any more in-depth explanation how it works - or examples how it should look like? Thanks, Clemens
Re: [OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces
For AA this is exactly what we do (round to nearest pixel centers for strokes). Note that this is done prior to any line widening code is executed. For non-AA we normalize coordinates to, I believe the (0.25, 0.25) sub-pixel location. This is so that the transitions between widening of lines occurs evenly (particularly for horizontal and vertical wide lines). If you round to pixel edges then you have the following progression (note that the line width grows by half on either side of the original geometry so you have to consider the "line widths" where you encounter the pixel centers to your left and right (or above and below) which govern when that column (or row) of pixels first turns on): width 0.00 => 0.99 nothing drawn (except we kludge this) width 1.00 => 1.00 1 pixel wide (col to left turns on) width 1.01 => 2.99 2 pixels wide (col to right turns on) width 3.00 => 3.00 3 pixels wide (etc.) width 3.01 => 4.99 4 pixels wide Note that it is nearly impossible to get an odd-width line. You basically have to have exactly an integer width to get an odd-width line. This is because at the odd widths you reach the "half pixel" locations on both sides of the line at the same time. Due to the "half-open" insideness rules only one of the pixels will be chosen to be inside this path. Just below these sizes and you fail to hit either pixel center. Just at the integer size you reach both pixel centers at the same time. Just slightly larger than that width and now you've fully enclosed both pixel centers and the line width has to increase by nearly 2.0 until you reach the next pixel centers. (The kludge I talk about above is that we set a minimum pen width so that we never fail to draw a line even if the line width is set to 0.0, but the above table was a theoretical description of the absolute rules.) If we rounded them to pixel centers, then the transitions look like this: width 0.00 => 0.00 nothing drawn (modulo kludge) width 0.01 => 1.99 1 pixel wide (column you are in turns on) width 2.00 => 2.00 2 pixels wide (column to left turns on) width 2.01 => 3.99 3 pixels wide (column to right turns on) width 4.00 => 4.00 4 pixels wide (etc.) width 4.01 => 5.99 5 pixels wide We have a similar effect as above, but biased towards making even line widths harder. So, by locating lines at (0.25, 0.25) subpixel location we end up with a very even progression: width 0.00 => 0.50 nothing drawn (modulo kludge) width 0.51 => 1.50 1 pixel wide (column you are in turns on) width 1.51 => 2.50 2 pixel wide (column to left gets added) width 2.51 => 3.50 3 pixel wide (column to right gets added) width 3.51 => 4.50 4 pixel wide (etc.) This gives us nice even and gradual widening of the lines as we increase the line width by sub-pixel amounts and the line widths are fairly stable around integer widths. Also, note that we don't say "when stroking" as you might want to normalize both strokes and fills so that they continue to match. I believe that we normalize both strokes and fills for non-AA and we only normalize strokes for AA (and leave AA fills as "pure"). AA is less problematic with respect to creating gaps if your stroke and fill normalization are not consistent. The rounding equations are along the lines of: v = Math.floor(v + rval) + aval; For center of pixel you use (rval=0.0, aval=0.5) For 0.25,0.25 rounding use (rval=0.25, aval=0.25) For edge of pixel you use (rval=0.5, aval=0.0) Also, we came up with an interesting way of adjusting the control points of quads and cubics if we adjusted their end points, but I don't know if what we did was really the best idea. For quads we adjust the control point by the average of the adjustments that we applied to its 2 end points. For cubics, we move the first control point by the same amount as we moved the starting endpoint and the second control point by the amount we moved the final endpoint. The jury is out on whether that is the most aesthetic technique... ...jim Denis Lila wrote: Regarding VALUE_STROKE_NORMALIZE the API says: Stroke normalization control hint value -- geometry should be normalized to improve uniformity or spacing of lines and overall aesthetics. Note that different normalization algorithms may be more successful than others for given input paths. I can only think of one example where VALUE_STROKE_NORMALIZE makes a visible difference between the closed source implementation and OpenJDK: when drawing anti-aliased horizontal or vertical lines of width 1, Pisces draws a 2 pixel wide line with half intensity (because integer coordinates are between pixels). Sun's jdk with VALUE_SROKE_NORMALIZE turned on draws a 1 pixel line with full intensity. This could to achieved by just checking for normalizati
Re: [OpenJDK 2D-Dev] Fix for drawing round endcaps on scaled lines.
You can google and find a dozen sites that detail the math that shows
that Bezier approximations to quarter circles approximate the original
arc to within about .1%. We use that kind of math in the geom classes
(see ArcIterator and EllipseIterator)...
...jim
Denis Lila wrote:
I also have two questions about computing a good bezier approximation
to circle arcs.
1. Given the arc (1,0)->(cos(a),sin(a)) where 0 wrote:
That's true.
Well, if we're worried about the generated paths being verbose
and taking long to process then the problem extends beyond just
drawing round end caps. As far as I can see, whenever a path is
drawn that doesn't consist only of straight lines (i.e. an ellipse),
a flattening path iterator is being used to feed Stroker. So all
the bezier curves are still broken down into tiny straight lines,
just not by Stroker itself.
So, my question is, given a bezier curve C and a number w, is
there a way of quickly computing the control points of two bezier
curves C1, C2 such that the stuff between C1 and C2 is the widened
path?
More formally: compute the control points of C1, C2, where
C1 = {(x,y) + N(x,y)*(w/2) | (x,y) in C}
C1 = {(x,y) - N(x,y)*(w/2) | (x,y) in C}, where N(x,y) is the normal
of C at (x,y).
If we could do this easily, then we can just make a new class that
outputs bezier curves that is similar in purpose to Stroker, but that
is used only when the output can handle bezier curves. This way, the
only use left for Stroker would be when anti-aliasing, and for
every thing else we wouldn't have to use a flattening path iterator.
Thanks,
Denis.
- "Jim Graham" wrote:
Hi Denis,
Consider the case of using BasicStroke.createStrokedShape(). How do
you
know how many pixels the resulting path will occupy? You can't
reduce
to concrete samples if you don't know the transform.
So, for rendering, then you may be correct. But for cases where the
path is being asked for then beziers are the only responsible
solution...
...jim
Denis Lila wrote:
Hello Jim.
I thought about checking the output and changing the behaviour
depending on whether the output is a PC2D or a LineSink, but I
didn't
implement it because I thought the point was to get rid of the
sampling
at this stage. However, if performance is the issue, then I guess
I'll
start working on it.
Although, I wonder whether it is really worth it. I think most
lines
drawn
won't be wider than about 5 pixels, which means that the current
way
will
emit about 7 lines, so that's 14 coordinates. 2 bezier quarter
circles will
require 12 coordinates. In terms of storage, there isn't much
difference, and
for lines of width 4 or smaller the current method is more
efficient.
I'm also guessing that it's harder for the rasterizer to deal with
bezier
curves than with straight lines, so is it possible that replacing
the
3.14*lineWidth/2 lines generated by the current method with 2
bezier
quarter circles isn't worth it (for small lineWidths)?
Thanks,
Denis.
- "Jim Graham" wrote:
Sigh - that makes sense. One issue is that the resulting paths
it
generates are much more "verbose" than they need to be. This
would
generally mean that it takes far more storage than it would
otherwise
need - and it means that if the result needs to be transformed
then
it
would take many more computations to transform each segment than
the
bezier.
So, perhaps it would be worth having it check the type of the
output
and
do either a bezier or a bunch of lines depending on if it is a
PC2D
or
a
LineSink?
Also, it isn't really that difficult to for Renderer to include
its
own
Cubic/Quadratic flattening code, but it might involve more
calculations
than the round-cap code since it would have to be written for
arbitrary
beziers whereas if you know it is a quarter circle then it is
easier
to
know how far to subdivide... :-(
...jim
Denis Lila wrote:
So, I have been thinking about this, and I can't see a good
way to do it that wouldn't involve heavy changes to Pisces.
In order for Stroker to generate Bezier quarter circles, it
would
have to implement a curveTo method, which means Stroker should
start implementing PathConsumer2D and instead of using a
LineSink
output it would have to use a PathConsumer2D output (either
that,
or
LineSink should include a curveTo method, but then there won't
really
be any difference between a LineSink and a PathConsumer2D. By
the
way,
LineSink doesn't have any implemented methods, so why is it an
abstract
class as opposed to an interface?)
Stroker is used in 3 ways:
1. As an implementation of BasicStroke's createStrokedShape
method.
This
uses a Path2D object as output.
2. As a way of feeding a PathConsumer2D without calling
createStrokedShape
to generate an intermediate Shape. This uses a PathConsumer2D
output.
3. As a way of feeding lines to a Renderer object, which
generates
alpha
tiles us
Re: [OpenJDK 2D-Dev] Fix for drawing round endcaps on scaled lines.
Hi Denis,
We need a lot of upgrades in this area, but they will come with some
engineering cost.
Note that the Ductus line widening code widens curves to curves, but
many (most?) line wideners flatten everything to do widening so they
only have to deal with algorithms that widen and join lines. I haven't
applied myself to the task of creating an algorithm that can do their
"direct curve widening" technique yet so I don't have a canned solution
for that, but it would make the results of
BasicStroke.createStrokedShape() much less verbose.
Also, for a practical matter the existing down-stream rendering classes
that take the output from these widening classes only deal with lines,
but if they took the curves directly then they might be able to do a
more efficient job of flattening the segments. Until then, the only
case where it would matter much for these classes to output curves would
be for BS.createStrokedShape() and even that would probably require some
more plumbing from the code that feeds these classes.
But, I want to raise visibility of these issues here because we should
not be blindly accepting flattening as the law when we consider upgrades
to this part of the code. It is currently an "easy way out" and as we
spend time on the code we should provide resistance to accepting that
philosophy by default...
...jim
Denis Lila wrote:
That's true.
Well, if we're worried about the generated paths being verbose
and taking long to process then the problem extends beyond just
drawing round end caps. As far as I can see, whenever a path is
drawn that doesn't consist only of straight lines (i.e. an ellipse),
a flattening path iterator is being used to feed Stroker. So all
the bezier curves are still broken down into tiny straight lines,
just not by Stroker itself.
So, my question is, given a bezier curve C and a number w, is
there a way of quickly computing the control points of two bezier
curves C1, C2 such that the stuff between C1 and C2 is the widened
path?
More formally: compute the control points of C1, C2, where
C1 = {(x,y) + N(x,y)*(w/2) | (x,y) in C}
C1 = {(x,y) - N(x,y)*(w/2) | (x,y) in C}, where N(x,y) is the normal
of C at (x,y).
If we could do this easily, then we can just make a new class that
outputs bezier curves that is similar in purpose to Stroker, but that
is used only when the output can handle bezier curves. This way, the
only use left for Stroker would be when anti-aliasing, and for
every thing else we wouldn't have to use a flattening path iterator.
Thanks,
Denis.
- "Jim Graham" wrote:
Hi Denis,
Consider the case of using BasicStroke.createStrokedShape(). How do
you
know how many pixels the resulting path will occupy? You can't reduce
to concrete samples if you don't know the transform.
So, for rendering, then you may be correct. But for cases where the
path is being asked for then beziers are the only responsible
solution...
...jim
Denis Lila wrote:
Hello Jim.
I thought about checking the output and changing the behaviour
depending on whether the output is a PC2D or a LineSink, but I
didn't
implement it because I thought the point was to get rid of the
sampling
at this stage. However, if performance is the issue, then I guess
I'll
start working on it.
Although, I wonder whether it is really worth it. I think most lines
drawn
won't be wider than about 5 pixels, which means that the current way
will
emit about 7 lines, so that's 14 coordinates. 2 bezier quarter
circles will
require 12 coordinates. In terms of storage, there isn't much
difference, and
for lines of width 4 or smaller the current method is more
efficient.
I'm also guessing that it's harder for the rasterizer to deal with
bezier
curves than with straight lines, so is it possible that replacing
the
3.14*lineWidth/2 lines generated by the current method with 2 bezier
quarter circles isn't worth it (for small lineWidths)?
Thanks,
Denis.
- "Jim Graham" wrote:
Sigh - that makes sense. One issue is that the resulting paths it
generates are much more "verbose" than they need to be. This would
generally mean that it takes far more storage than it would
otherwise
need - and it means that if the result needs to be transformed then
it
would take many more computations to transform each segment than
the
bezier.
So, perhaps it would be worth having it check the type of the
output
and
do either a bezier or a bunch of lines depending on if it is a PC2D
or
a
LineSink?
Also, it isn't really that difficult to for Renderer to include
its
own
Cubic/Quadratic flattening code, but it might involve more
calculations
than the round-cap code since it would have to be written for
arbitrary
beziers whereas if you know it is a quarter circle then it is
easier
to
know how far to subdivide... :-(
...jim
Denis Lila wrote:
So, I have been thinking about this, and I can
Re: [OpenJDK 2D-Dev] Fix for uniformly scaled dashed lines.
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" 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/ (where
di is the untransformed dash length, newx is the transformed x
coordinate, and is the untransformed line length). Obviously,
newx/ is constant for all dash segments, so it can be computed
outside of the loop, but I was computing t=di/ 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. Th
Re: [OpenJDK 2D-Dev] 2 small xrender fixes
I see the problem now. I looked at what T2K (the rasteriser) reports, but in the non-T2K glue code we then make an adjustment in the case of LCD glyphs which simply should never have been applied in the case of an empty image. It has never affected any of our code as I think we only truly use the width (not the same as advance) during blitting and the check for a null image stops us before that's an issue. I'll file a bug and fix this. Thanks, -phil. On 7/7/2010 12:28 PM, Clemens Eisserer wrote: Hi Phil, Strange, running your test I get width=-1 when uploading as well as rendering the glyph - and the pipeline basically just reads the native GlyphInfo structure by using Unsafe. I'll have to think about it a bit more .. Anything I could to to help to track that down? Thanks, Clemens
Re: [OpenJDK 2D-Dev] 2 small xrender fixes
Hi Phil, Strange, running your test I get width=-1 when uploading as well as rendering the glyph - and the pipeline basically just reads the native GlyphInfo structure by using Unsafe. > I'll have to think about it a bit more .. Anything I could to to help to track that down? Thanks, Clemens
