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 The actual course notes (big...) as they appeared on the CDROM. Also all the slides: There are also two (among a few others) applets which may be of interest.

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
Computer Graphics Laboratory
Gates Building, Rm 375
Stanford University
Stanford, CA 94305
vox: 650.723.6838
fax: 650.723.0033
net: dzorin@graphics.stanford.edu


Speakers

Tony DeRose David R. Forsey
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
Radical Entertainment Ltd.
1052 Homer St.
Vancouver B.C. Canada
V6B 2W9
vox: 604.602.2643
fax: 604.685.0298
net: dforsey@radical.ca

Leif Kobbelt Michael Lounsbery
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 of Technical Staff
Alias|wavefront
1218 Third Avenue, Suite 800
Seattle, WA 98101
vox: 206.287.5673
fax: 206.667.9049
net: louns@aw.sgi.com

Jörg Peters
Department of Computer Science
Purdue University
West Lafayette, IN 47907
vox: 795.494.6183
fax: 795.494.0739
net: jorg@cs.purdue.edu


Speaker Biographies

Peter Schröder

Peter Schröder is currently an assistant professor of computer science at the California Institute of Technology, Pasadena, where he directs the Caltech Multi-Res Modeling Group. He received a Master's degree from the MIT Media Lab and a PhD from Princeton University. During 1990/91 he worked for Thinking Machines. From 1992 to 1994 he held a visiting research fellow appointment at the German National Computer Science Research Center, and did postdoctoral work at the University of South Carolina. His research contributions range from massively parallel visualization, to physically based modeling, global illumination, wavelets and multiresolution geometry. For the past 5 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). 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 a research associate at the Computer Science Department of Stanford University. Starting in the fall of 1998, he will be 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. 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.

 

David Forsey David Forsey is an assistant professor of Computer Science at the University of British Columbia in Vancouver, Canada, where he co-directs the Imager Computer Graphics Laboratory. He is currently on leave at Radical Entertainment Ltd developing products based on Hierarchical B-splines. He obtained a BSc. in Zoology at the University of Guelph (1980) and a M.Math (1985) and PhD. (1990) from the University of Waterloo. He has taught in several SIGGRAPH courses, and has had two animations in the SIGGRAPH electronic theatre. His research interests include multiresolution modeling, facial animation as well as simulation and interactive tools as they relate to the artistic side of modeling and animation.

 

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.

 

Michael Lounsbery Michael Lounsbery is on the R&D staff for Alias | Wavefront in Seattle. He has a B.S. in Computer Science (1984) from the University of Maryland. In 1994, he completed a Ph.D. in Computer Science from the University of Washington, where he studied the development of wavelets over subdivision surfaces. He has taught in previous SIGGRAPH courses on wavelets, and has also published research in surface interpolation. His other graphics interests include fairness and compression issues for 3D surface modeling.

 

Jörg Peters Jörg Peters is an associate professor at the department of Computer Sciences at Purdue University . He received his PhD in 1990 from the University of Wisconsin-Madison advised by Carl de Boor. In 1991 and 1992 he held positions at the IBM T.J. Watson Research Center and Rensselaer Polytechnic Institute before joining the computer sciences department at Purdue in 1992.

In 1994, Dr. Peters was honored with a five year National Young Investigator Award for his work on Foundations and Tools for Surface Modeling . Currently Dr. Peters heads the SurfLab at CS Purdue and is a member of the Center for Visualization and Image Processing.

Peters' research focusses on represention and analysis of geometry on the computer. Notably, he has developed new tools for free-form modeling and design that combine the advantages of parametric spline representations and subdivision algorithms (recent papers).

 


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 and Zorin)
  • 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 and Peters), 140 min.
    • Overview of the analysis of subdivision; geometric smoothness and smooth parameterizations; 10 min.
    • Analysis for curves; subdivision matrices; 15 min.
    • Properties of the subdivision matrix and geometric smoothness; 15 min.
    • Classic schemes, their definition, and basic properties; 30 min.
      1. Catmull-Clark
      2. Doo-Sabin
      3. Loop
      4. Butterfly
      5. Midedge
    • Subdivision rules for special surface features; boundaries and creases; 10 min.
    • Subdivision matrices for surface schemes; smoothness criteria; 15 min.
    • Methods for constructing subdivision schemes; improving smoothness, curvature continuity, mesh quality; 15 min.
    • Computation of normals and moments; 20 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)
      • Subdivision Surfaces and Wavelets, 40 min. Wavelet techniques are well understood for regular domains, such as curves or rectangular tensor-product splines. Subdivision methods let us extend these techniques to more complex domains of arbitrary topological type. By developing multiresolution analysis over subdivision surfaces, we can apply wavelets to a wide variety of practical problems, including compression of polygonal data and multiresolution editing of smooth surfaces of arbitrary topology. (Lounsbery)
      • 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, 40 min. Geri's Game is a 3.5 minute computer animated film that Pixar recently completed (and which will be submitted to the 1998 SIGGRAPH film show). 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. This section will describe what led Pixar to use subdivision surfaces, discuss the issues encountered along the way, and present several of the solutions developed. (DeRose)
      • Exploiting Subdivision in Modeling and Animation, 40 min. Subdivision provides the mechanism for a multiresolution representation of smooth surfaces. This section explains how multiresolution surfaces can be used to greatly improve the modeling and animation of complex organic forms. Examples are taken from two commercial applications, where subdivision surfaces are used to seamlessly join together hierarchical tensor-product spline surfaces. (Forsey)
    • 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 has not been taught before.

    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 1998 is a particularly pertinent year to educate the graphics community in the use of this technique and remove its mystique.


    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. Some prior exposure to parametric representations of curves and surfaces and associated algorithms is helpful. 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 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. We will include a number of code samples in the electronic version.

    Special Presentation Requirements None beyond the standard slide, video and PC projection hookups.

    Special Notes Requirements None.


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