Course Title Subdivision for Modeling and Animation

Computing Moments (Peters)Geri's Game (DeRose)Tagged Subdivision (Lounsbery)Multiresolution Editing (Zorin)Modeling with local refinement (Forsey)Variational Subdivision (Kobbelt)

Course Materials For examples of the course materials and slides see the materials of the 1998 course.

Course Presenters' Information
Organizers

Peter Schröder Denis Zorin
Caltech Multi-Res Modeling Group
Computer Science Dept. 256-80
California Institute of Technology
Pasadena, CA 91125
vox: 626.395.4269
fax: 626.792.4257
net: ps@cs.caltech.edu
Media Research Laboratory
715 Broadway, Rm 1201
New York University
New York, NY 10003
vox: 212.398.3405
fax: 212.995.4122
net: dzorin@mrl.nyu.edu


Speakers

Tony DeRose Joe Warren
Studio Tools Group
Pixar Animation Studios
1001 West Cutting Blvd.
Richmond, CA 94804
vox: 510.620.6019
fax: 510.236.0388
net: derose@pixar.com
Department of Computer Science
Rice University
6100 South Main
Houston, Tx 77251
vox: 713.737.5728
fax: 713.285.5930
net: jwarren@rice.edu

Leif Kobbelt Jos Stam
Computer Graphics Group
University of Erlangen
Am Weichselgarten 9
91058 Erlangen, GERMANY
vox: +49.9131.859927
fax: +49.9131.859931
net: kobbelt@informatik.uni-erlangen.de
Member Technical Staff
Alias | wavefront
1218 First Avenue, 8th Floor
Seattle, WA 98104
vox: 206.287.5624
fax: 206.667.9049
net: jstam@aw.sgi.com



Speaker Biographies

Peter Schröder

Peter Schröder is currently an assodiate professor of computer science at the California Institute of Technology, Pasadena, where he directs the Caltech Multi-Res Modeling Group. For the past 7 years his work has concentrated on exploiting wavelets and multiresolution techniques to build efficient representations and algorithms for many fundamental computer graphics problems. He has taught in a number of Siggraph courses and most recently co-led the course on Wavelets in Computer Graphics (1996) and the course on Subdivision for Modeling and Animation (1998). His current research focuses on subdivision as a fundamental paradigm for geometric modeling and rapid manipulation of large, complex geometric models. The results of his work have been published in venues ranging from Siggraph to special journal issues on wavelets and WIRED magazine, and he is a frequent consultant to industry.

 

Denis Zorin Denis Zorin is an assistant professor at the Courant Institute of Mathematical Sciences, New York University. He received a BS degree from the Moscow Institute of Physics and Technology, a MS degree in Mathematics from Ohio State University and a PhD in Computer Science from the California Institute of Technology. In 1997-98, he was a research associate at the Computer Science Department of Stanford University. His research interests include multiresolution modeling, the theory of subdivision, and applications of subdivision surfaces in Computer Graphics. He is also interested in perceptually-based computer graphics algorithms. He has published several papers in Siggraph proceedings.

 

Tony DeRose Tony DeRose is currently a member of the Tools Group at Pixar Animation Studios. He received a BS in Physics in 1981 from the University of California, Davis; in 1985 he received a Ph.D. in Computer Science from the University of California, Berkeley. He received a Presidential Young Investigator award from the National Science Foundation in 1989. In 1995 he was selected as a finalist in the software category of the Discover Awards for Technical Innovation.

From September 1986 to December 1995 Dr. DeRose was a Professor of Computer Science and Engineering at the University of Washington. From September 1991 to August 1992 he was on sabbatical leave at the Xerox Palo Alto Research Center and at Apple Computer. He has served on various technical program committees including SIGGRAPH, and from 1988 through 1994 was an associate editor of ACM Transactions on Graphics.

His research has focused on mathematical methods for surface modeling, data fitting, and more recently, in the use of multiresolution techniques. Recent projects include object acquisition from laser range data and multiresolution/wavelet methods for high-performance computer graphics.

 

Jos Stam Jos Stam is currently a member of technical staff at Alias|wavefront. He received BS degrees in computer science and mathematics from the University of Geneva, Switzerland in 1988 and 1989, and he received a MS and a PhD in computer science both from the University of Toronto in 1991 and 1995, respectively. His research interests cover most areas of computer graphics: natural phenomena, rendering, animation and surface modeling. He has published papers at SIGGRAPH and elsewhere in all of these areas.

Recently, his research has focused on the fundamentals of subdivision surfaces and their practical use in a commercial product. Stam is a leading expert in both the theory and application of subdivision surfaces. His work on evaluating subdivision surfaces presented at last years SIGGRAPH conference has been widely acclaimed as being a landmark paper in the area.

 

Joe Warren Joe Warren is currently an Associate Professor in the Department of Computer Science at Rice University. He received his master's and Ph.D. degrees in 1986 from Cornell University. His research interests focus on the relationship between computers, mathematics and geometry. During the course of his research career, he has made fundamental contributions to topics such as algebraic surfaces, rational surfaces, finite element mesh generation and subdivision. Currently, he is investigating the relationship between subdivision and systems of partial differential equations.

 

Leif Kobbelt Leif Kobbelt currently holds a position as a post-doctoral research fellow at the University of Erlangen , Germany. His major research interest is sophisticated free-form modeling based on polygonal meshes. He received his master's (1992) and Ph.D. (1994) degrees from the University of Karlsruhe , Germany. He then spent one year at the University of Wisconsin, Madison as a visiting researcher in Carl de Boor's group. Since 1996 he has been working in the geometric modeling unit of the Computer Graphics Group at Erlangen. During the last 5 years he made significant contributions to the construction and analysis of subdivision schemes and pioneered the combination of the subdivision paradigm with variational methods from CAGD.

 


Course Syllabus Morning: The morning section will focus on the foundations of subdivision, starting with subdivision curves and moving on to surfaces. We will review and compare a number of different schemes and discuss the relation between subdivision and splines. The emphasis will be on properties of subdivsion most relevant for applications.

  • Introduction and overview (Schröder); 15 min.
    • Course outline and schedule
    • High-level introduction to the basic ideas of subdivision
    • Quick overview of application examples
  • Foundations I: Basic Ideas (Schröder)
  • 60 min.
    • Constructing smooth curves through subdivision; 10 min.
      examples: b-spline knot insertion and interpolating subdivision
    • Subdivision for surfaces; 10 min.
      an example of a subdivision scheme: Loop
    • Properties of subdivision schemes: smoothness, locality, hierarchical structure; 10 min.
    • How splines are related to subdivision; 10 min.
    • Advantages of subdivision: arbitrary topology, efficiency, controllable surface features such as creases and cusps; 10 min.
  • Foundations II: Construction and Analysis of Subdivision Schemes (Zorin), 90 min.
    • Overview of subdivision for surfaces; geometric smoothness. 15 min.
    • Subdivision matrices for surface schemes; computing tangents and limit positions 15 min.
    • Classic schemes, their definition, and basic properties; 25 min.
      1. Catmull-Clark
      2. Doo-Sabin
      3. Loop
      4. Butterfly
      5. Midedge
      6. Kobbelt
    • Subdivision rules for special surface features; boundaries and creases; 15 min.
    • Methods for constructing subdivision schemes; improving smoothness, curvature continuity, mesh quality; 10 min.
    • Computation of moments; 10 min.
    • Basic algorithms and data structures for implementing subdivision; adaptive evaluation, level-of-detail rendering; 10 min.
    Afternoon: The afternoon session will focus on applications of subdivision and the algorithmic issues practictioners need to address to build efficient, well behaving systems for modeling and animation with subdivision surfaces.
    • Applications and Algorithms:
      • Interactive Multiresolution Mesh Editing, 40 min. Subdivision can model smooth surfaces, but in many applications one is interested in surfaces which carry details at many levels of resolution. Multiresolution mesh editing extends subdivision by including detail offsets at every level of subdivision, unifying patch based editing with the flexibility of high resolution polyhedral meshes. The result is a hierarchical editing system built around highly adaptive algorithms and datastructures to deliver interactive performance on low end workstations for complex geometric models. This section will detail the underlying ideas and the algorithms necessary to build a scalable multiresolution editing system. (Zorin)
      • Exact Evaluation of Subdivision Surfaces Until recently it was believed that subdivision surfaces (Catmull-Clark, Loop, Doo-Sabin, ...) could not be evaluated exactly everywhere. This talk disproves this belief and presents the ideas and techniques that enable exact evaluation. Evaluation is important as it allows many standard algorithms developed for parametric surfaces to be applied to subdivision surfaces. The evaluation technique relies on a new set of eigen-basis functions which depend directly on the eigenvectors of the subdivision matrix. The cost of the resulting evaluation scheme is comparable to that of a bi-cubic spline for the case of Catmull-Clark subdivision. The emphasis of this talk is on an intuitive understanding of the mathematical techniques and on practical applications of the evaluation schemes. (Stam)
      • Subdivision Schemes for Fluid Flows, 40 min. The motion of fluids has been a topic of study for hundreds of years. In its most general setting, fluid flow is governed by a system of non-linear partial differential equations known as the Navier-Stokes equations. However, in several important setting, these equations degenerate into simpler systems of linear PDEs. This section will show that flows corresponding to these linear cases can be modeled using subdivision schemes for vectors. These schemes expressed the flow as the limit of an increasing dense set of vector fields. The beauty of this approach is that realistic flows can now be modeled and manipulated in real time using their associated subdivision scheme. The section will conclude by discussing a number of practical details that arose in the implementation of such a scheme. (Warren)
      • A Variational Approach to Subdivision, 40 min. Surfaces generated using subdivision have certain orders of continuity. However, it is well known from geometric modeling that high quality surfaces often require additional optimization (fairing). In the variational approach to subdivision, refined meshes are not prescribed by static rules, but are chosen so as to minimize some energy functional. The approach combines the advantages of subdivision (arbitrary topology) with those of variational design (high quality surfaces). This section will describe the theory of variational subdivision and highly efficient algorithms to construct fair surfaces. (Kobbelt)
      • Subdivision Surfaces in the Making of Geri's Game and A Bug's Life, 40 min. Geri's Game is a 3.5 minute computer animated film that Pixar completed in 1997. The film marks the first time that Pixar has used subdivision surfaces in a production. In fact, subdivision surfaces were used to model virtually everything that moves. Subdivision surfaces went on to play a large role in the recently released feature film 'A Bug's Life' from Disney/Pixar. This section will describe what led Pixar to use subdivision surfaces, discuss several issues that were encountered along the way, and present several of the solutions that were developed. (DeRose)
    • Summary and Wrapup: (all speakers)

    Innovative Methods of Presentation Aside from the usual slide and video projection used during the presentations we will have live demonstrations running on a PC illustrating some of the concepts as well as showing full blown applications using subdivision. While this is not new as such, we believe it will significantly enhance the learning experience of the participants.

    Course History This course was taught in 1998 with a slightly different crew. The subject is still relevant as we are only seeing the beginning of the wide deployment of subdivision technology. This reaches from applications in production (e.g., Pixar's Geri's Game and the most recent A Bug's Life), to tools offered by vendors (e.g., Reyes, 3D Studio Max plugins). The interest among practitioners to understand these new techniques and see how they can be deployed is currently still growing. The main difference to last year's course is a fine tuning in the presentations and the composition of the team. Based on feedback received we are adding more material relevant to practical applications and are cutting back on some of the more mathematical material in the presentations. This material will still be covered, but more in the course notes rather than in lectures. We have added two new speakers, Jos Stam and Joe Warren, who will present some of the most interesting recent work. At the same time we are changing the designation from intermediate to advanced as the material does require a solid familiarity with standard techniques such as spline patches (though no prior knowledge of subdivision). Although subdivision as a basic geometric modeling method was first proposed in 1978 it is only in the last 8 years that it has received greater attention in the CAGD and computer graphics community. Its attraction lies in the simplicity of the fundamental algorithms and the ability of subdivision to deal with large models of arbitrary topology in interactive settings. It was only very recently that fundamental results were proved and efficient algorithms developed to move this technique into the mainstream. There is now enough momentum behind subdivision that major production facilities are using it and tool companies are beginning to deploy it on a large scale. Because of these developments there is great interest among practictioners of computer graphics to learn more about subdivision and understand how to use it in their own work.

    Summary Statement This course provides an introduction to Subdivision, a technique to generate smooth curves and surfaces, which extends classical spline modeling approaches. The course will cover the basic ideas of subdivision as well as the particulars of a number of different subdivision algorithms; we will present the most recent contributions to the area in a form accessible to a wide audience. The emphasis will be on practical issues in using subdivision for geometric modeling and animation.

    Expanded Statement Subdivision is an algorithmic technique to generate smooth surfaces as a sequence of successively refined polyhedral meshes. Its origins go back to 1978 when Catmull and Clark, and Doo and Sabin first proposed to generalize spline-patch methods to meshes of arbitrary topology. Subdivision algorithms are exceptionally simple, work for arbitrary control meshes and produce globally smooth surfaces. Special choices of subdivision rules allow for the introduction of features into a surface in a simple way. Subdivision-based representations of complex geometry can be manipulated and rendered very efficiently, which makes subdivision a highly suitable tool for interactive animation and modeling systems.

    This course will cover the basic ideas of subdivision and a variety of different subdivision schemes detailing their properties, suitability for particular applications, and compare their relative merits. Strong emphasis will be placed on practical issues. At the end of the course participants will be well prepared to implement the basic techniques as well as delve into the research literature on the subject.


    Prerequisites The course will be self contained and does not assume prior knowledge of subdivision. Prior exposure to parametric representations of curves and surfaces and associated algorithms is required. Beyond that only basic linear algebra and introductory calculus are required.

    Topics Beyond the Prerequisites The course will teach the basic ideas of subdivision for curves and surfaces. We will explain a number of different subdivision methods for surfaces and briefly discuss the theoretical results (without proofs) useful in practice. The course will cover a variety of subdivision-based algorithms for modeling and animation, including adaptive evaluation, level-of-detail rendering and manipulation. A number of specific applications will be presented.

    Course Notes Description The course notes will contain tutorial material with pointers to the relevant literature for those who want to study individual issues in greater depth. The overall outline will follow the 1998 materials, but we will place more emphasis on the interrelationships between the different issues presented by the speakers. In essence the course notes will be a revised and expanded version of the 1998 notes.

    Special Presentation Requirements None.

    Special Notes Requirements None.


    Copyright © 1997-98 Peter Schröder and Denis Zorin