Why is a raven like a writing desk?

Xach has released version 1.2.1 of Vecto, featuring circle arc paths, and I’m sure a whole lot more on the drawing board.

(asdf-install:install :vecto)

Curve (com.elbeno.curve) is my common lisp package for doing cool things with two-dimensional curves. In particular, modulating cubic Bézier curves and splines, but also approximating arbitrary elliptical and circular arc segments with cubic Bézier curves.

It depends on Vector (com.elbeno.vector), a cobbled together set of functionality for representing and manipulating points on the 2D Cartesian plane. It also depends on Zach Beane’s excellent Vecto, for ease of drawing. Both Curve and Vector are available under the GPLv3 license.

Download Curve
Download Vector

Currently both Curve and Vector are at v0.1.

In doing my modulation work with curves and ellipses, I extended the vecto function for drawing an ellipse to enable an oriented ellipse. Lately it occurred to me that this didn’t go far enough in terms of functionality, and I began wondering about how to draw part of an elliptical arc.

Vecto’s ellipse drawing function works by drawing the ellipse in quarters, with four cubic Bézier curves. Each curve’s control points are calculated according to the radii and kappa, the constant that is 4(√2 – 1)/3, as explained by G. Adam Stanislav. This works fine if you are drawing quarters, halves, or complete ellipses (or circles of course), but what I wanted was a function like this:

(defun approximate-elliptical-arc (cx cy a b theta eta1 eta2)
…)

With (cx, cy) being the centre, a and b being the radii, theta being the orientation, and eta1 and eta2 being the start and end angles specifying the arc. The return value would be a Bézier curve, or a list of curves, depending on the required accuracy.

So I did some research and found an interesting paper by Luc Maisonobe on approximating such elliptical arcs with lines, quadratic and cubic Bézier curves. The maths is straightforward, if rather heavy on the constants, and it was less than an hour’s work to code up the function. I now have functionality to draw arbitrary elliptical (or circular) arc segments.

The interesting thing is that this method of approximating ellipses is not the same as G. Adam Stanislav’s method: to put it another way, when I compute a quarter-circle arc with a single Bézier curve, the control points are not quite coincident with the kappa-method control points. The error in the circle approximation is still undetectable to the eye, but careful comparison of two large circles shows that the kappa-method one is slightly larger: the curves are slightly more “pushed out”.

G. Adam writes: “It is my contention that we get the closest to a real circle if we draw the one curve with properties already discussed, and with the center point of the curve lying at the same point the center point of the circumference of a true quadrant of a circle would lie.” I would be interested to know if he has a proof behind this contention, and/or an expression for the error in such a curve. The derivation of kappa is based around this idea that the midpoint of the curve should be coincident with the midpoint of the arc.

G. Adam’s method seems accurate. But the Maisonobe method can be used to subdivide the arc, obtaining successively closer approximations to the true arc by using multiple Bézier curves, and includes a method for calculating an upper bound on the error. This, together with the fact that it easily handles start and end angle specification of the arc, leads me to favour it.

I’ve been wanting to do exclusive-or functional fill in vecto for a while, so tonight I delved in. I added a pixel function to the graphics state and kept the default as the normal alpha-blending it was already doing. The pixel function signature is a bit clumsy, but it was easy to knock up a couple of functional fill demos. Programmer art alert!

This is a cyan background, and a circle drawn with an XOR function, white fill, and green stroke. From this you can see that the fill happened before the stroke, since the stroke is half-and-half.

And this demonstrates an inclusive-OR fill: the standard additive colour chart.

Honestly, they’re incredibly interesting. Anyway, I’ll skip straight to the pièce de résistance:

This is a 4-curve cubic Bézier spline modulated onto an ellipse. The ellipse [a=4, b=3] is at an angle of π/4. C1 continuity of the complete curve is preserved. The flickr set tells the story of how I got here.

This is around 450 lines of my naive lisp, including class definitions and test code. So Gary, this is your g-code challenge!

The lisp code is object oriented (oh, and so much nicer than C++’s so-called object orientation). I rewrote the earlier code now that I knew what I was doing, and I added lines and polylines to the mix too (see the flickr set) so I can easily modulate whatever edge I want. You’ll notice if you look closely at the earlier attempts that they had a bit of a problem with c1 continuity, which is now fixed with the new code.

In closing, thanks, Zach!

After some code cleanup and generalisation, I can now modulate whole splines onto ellipses and onto splines themselves. Here is my simple 4-bezier spline modulated onto an ellipse:

And onto itself:

Repeatedly modulating a spline onto itself while varying the frequency parameter leads to some interesting and fractal patterns. Nice.

My efforts to equally subdivide a curve along its length have, in part, been leading to this. First, I extended the sampling to work with splines (made up of cubic Bézier curves with c1 continuity). This shot shows 4 curves put together to form a spline:

Next, I wrote some code to modulate a curve onto another curve. Here’s a curve, and the same curve with another curve modulated onto it.

Since I already had the binary search and interpolation code, it was just a matter of writing different samplers for ellipses and Bézier curves.

;; make a sampler function for a bezier curve
(defun make-bezier-sampler (p0 p1 p2 p3)
  (lambda (k)
    (decasteljau p0 p1 p2 p3 k)))

;; make a sampler function for an ellipse
(defun make-ellipse-sampler (center xradius yradius)
  (lambda (k)
    (let ((x (* xradius (cos k)))
          (y (* yradius (sin k))))
      (make-point (+ x (xcoord center)) (+ y (ycoord center))))))

Equal angle increments:

Equal circumferential distances:

I think I will use the same method as I do for Bézier curves to step along the circumference.

Another generalisation I had to make from the circle code is with respect to the normal. For a circle of radius r, centred on the origin, and parameterised by angle θ, a point on the circle is (r cos θ, r sin θ). And the normal is exactly the same: the point vector is normal to the circle.

For an ellipse, this is not the case. For an ellipse with half-dimensions a and b, centred on the origin, and parameterised by angle θ, a point on the ellipse is (a cos θ, b sin θ). But the normal is (b cos θ, a sin θ).

(Of course, the ellipse form degenerates to the circle form when a = b.)