ONE METHOD FOR REPRESENTING AN ARC OF ELLIPSE BY A NURBS

CURVE
Emiliyan Petkov, Liuben Cekov

University of Veliko Turnovo, Computer Systems and Technologies Department, Veliko Turnovo 5000,
2 Teodosii Turnovski str., tel.062 649831, e-mail: [email protected]
Technical University - Gabrovo, Computer Systems and Technologies Department, Gabrovo 5300,
4 Hadgi Dimitar str., tel. 066 223456, e-mail: [email protected]

Abstract: This paper offers one method for constructing an arc of ellipse – one of the conic sections, by NURBS – one of the most
popular mathematical model for representing curves and surfaces in CAGD. It also gives the analytical equations of this conic and
explains its relation with a quadratic rational Bezier curve. The developed technique is given by mathematically proved algorithms.

Key words: Computer Graphics, CAD/CAM, CAGD, Approximation, Bezier, NURBS

Introduction r
Computer-Aided Geometric Design (CAGD) is the base of
projection and construction in a number of industrial
∑M w B i i i ,r (t )
settings. CAGD is concerned with representations, β (t ) = i =0
r
(1.1)
constructions, deformations and approximations of curves
and surfaces. There is an aspiration for opening new and
∑w B
j =0
j j ,r (t )
more efficient tools for expanding the functionality of the
graphics systems.  n
Bi ,r (t ) =   t i (1 − t ) , i = 0,… , n and
r −1
We have a goal to provide new possibilities and bigger and
flexibility in designing graphic models of real objects by i
investigation of new methods, algorithms and graphics tools. t ∈ [0,1] is the polynomial of Bernstein.
Because very often the borders of the objects have forms of
conic sections, we concentrate our work on building methods β (t ) passes trough the first and the last control points and
allowing interactive modeling by ellipses, parabolas and the tangents in these points have the directions of the first
hyperbolas, as well as ellipsoids, paraboloids, hyperboloids and the last lines of the control polygon [4].
and etc. So, this task is a part of a bigger research for 1.2 General model of a NURBS curve
representing and constructing the all quadratic curves and In [5, p. 55] is given definition of a B-spline function of
surfaces by appropriate models and techniques. They should degree r . But the most often used are the normalized B-
be prepared for implanting in graphics systems. splines:
In this report we examine one of these curves – the ellipse, t − ti ti + r +1 − t
and with parabola and hyperbola we do the same in other N i ,r
(t ) =
ti + r − ti N i , r −1
(t ) +
ti + r +1 − ti +1 N (t ) ,
i +1, r −1
papers.
One of the most popular mathematical model in CAGD for 1 ti ≤ t ≤ ti +1
representing curves and surfaces is NURBS (Non-Uniform
Rational B-Spline). That is why we want to represent the N i,0 0 t ∉ [t , t ]
(t ) = (1.2)
ellipse by a NURBS curve.  i i +1

The mathematical base of the problem is given in section 1 Now one rational B-spline curve defined upon non-uniform
and 2 and it is based on the references [3,5,7]. In section 3 knot-vector in homogenous coordinates is given by
we publish the result of our research.
r −1

1. Mathematics background ∑M w N i i i ,r
(t )
(1.3)
NURBS curves is a modification of the rational B-spline γ (t ) = i =0
n −1
curves. They are obtained when special set of knots are
chosen. The knots form a numerical vector (known as knot-
∑w N
j =0
j j ,r
(t )
vector) and they are necessary to define the B-spline
function. Every curve approximates points in 2D or 3D. where M i ( xi , yi ) are control points with weights
These points are called control points and form the control
polygon. There is a relation between Bezier-Bernstein basis wi , i = 0,… , n , tj are m +1 knots for
and B-spline basis as well.
1.1 General model of a rational Bezier curve
Here is the parametric equation of one rational Bezier curve
t j ≤ t j +1 , j = 0,… , m − 1 and N i ,r (t ) is the B-spline

of degree r when r +1 control points M i ( xi , yi ) and function given by Eq. (1.2).

their weights wi are given: The definition, all characteristics and geometric properties of
the NURBS curves can be seen in [3]. Only the most
important property concerning this research will be given is an arc of ellipse. For the prove of it, you can look at [3, p.
here. 293].
Property 1.1 NURBS curve with no interior knots is a Varying w1 yields a family of conic arcs and one more
rational Bezier curve, since the N i ,r reduce to Bi ,r . convenient way to select a conic form is to specify a third
NURBS curves contain non-rational B-spline and non- point on the conic, which is attained at some parameter value
rational Bezier curves as special cases. t = 0.5 . This point is called the shoulder point of the conic
The advantage of using rational curves is that they
interpolate conic sections correctly [1,2,3,4]. It means that by
(Figure 1a). Substitution of t = 0.5 into Eq. (1.1) yields
these curves correct representation of ellipses, hyperbolas 1 w ,
S= P + 1 M1
and parabolas is possible. 1 + w1 1 + w1
1.3 Analytical representation of an ellipse (2.1)
The conic sections are the non-degenerate curves generated
by the intersections of a plane with one or two nappes of a where P is the midpoint of the cord M 0 M 2 . Let s be a
cone. These objects are very good examined [7]. They are new parameter that gives a linear interpolation between P
specified in three types of curves: elliptical, parabolic and
hyperbolic. and M 1 . Then for some value of s we have
The analytical representation of an ellipse in standard w1 s
position into orthogonal coordinate system S = (1 − s ) P + sM 1 ⇒ s = ⇒ w1 =
{ }
Oxy = O, e1 , e2 is given by the following equations
1 + w1
(2.2)
1− s
2
x y2 A circular arc of sweep angle les than 180° is also
ε : 2 + 2 = 1, a, b > 0 , (1.4)
a b represented by Eq. (1.1). For symmetry M 0 M 1M 2
 x = a.cos α (Figure 1a) must be an isosceles triangle, with
ε : , α ∈ [ 0; 2π ] . (1.5)
 y = b.sin α M 0 M 1 = M 1M 2 . Let θ = M 1M 2 P . From

2. Representing an arc of ellipse by a Bezier curve symmetry the arc M 2S is the same as SM 0 , hence the
There are a lot of techniques for building an arc of ellipse in
CAGD, but one of the most popular belongs to Farin Gerald
angle SM 2 P bisects θ. From Eq. (2.2) and the
[1] and Les Piegl [3]. They represent the arc of conic (that is properties of bisectors it follows that
defined by its endpoints and the tangents at them plus an s PS PM 2 e
intermediate point) by rational Bezier curve. w1 = = = = = cos θ (2.3)
1 − s SM 1 M 1M 2 f
They examine the quadratic rational Bezier curve for
representing an arc of conic by looking at Eq. (1.1). When
3. Building the arc of ellipse by a NURBS curve
n = 2 all conic sections could be represented because they On the base of the mathematics background we did above,
are quadratic curves as well. The parameters which influence
the representation of an arc of ellipse we shall do by finding
the form of the cure (when n = 2) are wi , i = 0,1,2 . the right place and order of the control points in the
quadratic NURBS model of a curve.
Usually, w0 = w2 = 1 are selected. It is called normal
parameterisation. Now, the form of the curve depends on
w1 ∈ ( −∞; +∞ ) . If −1 < w1 < 1 the form of the curve

Fig. 1 – a) representing an arc of circle by a Bezier curve; b)an arc of the ellipse ε;
c)an arc of the circle c represented by a Bezier curve

The conics always lie in one plain. So, let l be a plain and characterizes positive direction of visiting the points of l .
Let ε given by Eq. (1.4) be in standard position (Figure 1b).
{
K l = O, e1 , e2 } ( e = e ) a right oriented orthogonal
1 2 3.1 Determining the direction of the arc

coordinate system in it. Therefore, the couple ( e , e )

For Eq. (1.5) we have a requirement α ∈ [ 0; 2π ] , but we
1 2
could release α to vary in the range ( −∞; +∞ ) .
Therefore, varying α in the range [α s ;α e ] , for  xc = cos α p
Pc : 
 xl = a cos α p
, Pl :  and the point
α s ,αe ∈ , yields (repeatedly) turning the radius-vector  yc = sin α p  yl = b sin α p

(when α s − α e > 2π ) that builds the ellipse when α Pl could be obtained from the point Pc by the following
transformation:
changes its value from α s to α e .
 a 0
Let α s determine a point Ps ( xs , ys ) from ε with a Pl = TPc , T =   (3.1)
0 b
radius-vector rs , and αe determine a point Pe ( xe , ye ) 3.5 Building the arc γc by using the unit circle c
from ε with a radius-vector re . We know (from [7], pp. 22- We shall give a technique for constructing an arc defined by
αs and α e ( α s , α e ∈ ( −∞; +∞ ) ) of the unit circle c .
24), that 1) the vectors rs and re are lineal independent
We set the condition α s < α e , i.e. for building only a
xs ys x ys 
⇔ ∆= ≠ 0 ⇔ rang  s  = 2 and 2) positive arc. The whole arc will be divided into segments,
xe ye  xe ye  everyone of them will be not more than 90°.

(r , r )
Lets first examine the special case when
the couple is right and characterizes positive
s e α s − α e ≤ π / 2 , looking at a Figure 1c. We know that
direction of visiting ⇔ ∆ > 0, and it is left and
OPs = OPe = 1 . Let the tangents at Ps and Pe
characterizes negative direction of visiting ⇔ ∆ < 0.
Therefore, if αs < αe we have positive direction of intersects themselves at P1 . Then Ps , P1 , Pe are the control
points of the quadratic rational Bezier curve that interpolates
visiting the points of the arc, if αs > αe we have negative
 x = a cos α s
direction, and if αs = αe - the arc does not exist. Ps we the arc precisely. Ps , Pe ∈ ε ⇒ Ps :  s
 ys = b sin α s
shall call start point, Pe - end point, αs - start angle and
 x = a cos α e
αe - end angle. and Pe :  e . Let ws , w1 , we be the weights
Heuristic 3.1 Positive arc from ε (Figure 1b) we shall call  ye = b sin α e
the curve obtained by the movement of radius-vector r in of those three points. We want ws = we = 1 - for normal
positive direction from Ps to Pe when ∆>0 for parameterisation. Now, it is easy to calculate P1 . We obtain
α ∈ [α s ; α e ] . Negative arc from ε we shall call the  x = cos (α s + β / 2 ) .d
P1 :  1 . For finding w1 we do
curve obtained by the movement of radius-vector r in  y1 = sin (α s + β / 2 ) .d
negative direction from Ps to Pe when ∆<0 for the following:
α ∈ [α s ; α e ] . Let Ps Pe ∩ OP1 = Pm and P1 Pe Pm = θ (Figure 1c),

3.2 The problem Pe Pm

A continuous arc γε from ε to be represented by a NURBS
then from Eq. (2.3) ⇒ w1 = = cos θ . From
Pe P1
curve and to be determined by a, b, αs and αe . If OPe P1 and Pe Pm P1 we have:
αs < αe the arc to be built in positive direction, if
OPe P1 = Pe Pm P1 = 90 and
αs > αe - in negative direction, and if αs = αe - the arc
OP1 Pe = Pe P1 Pm ⇒
is not built.
3.3 The main idea for solving the problem PeOP1 = P1 Pe Pm = β / 2 = θ . Therefore,
First, we shall examine an arc γc given by αs and αe w1 = cos β / 2 .
from the unit circle c (Figure 1b). We shall find its
representation by NURBS curve. After that, by a suitable
Ps , P1 , Pe are the control points with the weights
affine transformation of this curve, we shall find the correct ws , w1 , we that we pass to Eq. (1.1) for n = 2 to obtain
representation of γε which is also determined by αs and the rational Bezier curve.
Now, we give the Algorithm 3.1 for building the whole arc
α e , but it belongs to the ellipse ε.
3.4 Transforming the unit circle c to the ellipse ε γc by NURBS curve, using several small segments which is
not more than 90°. We could do that relying on Property 1.1.
Let αp determine the points: Pc from the unit circle c Algorithm 3.1
and Pl from the ellipse ε . Therefore, relying on Eq. (1.5), ComputeNURBSCircularArc( α s , α e , segments, aPc [],
nNP, aK [], nNK ) {
//input: αs – start angle, αe – end engle, segments – number of aK [] , which are necessary for building the NURBS curve
segments of the whole arc by Eq. (1.3). That curve interpolates γc precisely.
//output: aPc – array of the control points, nNP – number of the
control points,
3.6 Representing the arc γε by a NURBS curve
//aK – knot-vector, nNK - number of knot-vector values
//narcs –number of the arcs of the whole arc
After we have the representation of the arc γc by NURBS
//w1 - weight of the mid-points (P1 in fig. 3.1b) of every segment curve, we could transform (relying on Eq. (3.1)) the control
buf : = α := α s − αe ; narcs := 0; points aPc obtaining aPε (Figure 2a). Also, we have to
while( buf > 0.0 ) { narcs++; buf -= π / 2; } conform the direction of the given arc. Algorithm 3.2
if( 0 < narcs && narcs < segments ) narcs := segments; contains these steps and constructs the NURBS elliptical arc
if( narcs > 0 ) { we are seeking for.
β := α / narcs; nNP := 2 * narcs + 1; w1 := cos( β / 2 ); Algorithm 3.2
aPc [ 0 ].x := cos( α s ); aPc [ 0 ].y := sin( α s ); ComputeNURBSEllipticalArc( a, b, α s , α e , segments, aPε [],
nNP, aK[], nNK ) {
aPc [ 0 ].w := 1.0; index := 0; angle := αs ;
//input: a, b, α s , α e , segments; //output: aPε , nNP, aK , nNK;
d := 1 / cos( β / 2 );
if( α s > α e ) { β s := α e ; β e := α s ; bAnglesEx := true; }
//computes every tree control points of every segment
for( int i := 1; i <= narcs; i++ ) { else { β s := α s ; β e := α e ; bAnglesEx := false;};
aPc [index+1].x := cos(angle+ β / 2 ) * d;
ComputeNURBSCircularArc( β s , β e , segments, aPc ,
aPc [index+1].y := sin(angle + β / 2 ) * d; nNP, aK, nNK );
aPc [index+1].w:=w1; aPc [index+2].x:=cos(angle+ β ); if( bAnglesEx ) ReverseOrderOfTheControlPoints( aPε );

aPc [index+2].y := sin(angle + β ); //transforms every control point of c to a control point of ε:

for( i := 0; i <= nNP-1 ; i++ ) {
aPc [index+2].w := 1; aPε [ i ].x *= a; aPε [ i ].y *= b; }
index += 2; angle += β ;} };
nNK := nNP + 1; step := 1.0; g := 0.0; After executing the Algorithm 3.2 the control points are
//computes the step of the knot-vector values: obtained in aPε [] and the values of the knot-vector in
if( nNK > 4 ) step := 1 / ( (nNK - 4) / 2 + 1 );
//computes the knot-vector values: aK [] , which are necessary for building the NURBS
for( i := 0; i <= nNK-1 ; i+=2 ) {
aK [ i ] := aK [ i+1 ] := g; g += step; } } elliptical arc by Eq. (1.3). That curve interpolates γε
}; precisely. Some examples could be seen in a Figure 2 b), c).
After executing the Algorithm 3.1 the control points are
obtained in aPc [] and the values of the knot-vector in

Fig. 2 – a) full ellipse; b) from -70° to 405° arc and the positions of the end points are changed; c) from 0° to 360° arc

Conclusion
We explained one technique for constructing NURBS References
elliptical arcs, that is useful for the computer-aided 1. Farin Gerald. From Conies to NURBS: A Tutorial and
geometric design. It makes the computer algorithms for Survey. IEEE CG&A, pp. 78-86, 1992.
representing this kind of curves effective and fast. The 2. Lee E. T. Y. Rational quadratic Bezier representation for
algorithms are developed to represent the conic of the lowest conics. Geometric Modelling: Algorithms and New Trends.
degree NURBS curve and fewest control points. For more Philadelphia: SIAM, pp. 3-19, 1987.
flexibility increasing the number of the control points and 3. Piegl Les, W. Tiller. The NURBS Book. Springer, USA,
constructing arcs for angles less than 0° and more than 360° 1997.
is possible. So designers could model elliptical forms with 4. Rogers David F., J. Alan Adams. Mathematical Elements
ease. for Computer Graphics, 2nd edition. McGraw-Hill, 1989.
In addition, a programming model for NURBS conic curves 5. Боянов Борислав. Лекции по числени методи. Дарба,
could be seen in [6]. С., 1995.
Our work is being expanded with developing new effective 6. Петков Емилиян. NURBS коники – програмен модел.
techniques for representing an arc of parabola and an arc of Международна научна конференция “УниТех’04”,
hyperbola by NURBS curves. In this way we shall have all Габрово. Сборник доклади, Том 1, стр. 359-363, 2004.
three generatrix curves that we need for representing the nine 7. Христов Милен. Аналитична геометрия. Астарта,
quadratic surfaces by NURBS. Велико Търново, 2003.