# Subdivision Depth Computation for Tensor Productn-Ary Volumetric Models

Authors: Ghulam Mustafa; Muhammad Sadiq Hashmi
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

We offer computational formula of subdivision depth for tensor
productn-ary (n⩾2) volumetric models based on error bound evaluation technique.
This formula provides and error control tool in subdivision schemes over regular
hexahedron lattice in higher-dimensional spaces. Moreover, the error bounds of
Mustafa et al.  (2006) are special cases
of our bounds.


---

## Body

## 1. Introduction

Subdivision is a simple and elegant method to describe smooth curves and surfaces. The approach of subdivision schemes is simple and efficient due to its mathematical formulation. Its application ranges from industrial design and animation to scientific visualization and simulation. Due to this, subdivision method is becoming a standard technique and now well-understood by both academic and industrial communities. It is an algorithm to generate smooth curves and surfaces as a sequence of successively refined control polygons. At each subdivision level, the subdivision scheme describe the source grid maps to the subdivided grid, which results in increase in the number of points. The number of points inserted at levelk+1 between two consecutive points from level k is called arity of the scheme. In the case when number of points inserted are 2,3,…,n the subdivision schemes are called binary, ternary, …, n-ary, respectively. For more details on n-ary subdivision schemes, we may refer to [1–4] thesis of Aspert [5] and Ko [6].However tensor product trivariate schemes obtained from above schemes have been proven themselves an excellent tool for the modeling of largely regular volumetric/solid models over hexahedron lattice, for example, manufacturing of industrial regular block, font animation and garment pressures for the biomechanical design of functional apparel products, and so forth.Although subdivision has many attractive advantages for modeling purposes, it has received far less attention in volumetric modeling. One of the reason is the topological complexity of domain meshes in higher-dimensional spaces. Another reason is lack of proper mathematical tools for extraordinary analysis. Even so, it is clear that subdivision is slowly gaining interest in solid modeling community. MacCracken and Joy [7] proposed a tensor product extension of the Catmull-Clark scheme in the volumetric setting over hexahedron lattice. Later on, Bajaj et al. [8] further extended the scheme with the analysis based on numerical experiments. In 2004, McDonnell et al. [9] present a volumetric subdivision scheme for interpolation of arbitrary hexahedral meshes. Mustafa and Liu [10] present subdivision scheme which exhibits control over shrink-age/size of volumetric models in 2005. The method here presented is much simpler and easier as compared to MacCracken and Joy [7]. Cheng and Yong [11] proposed subdivision scheme based on nonhexahedron lattice. Wang et al. [12] gave the application of the volumetric subdivision scheme in the simulation of elastic human body deformation and garment pressure.Subdivision schemes have become important in recent years because they provide a precise and efficient way to describe smooth curves/surfaces/volumetric models, however the little have been done in the area of error control for tensor productn-ary volumetric models. The investigation of error control for volumetric models arises two questions in mind.(i)
How well the regular hexahedron lattice approximate to the limit volumetric model?(ii)
How many subdivision steps are needed to satisfy a user-specified error tolerance?For given error tolerance, the subdivision levels performed on the initial control polygon, so that the error/distance between the resulting control polygon and the limit volumetric models would be less than the error tolerance is called subdivision depth.A subdivision depth and error bound based on forward differences of control points have been presented by [11, 13–18], while the methods [19–22] are based on eigenanalysis. But nothing in this area has been done for more general tensor product n-ary volumetric models yet. In this paper, we will answer-above-said questions and present a subdivision depth computation technique based on error bounds for tensor product n-ary volumetric models.It is notified that the increase in arity offers greater freedom than offered by low arity subdivision volumetric scheme in term of coefficients. Higher arity volumetric schemes allow a range of different behaviors than the lower arity volumetric schemes. Ko [6] notified that subdivision curves/surfaces with higher arity results in higher smoothness and approximation order but smaller in support, which make it more practical in use. It is also noticed that higher arity volumetric models have slightly lower computational cost than lower arity volumetric models. This discussion motivate us to calculate error bound and depth for higher arity subdivision volumetric models, that is, in general for tensor product n-ary subdivision volumetric models. Our method is generalization of Mustafa et al. [13, 15–17]. The paper is arranged as follows.Section2 is devoted for basic definitions and notations. In Section 3, we have computed subdivision depth for tensor product n-ary volumetric models. Section 4 presents applications of our results for tensor product n-ary volumetric models. Conclusion and future research directions are given in Section 5. The typical mathematical proofs are placed in Appendices A and B for improved presentation of the paper.


## 2. Preliminaries

In this section, first we list all the basic facts about subdivision curve, surface and volumetric models needed in this paper. Then we settle some notations for fair reading and better understanding of Section3.


### 2.1. Concepts

#### 2.1.1.n-Ary Subdivision Curve

Given a sequence of control pointspik∈ℝN, i∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, an n-ary subdivision curve [5] is defined by(2.1)pni+αk+1=∑j=0maα,jpi+jk,α=0,1,…,n-1,
where m>0 and(2.2)∑j=0maα,j=1,α=0,1,…,n-1.
The set of coefficients {aα,j,α=0,1,…,n-1}j=0m is called subdivision mask. Given initial values pi0∈ℝN, i∈ℤ, then in the limit k→∞, the process (2.1) defines an infinite set of points in ℝN. The sequence of control points {pik} is related, in a natural way, with the dyadic mesh points tik=i/nk, i∈ℤ. The process then defines a scheme whereby pni+αk+1 replaces the value pi+α/nk for α∈{0,n}. Here pni+αk+1 is inserted at the mesh point tni+αk+1=(1/n)((n-α)tik+αti+1k) for α=0,1,…,n. Labelling of old and new points is shown in Figure 1 which illustrates subdivision scheme (2.1).Solid lines show coarse polygons whereas doted lines are refined polygons. (a)–(c) represent binary, ternary, and quaternary refinement of coarse polygon of scheme (2.1) for n=2,3,4, respectively.
(a)(b)(c)


#### 2.1.2. Tensor Productn-Ary Subdivision Surface

Given a sequence of control pointspi,jk∈ℝN, i,j∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary surface is a tensor product of (2.1) defined by(2.3)pni+α,nj+βk+1=∑r=0m∑s=0maα,raβ,spi+r,j+sk,α,β=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j0∈ℝN, i,j∈ℤ, then in the limit k→∞, the process (2.3) defines an infinite set of points in ℝℕ. The sequence of values {pi,jk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk), i,j∈ℤ. The process then defines a scheme whereby pni+α,nj+βk+1 replaces the values pi+α/n,j+β/nk for α,β∈{0,n}. Here the values pni+α,nj+βk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1) for α,β=0,1,…,n. Labelling of old and new points is shown in Figure 2 which illustrates subdivision scheme (2.3).Solid lines show one face of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one face into four, nine and sixteen new faces by using (2.3) for n=2,3,4 (i.e., binary, ternary and quaternary), respectively.
(a)(b)(c)


#### 2.1.3. Tensor Productn-Ary Volumetric Model

Given a sequence of control pointspi,j,lk∈ℝN, i,j,l∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary volumetric model is tensor product of (2.3) defined by(2.4)pni+α,nj+β,nl+γk+1=∑r=0m∑s=0m∑t=0maα,raβ,saγ,tpi+r,j+s,l+tk,α,β,γ=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j,l0∈ℝN, i,j,l∈ℤ, then in the limit k→∞, the process (2.4) defines an infinite set of points in ℝℕ. The sequence of values {pi,j,lk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk,l/nk), i,j,l∈ℤ. The process then defines a scheme whereby pni+α,nj+β,nl+γk+1 replaces the values pi+α/n,j+β/n,l+γ/nk for α,β,γ∈{0,n}. Here the values pni+α,nj+β,nl+γk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1,(nl+γ)/nk+1) for α,β,γ=0,1,…,n. Labelling of old and new points is shown in Figure 3 which illustrates subdivision scheme (2.4).Solid lines show one cube of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one cube into 23, 33, and 43 new cubes by using (2.4) for n=2,3,4, respectively.
(a)(b)(c)


#### 2.1.4. Subdivision Depth

Given control polygon of tensor productn-ary volumetric model and an error tolerance ϵ, if we subdivide control polygon k times so that the error between resulting polygon and volumetric model is smaller than ϵ, then k is called subdivision depth of tensor product n-ary volumetric model with respect to ϵ.


### 2.2. Notations

Here, we assume(2.5)δ=max⁡α,β,γ{|∑r=0m∑s=0m∑t=0maα,raβ,sbγ,t|,α,β,γ=0,1,…,n-1},
where(2.6)bγ,j=∑t=0j(aγ,t-aγ+1,t),γ=0,1,…,n-2,bn-1,j=a0,j-∑γ=0n-2bγ,j.
Suppose further for α,β,γ=0,1,…,n-1,(2.7)Mα,β,γk=‖pni+α,nj+β,nl+γk+1-1n3{(n-α)(n-β)(n-γ)pi,j,lk+α(n-β)(n-γ)pi+1,j,lk+β(n-α)(n-γ)pi,j+1,lk+γ(n-α)(n-β)pi,j,l+1k+αβ(n-γ)pi+1,j+1,lk+αγ(n-β)pi+1,j,l+1k+βγ(n-α)pi,j+1,l+1k+αβγpi+1,j+1,l+1k}‖.
Assume
(2.8)Δi,j,l,1k=pi+1,j,lk-pi,j,lk,Δi,j,l,5k=pi+1,j,l+1k-pi,j,l+1k,Δi,j,l,2k=pi,j+1,lk-pi,j,lk,Δi,j,l,6k=pi,j+1,l+1k-pi,j,l+1k,Δi,j,l,3k=pi,j,l+1k-pi,j,lk,Δi,j,l,7k=pi+1,j+1,l+1k-pi,j+1,l+1k,Δi,j,l,4k=pi+1,j+1,lk-pi,j+1,lk,(2.9)χ=max⁡t{max⁡i,j,l‖Δi,j,l,t0‖,t=0,1,…,7},(2.10)ηα,β,γ1=|aβ,0aγ,0∑t=1maα,t-α(n-β)(n-γ)n3|+|aβ,0aγ,0∑s=1m-1ãα,s|,(2.11)ηα,β,γ2=|aγ,0∑t=1maβ,t-β(n-γ)n2|+|aγ,0∑r=0m∑s=1m-1aα,rãβ,s|,(2.12)ηα,β,γ3=|∑t=1maγ,t-γn|+|∑r=0m∑t=0m∑s=1m-1aα,raβ,tãγ,s|,(2.13)ηα,β,γ4=|aγ,0∑s=1m∑t=1maα,saβ,t-αβ(n-γ)n3|+|aγ,0∑t=1m∑s=1m-1aβ,tãα,s|,(2.14)ηα,β,γ5=|aβ,0∑s=1m∑t=1maα,saγ,t-αγ(n-β)n3|+|aβ,0∑t=1m∑s=1m-1aγ,tãα,s|,(2.15)ηα,β,γ6=|∑s=1m∑t=1maβ,saγ,t-βγn2|+|∑t=1m∑r=0m∑s=1m-1aγ,taα,rãβ,s|,(2.16)ηα,β,γ7=|∑r=1m∑s=1m∑t=1maα,raβ,saγ,t-αβγn3|+|∑r=1m∑t=1m∑s=1m-1aβ,raγ,tãα,s|,
where(2.17)ãα,0=∑t=1maα,t-αn,α=0,1,…,n-1,ãα,j=∑t=j+1maα,t,j⩾1,α=0,1,…,n-1.
Furthermore, suppose(2.18)ϑ=max⁡α,β,γ{(χ)∑t=17(ηα,β,γt),α,β,γ=0,1,…,n-1}.


## 2.1. Concepts

### 2.1.1.n-Ary Subdivision Curve

Given a sequence of control pointspik∈ℝN, i∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, an n-ary subdivision curve [5] is defined by(2.1)pni+αk+1=∑j=0maα,jpi+jk,α=0,1,…,n-1,
where m>0 and(2.2)∑j=0maα,j=1,α=0,1,…,n-1.
The set of coefficients {aα,j,α=0,1,…,n-1}j=0m is called subdivision mask. Given initial values pi0∈ℝN, i∈ℤ, then in the limit k→∞, the process (2.1) defines an infinite set of points in ℝN. The sequence of control points {pik} is related, in a natural way, with the dyadic mesh points tik=i/nk, i∈ℤ. The process then defines a scheme whereby pni+αk+1 replaces the value pi+α/nk for α∈{0,n}. Here pni+αk+1 is inserted at the mesh point tni+αk+1=(1/n)((n-α)tik+αti+1k) for α=0,1,…,n. Labelling of old and new points is shown in Figure 1 which illustrates subdivision scheme (2.1).Solid lines show coarse polygons whereas doted lines are refined polygons. (a)–(c) represent binary, ternary, and quaternary refinement of coarse polygon of scheme (2.1) for n=2,3,4, respectively.
(a)(b)(c)


### 2.1.2. Tensor Productn-Ary Subdivision Surface

Given a sequence of control pointspi,jk∈ℝN, i,j∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary surface is a tensor product of (2.1) defined by(2.3)pni+α,nj+βk+1=∑r=0m∑s=0maα,raβ,spi+r,j+sk,α,β=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j0∈ℝN, i,j∈ℤ, then in the limit k→∞, the process (2.3) defines an infinite set of points in ℝℕ. The sequence of values {pi,jk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk), i,j∈ℤ. The process then defines a scheme whereby pni+α,nj+βk+1 replaces the values pi+α/n,j+β/nk for α,β∈{0,n}. Here the values pni+α,nj+βk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1) for α,β=0,1,…,n. Labelling of old and new points is shown in Figure 2 which illustrates subdivision scheme (2.3).Solid lines show one face of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one face into four, nine and sixteen new faces by using (2.3) for n=2,3,4 (i.e., binary, ternary and quaternary), respectively.
(a)(b)(c)


### 2.1.3. Tensor Productn-Ary Volumetric Model

Given a sequence of control pointspi,j,lk∈ℝN, i,j,l∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary volumetric model is tensor product of (2.3) defined by(2.4)pni+α,nj+β,nl+γk+1=∑r=0m∑s=0m∑t=0maα,raβ,saγ,tpi+r,j+s,l+tk,α,β,γ=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j,l0∈ℝN, i,j,l∈ℤ, then in the limit k→∞, the process (2.4) defines an infinite set of points in ℝℕ. The sequence of values {pi,j,lk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk,l/nk), i,j,l∈ℤ. The process then defines a scheme whereby pni+α,nj+β,nl+γk+1 replaces the values pi+α/n,j+β/n,l+γ/nk for α,β,γ∈{0,n}. Here the values pni+α,nj+β,nl+γk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1,(nl+γ)/nk+1) for α,β,γ=0,1,…,n. Labelling of old and new points is shown in Figure 3 which illustrates subdivision scheme (2.4).Solid lines show one cube of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one cube into 23, 33, and 43 new cubes by using (2.4) for n=2,3,4, respectively.
(a)(b)(c)


### 2.1.4. Subdivision Depth

Given control polygon of tensor productn-ary volumetric model and an error tolerance ϵ, if we subdivide control polygon k times so that the error between resulting polygon and volumetric model is smaller than ϵ, then k is called subdivision depth of tensor product n-ary volumetric model with respect to ϵ.


## 2.1.1.n-Ary Subdivision Curve

Given a sequence of control pointspik∈ℝN, i∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, an n-ary subdivision curve [5] is defined by(2.1)pni+αk+1=∑j=0maα,jpi+jk,α=0,1,…,n-1,
where m>0 and(2.2)∑j=0maα,j=1,α=0,1,…,n-1.
The set of coefficients {aα,j,α=0,1,…,n-1}j=0m is called subdivision mask. Given initial values pi0∈ℝN, i∈ℤ, then in the limit k→∞, the process (2.1) defines an infinite set of points in ℝN. The sequence of control points {pik} is related, in a natural way, with the dyadic mesh points tik=i/nk, i∈ℤ. The process then defines a scheme whereby pni+αk+1 replaces the value pi+α/nk for α∈{0,n}. Here pni+αk+1 is inserted at the mesh point tni+αk+1=(1/n)((n-α)tik+αti+1k) for α=0,1,…,n. Labelling of old and new points is shown in Figure 1 which illustrates subdivision scheme (2.1).Solid lines show coarse polygons whereas doted lines are refined polygons. (a)–(c) represent binary, ternary, and quaternary refinement of coarse polygon of scheme (2.1) for n=2,3,4, respectively.
(a)(b)(c)


## 2.1.2. Tensor Productn-Ary Subdivision Surface

Given a sequence of control pointspi,jk∈ℝN, i,j∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary surface is a tensor product of (2.1) defined by(2.3)pni+α,nj+βk+1=∑r=0m∑s=0maα,raβ,spi+r,j+sk,α,β=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j0∈ℝN, i,j∈ℤ, then in the limit k→∞, the process (2.3) defines an infinite set of points in ℝℕ. The sequence of values {pi,jk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk), i,j∈ℤ. The process then defines a scheme whereby pni+α,nj+βk+1 replaces the values pi+α/n,j+β/nk for α,β∈{0,n}. Here the values pni+α,nj+βk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1) for α,β=0,1,…,n. Labelling of old and new points is shown in Figure 2 which illustrates subdivision scheme (2.3).Solid lines show one face of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one face into four, nine and sixteen new faces by using (2.3) for n=2,3,4 (i.e., binary, ternary and quaternary), respectively.
(a)(b)(c)


## 2.1.3. Tensor Productn-Ary Volumetric Model

Given a sequence of control pointspi,j,lk∈ℝN, i,j,l∈ℤ, N⩾2, where the upper index k⩾0 indicates the subdivision level, a tensor product n-ary volumetric model is tensor product of (2.3) defined by(2.4)pni+α,nj+β,nl+γk+1=∑r=0m∑s=0m∑t=0maα,raβ,saγ,tpi+r,j+s,l+tk,α,β,γ=0,1,…,n-1,
where aα,r satisfies (2.2). Given initial values pi,j,l0∈ℝN, i,j,l∈ℤ, then in the limit k→∞, the process (2.4) defines an infinite set of points in ℝℕ. The sequence of values {pi,j,lk} is related, in a natural way, with the dyadic mesh points (i/nk,j/nk,l/nk), i,j,l∈ℤ. The process then defines a scheme whereby pni+α,nj+β,nl+γk+1 replaces the values pi+α/n,j+β/n,l+γ/nk for α,β,γ∈{0,n}. Here the values pni+α,nj+β,nl+γk+1 are inserted at the mesh points ((ni+α)/nk+1,(nj+β)/nk+1,(nl+γ)/nk+1) for α,β,γ=0,1,…,n. Labelling of old and new points is shown in Figure 3 which illustrates subdivision scheme (2.4).Solid lines show one cube of coarse polygons whereas doted lines are refined polygons. (a)–(c) can be obtain by subdividing one cube into 23, 33, and 43 new cubes by using (2.4) for n=2,3,4, respectively.
(a)(b)(c)


## 2.1.4. Subdivision Depth

Given control polygon of tensor productn-ary volumetric model and an error tolerance ϵ, if we subdivide control polygon k times so that the error between resulting polygon and volumetric model is smaller than ϵ, then k is called subdivision depth of tensor product n-ary volumetric model with respect to ϵ.


## 2.2. Notations

Here, we assume(2.5)δ=max⁡α,β,γ{|∑r=0m∑s=0m∑t=0maα,raβ,sbγ,t|,α,β,γ=0,1,…,n-1},
where(2.6)bγ,j=∑t=0j(aγ,t-aγ+1,t),γ=0,1,…,n-2,bn-1,j=a0,j-∑γ=0n-2bγ,j.
Suppose further for α,β,γ=0,1,…,n-1,(2.7)Mα,β,γk=‖pni+α,nj+β,nl+γk+1-1n3{(n-α)(n-β)(n-γ)pi,j,lk+α(n-β)(n-γ)pi+1,j,lk+β(n-α)(n-γ)pi,j+1,lk+γ(n-α)(n-β)pi,j,l+1k+αβ(n-γ)pi+1,j+1,lk+αγ(n-β)pi+1,j,l+1k+βγ(n-α)pi,j+1,l+1k+αβγpi+1,j+1,l+1k}‖.
Assume
(2.8)Δi,j,l,1k=pi+1,j,lk-pi,j,lk,Δi,j,l,5k=pi+1,j,l+1k-pi,j,l+1k,Δi,j,l,2k=pi,j+1,lk-pi,j,lk,Δi,j,l,6k=pi,j+1,l+1k-pi,j,l+1k,Δi,j,l,3k=pi,j,l+1k-pi,j,lk,Δi,j,l,7k=pi+1,j+1,l+1k-pi,j+1,l+1k,Δi,j,l,4k=pi+1,j+1,lk-pi,j+1,lk,(2.9)χ=max⁡t{max⁡i,j,l‖Δi,j,l,t0‖,t=0,1,…,7},(2.10)ηα,β,γ1=|aβ,0aγ,0∑t=1maα,t-α(n-β)(n-γ)n3|+|aβ,0aγ,0∑s=1m-1ãα,s|,(2.11)ηα,β,γ2=|aγ,0∑t=1maβ,t-β(n-γ)n2|+|aγ,0∑r=0m∑s=1m-1aα,rãβ,s|,(2.12)ηα,β,γ3=|∑t=1maγ,t-γn|+|∑r=0m∑t=0m∑s=1m-1aα,raβ,tãγ,s|,(2.13)ηα,β,γ4=|aγ,0∑s=1m∑t=1maα,saβ,t-αβ(n-γ)n3|+|aγ,0∑t=1m∑s=1m-1aβ,tãα,s|,(2.14)ηα,β,γ5=|aβ,0∑s=1m∑t=1maα,saγ,t-αγ(n-β)n3|+|aβ,0∑t=1m∑s=1m-1aγ,tãα,s|,(2.15)ηα,β,γ6=|∑s=1m∑t=1maβ,saγ,t-βγn2|+|∑t=1m∑r=0m∑s=1m-1aγ,taα,rãβ,s|,(2.16)ηα,β,γ7=|∑r=1m∑s=1m∑t=1maα,raβ,saγ,t-αβγn3|+|∑r=1m∑t=1m∑s=1m-1aβ,raγ,tãα,s|,
where(2.17)ãα,0=∑t=1maα,t-αn,α=0,1,…,n-1,ãα,j=∑t=j+1maα,t,j⩾1,α=0,1,…,n-1.
Furthermore, suppose(2.18)ϑ=max⁡α,β,γ{(χ)∑t=17(ηα,β,γt),α,β,γ=0,1,…,n-1}.


## 3. Depth for Tensor Productn-Ary Volumetric Models

In this paragraph, we compute subdivision depth for tensor productn-ary volumetric model. Moreover, we show that error bound for binary subdivision volumetric models [17] is special case of our bound. Here we need following lemmas for Theorem 3.5. The proof of first two lemmas are shown in Appendices A and B, respectively.Lemma 3.1.
Given initial control polygonpi,j,l0=pi,j,l, i,j,l∈ℤ, let the values pi,j,lk, k⩾1 be defined recursively by (2.4) together with (2.2), then
(3.1)max⁡i,j,l‖Δi,j,l,tk‖⩽(δ)kmax⁡i,j,l‖Δi,j,l,t0‖,
where δ and Δi,j,l,tk, t=1,2,…,7, are defined by (2.5) and (2.8), respectively.Lemma 3.2.
Given initial control polygonpi,j,l0=pi,j,l, i,j,l∈ℤ, let the values pi,j,lk, k⩾1 be defined recursively by (2.4) together with (2.2), then
(3.2)Mα,β,γk⩽(χ)(δ)k∑t=17(ηα,β,γt),
where δ,Mα,β,γk, χ, ηα,β,γt for α,β,γ=0,1,…,n-1 are defined by (2.5), (2.7), (2.9)–(2.16), respectively.Lemma 3.3.
Given initial control polygonpi,j,l0=pi,j,l, i,j,l∈ℤ, let the values pi,j,lk, k⩾1 be defined recursively by (2.4) together with (2.2). Suppose Pk is the piecewise linear interpolant to the values pi,j,lk and P∞ is the limit volumetric model of (2.4). If δ<1, then error bound between tensor product n-ary volumetric model and its control polygon after k-fold subdivision is
(3.3)‖Pk-P∞‖∞⩽ϑ((δ)k1-δ),
where δ and ϑ are defined by (2.5) and (2.18), respectively.Proof.
Let∥·∥∞ denote the uniform norm. Since the maximum difference between Pk+1 and Pk is attained at a point on the (k+1)th mesh, we have
(3.4)‖Pk+1-Pk‖∞⩽max⁡α,β,γ{Mα,β,γk,α,β,γ=0,1,…,n-1},
where Mα,β,γk is defined by (2.7). By (3.2) and (3.4), we get
(3.5)‖Pk+1-Pk‖∞⩽ϑ(δ)k,
where δ and ϑ are defined by (2.5) and (2.18), respectively.
By triangle inequality we get (3.3). This completes the proof.Remark 3.4.
Theorem 3.10 in [17] is designed to estimate error bound for binary subdivision volumetric model (i.e., each cube is divided in 8 subcubes). But for the higher arity subdivision schemes such as for n=3,4,5,… (when each cube is divided in 33,43,53,… subcubes) error estimates are not feasible by existing result. So estimation of error bounds for tensor product n-ary volumetric model is quite necessary. Our Lemma 3.3 provides freedom to evaluate error bound for all arities. Here we also mention that Lemma 3.3 for n=2 reduces to [17, Theorem 3.10].Now we offer the computational formula of subdivision depth for tensor productn-ary volumetric model.Theorem 3.5.
Letk be subdivision depth, and let dk be the error bound between tensor product n-ary volumetric model P∞ and its k-level control polygon Pk. For arbitrary ϵ>0, if
(3.6)k⩾log⁡δ-1(ϑϵ(1-δ)),
then
(3.7)dk⩽ϵ.Proof.
From (3.3), we have
(3.8)dk=‖Pk-P∞‖∞⩽ϑ((δ)k1-δ).
This implies, for arbitrary given ϵ>0, when subdivision depth k satisfies the following inequality:
(3.9)k⩾log⁡δ-1(ϑϵ(1-δ)),
then
(3.10)dk⩽ϵ.
This completes the proof.


## 4. Applications

### 4.1. Error Bound and Subdivision Depth of Tensor Productn-Ary Interpolating Volumetric Models

In this section, we estimate the error bound and subdivision depth of(2b+2)-point tensor product n-ary interpolating volumetric models. By taking the tensor product of (2b+2)-point n-ary scheme of [4], we get the following:
(4.1)pni,nj,nlk+1=pi,j,lk,pni+s1,nj,nlk+1=∑t1=-bb+1(As1,t1)pt1+i,j,lk,pni,nj+s2,nlk+1=∑t2=-bb+1(As2,t2)pi,t2+j,lk,pni,nj,nl+s3k+1=∑t3=-bb+1(As3,t3)pi,j,t3+lk,pni+s1,nj+s2,nlk+1=∑t1=-bb+1∑t2=-bb+1(As1,t1)(As2,t2)pt1+i,t2+j,lk,pni+s1,nj,nl+s3k+1=∑t1=-bb+1∑t3=-bb+1(As1,t1)(As3,t3)pt1+i,j,t3+lk,pni,nj+s2,nl+s3k+1=∑t2=-bb+1∑t3=-bb+1(As2,t2)(As3,t3)pi,t2+j,t3+lk,pni+s1,nj+s2,nl+s3k+1=∑t1=-bb+1∑t2=-bb+1∑t3=-bb+1(As1,t1)(As2,t2)(As3,t3)pt1+i,t2+j,t3+lk,
where (4.2)Ax,y=∏m=-bb+1(x-nm)(x-ny)(-1)(b-1-y)(n)(2b+1)(b+y)!(b-y+1)!,s1,s2,s3=1,2,…,n-1, b=1,2,3,… and n stands for n-ary interpolating subdivision volumetric model, that is, n=2,3,4,… stands for binary, ternary, quaternary and so on, respectively.The error bounds and subdivision depth of (4.1) are shown in Tables 1 and 2, respectively. In these tables, we have shown the error bounds and depth of different arity interpolating subdivision volumetric models by using Lemma 3.3 and Theorem 3.5 with χ=0.1.Table 1
Error bound of tensor productn-ary interpolating volumetric models: here n presents the arity of subdivision volumetric model and k presents the subdivision level.
n∖k123456720.5187500.2593750.1296880.0648440.0324220.0162110.00810530.2915640.0971880.0323960.0107990.0036000.0012000.00040040.2045570.0511390.0127850.0031960.0007990.0002000.00005050.1578800.0315760.0063150.0012630.0002530.0000510.00001060.1286470.0214410.0035740.0005960.0000990.0000170.000003Table 2
Subdivision depth of tensor productn-ary interpolating volumetric models: here n presents the arity of subdivision volumetric model and ϵ presents error tolerance.
n∖ϵ0.5187500.2593750.1296880.0648440.0324220.0162110.0081052123456731223345411223345112223361112233


### 4.2. Error Bound and Subdivision Depth of Tensor Productn-Ary Approximating Volumetric Models

In this section, we estimate the error bound and subdivision depth of tensor product(2b+2)-point n-ary approximating volumetric models. By taking the tensor product of (2b+2)-point n-ary scheme of [4], we get the following:(4.3)pni+s1,nj+s2,nl+s3k+1=∑t1=-bb+1∑t2=-bb+1∑t3=-bb+1(Bs1,t1)(Bs2,t2)(Bs3,t3)pt1+i,t2+j,t3+lk,
where (4.4)Bx,y=(∏m=-bb+1(2x+1-2nm)(2x+1-2ny)(-1)(b-1-y)(2n)(2b+1)(b+y)!(b-y+1)!),s1,s2,s3=1,2,…,n-1, b=1,2,3,…, and n stands for n-ary approximating subdivision volumetric model, that is, n=2,3,4,… stands for binary, ternary, quaternary, and so on, respectively.The error bounds and subdivision depth of (4.3) are shown in Tables 3 and 4, respectively. In these tables, we have shown the error bounds and depth of different arity approximating subdivision volumetric by using Lemma 3.3 and Theorem 3.5 with χ=0.1.Table 3
Error bound of tensor productn-ary approximating volumetric models: here n presents the arity of subdivision volumetric model and k presents the subdivision level.
n∖k123456720.6239650.3119820.1559910.0779960.0389980.0194990.00974930.3273910.1091300.0363770.0121260.0040420.0013470.00044940.2227420.0556860.0139210.0034800.0008700.0002180.00005450.1689080.0337820.0067560.0013510.0002700.0000540.00001160.1360570.0226760.0037790.0006300.0001050.0000170.000003Table 4
Subdivision depth of tensor productn-ary approximating volumetric models: here n presents the arity of subdivision volumetric model and ϵ presents error tolerance.
n∖ϵ0.6239650.3119820.1559910.0779960.0389980.0194990.0097492123456731223345411223345112223361112233


## 4.1. Error Bound and Subdivision Depth of Tensor Productn-Ary Interpolating Volumetric Models

In this section, we estimate the error bound and subdivision depth of(2b+2)-point tensor product n-ary interpolating volumetric models. By taking the tensor product of (2b+2)-point n-ary scheme of [4], we get the following:
(4.1)pni,nj,nlk+1=pi,j,lk,pni+s1,nj,nlk+1=∑t1=-bb+1(As1,t1)pt1+i,j,lk,pni,nj+s2,nlk+1=∑t2=-bb+1(As2,t2)pi,t2+j,lk,pni,nj,nl+s3k+1=∑t3=-bb+1(As3,t3)pi,j,t3+lk,pni+s1,nj+s2,nlk+1=∑t1=-bb+1∑t2=-bb+1(As1,t1)(As2,t2)pt1+i,t2+j,lk,pni+s1,nj,nl+s3k+1=∑t1=-bb+1∑t3=-bb+1(As1,t1)(As3,t3)pt1+i,j,t3+lk,pni,nj+s2,nl+s3k+1=∑t2=-bb+1∑t3=-bb+1(As2,t2)(As3,t3)pi,t2+j,t3+lk,pni+s1,nj+s2,nl+s3k+1=∑t1=-bb+1∑t2=-bb+1∑t3=-bb+1(As1,t1)(As2,t2)(As3,t3)pt1+i,t2+j,t3+lk,
where (4.2)Ax,y=∏m=-bb+1(x-nm)(x-ny)(-1)(b-1-y)(n)(2b+1)(b+y)!(b-y+1)!,s1,s2,s3=1,2,…,n-1, b=1,2,3,… and n stands for n-ary interpolating subdivision volumetric model, that is, n=2,3,4,… stands for binary, ternary, quaternary and so on, respectively.The error bounds and subdivision depth of (4.1) are shown in Tables 1 and 2, respectively. In these tables, we have shown the error bounds and depth of different arity interpolating subdivision volumetric models by using Lemma 3.3 and Theorem 3.5 with χ=0.1.Table 1
Error bound of tensor productn-ary interpolating volumetric models: here n presents the arity of subdivision volumetric model and k presents the subdivision level.
n∖k123456720.5187500.2593750.1296880.0648440.0324220.0162110.00810530.2915640.0971880.0323960.0107990.0036000.0012000.00040040.2045570.0511390.0127850.0031960.0007990.0002000.00005050.1578800.0315760.0063150.0012630.0002530.0000510.00001060.1286470.0214410.0035740.0005960.0000990.0000170.000003Table 2
Subdivision depth of tensor productn-ary interpolating volumetric models: here n presents the arity of subdivision volumetric model and ϵ presents error tolerance.
n∖ϵ0.5187500.2593750.1296880.0648440.0324220.0162110.0081052123456731223345411223345112223361112233


## 4.2. Error Bound and Subdivision Depth of Tensor Productn-Ary Approximating Volumetric Models

In this section, we estimate the error bound and subdivision depth of tensor product(2b+2)-point n-ary approximating volumetric models. By taking the tensor product of (2b+2)-point n-ary scheme of [4], we get the following:(4.3)pni+s1,nj+s2,nl+s3k+1=∑t1=-bb+1∑t2=-bb+1∑t3=-bb+1(Bs1,t1)(Bs2,t2)(Bs3,t3)pt1+i,t2+j,t3+lk,
where (4.4)Bx,y=(∏m=-bb+1(2x+1-2nm)(2x+1-2ny)(-1)(b-1-y)(2n)(2b+1)(b+y)!(b-y+1)!),s1,s2,s3=1,2,…,n-1, b=1,2,3,…, and n stands for n-ary approximating subdivision volumetric model, that is, n=2,3,4,… stands for binary, ternary, quaternary, and so on, respectively.The error bounds and subdivision depth of (4.3) are shown in Tables 3 and 4, respectively. In these tables, we have shown the error bounds and depth of different arity approximating subdivision volumetric by using Lemma 3.3 and Theorem 3.5 with χ=0.1.Table 3
Error bound of tensor productn-ary approximating volumetric models: here n presents the arity of subdivision volumetric model and k presents the subdivision level.
n∖k123456720.6239650.3119820.1559910.0779960.0389980.0194990.00974930.3273910.1091300.0363770.0121260.0040420.0013470.00044940.2227420.0556860.0139210.0034800.0008700.0002180.00005450.1689080.0337820.0067560.0013510.0002700.0000540.00001160.1360570.0226760.0037790.0006300.0001050.0000170.000003Table 4
Subdivision depth of tensor productn-ary approximating volumetric models: here n presents the arity of subdivision volumetric model and ϵ presents error tolerance.
n∖ϵ0.6239650.3119820.1559910.0779960.0389980.0194990.0097492123456731223345411223345112223361112233


## 5. Conclusion and Future Work

We have computed subdivision depth based on error bounds for tensor productn-ary volumetric models. Furthermore, we have shown that error bounds for binary subdivision volumetric model [17] is special case of our bounds. It is noticed that the increase in arity results gradually decrease in error, which is shown in Tables 1, 3 and graphically in Figure 4. It is noticed from Tables 2 and 4 that higher arity subdivision volumetric models need less number of subdivision steps than lower arity to satisfy user-specified error tolerance.(a) Presents comparison among the error bounds of different arity subdivision volumetric models (4.1), that is, for n=2,3,4,5,6; (b) presents comparison among the error bounds of different arity subdivision volumetric models (4.3), that is, for n=2,3,4,5,6. Here k presents subdivision level, n presents the arity and ϵ presents the user-specified error tolerance.
(a)(b)The authors are looking, as a future work, to extend the computational techniques of subdivision depth forn-ary arbitrary subdivision volumetric models over rectangular/triangular hexahedron lattice. we will discuss them elsewhere.



---

*Source: 203453-2011-04-26.xml*