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