of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Degree Elevation of Interval B-Spline Curves

Category:

Speeches

Publish on:

Views: 2 | Pages: 6

Extension: PDF | Download: 0

Share
Description
International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 9 Degree Elevation of Interval B-Spline Curves Abstract This paper presents an efficient method for degree
Transcript
International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 9 Degree Elevation of Interval B-Spline Curves Abstract This paper presents an efficient method for degree elevation of interval B-spline curves. The four fixed Kharitonov's polynomials (four fixed B-spline curves) associated with the original interval B-spline curve are obtained. The method is based on the matrix identity. The B-spline basis functions are represented as linear combinations of the B-splines of a higher degree. The process of degree elevation is applied to the four fixed B-spline curves of degree to obtain the four fixed B- spline curves of degree without changing their shapes. Finally the new interval vertices *, -+ of the new interval polygon are obtained from vertices of the new fixed polygons of the four fixed B-spline curves. An illustrative example is included in order to demonstrate the effectiveness of the proposed method. Index Term Computer graphics, CAGD, degree elevation, interval B-spline curves. O. Ismail, Senior Member, IEEE very attractive properties such as compactness and continuity, local shape controllability, and invariance to affine transformations. The B-spline curve overcomes the main disadvantages of the Bezier curve which are (1) the degree of the Bezier curve depends on the number of control points, (2) it offers only global control, and (3) individual segments are easy to connect with continuity, but is difficult to obtain. The B-spline curve is an approximating curve and is therefore defined by control points. However, in addition to the control points, the user has to specify the values of certain quantities called knots. They are real numbers that offer additional control over the shape of the curve. I. INTRODUCTION The curve modeling plays an important role in geometric modeling because it can be generalized into the development of surfaces and solids. There are several kinds of polynomial curves in CAGD, e.g., Bezier 1], 2], 3], 4] Said-Ball 5], Wang-Ball 6], 7], 8], B-spline curves 9] and DP curves 10], 11]. These curves have some common and different properties. All of them are defined in terms of the sum of product of their blending functions and control points. They are just different in their own basis polynomials. In order to compare these curves, we need to consider these properties. The common properties of these curves are control points, weights, and their number of degrees. Control points are the points that affect to the shape of the curve. Weights can be treated as the indicators to control how much each control point influences to the curve. Number of degree determines the maximum degree of polynomials. In different curves, these properties are not computed by the same method. To compare different kinds of curves we need to convert these curves into an intermediate form. Typically, a curve construction is based on a sequence of the given control points that approximates the shape of this curve. In other words, the specified control points influence the appearance of the curve. Besides, this curve will pass through the first and the last endpoints but does not pass through every interior point. In addition, these polynomial curves can also be differently specified according to their blending functions (polynomials), e.g., Bezier, and B-spline curves. The models of these curves are also dissimilar from their different polynomial formulations. The B-splines stand as one of the most efficient curve representation and possess The author is with Department of Computer Engineering, Faculty of Electrical and Electronic Engineering, University of Aleppo, Aleppo, B-spline methods for curves and surfaces were first proposed in the 1940s but were seriously developed only in the 1970s, by several researchers. They have been studied extensively, and considerably extended since the 1970s, and much is currently known about them. The designation B stands for Basis, so the full name of this approach to curve and surface design is the basis spline. Why would we want to elevate the degree of a B-spline curve? (1) In general, it is not possible to display the characteristics of a curve of degree with a curve of degree. For example, we cannot describe a cubic curve with a quadratic function. Suppose that we are unable to produce a curve of the desired shape with a degree B-spline curve. One option is to use a B-spline curve of higher degree. (2) Degree elevation has important applications in surface design: for several algorithms that produce surfaces from curve input, it is necessary that these curves be of the same degree. Using degree elevation, we may achieve this by raising the degree of all the input curves to the one of the highest degree. (3) Another application lies in the area of data transfer between different CAD/CAM or graphics systems: Suppose you have generated a parabola and you want to feed it into a system that only knows about cubics. All you have to do is degree elevate your parabola. In some cases a designer has to link two or more B-spline curves of different degree to form a new curve or surface. In both situations the set of input curves must have a common degree. Such a problem can be solved either using degree elevation 12], 13] or reduction 14]. Both solutions should not affect the shape of curves. Although in general, degree reduction is an approximation of an input curve. Therefore, the only way to link several B-spline curves of different degree without affecting their shape is degree elevation. International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 10 An interval B-spline curve is a B-spline curve whose control points are rectangles (the sides of which are parallel to coordinate axis) in a plane. Such a representation of parametric curves can account for error tolerances. Based upon the interval representation of parametric curves and surfaces, robust algorithms for many geometric operations such as curve/curve intersection were proposed 15]. The series of works by the authors of 15] indicate that using interval arithmetic will substantially increase the numerical stability in geometric computations and thus enhance the robustness of current CAD/CAM systems. Several methods have been given for degree elevation of fixed B-spline curves 16], 17], 18], 19] and 20], the fastest of which is the algorithm in 18]. Unfortunately, their algorithm suffers from being complicated and hard to implement. On the other hand, the algorithm in 19] is more straightforward, and easier to understand. It splits the B-spline curve into Bezier curve pieces, raises the degree of each piece, and then recombines the degree-elevated Bezier curves to produce the new B-spline curve. The algorithm in 20] has the benefits of being both simple to implement and fast. It takes the approach of computing the new control points using a series of knot insertions followed by a series of knot deletions. In this paper an efficient method for degree-elevating of interval B-spline curves is presented. This method is based on matrix identity and a method for degree elevation of the interval Bezier curves can be regarded as the special case of the given method. This paper is organized as follows. Section contains the basic results, whereas section presents a numerical example, and the final section offers conclusions. II. THE BASIC RESULTS An interval B-spline curve of order is defined by a linear combination of B-spline basis functions as:, - where, - are the interval control points, and for are B-spline basis functions defined recursively on the knot vector * +, where and for between and. When for, is called a uniform B-spline. Otherwise it is called a non-uniform B- spline. Since a B-spline curve is a piecewise polynomial curve, it is possible to elevate its degree from to, where is an integer greater than or equal to. Thus, there must exist interval control points, - and a new knot vector * + such that:, - where is the number of interval control points of and are the B-spline basis functions of order defined on the knot vector * +. The interval curves and have the same geometry and parameterization. The computation of,, - and is referred to as elevating the degree of the curve. The four fixed Kharitonov's polynomials (four fixed B- spline curves), - associated with the original interval B- spline curve are: The four fixed Kharitonov's polynomials (four fixed B-spline curves) can be written as follows: The four fixed Kharitonov's polynomials (four fixed B- spline curves), - associated with the elevated interval B- spline curve are: The four fixed elevated Kharitonov's polynomials (four fixed elevated B-spline curves) can be written as follows: International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 11, The normalized local support B-spline basis functions of degree are defined by the following deboor-cox recursive formula 22], 23]. { {, -, - } } with the convention that, where are the knots and. It is clear that B-spline basis functions can be represented as linear combinations of the B-splines of a lower degree. In practice, the B-spline basis functions can be represented also as linear combinations of the B-splines of a higher degree. Lemma 1. Let. Then Equation can be proved using a divided difference identity 24], 25]. Lemma 2. The following identity is satisfied for B-spline functions of degree : Thus, ] Using the relation between the normalized local support B- spline basis functions of degree and the divided differences, one can obtain equation from equation. Lemma 3. Nonuniform B-spline basis functions of degree can be represented as linear combinations of B- splines of degree : where, ] { ] ] } ] { } Proof: This lemma can be proved using straightforward calculations 25] according to the definition of the divided differences, one can get,, -, - { } Proof: Let, respectively. One can obtain the following equations from Lemma 3., - International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 12 where, ] ] ] where is a, -, - matrix. ] ] Substituting equation into equation one can get equation. Theorem: The four fixed Kharitonov's polynomials (four fixed piecewise B-spline curves) associated with the original interval B-spline curve of degree defined by: where, ] ], - { } can be elevated from degree to, and the vectors of the new fixed control vertices associated with corresponding elevated fixed four Kharitonov s polynomials (elevated four fixed piecewise B-spline curves) can be obtained as follows: ] ( ), - ] ] ] Proof: The idea of the proof follows immediately from Lemma 3. Substituting equation into equation and it is very easy to calculate for ( ) using equation. ] is the vector of the fixed control vertices, which form the new control polygons, obtained by degree-elevating. The new control polygons for any segment of four fixed Kharitonov's polynomials (four fixed piecewise B-spline curves) have one more control vertex than the old control polygons of the same curve segment. Algorithm for the interval B-spline degree elevation Based on the equations developed above, we now give a procedural method for degree elevation of an interval B-spline curve as follows: 1. Use equation to find the four fixed Kharitonov's polynomials of degree (four fixed B-spline curves) associated with the original interval B-spline curve. 2. Apply equation to four fixed Kharitonov's polynomials (four fixed B-spline curves) to get the vector of the fixed control vertices ] for ( ) and of the elevated four fixed Kharitonov's polynomials (four fixed B-spline curves). 3. Finally the interval control points of the elevated interval B-spline curve can be obtained as follows:, - ( ) ( ) ] ( ) III. NUMERICAL EXAMPLE Consider the interval B-spline curve of degree (order ) defined by the two interval control points: International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 13 whose knot vector is defined by * +. It is required to elevate the degree of the given interval B- spline curve defined by them to 2 without changing its shape. The fixed control points of the elevated four fixed Kharitonov's polynomials (four fixed B-spline curves) are obtained after applying the algorithm explained in section as follows: The refined knot vector is defined by * +. Finally the interval control points of the elevated interval interval B-spline curve are found from the elevated four fixed Kharitonov's polynomials (four fixed B-spline curves) after applying the proposed algorithm as given below. IV. CONCLUSIONS An efficient algorithm to elevate the degree of the interval B-spline curve is presented in this paper. The four fixed Kharitonov's polynomials (four fixed B-spline curves) associated with the original interval B-spline curve are obtained. The method is based on the matrix identity. The B- spline basis functions are represented as linear combinations of the B-splines of a higher degree. The process of degree elevation is applied to the four fixed B-spline curves of degree to obtain the four fixed B-spline curves of degree without changing their shapes. Finally the new interval vertices *, -+ of the new interval polygon are obtained from vertices of the new fixed polygons of the four fixed B-spline curves. In general, it is not possible to display the characteristics of a curve of degree with a curve of degree. Degree elevation has important applications in surface design. Another application lies in the area of data transfer between different CAD/CAM or graphics systems. The only way to link several B-spline curves of different degree without affecting their shape is degree elevation. REFERENCES 1] P. Bezier, Definition Numerique Des Courbes et I , Automatisme, Vol. 11, pp , ] P. Bezier, Definition Numerique Des Courbes et II , Automatisme, Vol. 12, pp , ] P. Bezier, Numerical control, Mathematics and Applications, New York: Wiley, ] P. Bezier, The Mathematical Basis of the UNISURF CAD System, Butterworth, London, ] H. B. Said, A generalized Ball curve and its recursive algorithm , ACM. Transaction on Graphics, Vol. 8, No. 4, pp , ] A. A. Ball, CONSURF Part 1: Introduction to conic lofting tile, Computer Aided Design, Vol. 6, No. 4, pp , ] A. A. Ball, CONSURF Part 2: Description of the algorithms, Computer Aided Design, Vol. 7, No. 4, pp , ] A. A. Ball, CONSURF Part 3: How the program is used, Computer Aided Design, Vol. 9, No. 1, pp. 9 12, ] G. J. Wang, Ball curve of high degree and its geometric properties , Applied. Mathematics: A Journal of Chinese Universities Vol. 2, pp , ] J. Delgado and J. M. Pena, A linear complexity algorithm for the Bernstein basis, Proceedings of the 2003 International Conference on Geometric Modeling and Graphics (GMAG 03), pp , ] J. Delgado and J. M. Pena, A shape preserving representation with an evaluation algorithm of linear complexity, Computer Aided Geometric Design, pp. 1-10, ] O. Ismail, Degree elevation of rational interval Bezier curves . 'Proc., The Third International Conference of E-Medical Systems, Fez, Morocco, ] O. Ismail, Degree elevation of interval Bezier curves using Legendre-Bernstein basis transformations . International Journal of Video & Image Processing and Network Security (IJVIPNS), Vol. 10, No.6, pp. 6-9, ] O. Ismail, Degree reduction of interval Bezier curves using Legendre-Bernstein basis transformations . The 1st Taibah University International Conference on Computing and Information Technology (ICCIT 2012), pp ] G. Shen and N. M. Patrikalakis, Numerical and geometrical properties of interval B-spline, International journal of shape modeling, Vol. 4, No. (1/2), pp , ] H. Prautzsch, Degree elevation of B-spline curves, Computer Aided Geometric Design, Vol. 18, No. 12, pp , ] E. Cohen, T. Lyche, and L. Schumaker, Algorithms for degree raising of splines, ACM Trans. Graph., Vol. 4, No. 3, pp , ] H. Prautzsch, and B. Piper, A fast algorithm to raise the degree of B-spline curves, Computer Aided Geometric Design, Vol. 8, No. 4, pp , ] L. Pigel, and W. Tiller Software-engineering approach to degree elevation of B-spline curves, Computer-Aided Design, Vol. 26, No. 1, pp , ] W. Liu, and Wayne, A simple, efficient degree raising algorithm for B-spline curves, Computer Aided Geometric Design, Vol. 14, No. 7, pp , ] V. L. Kharitonov, Asymptotic stability of an equilibrium position of a family of system of linear differential equations , Differential 'nye Urauneniya, vol. 14, pp , ] C. deboor, On calculating with B-splines, J. Approx. Theory, Vol. 6, pp. 50, ] M. G. Cox, The numerical evaluation of B-splines, J. Inst. Math. & Applic., Vol. 10, pp. 134, ] E. T. Y. Lee, Remark on an identity related to degree elevation, CAGD, Vol. 11, pp. 109, ] F. Yamaguchi, Curves and surfaces in computer aided geometric design, Springer-Verlag, O. Ismail (M 97 SM 04) received the B. E. degree in electrical and electronic engineering from the University of Aleppo, Syria in From 1987 to 1991, he was with the Faculty of Electrical and Electronic Engineering of that university. He has an M. Tech. (Master of Technology) and a Ph.D. both in modeling and simulation from the Indian Institute of Technology, Bombay, in 1993 and 1997, respectively. Dr. Ismail is a Senior Member of IEEE. Life Time Membership of International Journals of Engineering & Sciences (IJENS) and Researchers Promotion Group (RPG). His main fields of research include computer graphics, computer aided analysis and design (CAAD), computer simulation and modeling, digital image processing, pattern recognition, robust control, modeling and identification of systems with structured and unstructured uncertainties. He has published more than 62 International Journal of Video&Image Processing and Network Security IJVIPNS-IJENS Vol:14 No:02 14 refereed journals and conferences papers on these subjects. In 1997 he joined the Department of Computer Engineering at the Faculty of Electrical and Electronic Engineering in University of Aleppo, Syria. In 2004 he joined Department of Computer Science, Faculty of Computer Science and Engineering, Taibah University, K.S.A. as an associate professor for six years. He has been chosen for inclusion in the special 25th Silver Anniversary Editions of Who s Who in the World. Published in 2007 and Presently, he is with Department of Computer Engineering at the Faculty of Electrical and Electronic Engineering in University of Aleppo.
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks