Approach for Approximating Arbitrary Curves by NURBS

Ling Huang Jianfeng Zhen Xinxiong Zhu

（School of Mechanical Engineering & Automation,

Beijing University of Aeronautics &
Astronautics, Beijing, 100083）

**Abstract:** All
curves in the CAD/CAM system should be represented by NURBS. This paper presents an
algorithm for approximating arbitrary curve by NURBS curve meeting the given
tolerance with least number of data. It is the basis of representing offset
curve(s) and surface/surface intersection curves in NURBS form and has been applied in the commercial CAD/CAE/CAM
software system – CAXA-ME.

NURBS have become the de
facto standard for the representation, design and data exchange of geometric
information processed by computers. All the curves in our CAD/CAM system should
be represented by NURBS. For all elementary analytic curves，such
as line, arc and conics, can be represented by NURBS precisely. But a number of
advanced analytic and geometric curves widely used in free-form modeling, can’t be represented by
NURBS precisely, for example:

l
Surface/surface intersection curves ( Fig.1.a ).

l
Offset curves (
Fig.1.b ).

l

Implicit curves or curves represented by formulas, for example( Fig.1.c ):

(a) Intersection curve
(b) offset curve (c) formula represented curve

Fig.1.
Curves need to be approximated by NURBS

Those
curves can only be approximated by NURBS within a given tolerance.

This memorandum introduces a new method for approximating arbitrary
curves called original curves by NURBS curves applying the techniques of curve
fitting and error estimation. Given an arbitrary original curve by parametric
representation (for example, offset curve) or by geometric equations (for
example, surface/surface intersection curve), the goal of the algorithm is to
construct a NURBS curve
approximating the original curve with least numbers of segments in terms
of the maximum deviation no more than the given tolerance. All positions and
derivatives on the original curve can be calculated properly.

The procedure of approximating an
arbitrary curve by a NURBS curve is as follows:

l
**Step1**: Calculate the key points on original
curve and divide it into many monotonic intervals.

l
**Step2**: Construct a NURBS curve fitting the
sample points (including key points) and get a candidate approximation curve.

l
**Step3**: Estimate the deviation between the original curve and the candidate NURBS
curve in every interval and check if the deviation is less than the
given tolerance E.

l
**Step4**: If all the deviations are less than
tolerance E, the candidate NURBS is accepted. Otherwise, go to step5.

l
**Step5**: Add new data point(s) into the sample points array at interval(s) where
the deviation exceeds the given tolerance E. Go to step 2.

See Fig.2 and Fig.3, The
key points on a curve, such as cusps,
inflections and extremes, subdivide the curve
into many monotonic intervals. We consider that the key points can reflect the main shape of the curve. It can be seen that the curve only interpolating
the key points
is almost the same as the original one. So the key points on a curve are important and helpful to the
approximation procedure.

Fig.2. Key points on curve

Many achievements can be used to calculate the key points on curves. [Stone’89] analyzed the key points on parametric cubic curves by expressing the curve as a linear combination of control points and transforming it to the “canonical curve”. [Manocha’92] presented an algorithm to compute the proper parameterization of a curve and determined the cusps by the vanishing of the first derivative vector. [Manocha’92] also used the regular parameterizations to analyzed the inflection points.

Applying the algorithms presented by those authors, we calculate
all the cusps and inflection points on the original curve which are denoted as points _{} and unit tangent vectors _{} at _{}. These points serve
as the point array for constructing the initial candidate NURBS curve.

We first locally interpolate points by cubic Bezier segments and then compose all the Bezier segments to a candidate NURBS curve by selecting a suitable knot vector.

Given points _{} and unit tangent vectors _{} at _{}, we can construct a
number of cubic Bezier curve segments, _{}, so that _{} and _{} are the endpoints of _{}. Neighboring
segments are joined together with _{} continuity. Let _{} denotes the
control points of the Bezier segments _{} which
interpolate points of _{} and _{} and tangent
vectors _{} and _{}, _{}. Thus _{}, _{}, and _{} and _{} are unknowns.
The Bezier segments can be represented as follows:

_{}, _{} (
1 )

It is possible to
construct a cubic Bezier curve _{} satisfying the following constraint:

_{} (
2 )

where
_{}, _{} and _{} are the derivatives of the cubic Bezier
curve at parameters 0, _{} and 1,
respectively.

According to the properties of the derivatives at the end points of a cubic Bezier curve, Equation ( 2 ) implies that

_{} _{} ( 3 )

_{} (
4 )

where
_{}, are the first derivatives
of the cubic Bernstein basis function. Combining Equations ( 2 ), ( 3 )
and ( 4 )，we can get two real solutions for _{}. Substituting the positive solution into Equation ( 3 )
yields the desired two inner control points _{} and _{}. Every segment of _{} can be generated
by applying this algorithm and the neighboring
segments are joined together with _{} continuity. The
Bezier segments can be composed to a NURBS curve by selecting a suitable knot
vector. Applying the curve fitting
algorithm described, we can get a candidate NURBS curve based on the sample
points, consisting of key points and the point(s) added in interval(s) where
the deviation is greater than the given tolerance E.

The deviation between the candidate curve and the original one should be estimated. All the points interpolated by the NURBS curve are calculated from the original curve. Obviously, the candidate NURBS curve goes through those points precisely. So we should only estimate the deviation in the corresponding interval(s).

As shown in Fig.3, the dashed curve is the one interpolating key points and the real curve original one. Apparently, there is a maximum deviation between the approximated and the original curves in an interval. For convenience, we can consider that the maximum deviation in every interval is located at the point where the parameter value is the average of those corresponding to two adjacent interpolating points, such as the point M in the interval between points A and B on the original curve as shown in Fig.4.

Then, apply Equation ( 4 ), project point M to candidate curve
and get point _{}. _{} is the distance from point M to the candidate curve
and can be considered the maximum deviation in interval AB. The maximum
deviation of all intervals can be calculated by:

_{} (
5 )

Fig.3. Curve interpolating key
points Fig.4. Max deviation between two curves

If the maximum deviation
calculated by Equation ( 5 ) is less then the given tolerance, the
procedure stops and the candidate NURBS curve is the right one. If the deviation in some interval(s) exceed(s) the given tolerance, the
interval(s) should be subdivided. For example, if _{} is less than the
given tolerance, the candidate curve in interval AB meets the tolerance
requirement; otherwise, we should
subdivided interval AB to AM and MB by adding a point M to the initial point array that should be interpolated again. Estimate all the deviations
interval by interval, add point(s) in
interval(s) where the deviation does not reach the tolerance and generate a new
NURBS curve. Repeating the procedure, we can get the candidate NURBS curves
with less and less deviation. The procedure goes repeatedly until a
satisfied curve is obtained.

We have applied the algorithm to the NURBS representations of surface/surface intersection curve, offset curve and formula represented curve as show in Fig.5, Fig.6 and Fig.7 respectively. This algorithm has been incorporated into our commercial CAD/CAE/CAM software system —CAXA-ME.

Fig.5. Approximation
of Surface/surface intersection curve

(a) The equation
of the original curve (b) The curve approximated by NURBS

Fig.6. Approximation
of formula represented curve

Fig.7. Approximation
of offset curve

[1]
Piegl,L. and Tiller,W., The NURBS Book, Springer, 1995.

[2]
Stone,M.C. and DeRose,T.D., A Geometric
Characterization of Parametric cubic Curves, ACM Transaction on Graphics,
Vol.8, No.3, 1989, 147-163.

[3]
Manocha,D. and Canny,J.F., Detecting Cusps and
Inflection Points in Curves, Computer Aided Geometric Design, 9(1992),1-24.