Hello Jim.
I think this would actually ensure that every resulting curve can
be rotated to be made monotonic in both x and y (at least after
inflections are eliminated), which means it's at least as good as
what I have now.
While that first statement is true, it unfortunately does not mean
it's
"at least as good as" breaking the curve into monotonic pieces. I
implemented the angle checking method, and the problem is that for
curves like (0,0),(1000,1),(-1000,1),(0,0) it is very bad. That's
because I implemented it by subdividing at t=0.5, so the angles
in the resulting curves' polygons are still wide. After enough
subdivisions the polygons would have angles below 45, but that would
defeat the point, since we're trying to minimize the number of output
curves.
I can't think of a good way to chose the subdivision t so that
this method is as good as the rotation and make monotonic one (nothing
with any properties I can prove, anyway), so I'll implement the
rotating version, as much as I don't like it. At least it gives a good
upper bound in the number of output curves.
Regards,
Denis.
----- "Denis Lila"<dl...@redhat.com> wrote:
Hello Jim.
Thanks for taking the time to think about this.
I implemented a few different offsetting schemes. On well behaved
curves, my original "parallel first and last control vectors and go
through B(0.5)" algorithm was by far the best. Theoretically it is
also somewhat better justified than the others (some of which were
like Apache Harmony's way - offsetting p2 and p3), since we're
interpolating instead of just using some heuristic. It is also
the only one I've encountered that widens quarter circles optimally,
and it only needs one curve per side too (i.e. if we have to widen
the path of a PathIterator of a circle with radius r, using width w,
Pisces' output will be identical to the output of the PathIterators
of 2 circles with radii r+w and r-w (perhaps not identical
identical,
since PathIterators can use doubles, and we only use floats in
pisces,
but... that's nitpicking)).
As I've said before, the only 2 problems with it were that it was
bad
on high curvatures (but this was fixed by breaking down the curves
into
monotonic ones), and it was bad on curves like
p.moveTo(0,0);p.curveTo(100,100,0,100,100,1). I thought the latter
was
fixable with the "d1/(d1+d2)" algorithm I suggested in my previous
e-mail.
I implemented it, and it turns out I was wrong. Then I came up with
my
own
variation of that algorithm (the original one I used was from Don
Lancaster's
website) that did sort of work. But then I implemented your
suggestion
of
splitting the curve at the inflection points as well as breaking it
into
monotonic pieces, and the problem was gone. I didn't even have to
use
the
fancy variation of the "d1/(d1 + d2)" algorithm - just the plain old
interpolation one worked (I should say that the fancy one is still
probably
better, but undetectably so, now that we break at inflection points
and at
xy direction changes, so the added complexity is probably not worth
it).
I've attached my latest Stroker.java, if you want to take a look at
these
algorithms (they're in computeOffsetWay1 (for the old interpolation)
and
computeOffsetWay3 (for the fancy version). There are 2 more, but
these
aren't as good, and one is just shameful). I didn't make a webrev
because
I still need to fix how it handles cusps (which should be easy), and
I
need to implement a way to avoid subdividing a rotated quarter
circle.
I can do this either by rotating curves so that p2-p1 is parallel to
the
x axis and then subdivide like I do now (i.e. make monotonic, break
at
inflections) or get rid of the monotonic subdivision, and instead
subdivide
by checking the angles of the control polygon. I could make it so it
subdivides whenever the angles between p2-p1 and p3-p2 or p3-p2 and
p4-p3
are greater than 45 degrees.
Very well. I've convinced myself. I'll implement the latter.
Thanks,
Denis.
----- "Jim Graham"<james.gra...@oracle.com> wrote:
Hi Denis,
Just to let you know that I've seen this and I'm thinking.
But it will take a bit of "more thinking" when I have time for
more.
Hopefully in a couple of days.
For one thing, it sounds like you already understand the Apache
Harmony
approach quite a bit better than I ever did and, in particular,
why
it
didn't work well - which is encouraging. Hopefully your solution
will
sound pretty good when I get around to wrapping my head around
it...
...jim
On 8/30/2010 3:03 PM, Denis Lila wrote:
Hello Jim.
One way in which they may not break enough is that I think that
inflections also need to be broken in order to find a parallel
curve
(though I suppose a very tiny inflection might still be
approximated by
a parallel curve easily) and inflections can happen at any
angle
without
going horizontal or vertical.
It wouldn't be hard to add additional breaks at the
inflection
points.
Secondly, although a circle tends to be represented by quadrant
sections
which are monotonic, a circle rotated by 45 degrees would have
horizontal and vertical sections in the middle of each quadrant
and
you
would split those, but really they can be made parallel
regardless
of
angle so these would be unnecessary splits.
That's true, and it's one reason I didn't like my method
very
much when I sent
my previous e-mail. However, what if we rotated curves so that
B'(0)
is
parallel to the x-axis before splitting at points where dx/dt or
dy/dt are 0?
This would certainly get rid of this problem for circles, and
probably for
other curves. All it would cost is 1 Math.cos and 1 Math.sin and
a
few
multiplications and additions per curve.
The biggest problem with my implementation was that some curves
that
were almost
lines were drawn horribly. I computed the parallel (p1', p2',
p3',
p4') of
a given curve (p1, p2, p3, p4) by making p2'-p1' parallel to
p2-p1,
making p4'-p3' parallel to p4-p3. This leaves a 2 unknowns, so
to
get 2 more
equations I made the computed parallel at t=0.5 equal to the
ideal
parallel
at t=0.5. The problem was that for some curves (ones with very
high
curvature)
p2'-p1' and p4'-p3' were parallel to p2-p1 and p4-p3 but their
directions were
opposite, so you can imagine what the computed "parallel" looked
like.
However, I am almost certain that the problem was caused by
making
C(0.5) = P(0.5)
(where C is the computed curve, and P is the ideal parallel). A
much
better
restriction, that I think would eliminate the problem would be
C(d1/(d1 + d2)) = P(0.5).
where d1 = ||P(0.5)-P(0)|| and d2 = ||P(1)-P(0.5)||.
My belief is that lengths and angles of the control polygon
help
determine if it is well-behaved and can be made parallel simply
by
offsetting. Some formula involving those values would likely
be
happy
with circle sections regardless of their angle of rotation. I
believe
the Apache Harmony version of BasicStroke used those
criteria...
I've been reading the Apache Harmony file. The way they do
it
is compute
the tangent of an angle using the line width and a predefined
constant
(which doesn't seem to be related to the curve's polygon - it's
just
a decreasing
function with the range (-1,1)), and if some angles in the
polygon
are smaller than
the computed angle, offset curves are computed. Otherwise the
curve
is subdivided.
However, I can't understand how offsets for the control points
are
computed (i.e.
why they use the equations they use, and why they work).
If we're using the widening of quarter circles as a yard stick,
then
Apache Harmony's
BasicStroke does not do very well. If we have a quarter circle
from
(1,0) to (0,1),
then the control points c1 and c2 should be (1,k) and (k,1)
where
k
= 4*(sqrt(2)-1)/3.
A parallel curve w away from this quarter circle should have
control
points
(1+w,k+k*w) and (k+k*w,1+w). I traced Apache Harmony's
computations
on a quarter
circle, and this is not what it outputs. Furthermore, all
quarter
circles with line
width< 9.65 will be subdivided. My method with the
modifications
suggested above
doesn't have these problems.
But perhaps it's better to not interpolate through P(0.5)
after
all.
In addition to making p4'-p3' and p2'-p1' parallel to p4-p3 and
p2-p1, we could
also make p3'-p2' parallel to p3-p2. These constraints leave
just
one unknown, which
needs to be eliminated. I am not sure how to do this. I thought
about making the line
(p2',p3') be a distance of w from (p2,p3) (which is exactly what
needs to be done for
(p1',p2') and (p3',p4')) but this doesn't get us what we want
for
quarter circles. So, finding
the control points would boil down to finding intersections of 3
lines.
Do you have any suggestions on how to do the offsetting for the
control points?
Thank you,
Denis.
----- "Jim Graham"<james.gra...@oracle.com> wrote:
Hi Denis,
At the bottom-most rendering level monotonic curves can be cool
to
deal
with, but I'm dubious that they help with widening. For one
things, I
think you need more breaks than they would give you and also
they
might
sometimes break a curve when it doesn't need it.
...jim
On 8/25/2010 2:36 PM, Denis Lila wrote:
Hello Jim.
I think a more dynamic approach that looked at how "regular"
the
curve
was would do better. Regular is hard to define, but for
instance
a
bezier section of a circle could have parallel curves
computed
very
easily without having to flatten or subdivide further.
Curves
with
inflections probably require subdividing to get an accurate
parallel
curve.
I'm not sure if you read it, but after the email with the
webrev
link
I sent another describing a different method of widening:
split
the
curve at every t where dx/dt == 0 and dy/dt == 0. This
guarantees
that
there will be no more than 5 curves per side, and since each
curve
will
be monotonic in both x and y the curve that interpolates its
parallel
should do a pretty good job.
This is far better than interpolating at regular t intervals,
but
I'm
trying to find a better way. I don't like this because the
split
depend not only on the curve itself, but also on the axes. The
axes
are
arbitrary, so this is not good. For example a curve like this
|
\_ would get widened by 1 curve per side (which is good and
optimal), but
if we rotate this curve by, say, 30 degrees it would be
widened
by
2
curves
per side.
It also doesn't handle cusps and locations of high curvature
very
well (although
I think the latter is a numerical issue that could be made
better
by
using
doubles).
Regards,
Denis.
----- "Jim Graham"<james.gra...@oracle.com> wrote:
Hi Denis,
On 8/23/2010 4:18 PM, Denis Lila wrote:
To widen cubic curves, I use a cubic spline with a
fixed
number
of curves for
each curve to be widened. This was meant to be temporary,
until
I
could find a
better algorithm for determining the number of curves in the
spline,
but I
discovered today that that won't do it.
For example, the curve p.moveTo(0,0),p.curveTo(84.0,
62.0,
32.0, 34.0, 28.0, 5.0)
looks bad all the way up to ~200 curves. Obviously, this is
unacceptable.
It would be great if anyone has any better ideas for how to
go
about
this.
To me it seems like the problem is that in the webrev I chop
up
the
curve to be
interpolated at equal intervals of the parameter.
Perhaps looking at the rate of change of the slope (2nd
and/or
3rd
derivatives) would help to figure out when a given section of
curve
can
be approximated with a parallel version?
I believe that the BasicStroke class of Apache Harmony
returns
widened
curves, but when I tested it it produced a lot more curves
than
Ductus
(still, probably a lot less than the lines that would be
produced
by
flattening) and it had some numerical problems. In the end I
decided
to
leave our Ductus stuff in there until someone could come up
with
a
more
reliable Open Source replacement, but hopefully that code is
close
enough to be massaged into working order.
You can search the internet for "parallel curves" and find
lots
of
literature on the subject. I briefly looked through the web
sites,
but
didn't have enough time to remember enough calculus and
trigonometry
to
garner a solution out of it all with the time that I had.
Maybe
you'll
have better luck following the algorithms... ;-)
As far as flattening at the lowest level when doing scanline
conversion,
I like the idea of using forward differencing as it can
create
an
algorithm that doesn't require all of the intermediate
storage
that
a
subdividing flattener requires. One reference that describes
the
technique is on Dr. Dobbs site, though I imagine there are
many
others:
http://www.drdobbs.com/184403417;jsessionid=O5N5MDJRDMIKHQE1GHOSKH4ATMY32JVN
You can also look at the code in
src/share/native/sun/java2d/pipe/ProcessPath.c for some
examples
of
forward differencing in use (and that code also has similar
techniques
to what you did to first chop the path into vertical pieces).
BUT
(*Nota Bene*), I must warn you that the geometry of the path
is
somewhat
perturbed in that code since it tries to combine "path
normalization"
and rasterization into a single process. It's not rendering
pure
geometry, it is rendering tweaked geometry which tries to
make
non-AA
circles look round and other such aesthetics-targeted
impurities.
While
the code does have good examples of how to set up and
evaluate
forward
differencing equations, don't copy too many of the details or
you
might
end up copying some of the tweaks and the results will look
strange
under AA. The Dr. Dobbs article should be your numerical
reference
and
that reference code a practical, but incompatible, example...
...jim
