CIS 510/CSE410, Fall 2002

Curves and Surfaces: Theory and Applications

Formerly called

Introduction to Geometric Methods in Computer Science

Course Information August 29, 2002

Coordinates:

Instructor:

Office Hours:

Teaching Assistant:

Office Hours:

Prerequesites:

Linear Algebra and its Applications, Strang, Gilbert, Saunders HBJ, 1988, Third Edition

An alternative is the first two chapters of

Introduction to Applied Mathematics, Strang, Gilbert, Wellesley Cambridge Press, 1986, First Edition

A clear and rather elementary presentation of linear algebra with a strong geometric flavor can be found in

A vector space approach to geometry, Hausner, Melvin, Dover, 1998

(CIS560 NOT required).

Textbooks:

Morgan Kaufmann and Amazon.com

Review in MathSciNet (item 1) MathSciNet

Computer Animation. Algorithms and Techniques, Rick Parent,
Morgan Kaufmann, 2001 Morgan Kaufmann and Amazon.com

Additional Relevant text:
Curves and Surfaces for Computer Aided Geometric Design, Gerald Farin, Morgan Kaufmann, Fifth Edition, 2001 Morgan Kaufmann and Amazon.com

Other Related Books:
Computer Aided Geometric Design, Hoschek, J. and Lasser, D., AK Peters, 1993
Geometric Modeling with Splines, Cohen, E., Riesenfeld, R. and Elber, G., AK Peters, 2001
The NURBS Book, Piegl, L. and Tiller, W., Springer, 1995
Subdivision Methods for Geometric Design, Warren, J. and Weimer, H., Morgan Kaufmann, 2002
From Projective Geometry to Practical Use, Farin, G., AK Peters, 1999

Grades:

Problem Sets, Programming Projects

• Homework 1 ps, pdf
• Homework 2 ps, pdf
• Homework 3 ps, pdf
• Homework 4 ps, pdf

A Word of Advice :

The final grade in the course grade will be determined based on a combination of

• Problem Sets (2 or 3) and
• Projects (3).

Sometimes, I will give you the option to do a programming project rather than a ``standard'' homework assignment.

There will be no exam(s).

Some Slides

• Introduction to Polynomial curves and polar forms, I
• Introduction to Polynomial curves and polar forms, II
• Polynomial curves and Control Points
• Polynomial Surfaces (Introduction)
• Basics on Affine spaces, I
• Basics on Affine spaces, II
• Multiaffine maps, affine polynomial maps, and polar forms
• Bezier curves, the de Casteljau algorithm, subdivision methods
• Derivatives of Polynomial Curves. Conditions for C^k continuity
• Spline Curves (B-splines)
• Polynomial Surfaces, the de Casteljau algorithm
• Polynomial Surfaces, subdivision methods for triangular and rectangular patches
• Rectangular and Triangular polynomial spline surfaces
• Subdivision surfaces I, Doo-Sabin, Catmull-Clark, Loop
• Subdivision surfaces II, Analysis of Loop's scheme
• Mathematica programs to draw polynomial curves
• Mathematica programs to draw poly. and rational curves
• Control polys for poly. and rational curves
• Mathematica programs to draw poly. and rational surfaces
• Control polys for rational surfaces
• Mathematica Programs to compute control points
• Parametric curves and surfaces to be polarized
• Embedding an affine space into a vector space

Brief description:

Basically, the course will be about mathematical and algorithmic techniques used for geometric modeling and geometric design, using curves and surfaces. There are many applications in computer graphics (but also in robotics, vision, and computational geometry). Such techniques are used in 2D and 3D drawing and plot, object silhouettes, computer animation, product design (cars, planes, buildings), topographic data, medical imagery, active surfaces of proteins, attribute maps (color, texture, roughness), weather data, art(!), ... . Three broad classes of problems will be considered:

• Approximating curved shapes, using smooth curves or surfaces.
• Interpolating curved shapes, using smooth curves or surfaces.
• Rendering smooth curves or surfaces.

We will take a two--pass approach, the first one informal and intuitive, and the second pass more rigorous.

During the first pass, Be'zier curves will be introduced ``gently'', in terms of multiaffine symmetric polar forms, also known as ``blossoms''. We will begin with degree 2, move up to degree 3, giving lots of examples, and derive the fundamental ``de Casteljau algorithm'', and show where the Bernstein polynomials come from. Then, we will consider polynomial curves of arbitrary degree. We will present the subdivision version of the de Casteljau algorithm. We will then introduce rectangular Be'zier surfaces and triangular Be'zier surfaces. We will give a glimpse of the subdivision version of the de Casteljau algorithm for triangular patches.

After this rather informal presentation, we will take another pass at curves and surfaces from a more rigorous point of view. We will begin with some basics on affine spaces and affine maps. Then, we will revisit curves defined in terms of control points. The use of polar forms yields a very elegant and effective treatment of tangents. The conditions for joining polynomial curves will be derived using polar forms, and this will lead to a treatment of B-splines in terms of polar forms. In particular, the de Boor algorithm will be derived as a natural extension of the de Casteljau algorithm. Rectangular (tensor product) Be'zier surfaces, and triangular Be'zier surfaces will also be introduced using polar forms, and the de Casteljau algorithm will be derived. Subdivision algorithms and their application to rendering will be discussed extensively.

We will also discuss subdivision surfaces: Doo-Sabin, Catmull-Clark, and Loop subdivision surfaces will be presented. Such surfaces have been used in some recent computer graphics work, notably, in the movie Geri's game.

Applications of the above methods to motion interpolation/blending, global deformation of objects and images (warping), and possibly modeling and animating figures (walking, facial animation, etc.), will be discussed (notably, material from Parent's book listed above).

Back to Gallier Homepage

published by:

Jean Gallier