A Note On Subdivision Curves
Wieslaw Kotarski (kotarski@math.us.edu.pl) & Agnieszka Lisowska (alisow@ux2.math.us.edu.pl)
Institute of Computer Science
Silesian University
Bedzinska 3941-200 Sosnowiec, Poland

(Abstract)
In this worksheet we present subdivision method applied to three non-collinear control points. It will be demonstrated that depending on the form of subdivision matrices quadratic B-spline, quadratic B?zier and fractal- like curves or other fractal objects can be generated.  

1.Introduction 

 

De Rham in 1947 [2] investigated the corner cutting  algorithm presented in Fig.1. Assume, that three non-collinear points ,  and two parameters u, v, such that 0 < u, v < 1, are given . Two segments [] and  [] are divided into three parts in the ratios u:1-(u+v):v creating new points  and   , respectively. 

 

 

 

Fig. 1. Cutting corner algorithm. 

 

 

Dependency between points  and    and  can be represented, using subdivision matrices L and R, in the following form: 

 

 

 

After several iterations of corner cutting algorithm with suitable choice of parameters u and v one obtains a good approximation of a smooth curve. It is known from [2] that for u = v = one  gets curve. Later, de Rham in 1956 discoverd that by taking u = v = one  gets curve. That fact was reinvented by Chaikin [1] in 1974. Chaikin additionally proved that the obtained curve is a quadratic B-spline and he was the first who introduced geometric methods to Computer Aided Design.  

 

In early 1960s de Casteljau and B?zier [11] suggested another  corner cutting algorithm presented in Fig. 2. Now, we apply midpoint strategy. It means that on every segment we put a new point in its middle. 

 

 

Fig. 2. De Casteljau algorithm. 

 

 

Dependency between points and and  can be given in the form: 

 

 

 

 

 

That scheme produces a quadratic B?zier curve. 

 

In 1990 van Overveld [10] showed that subdivision matrices can be perturbated and using them it is possible to get  fractal- like cuves that are perturbated cubic ones. Subdivision matrices are perturbated in such a way that it is possible to preserve curve continuity and tangency at first and last points. We demonstrate that the same effect can be get for quadratic curves. 

 

Consider general form of subdivision matrices: 

 

 

 

We postulate the following conditions  to be satisfied: 

 

A) the curve has to go through points and , so then  

 

 

 

B) tangency to the curve at points and   requires 

 

 

 

where parameters 0 ≤ a, b ≤ 1. 

 

C) continuity of the curve needs 

 

 

 

where parameters 0 ≤ c, d ≤ 1.  

 

D) Matrices L and R are assumed to be Markovian ones. That means that their coefficients in rows sum up to 1. It assures affine invariance of the generated curves by such subdivision matrices. 

 

Summing up, subdivision matrices L and R with four parameters a, b, c, d generate affine invariant continuous curve that passes through points ,and is tangent at those points. Those subdivision matrices have the following form:   

 

 

 

 

 

At the end of this section  we recall the result by Goldman [3], [9] that states that every subdivision implies the following form of IFS: 

 

IFS ={ 

 

where 

 

 

 

 

 

 

is the matrix of control points , is the inverse matrix to P. So then, points  should not be collinear.  

 

In this worksheet we generate curves or other fractal shapes using deterministic algorithm used to IFS  defined by subdivision matrices with different parameters. The given below Maple programs are similar to those presented in earlier authors' worksheet  [4] - [7].  

   

 

2. Maple Program 

 

 

 

 

Definition of homegeneous point in  

 

 

 

Point Transformation 

 

 

 

Polygon Transformation 

 

 

 

Iterated function system (the number of iterations, list of transformations and initial polygon should be given)
 

 

 

Procedure 1 

(u, v are parameters of subdivision matrices, n- number of iterations, initial polygon is a triangle with vertices ) 

 

 

 

 

Procedure 2 

(a,b,c,d are parameters of subdivision matrices, n - number of iterations, initial polygon is a triangle with vertices ) 

 

 

3. Examples 

Examples 3.1 

Below we obtain several curves using different parameters u and v  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Animations 

 

 

 

 

 

 

 

 

Examples 3.2 

Below we obtain several curves using different parameters a,b,c,d  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Animations 

 

 

 

 

 

 

 

4. Final Remarks 

 

Analysing presented above examples one can observe that a great variety of curves it is possibly to generate basing on three control points using subdivision matrices. All obtained curves and fractal shapes are contained in the convex hull of three control points i.e.they lie  inside the triangle with vertices  

From Computer Aided Design point of view only smooth curves e.g. B-splines and B?zier curves are interesting in practical applications. They are obtained using subdivision matrices for special choice of parameters. It should be pointed out that subdivision is a powerful approach because it offers very easy to implement algorithms that efficiently produce smooth curves or patches used in geometrical modeling of shapes.Considerations presented in this worksheet can be easily generalized to tensor patches generated with the help of the obtained curves. We would like to suggest those who are interested in subdivision and fractal generation of shapes to consult our earlier worksheets [4] - [7] or the monograph [8].   

5. References 

 

[1] Chaikin G., An algorithm for high-speed curve generation, Computer Graphics and Image Processing, Vol. 3, 346-349, 1974. 

[2] de Rham, G., Un peu de math?matiques `a propos d?une courbe plane. Elemente der Math. 2, 73?76, 89?97, 1947. 

[3] Goldman R., The Fractal Nature of B?zier Curves, Proceedings of the Geometric Modeling and Processing, April 13-15, 2004, Beijing, China, 3-11.
[4] Kotarski W., Lisowska A., On Fractal Modeling of Contours, Maplesoft, 2005, http://www.maplesoft.com/applications/app_center_view.aspx?AID=1651. 

[5] Kotarski W.,  Lisowska A., Probabilistic Approach to Fractal Modeling of Shapes, Maplesoft, 2005, http://www.maplesoft.com/applications/app_center_view.aspx?AID=1657 .    .
[6] Kotarski W., Lisowska A., Fractal Teapot from Utah, Maplesoft, 2006, http://www.maplesoft.com/applications/app_center_view.aspx?AID=1956.
[7]  Kotarski W., Lisowska A., Fractal Rendering of 3D Patches, Maplesoft, 2006, http://www.maplesoft.com/applications/app_center_view.aspx?AID=1955.  

[8]  Kotarski W., Fractal modeling of Shapes, EXIT, Warsaw 2008, (in Polish). 

[9] Schaefer S., Levin D., Goldman R., Subdivision Schemes and Attractors, Eurographics Symposium on Geometry Processing, 171-180, 2005. 

[10]  van Overveld CWAM, Family of recursively defined curves related to the cubic Bezier curve, Computer Aided Design, Vol. 22, No. 9, 591-597, 1990. 

[11] Warren J., Weimer H., Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann, San Francisco, 2001.
 

 

 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.