Warren J., Weimer H. Subdivision Methods for Geometric Design. A Constructive Approach
Подождите немного. Документ загружается.
Subdivision Methods
for Geometric Design:
A Constructive Approach
The Morgan Kaufmann Series in Computer
Graphics and Geometric Modeling
Series Editor: Brian A. Barsky,
University of California, Berkeley
Subdivision Methods for Geometric Design:
A Constructive Approach
Joe Warren and Henrik Weimer
The Computer Animator’s Technical
Handbook
Lynn Pocock and Judson Rosebush
Computer Animation: Algorithms and
Techniques
Rick Parent
Advanced RenderMan: Creating CGI
for Motion Pictures
Anthony A. Apodaca and Larry Gritz
Curves and Surfaces in Geometric Modeling:
Theory and Algorithms
Jean Gallier
Andrew Glassner’s Notebook: Recreational
Computer Graphics
Andrew S. Glassner
Warping and Morphing of Graphical Objects
Jonas Gomes, Lucia Darsa, Bruno Costa,
and Luis Velho
Jim Blinn’s Corner: Dirty Pixels
Jim Blinn
Rendering with Radiance: The Art and Science
of Lighting Visualization
Greg Ward Larson and Rob Shakespeare
Introduction to Implicit Surfaces
Edited by Jules Bloomenthal
Jim Blinn’s Corner: A Trip Down the Graphics
Pipeline
Jim Blinn
Interactive Curves and Surfaces:
A Multimedia Tutorial on CAGD
Alyn Rockwood and Peter Chambers
Wavelets for Computer Graphics: Theory and
Applications
Eric J. Stollnitz, Tony D. DeRose, and
David H. Salesin
Principles of Digital Image Synthesis
Andrew S. Glassner
Radiosity & Global Illumination
Franc¸ois X. Sillion and Claude Puech
Knotty: A B-Spline Visualization Program
Jonathan Yen
User Interface Management Systems: Models
and Algorithms
Dan R. Olsen, Jr.
Making Them Move: Mechanics, Control, and
Animation of Articulated Figures
Edited by Norman I. Badler, Brian A. Barsky,
and David Zeltzer
Geometric and Solid Modeling:
An Introduction
Christoph M. Hoffmann
An Introduction to Splines for Use in Computer
Graphics and Geometric Modeling
Richard H. Bartels, John C. Beatty, and
Brian A. Barsky
Subdivision Methods
for Geometric Design:
A Constructive Approach
Joe Warren
Rice University
Henrik Weimer
DaimlerChrysler AG, Berlin
Executive Editor Diane D. Cerra
Publishing Services Manager Scott Norton
Production Editor Howard Severson
Assistant Editor Belinda Breyer
Cover Design Ross Carron Design
Text Design Rebecca Evans & Associates
Composition and Illustration Interactive Composition Corporation
Copyeditor Daril Bentley
Proofreader Mary Roybal
Indexer Bill Meyers
Printer Courier Corporation
Designations used by companies to distinguish their products are often claimed as trade-
marks or registered trademarks. In all instances in which Morgan Kaufmann Publishers is
aware of a claim, the product names appear in initial capital or all capital letters. Readers,
however, should contact the appropriate companies for more complete information regard-
ing trademarks and registration.
Morgan Kaufmann Publishers
340 Pine Street, Sixth Floor, San Francisco, CA 94104-3205, USA
http://www.mkp.com
ACADEMIC PRESS
A Division of Harcourt, Inc.
525 B Street, Suite 1900, San Diego, CA 92101-4495, USA
http://www.academicpress.com
Academic Press
Harcourt Place, 32 Jamestown Road, London, NW1 7BY, United Kingdom
http://www.academicpress.com
c
2002 by Academic Press
All rights reserved
Printed in the United States of America
0605040302 54321
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in
any form or by any means—electronic, mechanical, photocopying, or otherwise—without
the prior written permission of the publisher.
Library of Congress Control Number: 2001094349
ISBN: 1-55860-446-4
This book is printed on acid-free paper.
Foreword
Tony DeRose
Pixar Animation Studios
Considerable effort has been expended over the last forty years in the area of geo-
metric design, the goal of which is to develop efficient and flexible representations
of complex shapes. Applications of geometric design are broad and varied; they in-
clude aerospace and automotive design, industrial design, and computer animation
for interactive games, commercials, and full-length feature films.
B
´
ezier curves, developed independently by Pierre B
´
ezier at Renault and Paul
de Casteljau at Citroen in the early ’60s, were one of the first successful computer
representations. They are still the representation of choice in some applications.
B
´
ezier curves were followed by B-splines, which were introduced into geometric
design in the mid ’70s by Riesenfeld and others. B-splines possess a beautiful un-
derlying theory that leads to a wide range of highly efficient algorithms, which is
why they have become the standard representation in geometric design systems.
B-spline surfaces do however have a severe shortcoming. They can only represent
a limited set of surface topologies—namely, topological disks, cylinders, and tori.
The search for a representation that overcomes the topological limitations of
B-splines began shortly after the introduction of B-splines to geometric design.
Inspired by George Chaikin’s work that described curves as the limit of a sequence
of subdivision steps, two teams of researchers (Ed Catmull and Jim Clark, and
Malcolm Sabin and D. Doo) independently developed the notion of subdivision
surfaces in 1978.
Subdivision surfaces naturally admit arbitrary surface topologies. They were
initially met with considerable enthusiasm, but since they lacked the beautiful and
powerful theory of B-splines, they were treated as a rather exotic representation
for nearly 20 years. That began to change in the mid ’90s. Advances were made on
a number of fronts by researchers in numerous disciplines, including approxima-
tion theory, numerical analysis, and computer graphics. These surfaces are rapidly
establishing themselves as the new representation of choice, and I predict that in
v
vi Foreword
coming years they will largely supplant B-splines in many application domains. In
feature film production here at Pixar for instance, subdivision surfaces are already
the preferred way to represent the shape of virtually everything that moves.
The authors of this book have been on the forefront of these advances, and
this book represents the first comprehensive description of subdivision methods.
However, the book is not simply a collection of material that can be found in the
open literature. Rather, it offers a deep and unique perspective into the world of
subdivision. I learned a tremendous amount from reading this book. I’m sure you
will too.
Contents
Foreword v
Preface xi
Table of Symbols xiii
Chapter 1 Subdivision: Functions as Fractals 1
1.1 Functions 1
1.1.1 Piecewise Polynomials 3
1.1.2 B ´ezier Curves 5
1.2 Fractals 9
1.2.1 Iterated Affine Transformations 9
1.2.2 The Sierpinski Triangle 12
1.2.3 The Koch Snowflake 13
1.2.4 B ´ezier Curves 15
1.3 Subdivision 18
1.3.1 Piecewise Linear Splines 19
1.3.2 Subdivision for Piecewise Linear Splines 22
1.4 Overview 25
Chapter 2 An Integral Approach to Uniform Subdivision 27
2.1 A Subdivision Scheme for B-splines 28
2.1.1 B-spline Basis Functions via Repeated Integration 29
2.1.2 A Refinement Relation for B-spline Basis Functions 32
2.1.3 The Associated Subdivision Scheme 35
2.2 A Subdivision Scheme for Box Splines 40
2.2.1 B-spline Basis Functions as Cross-sectional Volumes 41
2.2.2 Box-spline Scaling Functions as Cross-sectional Volumes 44
2.2.3 Subdivision for Box Splines 45
2.2.4 Examples 48
2.3 B-splines and Box Splines as Piecewise Polynomials 52
2.3.1 B-splines as Combinations of Truncated Powers 53
vii
viii Contents
2.3.2 Box Splines as Combinations of Cone Splines 57
2.3.3 Bivariate Examples 58
Chapter 3 Convergence Analysis for Uniform Subdivision Schemes 62
3.1 Convergence of a Sequence of Functions 63
3.1.1 Pointwise Convergence 63
3.1.2 Uniform Convergence 65
3.1.3 Uniform Convergence for Continuous Functions 67
3.1.4 Uniform Convergence for Smooth Functions 68
3.2 Analysis of Univariate Schemes 69
3.2.1 A Subdivision Scheme for Differences 70
3.2.2 A Condition for Uniform Convergence 73
3.2.3 A Subdivision Scheme for Divided Differences 75
3.2.4 Example: The Four-point Scheme 79
3.3 Analysis of Bivariate Schemes 81
3.3.1 A Subdivision Scheme for Differences 82
3.3.2 A Condition for Uniform Convergence 83
3.3.3 Convergence to a Smooth Function 85
3.3.4 Example: Bivariate Interpolatory Schemes 88
Chapter 4 A Differential Approach to Uniform Subdivision 91
4.1 Subdivision for B-splines 92
4.1.1 A Differential Equation for B-splines 92
4.1.2 A Finite Difference Equation for B-splines 95
4.1.3 The Associated Subdivision Scheme 97
4.2 Subdivision for Box Splines 99
4.2.1 A Differential Equation for Box Splines 99
4.2.2 The Subdivision Scheme for Box Splines 101
4.3 Subdivision for Exponential B-splines 103
4.3.1 Discretization of the Differential Equation 103
4.3.2 A Subdivision Scheme for Exponential Splines 105
4.3.3 Exponential B-splines as Piecewise Analytic Functions 106
4.4 A Smooth Subdivision Scheme with Circular Precision 110
4.4.1 Splines in Tension 110
4.4.2 Mixed Trigonometric Splines 112
4.4.3 The Unified Subdivision Scheme 114
4.4.4 Convergence Analysis for Nonstationary Schemes 116
Chapter 5 Local Approximation of Global Differential Schemes 120
5.1 Subdivision for Polyharmonic Splines 120
5.1.1 The Radial Basis for Polyharmonic Splines 121
Contents ix
5.1.2 A Bell-shaped Basis for Polyharmonic Splines 124
5.1.3 A Subdivision Scheme for Polyharmonic Splines in the Bell-shaped
Basis 127
5.2 Local Approximations to Polyharmonic Splines 129
5.2.1 The Exact Scheme via Laurent Series 129
5.2.2 Local Approximations via the Jacobi Iteration 133
5.2.3 Optimal Local Approximations via Linear Programming 136
5.2.4 A Comparison of the Three Approaches 138
5.3 Subdivision for Linear Flows 141
5.3.1 Linear Flows 142
5.3.2 Primal Versus Dual Subdivision 145
5.3.3 A Finite Difference Scheme for Perfect Flows 147
5.3.4 A Subdivision Scheme for Perfect Flows 149
5.3.5 An Analytic Basis for Linear Flows 151
Chapter 6 Variational Schemes for Bounded Domains 157
6.1 Inner Products for Stationary Subdivision Schemes 157
6.1.1 Exact Derivatives 158
6.1.2 Exact Inner Products 162
6.1.3 Example: Exact Enclosed Area for Parametric Curves 165
6.2 Subdivision for Natural Cubic Splines 167
6.2.1 A Variational Formulation of Cubic Splines 167
6.2.2 A Finite Element Scheme for Natural Cubic Splines 169
6.2.3 A Multiscale Relation for Natural Cubic Splines 173
6.2.4 Subdivision Rules for Natural Cubic Splines 176
6.3 Minimization of the Variational Scheme 180
6.3.1 Interpolation with Natural Cubic Splines 180
6.3.2 Exact Inner Products for the Variational Scheme 182
6.3.3 Multiresolution Spaces for Energy Minimization 184
6.4 Subdivision for Bounded Harmonic Splines 188
6.4.1 A Finite Element Scheme for Bounded Harmonic Splines 188
6.4.2 Subdivision for Harmonic Splines on a Quadrant 191
6.4.3 Subdivision for Harmonic Splines on Bounded Rectangular
Domains 193
Chapter 7 Averaging Schemes for Polyhedral Meshes 198
7.1 Linear Subdivision for Polyhedral Meshes 198
7.1.1 Polyhedral Meshes 199
7.1.2 Topological Subdivision of Polyhedral Meshes 201
7.2 Smooth Subdivision for Quad Meshes 204
7.2.1 Bilinear Subdivision Plus Quad Averaging 205
7.2.2 Comparison to Other Quad Schemes 209