Warren J., Weimer H. Subdivision Methods for Geometric Design. A Constructive Approach
Подождите немного. Документ загружается.
294 Index
natural cubic splines (continued)
Euler-Lagrange theorem, 175
exact inner products, 182–183
finite element basis functions,
170–171, 183
finite element scheme for, 169–173
inner product matrices, 170–174
inner products, continuous, 169–170
interpolation with, 180–182
knots, 168–169
limit functions, computing, 182–183
matrix refinement relation, 171
multiscale relation for, 173–176
stationary subdivision matrix
computation, 177–178
subdivision matrices, 173–176, 176–177
subdivision rules for, 176–180
two-scale relation theorem, 174
variational formulation, 167–169
variational functional, 175
variational matrix multiscale
relation, 174
Navier-Stokes equations, 142
non-defective subdivision matrices, 245
nonstationary schemes, 105, 106, 110,
116–119
nonuniform domains, 157. See also
bounded domains
norms
of block matrices, 84, 87
defined, 65–66
minimizing limit norms, 137
of a vector, 73
NURBS (nonuniform rational B-spline),
212, 274–275
one-ring, 244
open surface meshes, 201
operators, 93–94
ordinary vertices, 203
Oslo algorithm, 273
parametric representation of functions, 1–3
partial differential equations
Navier-Stokes equations, 142
polyharmonic splines, 128
pawn (chess) construction, 216–217
perfect flows, 143
piecewise analytic functions, exponential
B-splines as, 106–109
piecewise linear functions
conditions for uniform convergence,
73–75
convergence of sequences of, 63
derivatives, convergence of, 68
pointwise convergence, 63–64
uniform convergence, 65–69
piecewise linear splines
basis functions, 20
collage property, 21–22
dilating the coordinate axis, 21
hat functions, 19–20, 22
knots, 20
refinement relation, 21–22
scaling functions, 20–22, 27
subdivision scheme for, 22–25
two-slanted matrices, 22–23
uniform splines, 20
piecewise polynomial basis functions
box spline scaling functions, 44
B-spline basis functions, 30
piecewise polynomials
approximating control polygons, 28
box splines as, 52–53
B-splines as, 52–56
difficulties with, 3–4
smoothness, 28
utility of, 18–19
pointwise convergence, 63–64
polyharmonic splines, 120–141
analytic solution to differential
equation, 122
bell-shaped basis for, 124–127
biharmonic spline difference masks, 125
comparison of methods, 138–141
correction masks, 134
difference masks, 128–129
discrete Laplacian masks, 124–125
finite difference equation, 128
finite truncation masks, 131–132
Green’s function, 121–122
harmonic masks, 130–131
Jacobi iteration for local approximations,
133–136, 138–141
Laplace operator, 121
Laurent series expansion, 129–133,
138–141
linear programming for optimal local
approximations, 136–141
local approximations to, 129–141
localized nature of basis functions, 126
minimization of limit norm problem, 137
Index 295
partial differential equation
governing, 128
radial basis for, 121–124
residual plots, compared, 138–141
smoothing masks, 134
smoothness of basis functions, 126
subdivision masks, 128–129
subdivision relation equation, 128
subdivision scheme for, 127–129
thin plate splines, 123–124
polyhedral meshes
4-8 subdivision, 203–204
bilinear subdivision plus quad averaging,
205–209
circulant matrices, computing
eigenvalues of, 260–263
constant subdivision, 236
continuity at extraordinary vertices,
254–259, 275
defined, 200
discs, 201
doughnut shaped example, 208
dual subdivision schemes, 234–238
edge-splitting subdivisions, 203–204
embedded creases, averaging for,
220–226
exact evaluation near an extraordinary
vertices, 246–249
extraordinary vertices, convergence
analysis at, 239–249
face-splitting schemes, 232–234
geometrical positioning step, 201
interpolatory face-splitting schemes,
233–234
isolation of extraordinary vertices, 203
manifolds defined, 249
quad meshes. See quad meshes
rational parametrizations, 212
rings, 201
separating topology from geometry, 200
smoothing quad meshes, 207
stellated octahedron example, 229
surfaces of revolution, 212–220
tensor product rule, 205–206
topological subdivision of, 201–204
triangle mesh smooth subdivision,
226–232
triangle subdivision, 201–202
two-step subdivision schemes,
201, 226
valences, 201, 203
vertices, 200–202
polynomials
basis function representation, 5
convergence of subdivision schemes
on, 76
defined, 3–4
piecewise. See piecewise polynomials
polynomial splines
differential approach, 92, 98
interpolation matrices, 158–159
splines in tension, 110–112
power series expansion, 129
prediction followed by smoothing, 136
primal schemes, 146–147
quad meshes
averaging operator, 206–207
axe, mesh model of, 221, 223
bilinear subdivision plus quad averaging,
205–209
Catmull-Clark subdivision, 209–212
defined, 201
doughnut shaped example, 208
dual meshes, 235–236
embedded creases, averaging for,
220–226
extraordinary vertex rule, 210–211
face-splitting schemes, 232–234
high-dimensional generalizations, 209
king, chess, mesh model, 224
non-manifold topology, 208
quad averaging, 207–208
ring, mesh model of, 221–222
smoothing rule, 207
tensor product rule, 205–206
umbilic tori, mesh model, 224–225
uniform rule, 209–210
weighted centroids, 214–215
quadratic box splines, 49–50, 59–60, 87–88
quadratic B-splines, cross-sectional
refinement relations, 43–44
quadratic cone splines, 59–60
quad subdivision, 202. See also quad meshes
quartic box splines, 51–52, 61
radial basis functions, 123–124, 151–156
rational parametrizations, 212
real numbers, convergence of
sequences, 63
rectangular domains, subdivision on,
193–197
296 Index
recurrences
B
´
ezier control points, 15
B-spline basis functions differential
recurrence, 95
B-splines, 29, 34, 39, 42
characteristic maps, 251
Cosh, 111
differential method, 91, 93, 95, 97
eigenfunctions, 253
eigenvectors with self-similar structure,
247–248
inner product matrix theorem, 163
interpolation matrices, 160
refinement. See refinement relations
tension parameter, 115
two-scale, 21
refinement relations
box splines, 45–48, 46
B-spline basis functions, 29, 33–35, 43
cross-sectional volumes, 43
defined, 21–22
generating functions for subdivision
masks, 33
hypercube subdivision method, 43
piecewise linear splines, 27
for polyharmonic splines, 127–128
subdivision masks, B-spline, 33–35
regular characteristic maps, 250–251,
267–271
relaxation factors for iterative methods, 134
repeated integration
box splines, 45–48
B-splines, 29
defined, 27
ring, mesh model of, 221–222
rings of vertices, 201, 244
scaling functions
box splines, 44–47, 101
defined, 20–22
exact derivatives for, 158–162
exponential B-splines, 108
piecewise linear splines, 27
quartic box splines, 51–52
refinement relations, 27
with stationary vs. nonstationary
schemes, 106
scaling relations
cone splines, 57
for Laplace operator partial differential
equation, 122
self-similarity relation, 13
Sierpinski triangle, 12–13
slow flow, 143–144, 155–156
smoothing masks, 134
smoothness
of basis functions for polyharmonic
splines, 126
bivariate schemes, convergence to, 85–88
Butterfly scheme, 88–89
characteristic maps, 250–252, 267–271
continuity at extraordinary vertices,
254–259
eigenfunctions, 252–253
extraordinary vertices, analysis at,
249–259
extraordinary vertices, verifying for
schemes, 259–271
four-point scheme, 79–81
interpolatory bivariate schemes, 88–90
manifolds defined, 249
smoothing masks, 134
tensor product meshes, 89–90
testing for, 77–78
triangle mesh surfaces, 229
smooth piecewise polynomial basis
functions, 28, 30
spaces, multiresolution, 184–188
spectral analysis
Catmull-Clark subdivision, 267
characteristic maps, 250–252, 267–271
circulant matrices, computing
eigenvalues of, 260–263
condition for convergence, 246
continuity at extraordinary vertices,
254–259
defined, 244–245
eigenfunctions, 252–259
local, of extraordinary vertices, 243–246
local subdivision matrices, computing
eigenvectors and eigenvalues at,
263–267
Loop subdivision, 263–267
non-defective subdivision matrices, 245
regularity of characteristic maps,
267–271
smoothness analysis, 249–259
spheres
rational parametrizations, 212
as surface of revolution mesh, 216–218
topological restrictions on, 199
splines
B. See B-splines
Index 297
bending energy, 168
bounded harmonic. See bounded
harmonic splines
defined, 91
differential equations forming, 91
helix, 112
mixed trigonometric, 112–114
natural, equation of, 168
physical origin of idea, 167–168
piecewise linear. See piecewise linear
splines
polyharmonic. See polyharmonic splines
theory of, 91
splines in tension, 107, 110–112
Stam’s method, 246–249
stationary schemes, 105, 106, 110
at extraordinary vertices, 239
inner products for, 157–167
stellated octahedron example, 229
subdivision
advantages of, 25
defined, 19, 24
subdivision masks, 33–35
affine invariant, 82–83
bivariate difference case, 82
block matrix analog, 84, 87
box splines, 45–48
centering, 37
conditions for converging to
polynomials, 76
cubic B-splines, 37–38
differences of functions, 70–72
exact, bounded harmonic splines,
191–192
existence of, for differences, 78
factoring, 39
four-point scheme, 79–81
generating functions defined by, 62
harmonic masks for polyharmonic
splines, 130–131
of interpolatory bivariate schemes, 88–90
Jacobi iteration for local approximations,
133–136
linear flows, 149–150
matrix refinement relation, 35–36
polyharmonic splines, 128–129
for polynomial splines, 98
quadratic box splines, 49–50
quartic box splines, 51–52
for splines in tension, 111
stationary vs. nonstationary, 110
tensor product meshes, 89–90
three-direction linear splines, 48–49
unified for exponential splines,
114–115
uniform B-splines, 37
uniform convergence, conditions for,
73–75
with zeros of order m + 1, 77, 86
subdivision matrices
bounded harmonic splines, 191–193
circles, 212–213
defined, 22
inner product matrix theorem, 163
natural cubic splines, 173–177
properties of, 25–26
triangle meshes, 230–232
uniform convergence, 84, 87
using, 23–25
subdivision on a quadrant, 191–193
subdivision on bounded rectangular
domains, 193–197
subdivision schemes
bivariate, analysis of, 81–90
box splines, 45–48
B-splines, differential approach, 97–99
B-splines, integration approach, 29–40
capable of reproducing all polynomials,
77–78
convergence. See convergence analysis
differences of functions, 70–72
differential method for box splines,
101–102
exponential B-splines, 105–106, 109
interpolatory univariate, 79
for linear flows, 149–151
piecewise linear splines, 22–25
for polyharmonic splines, 127–129
quadratic box splines, 49–50
quartic box splines, 51–52
stationary vs. nonstationary, 105,
106, 110
three-direction linear splines, 48–49
unified, differential approach, 114–115
uniform convergence, conditions for,
73–75
surface meshes
defined, 201
edge-splitting subdivisions, 203–204
isolation of
extraordinary vertices, 203
quad subdivision, 202
topological subdivision, 201–202
triangle subdivision, 201–202
surface representation problem, 199
298 Index
surfaces of revolution
double-sheeted surfaces, 218
tensor product meshes, 215–216
tensor product of mixed trigonometric
splines, 113–114
weighted averaging of polyhedral meshes,
212–220
weighted centroids, 214–215
surface/surface intersection, 275
synthesis filters, 274
tension parameter
mixed trigonometric splines, 112–114
recurrence theorem, 115
splines in tension, 107, 110–112
unified scheme, 114–115
tensor product meshes, 215–216
tensor product rule, 205–206
thin plate splines, 123–124
three-direction linear cone splines,
58–59
three-direction linear splines, 48–49,
58–59
three-direction quartic box splines, 51–52,
61, 226–229
three-direction quartic cone splines, 61
topological duals, 235
topological meshes
creases, expanding to include,
220–221
defined, 199
polyhedral. See polyhedral meshes
quad meshes. See quad meshes
surface meshes, 201
topological subdivision, 201–202
triangle meshes, 201
triangle subdivision, 201–202
vertices, numbering, 199
topological restrictions, 199
topological subdivision, 201–203
tori
parametric surface equivalent,
198–199
rational parametrizations, 212
as surface of revolution mesh,
216–218
transformations, 9–11
triangle averaging, 227–228
triangle meshes
defined, 201
dual meshes, 235, 237–238
edge rules, 230
face-splitting schemes, 232–234
linear subdivision with averaging,
226–229
Loop subdivision, 230–232
smooth subdivision, 226–232
subdivision, 201–202
subdivision matrix method, 230–232
vertex rules, 230
vertices, 203
truncated powers
differential operator representation, 94
function, 54–55
Green’s functions for exponential
B-splines, 107
integral operator representation, 93
multivariate. See cone splines
representation of B-splines, 53–56, 93
two-direction (tensor product) meshes,
89–90
two-ring, 244
two-scale relations, 21
two-slanted matrices, 22–23
umbilic tori, mesh model, 224–225
uniform B-splines
defined, 28
interpolation matrices, 158–159
subdivision scheme, 37
uniform convergence
of bivariate schemes, conditions for,
83–85
conditions for, 73–75
difference method, 65–68
smooth functions, 68–69
uniform splines, defined, 20
unit hat function, 19–20
univariate subdivision schemes, 69–81.
See also B-splines
upsampling matrices, 159, 174, 191
valences, 201, 203, 240
variational functionals
bounded harmonic splines, 188
discrete version, 175
inner product form of expression,
185–186
minimization using limit functions,
184–188
natural splines, 168–170, 175
Index 299
variational problems, finite element
method, 169–173
vector fields, subdivision schemes for. See
linear flows
vertices
defined, 203
dimension of, defined, 221
extraordinary. See extraordinary vertices
weighted averaging for surfaces of
revolution, 212–220
weighted centroids, 214–215, 227–228
zeros of order m + 1
bivariate scheme masks with, 86
univariate subdivision masks with, 77