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.
The Algorithmist 