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.
Short and to the point. Paul Taylor just posted some demos, one of which shows the quadratic Bezier spline used in advanced layout and another showing the organic, spline-based scroller in action. I’ve pretty much decided to write a white paper on the math behind the scroller at some point in the near future.
I have received several questions regarding the organic scroller preview. The code will be released when Paul Taylor releases the final set of TinyTLF demos (layouts are currently being refactored). Our collaborative work will illustrate html text laid out respecting a spline boundary with the right boundary serving as a dynamic scroller component. I’ll provide a brief overview of how the scroller works in this post. A detailed deconstruction is a topic for a later white paper or book chapter.
The boundary spline is a G-1 continuous quadratic Bezier spline. The spline is generally non-interpolative and has a tension parameter. I tend to like 0.3 a lot 🙂 The spline interpolates the first and last points. Interior control points influence the shape of the spline, but the spline does not necessarily interpolate those points. I’ve covered the spline in past posts and its fundamentally the same algorithm I implemented in the Degrafa quadratic spline. As the spline is naturally composed of quadratic Bezier segments, it constructs and renders fast.
The boundary is duplicated and shifted a number of pixels to the right to create the scroller track. The spline is naturally uniform parameterized. If invalidated, the spline is reparameterized on arc length. This is done with a simple heuristic that varies the interpolation granularity based on the length of each spline segment. I will overhaul this heuristic in the future when I release arc-length parameterization for an arbitrary path. For now, it’s a demo, so it’s kept simple. Simple is good 🙂
The scroller thumb length is a fraction in [0,1] representing the fraction of the total boundary spline length to use when rendering the thumb. The component maps the thumb value to arc length in [s1,s2] so that the thumb length is preserved and the midpoint of the thumb (in arc length) represents the thumb value.
Now, for the fun part. The scroller class returns a vector of quadratic Bezier instances representing the path along the boundary from arc length s1 to arc length s2. This is an exercise in deCasteljau subdivision. Subdividing a quadratic Bezier at parameter t produces two independent quadratic Beziers that exactly represent segments of the original curve. The first quadratic represents the original curve in [0,t]. The second represents the original curve in [t,1]. The subdivision code was modified to return coefficients of either segment. That’s fine when s1 and s2 represent points in different quadratic segments. The situation is more subtle when s1 and s2 are in the same quad. This involves refining the original quadratic Bezier in the interval [s1,s2]. Once the vector of quadratic Bezier coefficients is returned, the thumb can be drawn quickly with the usual moveTo(), lineTo(), curveTo().
Interactivity is also an issue. For a vertical scroller, vertical mouse movements do not map linearly into scroller arc length. Attempting to do so may cause the scroller to jump erratically in some configurations. Instead, a quadratic model for mapping vertical mouse movements into thumb value is employed.
I suspect there is still some tweaking to do (isn’t there aways), so I’ll continue to provide updates. In the mean time, the next background project is arc-length parameterization of a general path, which may be both spatially discontinuous and likely discontinuous in first derivative.