**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. *