04.04.2023

C3D Kernel: Curve Extension

Both the C3D kernel and the KOMPAS 3D computer-aided design (CAD) solution are rapidly gaining popularity. To support this trend, we improve the product functionality by introducing new features. One such feature is the operation that extends a 3D curve by a given length in a metric space.

Suppose there is some curve of lenght L. Get a curve of length L+Δl (Δl is required to be set). At that the original curve must be a part of a new one. A new segment is added either before the curve beginning (we will refer to this case as “start extension") or after the end (“end extension") of the original curve.

Curve Extension Operation

Possible extension options

Please note that the API (Application Programming Interface) for the new functionality supports spatial (3D) curves only. HoweverC3D kernel categorizes curves on planes as 3D curves as well. Therefore, the software implementation of this operation is also applicable to planar2D) curves. For obvious reasons, such curves (2D and 3D) should not be closed. After extending a 2D curve, the resulting curve is putted into the same plane as the original one.

Note that 2D curve is included to the surface curves. In this case, the surface curve can be extended by extending the respective 2D curve. This will be further discussed below.

As requested, in order to provide the required smoothness value, we implemented three curve extension ways.

  1. Extension by tangent (the linear way. Here we create the line segment tangent to the source curve at the extension point. After that, we shall shift by the given length from this point along it (the segment). This option guarantees the G1 smoothness at the extension point.
  2. Extension by arc (circular method). In terms of mathematics, it is more correct to call it "the osculating circle method”. We create a circle with a radius equal to the curvature radius at the extension point. The plane, in which this circle is located, is defined by the vectors t − n of the Frenet trihedron (the orthonormal system of vectors: tangent (t), normal (n) and binormal (b)). The plane passes through the point of extension. This method of extension provides at least C2 smoothness.
  3. "Same curve” extension (“natural method"). The method in a nutshell (respect to use parametric representation of curves and surfaces in C3D): "Maintain the equation of the original curve while modifying only the range of the parameter (domain)".

Fig. 1 shows the results of each extension method (both start and end) for a 2D curve.

C3D Kernel: Curve Extension, photo 1
Fig. 1 – The result of three ways of curve extension: "by tangent" (red), "by arc" (purple) and "same curve" (brown).
The original curve is blue.

The first two methods are well known (and can be found in mathematical textbooks), so they are not of great interest. Therefore, later we will consider only the natural extension way.

Note that NURBS-curves are extended (it will be explained below) without changes their domain (more precisely, we re-parameterize the result to obtain the same domain as that of the original curve).

Another feature of the natural extension method is that the type of source and resulting curves may be different (that is why "the same curve" is somewhat misleading). In some cases, the analytical definition of the curve is challenging or the equation’s parameter domain is limited. Then we do not extend the original curve but attach a NURBS segment to it in such a way that the smoothness at the junction point is not worse than C3 (Fig. 1 shows the curve extended with this very method). The result is a contour with several segments. For brevity, we will call this extension method (with a NURBS segment attachment a "general-type extension".

Extension of a curve based on another curve

A common example of a such curve is an offset curve. It is a curve, each point of which is obtained by shifting the point in some basis curve by a certain vector. The vector may be constant (in magnitude and direction) or a function of the basis curve parameter. An example of an offset is shown in the Fig. 2.

C3D Kernel: Curve Extension, photo 2
Fig. 2 Offset curve (green). The basis curve is blue.

There are two extension options here. We will designate them as "Common Natural" and "Base Natural". These two options are different only when applied to the specified curve types (curves based on other curves). For other curve types choose one or the other option leads to the same result.

The Common Natural extension option was presented earlier. We just add that if a curve is based on another curve, it is always extended by general-type extension method. The only feature is that the NURBS segment will be attached not to the basis curve, but to the curve being extended.

The essence of the Basic Algorithm is that the original curve is extended via the basis curve. After that, the extended basis curve is treated just like the original one. This algorithm is quite tricky and is not yet commercially available as a C3D kernel feature.

Note that a truncated curve (a fragment of the basic curve) is always (!) extended by "base natural" algorithm. Initially, it is extended to the basic curve boundary. If the required length is not achieved, the base curve is lengthened according to its type.

Other Extension Parameters

It follows from the above that the algorithm has two key input parameters: the extension way and the extension length. The other input parameters are listed below.

1. Allow closure (Boolean). A curve can become close after extention. In real-life problems, closed curves are not always suitable. For example, consider a shell (Fig. 3). If this parameter is set to false, the curve will never being closed during extention, i.e. there will always be a gap between its ends. If this parameter is set to true, the curve will be extended until it is closed. If the curve cannot be closed when extended, then this parameter is irrelevant.

C3D Kernel: Curve Extension, photo 3
Fig. 3 A shell. There should always be a gap.

2. Extension along the surface (Boolean). A curve on a surface can be extended as 3D-curve (by general-type extension method) or via extending the respective 2D curve and putting the result on the same surface. For brevity, we will call the second approach “Extension along the surface”.

The difference between these two approaches is shown on Fig. 4. It shows a surface of revolution with an arbitrary surface curve on it (blue). In both cases, the curve is extended by arc. If we extend it as a 3Dcurve, the extending fragment (purple) will be an arc of a circle, but it may be detached from the surface. When extending along the surface, the result curve always lies on the surface, but the extended segment (orange) may have some unusual shape.

C3D Kernel: Curve Extension, photo 4
Fig. 4 Extension as 3D-curve or "along surface" by arc method. The original curve is blue.

Extension of a NURBS with natural method

As an example, let us consider extension of a NURBS with natural method. First, we focus on the extension of a non-rational NURBS curve. We will show that the algorithm can be easily tweaked to extend rational NURBS curves.

We assume the reader is familiar with spline and in particular NURBS curve. For more information please refer to [1] and [2].

One way to implement the algorithm presented below is to get all necessary formulas for four-degree NURBS (as an example). If we have a spline of a different degree, we can apply the known algorithm of increase/decrease degree of any NURBS to become a fourth-degree spline. Finally we will apply the same algorithms to the resulting curve in order to obtain a NURBS with the same degree as the source one. However, we took another approach. That is...

Non-Rational NURBS Extension

Let us remind you that a non-rational NURBS of the degree p is a piecewise-defined curve. Each component of its radius vector is a polynom of the p−1 degree. Generally, the radius vector of the curve point, which corresponds to the parameter τ can be expressed as follows:

C3D Kernel: Curve Extension, photo 5

where {Pi} is the vector of spline control points. The knot-vector {ti} specifies the boundaries of each span. It defines the NURBS basis functions as follows:

C3D Kernel: Curve Extension, photo 6

When a NURBS curve is extended, its span is extended with the same polynomial relationship applied to the correspond extension point. The biggest challenge is to deduct this relationship for an arbitrary NURBS curve. The C3D kernel solves the problem by a Taylor series expansion in the neighborhood of the extension point. Since the relationship is polynomial, a finite number of series elements is sufficient to restore the exact, not approximate, relationship.

As the analytical definition for the extended end is obtained, we move along the curve by the given metric length Δl>0. Solving the equation (3) numerically, we have to find necessary intergration limit: t0' for a start extension (provided that t0 is the infimum of the curve domain) or t0 for an extension at the end (provided that t0' is the supremum of the curve domain).

C3D Kernel: Curve Extension, photo 7

After a new boundary of the extended curve is found, we can recompute the knot vector of the resulting NURBS curve and recompute its basis functions (because basis functions depend on the NURBS knot vector only). When the basis functions are known, one can recalculate the control points so that the extended spline segment coincides with the original spline segment.

Now the extension problem is solved: we obtained the knot vector and vector of poles for the extended non-rational NURBS spline. This is sufficient to define the spline. Fig. 5 shows an example of the original and extended NURBS splines (both start/end extended).

C3D Kernel: Curve Extension, photo 8
Fig. 5 Non-rational NURBS extension. Original spline: red. Extended spline: orange.

Rational NURBS Spline Extension

The key difference between rational and non-rational NURBS splines is that in rational ones each control point Pi has its weight wi>0. The radius vector of each curve point is expressed as:

C3D Kernel: Curve Extension, photo 9

When all the control point weights are equal to 1, we obtain the non-rational NURBS spline described above. For a rational spline, we also have piecewise-defined curve and (as for non-rational one) must restore it for extending fragment. However, we should take into account the fact that correspond functions are not polynomial. They are rational: both numerator and denominator are polynoms. Therefore we will not be able to with finite number of Taylor series members.

We can reduce the problem to the one we already solved (for non-rational NURBS) by identifying the dependence not for the entire curve, but for the both expressions: numerator and denominator. If we need to compute the derivatives of the curve equation (as in (3)), they can be obtained via numerator/denominator derivatives.

After reconfiguring the knot span and recalculating the basis functions, we need to achieve a coincidence of polynomial dependence for the denominators of the initial and extended NURBS curves (they behave as polynomials, so we proceed just like with a non-rational spline). In this way, we can find the weights vector of the extended spline. By substituting the weights into the numerator of the extended NURBS curve equation on the condition that the numerator is identical to that of the original spline, we can find the missing control point vector.

So far, we found the knot vector, the control point vector, and the weights vector for the resulting (extended) rational NURBS spline. This is sufficient to define the spline unambiguously. The problem is now solved.

Now we can see the rational NURBS spline extension algorithm is essentially the same as the one for non-rational splines, but it includes some extra steps. Fig. 6 shows the original and extended splines.

C3D Kernel: Curve Extension, photo 10
Fig. 6 A rational NURBS spline extension. Original spline: red. Extended spline: orange.

To conclude, let us note that any NURBS spline (both rational and non-rational) "straightens out" (its curvature tends to zero) at infinity. This fact has rigorous mathematical proof, but it is beyond the scope of this article. Let us show only how this fact affects the extension of a cylindrical helix converted to NURBS. It may seem that the extension should be made by adding new convolutions but the actual result is something different (see Fig. 7).

C3D Kernel: Curve Extension, photo 11
Fig. 7 A NURBS curve straightening as while start/end extending.
Original curve (NURBS converted from the cylindrical helix): blue. Extended curve: red.

Conclusion

This new functionally has been implemented to satisfy requests of our users and customers. Therefore, in this article, we tried to avoid ranting about its complexity and significance. It has been done and available now.

Certainly, we omitted many implementation details and challenges. We presented an algorithm for NURBS curve extension only, while we had to cover many other types of curves by separating special cases.

There is a roadmap for further enhancement. Still, the C3D kernel and KOMPAS 3D users can use it out right now: the curve extension functionality is already available. We will keep improving it.

References

[1] Nikolay Golovanov , Geometric Modeling: The mathematics of shapes, CreateSpace Independent Publishing Platform; Reprint edition (December 24, 2014).

[2] L. Piegl and W. Tiller, The NURBS Book, Springer-Verlag, 1997.

Nikolay Bukhaliv, mathematician Software Developer, C3D Labs
Author:
Nikolay Bukhaliv
Mathematician Software Developer, C3D Labs
Share
Up