[OpenJDK 2D-Dev] X11 uniform scaled wide lines and dashed lines; STROKE_CONTROL in Pisces

[Denis Lila]

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.graham at 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.graham at 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