5
$\begingroup$

Before widespread use of digital computers lofting was done using a thin flexible strip, called spline, held in place by a series of weights. This technique is a type of interpolation (curve exactly passes over sample points) using a physical analog model (minimal potential energy of a thin flexible beam).

Analog lofting spline

With the advent of digital computers and CAD tools, engineers developed a digital version of lofting splines, but instead of using a similar interpolation technique they chose an approximation technique by means of distant control points called NURBS.

Digital lofting spline (NURBS)

With an approximation approach you need to perform an iterative process to manually fit a curve to the desired path. In the field of graphic design this may not be a drawback, but in the field of engineering, where accuracy is a maximum, an interpolating approach is much more useful because you can easily interpolate smooth surfaces from a few sample points (analogous to use a lofting spline or a set of French curves). Why was this decision made?

EDIT

I clarify that this is not a question about a particular software, but on the history of the development of CAD tools.

$\endgroup$
4
  • $\begingroup$ Are you saying that there is no way to draw a spline that goes through the points given? This seems like an issue with your drawing tool, not CADD in general. I know that there are CADD programs that work in both ways. $\endgroup$
    – hazzey
    Oct 21 '15 at 12:33
  • $\begingroup$ You can use a linear regression method to get the control points for the NURBS from the points you need to go through $\endgroup$ Oct 21 '15 at 12:35
  • $\begingroup$ @hazzey No, I'm not talking about particular CAD tools. I'm talking about the history of the development of CAD tools. The first digital models to draw complex curves on technical drawings were bezier curves, B-splines and NURBS, all of them controlled by a set of points which not necessarily are included in the set of curve points. $\endgroup$ Oct 21 '15 at 12:48
  • $\begingroup$ Interesting post - I've never heard of such a device, but I can see how it would have been very useful and effective during the days of the slide rule when calculating a best fit curve would have been an arduous task. $\endgroup$
    – AsymLabs
    Oct 22 '15 at 17:41
2
$\begingroup$

I think your history isn't quite right here. The first widely-used CAD systems used Bezier curves, where the end points of each section do lie on the curve. For cubic Bezier curves, the intermediate points also lie on the tangent lines at the end of each segment. This corresponds quite closely to the constraints that are implied by using a physical drafting spline as in your image.

Bezier curves are still used - for example to define the character shapes (glyphs) in digital fonts.

The next step was the realization that there are other mathematical ways to express the same curve shapes as Bezier curves, which are more convenient for some purposes. A commonly used alternative is B-splines, which can represent everything that Bezier curves can do, plus the capability of having discontinuities of slope (i.e. "kinks") along the length of the curve.

This is valuable in CAD software because there is no difference in the math required to handle a polygon made of straight line segments, or a smooth curve.

But B-splines were not the complete solution to the problem of computer geometry, because they can only represent approximations to circles, and engineers just love circles!

Nurbs (Non-uniform Rational B-splines) were the next level of generalization. The key feature of Nurbs is that they can represent curves such as circles and ellipses exactly. The math required to work with Nurbs is more complicated than for B-splines, but you can write "real-world" CAD software that uses Nurbs to define every geometrical object. Since there are now well-established software libraries to do the math that underlines Nurbs geometry, you don't need to understand the math in detail to be able to use it in developing new CAD application software.

International standards for defining and transferring CAD geometry between different computer systems, like IGES and STEP, use Nurbs geometry as their basic mathematical foundation.

Historical timeline:

  • Bezier curves (or their equivalent, Bernstein polynomials): first defined in 1912, first use in computer graphics in the 1960s.
  • B-splines: The math was actually discovered in the 19th century, but efficient computer algorithms date from the 1970s.
  • Nurbs - first computer implementation in 1989, first practical CAD systems in the 1990s.

Other types of splines have been proposed, including "minimum-energy splines" which model the behaviour of an idealized physical spline as illustrated by the OP), "minimum-curvature-variation splines", B-splines with an extra "tension" parameter to allow the user to control the amount of curvature at different parts of the curve, etc.

In reality, there is no universally accepted objective criterion for judging the "best" spline. This http://levien.com/phd/LevienSequinCAD09_014.pdf discusses some of the issues, and includes the results of a survey in which the minimum-energy spline fit was not subjectively judged to be the "best" fitted curve.

Since Nurbs or B-splines can approximate any spline shape to any required degree of accuracy, the debate about what is the "best" shape is perhaps not of critical importance - you can learn how to use whichever type of spline your CAD system provides to produce the result that you (personally and subjectively) like best. An important practical issue is the "stability" of the spline fit, i.e. whether a small changes in the control points can produce undesirable large and non-local changes in the spline shape.

$\endgroup$
6
  • $\begingroup$ Read the first part of my question. I'm comparing digital splines vs mechanical splines. They are unquestionably different and I'm asking why this difference. $\endgroup$ Oct 22 '15 at 9:55
  • $\begingroup$ Answer updated. $\endgroup$
    – alephzero
    Oct 22 '15 at 17:23
  • $\begingroup$ Minimum-energy splines model an idealized version of real splines. Some restrictions are small deformations (because of elastic theory simplifications) and frictionless scenario (real splines have more constraints than ideal ones). $\endgroup$ Oct 22 '15 at 19:57
  • $\begingroup$ The problem with control points is that you can't edit them without an interactive editing tool or without performing complex mathematical operations. An interpolation spline, on the other hand, can be generated by means of a handful of sample points of the desired path. $\endgroup$ Oct 22 '15 at 20:02
  • $\begingroup$ There is no reason why you can't define B-splines using only points on the curve. If your CAD system won't let you do that, it's a limitation of your CAD software, not of the spline formulations. It doesn't require any math beyond high-school algebra. $\endgroup$
    – alephzero
    Oct 22 '15 at 20:15
0
$\begingroup$

You are conflating two different ideas here, probably by accident. The spline curve achieved with a spline and ducks is a minimum energy curve. The defining points have support over the entire length of the spline, meaning moving one affects the entire length of the curve. That doesn't seem to be the thrust of you question, but it plays a major roll in the history of surface representation. By contrast, with nurbs and subdivision surfaces, control points exercise local control, beyond which the surface is unaffected. When designing a surface, it is often very useful to be able to say with certainty that some variation is localized. Imagine wanting to run a series of different ship bow designs through a performance model, all affixed the same aft hull.

From Local Support: Wikipedia

In mathematics, the support of a real-valued function f is the subset of the domain containing those elements which are not mapped to zero. If the domain of f is a topological space, the support of f is instead defined as the smallest closed set containing all points not mapped to zero. This concept is used very widely in mathematical analysis.

From Nurbs: Wikipedia

In many applications the fact that a single control point only influences those intervals where it is active is a highly desirable property, known as local support. In modeling, it allows the changing of one part of a surface while keeping other parts unchanged.

Now for what you did ask about - interpolation vs approximation schemes. These can apply to either case - local or non-local, but the effort required increases as the span of the variation increases (ie. using higher order nurbs).

In a comment, alephzero said

There is no reason why you can't define B-splines using only points on the curve. If your CAD system won't let you do that, it's a limitation of your CAD software, not of the spline formulations. It doesn't require any math beyond high-school algebra.

That is a bit disingenuous with respect to the algorithms needed to pull off interpolating schemes. It requires an optimization step not found in approximation schemes. These have to be implemented with some care.

From Subdivision Surfaces: Wikipedia

Subdivision surface refinement schemes can be broadly classified into two categories: interpolating and approximating. Interpolating schemes are required to match the original position of vertices in the original mesh. Approximating schemes are not; they can and will adjust these positions as needed. In general, approximating schemes have greater smoothness, but editing applications that allow users to set exact surface constraints require an optimization step.

[...]

After subdivision, the control points of the original mesh and the new generated control points are interpolated on the limit surface. The earliest work was the butterfly scheme by Dyn, Levin and Gregory (1990), who extended the four-point interpolatory subdivision scheme for curves to a subdivision scheme for surface. Zorin, Schröder and Sweldens (1996) noticed that the butterfly scheme cannot generate smooth surfaces for irregular triangle meshes and thus modified this scheme. Kobbelt (1996) further generalized the four-point interpolatory subdivision scheme for curves to the tensor product subdivision scheme for surfaces. Deng and Ma (2013) further generalized the four-point interpolatory subdivision scheme to arbitrary degree.

For free-form design, the approximation technique is easier to implement. The control points need to be chosen with care by the designer in both cases, but it is easier to understand why you have to exercise care with the approximation techniques. For importing a surface from another format, interpolation techniques may be desirable, at least to form an initial coarse mesh, with an operator putting these in the right place for the job.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.