Sub division metho ds for geometric design
Jo e Warren
Department of Computer Science
Rice University
Novemb er 15, 1995
Contents
1 Intro duction 5
2 Sub division metho ds for uniform B-splines 11
2.1 Degree zero B-splines
::: ::::: :::: ::::: :::: :::: ::::: :
11
2.2 Higher degree B-splines
::::: :::: :::: ::::: :::: ::::: :::
12
2.3 Subdivision as discrete convolution
:::: ::::: :::: :::: ::::: :
15
2.4 The Lane-Riesenfeld algorithm
::: :::: ::::: :::: :::: ::::: :
17
3 Convergence analysis for uniform sub division 19
3.1 Parameterization of subdivision metho ds
::: ::::: :::: ::::: :::
19
3.2 Convergence of sequences of functions
::: ::::: :::: :::: ::::: :
20
3.3 Uniform convergence to a continuous function
::::: :::: ::::: :::
22
3.4 Convergence to a smooth function
::: :::: ::::: :::: ::::: :::
25
4 Sub division over irregular knot sequences 29
4.1 Denition of irregular subdivision schemes
::::: :::: :::: ::::: :
30
4.2 Basis functions
:::: ::::: :::: :::: ::::: :::: ::::: :::
31
4.3 Example: Interpolating subdivision
:::: ::::: :::: :::: ::::: :
32
4.4 Reduction to the stationary case
:::: :::: ::::: :::: ::::: :::
34
5 Univariate stationary sub division 37
5.1 Spectral analysis
::: ::::: :::: :::: ::::: :::: ::::: :::
37
5.1.1 A sp ectral recurrence
:::: :::: ::::: :::: :::: ::::: :
39
5.1.2 Properties of the recurrence
:::: ::::: :::: :::: ::::: :
39
5.2 Necessary conditions for
C
k
continuity
:::: ::::: :::: ::::: :::
40
5.3 Sucient conditions for
C
k
continuity
::::::::::::::::::::::
42
5.4 Derivativeschemes
:::: ::::: :::: ::::: :::: :::: ::::: :
44
5.4.1 Linear parameterizations
:::: :::: ::::: :::: ::::: :::
45
1
2
CONTENTS
5.4.2 Non-uniform dierencing op erator
::: ::::: :::: ::::: :::
47
5.4.3 Derivativeschemes
::::: :::: ::::: :::: :::: ::::: :
48
5.5 Parametric analysis
:::: ::::: :::: ::::: :::: :::: ::::: :
50
6 Multi-variate sub division over regular grids 53
6.1 B-splines as cross-sectional volumes
:::: ::::: :::: :::: ::::: :
53
6.2 Box splines
:::: :::: ::::: :::: ::::: :::: :::: ::::: :
55
6.3 Properties of box splines
:::: :::: :::: ::::: :::: ::::: :::
58
6.4 Examples
::: :::: ::::: :::: :::: ::::: :::: ::::: :::
59
7 Sub division over irregular triangulations 65
7.1 Bivariate subdivision schemes
::: :::: ::::: :::: :::: ::::: :
65
7.1.1 Basis functions
::::: :::: :::: ::::: :::: ::::: :::
67
7.1.2 Reduction to the stationary case
:::: ::::: :::: ::::: :::
68
7.2 Spectral conditions for irregular subdivision
:::: :::: :::: ::::: :
69
7.2.1 Spectral analysis
:::: :::: :::: ::::: :::: ::::: :::
69
7.2.2 A sp ectral recurrence
:::: :::: ::::: :::: :::: ::::: :
70
7.2.3 Properties of the recurrence
:::: ::::: :::: :::: ::::: :
71
7.2.4 Necessary conditions for
C
k
subdivision
:::::::::::::::::
72
7.3 Convergence conditions for irregular subdivision
:::: :::: ::::: :::
74
7.3.1 Dierence schemes
::::: :::: ::::: :::: :::: ::::: :
74
7.3.2 A lo cal construction for dierence schemes
:::::::::::::::
78
7.4 An approximating
C
1
scheme
::::::::::::::::::::::::::
81
7.4.1 Perturbation using
:::: :::: ::::: :::: :::: ::::: :
81
7.4.2 Proof of
C
1
continuity
::::::::::::::::::::::::::
82
8 Sub division schemes for triangular meshes 89
8.1
C
k
manifolds
::: :::: ::::: :::: ::::: :::: :::: ::::: :
89
8.2 Limitations of regular meshes
::: :::: ::::: :::: :::: ::::: :
90
8.3
C
1
subdivision methods for closed meshes
::::: :::: :::: ::::: :
91
8.4
C
1
continuity at extraordinary vertices
:::: ::::: :::: ::::: :::
94
8.5 Subdivision along b oundaries
::: :::: ::::: :::: :::: ::::: :
96
8.5.1 Boundaries for curves
:::: :::: ::::: :::: :::: ::::: :
96
CONTENTS
3
8.5.2 Boundaries for surfaces
::: :::: ::::: :::: :::: ::::: :
98
9 Multiresolution analysis based on sub division 103
9.1 Overview
:::: :::: ::::: :::: :::: ::::: :::: ::::: :::
103
9.2 Nested spaces
::: :::: ::::: :::: ::::: :::: :::: ::::: :
104
9.3 Orthogonal spaces
::: ::::: :::: :::: ::::: :::: ::::: :::
106
9.4 Filter banks
:::: :::: ::::: :::: ::::: :::: :::: ::::: :
107
4
CONTENTS
