## Quadratic Arc Decorators for Freehand Drawing Library

I just finished the first cut at the quadratic arc decorators for the Freehand Drawing Library. Previously, only solid arcs could be drawn. The example below shows dashed- and dotted-line decoration applied to arrowed arcs.

The decorators all share a fast, on-the-fly arc-length parameterization utility. I still have a few tweaks to make to one of the decorators before full production release, but the new library is going out to all beta users this morning.

Based on feedback, I’m going to add one more stroke (Polygonal) and two spline-based drawing engines to the full release. Because of this new addition, I’m seeking a couple more beta users. If your drawing requirements could benefit from a variety of splines, including splines that auto-convert to shapes (i.e. lines and quads) for creating dynamic outlines/fills, please e-mail me for more information on entering the beta program.

The beta includes full source code and there is a small, 3-figure license fee. All beta users get FREE upgrades for life. Email is theAlgorithmist [at] gmail [dot] com. Thanks!

## Dynamic Bezier Spline Scroller With Source

Paul Taylor and I collaborated on a TinyTLF demo for 360|Flex last fall that used a quadratic Beizer spline to form left and right vertical constraints for dynamic text layout. After the demo, a few people said it would be really cool to see the text scroll. The idea scroller, however, should be organic to match the text boundaries, just as a vertical scroller matches a straight-line text boundary. Since the spline boundary is dynamic, this means the scroller track and thumb should be dynamically drawn.

Since I had some time, I took on the task to create another demo for Adobe MAX 2010 and it was completed during the conference. I envisioned a possible TechNote on the scroller’s construction, but time constraints have since rendered that idea impractical. Since a TechNote implies open-sourcing the code, the next best solution is to just open-source the code. If there is sufficient interest, I might do a deconstruction over the course of several blog posts.

Now, the track is the easy part since we already have the constraint and the quad. Bezier spline is one that I released in Degrafa. It’s a simple construction with G-1 continuity and a tension parameter. Additional artificial tangent control is provided by augmenting the spline with degenerate quad. segments at the beginning and end. The spline is non-interpolative.

Most of the details are in the thumb construction and update. This demo uses a relatively simple arc-length parameterization based on adaptive interpolation, and the interpolator may be injected. Two interpolators are provided with the demo, but I’ve only tested one.

The scroller uses a linear model to map thumb position to [0,1] for the thumb value. I don’t like the linear model since it has some issues, so I sketched out a quadratic model, but did not have bandwidth to test the implementation. I also did not have time to test every conceivable path through the code, so there may be a bug or two yet to be uncovered. So, check it out and see if you can come up with some interesting ideas for using this in an application.

Yes, that’s a pretty ugly-looking demo 🙂 Your job is to turn it into something visually impressive. Good luck!

The companion demo illustrates how to use two of the Bezier splines to bound the width of an element.

## Path Arc-Length Parameterization Preview I

One of my favorite background projects at this time is arc-length parameterization of general paths. Think of a path informally as an ordered collection of planar, parametric curves that may be both spatially discontinuous and discontinuous in first derivative at the end of one curve and the beginning of another curve. Each curve in the path is called a segment and segments may degenerate into lines or points.

One may wonder if cartesian curves, i.e. y = f(x), x in [a,b], are allowable as path segments if all segments are parametric, i.e. x=x(t), y=y(t), t in [0,1]. We can reparameterize the cartesian curve as x(t) = (1-t)a + tb for t in [0,1] and y(t) = f( x(t) ). So, it is acceptable in the future to have natural cubic splines comprise path segments. Can any programmers spot an Adapter pattern here?

The problem in this development is an efficient strategy for the approximate arc-length parameterization of the entire path. In other words, a query for the x-coordinate of the path at a parameter 0.5 should return the x-coordinate of the path segment that is ‘close’ to halfway along the entire path length.

The difficulty lies in the fact that the individual segments (other than lines or points) are not naturally arc-length parameterized. Aside from creating complex, higher-order curves that have the necessary parameterization embedded in the curve construction, the classic efficient solution is to interpolate natural parameter as a function of normalized arc length (i.e. fraction of total length in [0,1]). This yields a model, t = M(s), where both t and s are in [0,1].

The re-parameterization problem consists of finding M for each segment in the total path. Each segment comprises some interval of normalized arc length, i.e. [s0, s1]. Given an input value, s, in [0,1], the Path first determines which segment ‘owns’ that normalized arc length. The segment evaluates its local model to return a natural parameter, t, corresponding to the approximate normalized arc length. The segment is then evaluated in its natural form to return the requested coordinate values.

Because of the wide variety of potential segments, a key to efficient implementation is the concept of reducibility. In other words, each segment must be efficiently approximated as a sequence of simpler segments. Then, we can use one model for each of the ‘atomic’ elements of each segment.

A linear interpolation model sounds reasonable, at least in terms of efficient evaluation. Certainly, any curve may be reduced to a number of small segments over which the normalized arc length as a function of natural parameter is near-linear. The problem is the large number of required subdivisions.

The current work uses a quadratic Bezier as an atomic element. I’ve already illustrated with Degrafa that a wide variety of both cartesian and parametric splines can be reasonably approximated as a sequence of quadratic Beziers. Subdivision of cubic Beziers into sequences of quads is a well-known process.

By reducing all segments other than lines and points to sequences of quadratic Beziers, the re-parameterization problem reduces to that of modeling natural parameter as a function of normalized arc length for a quad. Bezier. It is computationally simple to subdivide a quad. Bezier into a sequence of smaller quad. Beziers. As the number of subdivisions increases, it is reasonable to expect the quad. sequence to ‘flatten’ and eventually approach straight lines. While this approach is suitable for fitting a linear model, it has the disadvantage of producing a very large number of sub-segments. Each subdivision sweep involves fitting and testing a model, so linearization is not an efficient approach.

The current work uses a quadratic model and a more intelligent procedure for subdividing the original quad. Bezier. That process is based on curvature as curvature vs. arc-length is a natural means for describing the shape of a curve. This procedure only fits a quadratic model if the subdivided segment first passes a simple curvature-based test. Subdivision proceeds only if the model fails a relative error test.

In addition to producing much fewer atomic segments for the model, this approach has the advantage of allowing the geometry of the original quad. Bezier to dictate the number of interpolation points. This avoids oversampling for small, flatter segments and undersampling for long segments with large curvature.

I’m currently working on the model for a single, quad. Bezier segment and the structure of the class library. The screen shot below illustrates a sample unit test.

This is just a query of coordinates at normalized arc length 0, 0.5, and 1. The boundary tests are important as the above quad. Bezier is itself subdivided into ten smaller quadratic Beziers. This is far less than the nearly 30 samples I would use for linear interpolation and even with the number of samples for a crude approach to cubic spline interpolation. The latter is very accurate, but very expensive. So, I’m very pleased with this first result although a great deal of additional testing is required before moving onto more complex segments and paths.

The code itself is built entirely to interfaces, not specific implementations. This allows new segments to be quickly inserted into paths and application-specific versions of paths to be created without modifying the code that uses a path. In the current test code, the following interfaces and factories are imported,

import path.SegmentFactory;

import path.PathFactory;

import path.IPath;

import path.IPathSegment;

The two relevant class variables are

private var __path:IPath;

private var __segment:IPathSegment;

The general approach is to create an IPath instance using PathFactory, create segments using SegmentFactory, add those segments to the path, then manipulate the path.

__segment = SegmentFactory.createSegment(p0.x, p0.y, p1.x, p1.y, p2.x, p2.y);

__path = PathFactory.createPath();

__path.addSegment(__segment);

Currently, there is a default Path class that implements IPath. In the event a programmer needs to modify that functionality, the PathFactory may be modified to return a new IPath implementation. The interface supports getParam() and setParam() methods to allow for access and mutation of arbitrary parameters. The factory constructor supports variable arguments, so it is possible to create a wide variety of IPath implementations without modifying the core application code that uses the path.

The SegmentFactory functions in a similar manner. The first variable arg is an optional String. If that argument is a String, it is treated as the fully qualified class name of a Class that implements IPathSegment. The instance is constructed using the remaining parameters. This allows splines, for example, to be quickly constructed and added to paths without worrying about the specific implementation of each spline.

That’s it for the first preview. Unfortunately, I have to put this project on the back burner once again since I’ve picked up a couple short-term projects. I’ll post more code snippets and results as time allows in the future.

## Quad Bezier Curvature

I’ve been working with curvature of parametric curves and quadratic Beziers in particular as part of the project on arc-length parameterization of a general path. A few recent emails have broached this topic. Differential geometry often discusses both extrinsic and intrinsic curvature. Intrinsic curvature is too theoretical for this casual post. Extrinsic curvature is defined on curves embedded into a Euclidean (or other) space. A relationship exists between extrinsic curvature and the radius of the osculating circle (read all about it on Wikipedia).

Extrinsic curvature for parametric curves is well covered in Grey [1]. Given a Bezier curve, B(t), curvature is defined as κ(t) = |B'(t) x B”(t)|/||B'(t)||^{3} . Now, a quadratic Bezier is a parabola and geometric properties, including curvature, can be computed from parabolic representation or the polynomial coefficients. There are, however, instances where control-point coordinates are immediately available and it is not desirable to compute coefficients. Fortunately, the open literature contains everything we need to work with curvature based solely on the geometric constraints of the quadratic Bezier curve.

Suppose the control points are p_{0}, p_{1}, and p_{2}. Let A represent the area enclosed by the convex hull (triangle in this case) of the control points. Computing the area given the control point coordinates is trivial. Let m be the midpoint of the p_{o}p_{2} segment. The distance, d = ||p_{0}m|| = ||mp_{2}|| is the diameter of two circles passing through p_{0}, m, and p_{2}. A screen shot from the output of a simple Flex program to illustrate these properties is shown below.

p_{1} is the top, middle control point. m is the red dot.

Sapidis and Frey [2] established that B(t) has monotone curvature if p_{1} lies inside either circle. Deddi, Everett, and Lazard [3] proved that the maximum curvature of B(t) is ||p_{1}m||^{3}/A^{2} if p_{1} lies strictly outside the circles. If inside, the maximum curvature is max(κ_{0}, κ_{1}) where

κ_{0} = A/||p_{0}p_{1}||^{3}

κ_{1} = A/||p_{1}p_{2}||^{3}

are the curvature at B(0) and B(1), respectively.

Knowing regions of monotone curvature and relationships between curvature at the endpoints vs. maximum curvature is helpful in that there are nice heuristic relationships between arc length and curvature in these regions. That is, we can subdivide a quadratic Bezier into equivalent quadratics with monotone curvature and use the information to sample the curve to reparameterize on arc length. Only control points immediately available from subdivision are needed.

The appealing feature of this approach is that the geometric constraints of the curve itself determine the sampling, not a predetermined heuristic. This tends to increase both accuracy and efficiency by not undersampling curves with large lengths and points of high curvature or oversampling curves with small length or near linearity.

More to come as this project progresses 🙂

References

[1] Gray, A. *Modern Differential Geometry of Curves and Surfaces with Mathematica, 2nd ed.* Boca Raton, FL: CRC Press, 1997.

[2] Sapidis, N.S. and Frey, W.H., “Controlling the curvature of a quadratic Bezier curve,” Computer Aided Geometric Design 9, 1992, pp. 85-91

[3] Deddi, H, Everett, H. and Lazard, S., “Interpolation problem with curvature constraint,” In C. Rabut A. Cohen and L. L. Schumaker, editors, *Curve and Surface Fitting*. Vanderbilt University press, Nashville, 2000.

## Quad Bezier Refinement in Degrafa

De Casteljau subdivision is a procedure by which a Bezier curve is defined. It is also used to subdivide a quadratic Bezier curve into two distinct quadratic Beziers representing individual segments of the original curve. The first Bezier segment is in the interval [0,t] and the second lies in [t,1] for t in (0,1). Some 3D graphics packages use the term refinement to describe to the process of subdividing or splitting a curve into two equivalent segments at some interior point. Refinement is also used to describe a process of extracting the coefficients of an equivalent-degree curve at two interior points. In this context, refining a quadratic Bezier curve produces another quadratic Bezier that represents the original curve in the interval [t1,t2] where t1 < t2 and both t1, t21 are in [0,1].

This is an infrequent operation, although I recently used it in the organic scroller, the boundary of which is a quadratic Bezier spline. The process may also be used to extrude any segment of a path comprised of quadratic Beziers (such as a circle approximation).

The quad refinement algorithm is now in Degrafa. I’m still in the process of conducting some unit tests for possible numerical issues. I wanted to get a release out now, while I’m in between gigs, since I have the time and am thinking about it. Otherwise, you know what happens. It’s onto the next gig and I forget 🙂

A screen shot of the demo program is shown below.

Not much to the demo. The blue curve is the quad. Bezier that interpolates the three points, P0, P1, and P2 with chord-length parameterization. The red curve is drawn from coefficients returned from the quadRefine() method of the BezierUtils class. Above, the red curve illustrates refining the original quad in the interval [0.2, 0.6].

Drag the points to see how the refinement is modified. Adjust the stepper thingies to modify the interval. [t1,t2] can be extended to a maximum of [0.1,0.9] in increments of 0.1. Note that t2 must be strictly greater than t1. Code has been committed to the Origin branch.

## Actionscript Organic Scroller Preview

Just a quick note to say hello from Adobe MAX in LA. This is a short preview of a project I’ve been working on with Paul Taylor. At 360|Flex, we showed a demo where TinyTLF was used to layout text respecting a spline boundary. Paul showed scrolling with TinyTLF here at the 360|Flex Unconference. The next natural progression is to have both the text boundary and the scroller be organic; that is, both are based on the same Bezier spline. The scroller itself and the thumb are dynamically rendered in Actionscript. The small image below shows a preview of one test case.

Needless to say, there is a *lot* of math involved ranging from arc-length parameterization to interpolation models to a nonlinear model for scroller thumb interaction. The alpha component is being turned over to Paul for integration into a TinyTLF demo and further testing. Once it’s solid, we will work on a vehicle for distributing the code, which will include at least a white paper on all the math used in the scroller construction.

More to come later!

## Automatic Bezier Arcs in Degrafa

An interesting problem is to draw an eye-pleasing arc between two points. This can be used for anything from drawing origin-destination route arcs to approximating trajectories in animation. Since we already know how to interpolate a quadratic Bezier between three points, one possible solution is to parameterize the generation of a middle interpolation point given two initial points.

I’ve used an algorithm along these lines since about 1982. It takes two parameters, one of which determines the concavity of the arc. The second parameter controls the distance between the midpoint of the line segment from first to last point and the middle interpolation point. This provides a large amount of control over the generated arc.

A closely related problem is animating the arc. This is trivial with a quadratic Bezier as the section of arc at any parameter value can be drawn with a single curveTo command using deCasteljau subdivision.

The auto-arc generation is now in the BezierUtils class and the subdivision method has been added to the AdvancedQuadraticBezier class. A screen shot from the rather plain and simple demo is shown below.

The code has been checked into the Origin branch.