26 Sep 2004 raph   » (Master)

Curves

haruspex wrote (in context of advocating circular arcs as a curve-drawing primitive):

That's a good point. But rather than having the user think about the circles, I wonder if they could use the abstraction of a digital spline and ducks (the non-mathematical meaning of spline). I suspect this is what Dr Karow had in mind when he came up with IKARUS' curve model.

Very likely it is. I think we're vehemently in agreement that drawing a curve using on-curve points (as in Ikarus) is good UI, as long as everybody is happy with the curve drawn between the points.

I will argue the superiority of Cornu spiral segments over circular arcs visually[*]. Here you see the same sequence of points fit both by tangent-continuous circular arcs, and by tangent- and curvature-continuous Cornu spiral segments. The main lesson here is that the perturbation of the middle knot damps out very quickly as you traverse (S-shaped) Cornu spiral segments, but doesn't damp out at all with the circular arcs. I think this is true in general, not just for the example shown here. The tangent continuity constraints for circular arcs propagate like a gear train: tweaking the angle up on one side of the arc pushes it down by an equal amount on the other side.

*Note to self: tweak mod_virgule code to allow high-ranked diary authors to post <img> tags inline.

There has been a certain amount of work duplicating the traditional spline-with-ducks. The relevant mathematical abstraction is an elastica. A good introduction is given in the paper Euler Spiral for Shape Completion. I think it's a nice curve with most of the properties you want for curve design. The big one that it's missing is scale invariance; in the physical analogy, you need a thinner strip of wood to wrap around tight corners than broad curves. For boats, that's not a serious problem, because it's rare for curves to have sections of both very tight and very broad curvature, but I believe that's a much more serious problem for fonts and other curves used in 2D graphics. The Cornu spiral shares many desirable properties with the elastica, and is scale invariant to boot.

There's a bunch more material I haven't had a chance to study yet at Shin Yoshizawa's page.

nomis wrote:

Unless I misunderstood you, your assumption about a maximum of two intersections for two (180°-angle) cornu segments is wrong. Have a look at this image which shows three intersections. Since I don't have a tool to easily create cornu segments I used the image at mathworld for the shape of the cornu segment. The second segments (red) are flipped and 90°-rotated versions of the first segments.

You are right and I was wrong. I still believe my intuition is correct that intersections between two Cornu spiral segments are more economical than corresponding intersections between two Bezier curves, (especially cubic, but I think quadratic also), but the details are trickier than I first guessed. Among the many subtleties is the question of how to measure "degrees of arc" for an S-shaped curve segment (i.e. one containing an inflection point). I don't think I'm going to try to solve this problem right now, but it should make a hell of an exercise for the reader :)

Can you point me to some more in-depth literature? My knowledge is basically limited to the mathworld entry and I am curious on the parameter set used to pick a certain segment of the cornu spiral.

The best literature I've found for Cornu spirals is the Euler Spiral for Shape Completion paper mentioned above. They have a fairly hairy algorithm for choosing the parameters (based on first fitting a biarc, then doing gradient descent to find the parameters for a Cornu spiral segment with similar endpoint tangents). I worked out a much simpler solution to the same problem, for which I can refer you to RTFS. I do want to explain this in more detail, but my queue for doing writeups is pretty clogged up right now.

The ease of affine transformations for bezier segments basically stems from the fact, that all points on a segment are a linear (even convex) combination of the control points. I wonder how to transfer at least some of this ease to cornu segments.

The short answer, I think, is that this ease does not transfer. The affine transformation of a circular arc is an elliptical arc, and that cannot be represented exactly by Cornu spiral segments, only approximated. Thus, my current plan is for the low level representation of curves to be a high resolution sequence of quadratic Beziers. By high resolution, I mean that I'm willing to tolerate a significantly larger number of primitives in this internal representation than either input through the UI or exported into a font file format after all manipulations have been done (most importantly affine transforms, stroke offset, self-intersection removal, and possibly special effects such as "antiquing" as well).

In your diary entry from august 13th you mentioned a presentation from siggraph. Interesting read. I think this would be awesome for interpolating the coordinates of a quick mouse movement which sometimes result in jaggy brush strokes with a paint tool

Yes! In fact, this problem is closely related to autotracing, of which potrace is currently the most advanced free solution. I have some ideas here, which I'm hoping to write up in an email to Peter Selinger soon. In very brief outline, the steps are:

  • Get a polygonal approximation of the source shape; this takes some doing when you're starting from a bitmap, but if you have a mouse or pen stroke, you're already there.
  • Numerically evaluate curvature along the path.
  • Find a sequence of points along the path such that linear interpolation between curvature sampled at these points is a good approximation to the numerically evaluated curvature.
  • Use these points as input to a Cornu spline fitter.

There are more subtleties for dealing with corners and the endpoints of smooth curve sections, but I think the basic idea has lots of potential. In particular, finding a good linear approximation to curvature will tend to put knot points at curvature minima and maxima, which I believe is exactly where they belong. I also think you'll get very graceful curve simplification behavior as you use decrease the number of points and get a looser linear fit to the curvature profile.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!