Lobachevskii Journal of Mathematics

http://ljm.ksu.ru
ISSN 1818-9962

Vol. 26, 2007, 51–61 \begin{matrix}c \\ ◯ \end{matrix} Ghulam Mustafa, Sadiq Hashmi, and K. P. Akhtar

Ghulam Mustafa, Sadiq Hashmi, and K. P. Akhtar

ESTIMATING ERROR BOUNDS OF BAJAJ’S SOLID MODELS AND THEIR CONTROL HEXAHEDRAL MESHES

(submitted by A. V. Lapin)

Abstract. In this article, we estimate error bounds between the surface boundary patch of Bajaj et al’s solid models (The Visual Computer 18, 343-356, 2002) and their boundary of control hexahedral meshes after k-fold subdivision. Our bounds are express in terms of the maximal differences of the initial control point sequences and constants. The bound is independent of the process of subdivision and can be evaluated without recursive subdivision. From this error bound one can predict the subdivision depth within a user specified error tolerance.

1. Introduction

The notion of solid modelling, as practiced today, was developed in the early to mid-1970, in response to a very specific need for informational completeness in mechanical geometric modelling systems. It is a consistent set of principles for mathematical and computer modelling of three-dimensional solids. It is now mature enough to be termed a ‘discipline’. Its major themes are theoretical foundations, geometric and topological representations, algorithms, systems, and applications. Although solid modelling is more desirable in many engineering and manufacturing applications, it has not yet gained popularity until recently due to both a lack of widespread standards and its strong need for more powerful computing resources. The past two decades have witnessed a significant growth in solid modelling, especially in the development of new solid representations. Solid modelling is distinguished from other areas in geometric modelling and computing by its emphasis on informational completeness, physical fidelity, and universality. Volumetric subdivision is an important method for solid modelling which first appeared [7] as tensor product extension of the Catmull-Clark scheme [2] in the volumetric setting, mainly for the purpose of free-form deformation in the three-dimensional space. It is a hexahedral-based, approximation scheme. The related work also has been done by Bajaj et al. [1]. Their scheme is also hexahedral-based, approximation scheme. Chang et al. [3] and [4] proposed two new subdivision schemes based on nonhexahedral meshes. They proposed an approximation subdivision solid scheme based on the box splines and an interpolating scheme. Given an outline of the desired shape by means of a so-called control hexahedral mesh in the limit subdivision scheme produce solid models. It is natural to ask the following problems: For volumetric subdivision, how well do the control hexahedral mesh approximate to the limit solid model? Fuhua Cheng [5] gave an algorithm to estimate subdivision depths for rational curves and surfaces. The subdivision depth is not estimated for the given curve/ surface directly. Their algorithm computes a subdivision depth for the polynomial curve/ surface of which the given rational curve/ surface is the image under the standard perspective projection. Xiao et al. [9] derive computational formula of depth for Catmull-Clark subdivision surfaces. Recently, Mustafa et al. [6], estimate error bounds for tensor product form of binary subdivision surfaces in terms of the maximal differences of the initial control point sequence and constants that depend on the subdivision mask. The first aim of this article is to answer the question, how well do the control hexahedral meshes approximate to the limit solid/volumetric models? The second aim of this article is: Given an error tolerance , how many times the control mesh of a Bajaj’s subdivision surface boundary patch should be recursively subdivided so that the distance between the resulting control mesh and the limit surface boundary patch would be less than the error tolerance. This error control technique, called subdivision depth computation. The paper is organized as follows: We give a brief introduction to Bajaj et al’s subdivision scheme for hexahedral meshes [1] in Section 2. We also settle some notations in Section 2. In Section 3, we present our main result about the estimation of error bounds between the surface boundary patch of Bajaj et al’s solid models and their boundary of control hexahedral meshes. Section 4 is devoted for conclusions and future research directions.

2000 Mathematical Subject Classification. 65D17, 65D07, 65D05.

Key words and phrases. Solid modelling, Volumetric subdivision, Error bound, Subdivision Depth, Hexahedral mesh.

2. Preliminaries

In this section, first we give brief introduction about Bajaj et al’s subdivision scheme for hexahedral meshes and then settle some notations required for fair reading and better understanding.

2.1. A subdivision scheme for hexahedral meshes. Bajaj et al’s subdivision scheme for hexahedral meshes is expressed as a multi-linear subdivision followed by two rounds of averaging, to generate solid model.

2.1.1. Multi-linear subdivision. Multi-linear subdivision consist of splitting a topological n-hypercube into 2^{n} sub-hypercubes and positioning the new vertices using multi-linear interpolation. Given an n-hypercube, then recursively compute the multi-linear subdivision of two (n − 1)- hypercubes comprising the n-hypercube and call the two resulting lists of 2^{(n−1)} (n−1)-hypercubes left and right, respectively. left and right are splits of the left and right faces of n-hypercube. Next, use linear interpolation to compute a list of 2^{(n−1)} (n−1)-hypercubes called middle that lie halfway between left and right. Finally, return 2^{n−1} n-hypercubes from corresponding pairs of (n-1)-hypercubes in left and middle and 2^{n−1} nhypercubes from corresponding pairs of (n-1)-hypercubes in middle and right. Given a volume mesh {T_{k−1}, P_{k−1}} which consists of a topological mesh T_{k−1} of n-hypercubes and a vector of vertex positions P_{k−1} multi-linear subdivision produces a refined mesh {T_{k}, P̃_{k}} with the desired topology T_{k}.

2.1.2. Cell averaging. Given a vertex v, compute the centroids of those topological n-hypercubes that contain v. Reposition v at the centroid of these centroids in order to get final mesh {T_{k}, P_{k}}.

2.1.3. Boundary rules. Assume q_{0}^{k} is a vertex, at the boundary of control hexahedral mesh, with valence N ≥ 3, k ≥ 0 after k times of subdivision. Other 2N vertices q_{i}^{k}, i = 1, …, 2N, around q_{0}^{k} are labelled as shown in Figure 1. In the Bajaj et al’s subdivision, the new vertices at the boundary of control hexahedral mesh are computed as follows:

Figure 1. A subdivision scheme for hexahedral meshes

\{ \begin{matrix}q_{1}^{k+1} = \frac{3}{8}(q_{0}^{k} + q_{1}^{k}) + \frac{1}{16}(q_{2}^{k} + q_{3}^{k} + q_{2N}^{k} + q_{2N−1}^{k}), \\ q_{2i}^{k+1} = \frac{1}{4}(q_{0}^{k} + q_{2i−1}^{k} + q_{2i}^{k} + q_{2i+1}^{k}), i = 1, 2, …, N − 1, \\ q_{2i−1}^{k+1} = \frac{3}{8}(q_{0}^{k} + q_{2i−1}^{k}) \\ +\frac{1}{16}(q_{2i}^{k} + q_{2i+1}^{k} + q_{2i−2}^{k} + q_{2i−3}^{k}), i = 2, 3, …, N − 1, \\ q_{2N}^{k+1} = \frac{1}{4}(q_{0}^{k} + q_{2N−1}^{k} + q_{2N}^{k} + q_{1}^{k}), \\ q_{2N−1}^{k+1} = \frac{3}{8}(q_{0}^{k} + q_{2N−1}^{k}) + \frac{1}{16}(q_{1}^{k} + q_{2N}^{k} + q_{2N−3}^{k} + q_{2N−2}^{k}), \\ q_{0}^{k+1} = \frac{9}{16}q_{0}^{k} + \frac{3}{8N} ∑_{i=1}^{N} q_{2i−1}^{k} + \frac{1}{16N} ∑_{i=1}^{N} q_{2i}^{k}. \end{matrix} (1)

2.2. Notations. Here, we settle some basic notations.

\{ \begin{matrix}Δ_{i,1}^{k} = q_{2i}^{k} − q_{2i−1}^{k}, \\ Δ_{i,2}^{k} = q_{2i−1}^{k} − q_{2i−2}^{k}, \\ Δ_{3}^{k} = q_{2N}^{k} − q_{1}^{k}, \\ Δ_{i,4}^{k} = q_{2i−1}^{k} − q_{0}^{k}, \end{matrix}  (2)

for i = 1, 2, …, N.

\{ \begin{matrix}Λ_{1}^{k} = max \{ max_{i=1,2,...,N} ∥Δ_{i,1}^{k}∥ , max_{i=1,2,...,N} ∥Δ_{i,2}^{k}∥ , ∥Δ_{3}^{k}∥\} , \\ Λ_{2}^{k} = max_{i=1,2,...,N} ∥Δ_{i,4}^{k}∥ . \end{matrix}  (3)

3. The error bounds of Bajaj et al’s solid models

A subdivision scheme for hexahedral meshes is a generalization of Catmull-Clark surface. For a given control hexahedral mesh, every surface boundary face of hexahedral mesh is four-sided after one step of subdivision, and after one more, each extraordinary point (with valence other that 4) is isolated, and each boundary face contains at most one extraordinary point. The surface boundary reduces to a uniform bi-cubic B-spline surface where the control mesh is regular. The surface boundary near an extraordinary point is made up of many bi-cubic B-spline patches with less sizes, as parametrized by Stam [8]. Therefore it is enough to estimate error bounds between the surface boundary patch of Bajaj et al’s solid models and their boundary of control hexahedral meshes after k-fold subdivision.

Here we present our main result to estimate error bounds.

Theorem 1. Given initial boundary of control hexahedral mesh Q^{0} = {q_{i}^{0} = q_{i}, i = 0, 1, … 2N} containing the extraordinary point q_{0} of valence N ≥ 3, let the values q_{i}^{k}, k > 0, i ∈ ℤ^{+} be defined recursively by subdivision process (1). Suppose Q^{k} be the piecewise linear interpolation to the values q_{i}^{k} and Q^{∞} be the limit surface boundary patch generated by subdivision process (1) from Q^{0}. Then error bounds between limit surface boundary patch of Bajaj et al’s solid model and its boundary of control hexahedral mesh after k-fold subdivision is

∥Q^{k} − Q^{∞}∥_{∞} ≤ \frac{23}{12} (\frac{3}{4})^{k} β^{0}  (4)

where

β^{0} = max {Λ_{1}^{0}, Λ_{2}^{0}} ,  (5)

Λ_{1}^{0}, Λ_{2}^{0} are defined in (3).

Proof. Let ∥.∥_{∞} denote the uniform norm. Since the maximum difference between Q^{k+1} and Q^{k} is attained at a point on the (k + 1)th mesh, then

∥Q^{k+1} − Q^{k}∥_{∞} ≤ max{M_{k}^{1}, M_{k}^{2}, M_{k}^{3}, M_{k}^{4}},  (6)

where

\{ \begin{matrix}M_{k}^{1} = ∥q_{0}^{k+1} − q_{0}^{k}∥ , \\ M_{k}^{2} = max_{i=1,2,...,N} ∥q_{2i−1}^{k+1} − \frac{1}{2}(q_{0}^{k} + q_{2i−1}^{k})∥ , \\ M_{k}^{3} = max_{i=1,2,...,N−1} ∥q_{2i}^{k+1} − \frac{1}{4}(q_{0}^{k} + q_{2i}^{k} + q_{2i−1}^{k} + q_{2i+1}^{k})∥ , \\ M_{k}^{4} = ∥q_{2N}^{k+1} − \frac{1}{4}(q_{0}^{k} + q_{1}^{k} + q_{2N}^{k} + q_{2N−1}^{k})∥ . \end{matrix}  (7)

56 MUSTAFA, HASHMI, AND AKHTAR From (1) and (7) we see that

M_{k}^{3} = M_{k}^{4} = 0.  (8)

From (1) we get

q_{2i−1}^{k+1} − \frac{1}{2}(q_{0}^{k} + q_{2i−1}^{k}) = \frac{1}{16}(q_{2i}^{k} − q_{2i−1}^{k}) + \frac{1}{16}(q_{2i+1}^{k} − q_{0}^{k})

+\frac{1}{16}(q_{2i−1}^{k} − q_{2i−2}^{k}) + \frac{1}{16}(q_{2i−3}^{k} − q_{0}^{k}), i = 2, 3, …, N − 1, (9)

q_{1}^{k+1} − \frac{1}{2}(q_{0}^{k} + q_{1}^{k}) = \frac{1}{16}(q_{2N−1}^{k} − q_{0}^{k})

+\frac{1}{16}(q_{2N}^{k} − q_{1}^{k}) + \frac{1}{16}(q_{2}^{k} − q_{1}^{k}) + \frac{1}{16}(q_{3}^{k} − q_{0}^{k}),  (10)

and

q_{2N−1}^{k+1} − \frac{1}{2}(q_{0}^{k} + q_{2N−1}^{k}) = \frac{1}{16}(q_{2N−2}^{k} − q_{2N−1}^{k})

+\frac{1}{16}(q_{2N−3}^{k} − q_{0}^{k}) + \frac{1}{16}(q_{2N−1}^{k} − q_{2N}^{k}) + \frac{1}{16}(q_{0}^{k} − q_{1}^{k}). (11)

From (1) we can get the following

q_{0}^{k+1} − q_{0}^{k} = \frac{9}{16}q_{0}^{k} + ∑_{i=1}^{N} \frac{3}{8N} q_{2i−1}^{k} + ∑_{i=1}^{N} \frac{1}{16N} q_{2i}^{k}

− (\frac{9}{16} + ∑_{i=1}^{N} \frac{3}{8N} + ∑_{i=1}^{N} \frac{1}{16N} ) q_{0}^{k}.

This implies

q_{0}^{k+1} − q_{0}^{k} = ∑_{i=1}^{N} \frac{7}{16N} (q_{2i−1}^{k} − q_{0}^{k}) + ∑_{i=1}^{N} \frac{1}{16N} (q_{2i}^{k} − q_{2i−1}^{k}) .  (12)

From (7) and (12)

M_{k}^{1} ≤ \frac{7}{16} max_{i} ∥Δ_{i,4}^{k}∥ + \frac{1}{16} max_{i} ∥Δ_{i,1}^{k}∥.

Using (3) we get

M_{k}^{1} ≤ \frac{1}{16}Λ_{1}^{k} + \frac{7}{16}Λ_{2}^{k}.  (13)

From (7) and (9)

M_{k}^{2} ≤ \frac{1}{16} \{max_{i} ∥Δ_{i,1}^{k}∥ + 2 max_{i} ∥Δ_{i,4}^{k}∥ + max_{i} ∥Δ_{i,2}^{k}∥\} .  (14)

From (7) and (10)

M_{k}^{2} ≤ \frac{1}{16} \{2 max_{i} ∥Δ_{i,4}^{k}∥ + ∥Δ_{3}^{k}∥ + max_{i} ∥Δ_{i,1}^{k}∥\} .  (15)

ESTIMATING ERROR BOUNDS 57

From (7) and (11)

M_{k}^{2} ≤ \frac{1}{16} \{max_{i} ∥Δ_{i,2}^{k}∥ + 2 max_{i} ∥Δ_{i,4}^{k}∥ + max_{i} ∥Δ_{i,1}^{k}∥\} .  (16)

From (14), (15) and (16) we get

M_{k}^{2} ≤ \frac{1}{8} \{Λ_{1}^{k} + Λ_{2}^{k}\} .  (17)

From (1) we get the following differences for i = 2, 3, …, N − 1,

q_{2i}^{k} − q_{2i−1}^{k} = \frac{1}{4} (q_{0}^{k−1} + q_{2i−1}^{k−1} + q_{2i}^{k−1} + q_{2i+1}^{k−1})

− (\frac{3}{8} (q_{0}^{k−1} + q_{2i−1}^{k−1}) + \frac{1}{16} (q_{2i}^{k−1} + q_{2i+1}^{k−1} + q_{2i−2}^{k−1} + q_{2i−3}^{k−1})) .

This implies

q_{2i}^{k} − q_{2i−1}^{k} = \frac{1}{8} (q_{2i}^{k−1} − q_{2i−1}^{k−1}) + \frac{1}{8} (q_{2i+1}^{k−1} − q_{0}^{k−1})

+\frac{1}{16} (q_{2i}^{k−1} − q_{2i−1}^{k−1} + q_{2i−1}^{k−1} − q_{0}^{k−1} + q_{0}^{k−1} + q_{2i+1}^{k−1})

−\frac{1}{16} (q_{2i−2}^{k−1} − q_{2i−1}^{k−1} + q_{2i−1}^{k−1} − q_{0}^{k−1} + q_{0}^{k−1} + q_{2i−3}^{k−1}) .

Finally, for i = 2, 3, …, N − 1, we have

q_{2i}^{k} − q_{2i−1}^{k} = \frac{3}{16} (q_{2i}^{k−1} − q_{2i−1}^{k−1}) + \frac{3}{16} (q_{2i+1}^{k−1} − q_{0}^{k−1})

+\frac{1}{16} (q_{2i−1}^{k−1} − q_{2i−2}^{k−1}) − \frac{1}{16} (q_{2i−3}^{k−1} − q_{0}^{k−1}) .  (18)

Similarly, we get following differences

q_{2}^{k} − q_{1}^{k} = \frac{3}{16} (q_{2}^{k−1} − q_{1}^{k−1}) + \frac{3}{16} (q_{3}^{k−1} − q_{0}^{k−1})

+\frac{1}{16} (q_{1}^{k−1} − q_{2N}^{k−1}) − \frac{1}{16} (q_{2N−1}^{k−1} − q_{0}^{k−1}) ,  (19)

q_{2N}^{k} − q_{1}^{k} = \frac{3}{16} (q_{2N−1}^{k−1} − q_{0}^{k−1}) + \frac{3}{16} (q_{2N}^{k−1} − q_{1}^{k−1})

−\frac{1}{16} (q_{2}^{k−1} − q_{1}^{k−1}) − \frac{1}{16} (q_{3}^{k−1} − q_{0}^{k−1}) ,  (20)

q_{2N}^{k} − q_{2N−1}^{k} = \frac{3}{16} (q_{2N}^{k−1} − q_{2N−1}^{k−1}) + \frac{3}{16} (q_{1}^{k−1} − q_{0}^{k−1})

+\frac{1}{16} (q_{2N−1}^{k−1} − q_{2N−2}^{k−1}) − \frac{1}{16} (q_{2N−3}^{k−1} − q_{0}^{k−1}) .  (21)

58 MUSTAFA, HASHMI, AND AKHTAR For i = 1, 2, …, N − 2, we have

q_{2i+1}^{k} − q_{2i}^{k} = \frac{3}{16} (q_{2i+1}^{k−1} − q_{2i}^{k−1}) − \frac{3}{16} (q_{2i−1}^{k−1} − q_{0}^{k−1})

+\frac{1}{16} (q_{2i+2}^{k−1} − q_{2i+1}^{k−1}) + \frac{1}{16} (q_{2i+3}^{k−1} − q_{0}^{k−1}) .  (22)

q_{2N−1}^{k} − q_{2N−2}^{k} = −\frac{3}{16} (q_{2N−3}^{k−1} − q_{0}^{k−1}) + \frac{3}{16} (q_{2N−1}^{k−1} − q_{2N−2}^{k−1})

+\frac{1}{16} (q_{2N}^{k−1} − q_{2N−1}^{k−1}) + \frac{1}{16} (q_{1}^{k−1} − q_{0}^{k−1}) .  (23)

For i = 1, 2, …, N − 2, we have

q_{2i+1}^{k} − q_{0}^{k} = \frac{7}{16} (q_{2i+1}^{k−1} − q_{0}^{k−1}) + \frac{2}{16} (q_{2i−1}^{k−1} − q_{0}^{k−1})

+ \frac{1}{16} (q_{2i+3}^{k−1} − q_{0}^{k−1}) + \frac{1}{16} (q_{2i+2}^{k−1} − q_{2i+1}^{k−1})

+ \frac{1}{16} (q_{2i}^{k−1} − q_{2i−1}^{k−1}) . (24)

q_{2N−1}^{k} − q_{0}^{k} = \frac{8}{16} (q_{2N−1}^{k−1} − q_{0}^{k−1}) + \frac{1}{16} (q_{1}^{k−1} − q_{0}^{k−1})

+ \frac{1}{16} (q_{2N−3}^{k−1} − q_{0}^{k−1}) + \frac{1}{16} (q_{2N}^{k−1} − q_{2N−1}^{k−1})

− \frac{1}{16} (q_{2N−1}^{k−1} − q_{2N−2}^{k−1}) . (25)

q_{1}^{k} − q_{0}^{k} = \frac{7}{16} (q_{1}^{k−1} − q_{0}^{k−1}) + \frac{1}{16} (q_{3}^{k−1} − q_{0}^{k−1})

+ \frac{2}{16} (q_{2N−1}^{k−1} − q_{0}^{k−1}) + \frac{1}{16} (q_{2N}^{k−1} − q_{2N−1}^{k−1})

− \frac{1}{16} (q_{2}^{k−1} − q_{1}^{k−1}) . (26)

From (3), (18) to (23) we have

Λ_{1}^{k} ≤ \frac{1}{4} \{Λ_{1}^{k−1} + Λ_{2}^{k−1}\} .  (27)

From (3), (24) to (26) we have

Λ_{2}^{k} ≤ \frac{1}{8} \{Λ_{1}^{k−1} + 5Λ_{2}^{k−1}\} .  (28)

From (27) and (28) we get

Λ_{1}^{k} ≤ \frac{1}{2}β^{k−1},  (29)

and

Λ_{2}^{k} ≤ \frac{3}{4}β^{k−1},  (30)

where

β^{k−1} = max {Λ_{1}^{k−1}, Λ_{2}^{k−1}} .  (31)

From (29), (30), and (31)

β^{k−1} ≤ max \{\frac{1}{2}β^{k−2}, \frac{3}{4}β^{k−2}\} ≤ \frac{3}{4}β^{k−2}.

Now recursively, we get

β^{k−1} ≤ (\frac{3}{4})^{k−1} β^{0}.  (32)

From (29), (30) and (32)

Λ_{1}^{k} ≤ \frac{1}{2} (\frac{3}{4})^{k−1} β^{0},  (33)

and

Λ_{2}^{k} ≤ \frac{3}{4} (\frac{3}{4})^{k−1} β^{0}.  (34)

From (13), (33) and (34) we get

M_{k}^{1} ≤ \frac{23}{48} (\frac{3}{4})^{k} β^{0}.  (35)

From (17), (33) and (34) we get

M_{k}^{2} ≤ \frac{5}{24} (\frac{3}{4})^{k} β^{0}.  (36)

From (6), (8), (35) and (36) we see that

∥Q^{k+1} − Q^{k}∥_{∞} ≤ \frac{23}{48} (\frac{3}{4})^{k} β^{0}.  (37)

From (37) and using triangle inequality we get

∥Q^{k+1} − Q^{∞}∥_{∞} ≤ \frac{23}{12} (\frac{3}{4})^{k} β^{0}.

This completes the proof.

Here we present the first order forward differences based subdivision depth computation technique for extra-ordinary Bajaj’s subdivision surface boundary patch’s control points.

Theorem 2 Let k be the subdivision depth and let d^{k} be the error bound between Bajaj’s subdivision surface boundary patch and its k-level control hexahedral mesh Q^{k}. For arbitrary ϵ ≥ 0, if

k ≥ log_{( \frac{4}{3} )}(\frac{23β^{0}}{12ϵ}).

Then

d^{k} ≤ ϵ.

Proof. From (4), we have

d^{k} = ∥Q^{k} − Q^{∞}∥_{∞} ≤ \frac{23}{12} (\frac{3}{4})^{k} β^{0}.

This implies, for arbitrary given ϵ > 0, when subdivision depth k satisfy the following inequality

k ≥ log_{( \frac{4}{3} )}(\frac{23β^{0}}{12ϵ}).

Then

d^{k} ≤ ϵ.

This completes the proof.

4. Conclusions and further work

We have estimated error bounds between the surface boundary patch of Bajaj et al’s solid models and their boundary of control hexahedral meshes after k-fold subdivision. we have presented the first order forward differences based subdivision depth computation technique for extraordinary Bajaj’s subdivision surface boundary patch’s control points. From this computational technique one can predict the subdivision depth within a user specified error tolerance. Estimation of error bounds between higher dimensional boundary of Bajaj et al’s solid models and their boundary of control n−hypercube meshes is a possible future research directions. It is yet to be investigated whether we can use above technique for estimating error bounds of other well known subdivision schemes for solid modelling.

5. Acknowledgements

This work is supported by the Indigenous Ph. D Scholarship Scheme of Higher Education Commission (HEC) Pakistan.

ESTIMATING ERROR BOUNDS 61

References

[1] Bajaj C., Warren J., and Xu G., (2002): A subdivision scheme for hexahedral meshes. The Visual Computer 18, 343-356

[2] Catmull E., Clark J., (1978): Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10, 350-355

[3] Chang Y-S., McDonnell K. T., and Qin H., (2002): A new solid subdivision scheme based on box splines. In Proceedings of Solid Modeling, 226-233

[4] Chang Y-S., McDonnell K. T., and Qin H., (2003): An interpolatory subdivision for volumetric models over simplicial complexes. In Proceedings of Shape Modeling International 2003, 143-152.

[5] Cheng F., (1992): Estimating subdivision depths for rational curves and surfaces. ACM Transactions on Graphics, 11(2), 140-151

[6] Ghulam Mustafa, Chen Falai, and Jiansong Deng, (2006): Estimating error bounds for binary subdivision curves/surfaces. J. Comp. Appl. Math., 193,596-613

[7] MacCracken R., and Joy K. I., (1996): Free-form deformations with lattices of arbitrary topology. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH’96, 181-188

[8] Stam J., (1998): Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. Computer Graphics Proceeding of SIGGRAPH’98, 395-404

[9] Xiao-Ming Zeng and Chen X. J., (2006): Computational formula of depth for Catmull-Clark subdivision surfaces. J. Comp. Appl. Math., 195(1-2), 252-262.

Department of Mathematics, Islamia University Bahawal pur, Pakistan

E-mail address: mustafa rakib@yahoo.com

Department of Mathematics, Islamia University Bahawal pur, Pakistan

K. P. Akhtar, Department of Mathematics, Islamia University Bahawal pur, Pakistan

Received November 6, 2006