CSE410/CIS510 - Curves and Surfaces: Theory and Applications

Fall 2005
Course Description | Blackboard | Syllabus | Schedule | Handouts | Homeworks | Project | Textbook | Related Links

Announcements

Course Description

Instructor: Marcelo Siqueira

marcelos@seas.upenn.edu

Moore 172

Office hours: Wednesdays, 4.30PM to 6PM or by appointment

Administrative Assistant:

 Janean Williams

janeanw@cis.upenn.edu

Levine 313
Meeting times and place: MW 10.30AM - 12PM, Towne 303

 

Course Work and Grading Policy:

The required work for this course consists of six or seven homeworks and one project. Most homeworks will consist of short programs, while the project is a larger program. Ocasionally, homeworks may also contain theoretical questions related to the foundations of the algorithms used in other parts of the homeworks.

The grading breakdown is as follows: the average grade of the homeworks counts for 50% of the course grade, and the project counts for 50%.

You will be allowed to work in groups of at most 3 students for all homeworks and project. You are also free, and in fact encouraged, to discuss homeworks and project with your instructor and classmates from other groups, but each group must hand in its own homeworks and project, and your group is not permitted to copy or share written work details from other groups. It is undertood that the work submitted by each group may be based on these discussions but has not been either copied directly from another group's work nor is it, in part or in whole, the product of impermissible collaboration.

Prerequisites:

Basic knowledge of linear algebra and multivariate calculus. For instance, MATH240 or an equivalent course. If you are not so sure about what I mean by "basic knowledge" of linear algebra and multivariate calculus, please do not hesitate in contacting me by email or in person.

You will also need to know some programming language to do your course work. Although I will not require a particular language, my code examples will be either in C++ or Matlab. So, if you are a C++ programmer or a Matlab user, you will certainly feel more comfortable with the examples.

Knowledge on computer graphics is NOT a requirement. We will use visulization tools to help us render the 2D and 3D models we will build. But, I will provide you with some freely available tools for this purpose, and I will also show you how to visualize such models using software available in our labs. Of course, you are more than welcome to use your favorite visualization tools or any software that provides this capability, such as Maya or 3DS.

Blackboard

Refer to the course blackboard to take part in discussions related to lectures, homeworks, and project, and to check out your grades.

Syllabus

Topic #
Topic

 

 
   
1
 Introduction
  • Models, geometric models, and geometric modeling;
  • The paradigm of the four universes;
  • Curve, surface, and solid models.
2
 Basics of affine geometry
  • Affine spaces;
  • Points and vectors;
  • Affine combinations;
  • Affine transformations.
3
 Parametric curves
  • Bezier curves;
  • Spline curves;
  • Polynomial interpolation.
4
 Parametric surfaces
  • Bezier surfaces;
  • Spline surfaces;
  • Geometric continuity.
5
 Subdivision surfaces
  • Catmull-Clark subdivision surfaces;
  • Loop subdivision surfaces
6
 Implicit surfaces
  • Modeling techniques for implicit surfaces;
  • Blobs;
  • Polygonization.

 

Schedule

Date
Topic
Reading Material
09/07
Course introduction
Chapter 5 of primary reference 1 (optional).
09/08
Basics of affine geometry - Part I
Any basic linear algebra book or Appendix A of primary reference 3 (optional).
09/15
Basics of affine geometry - Part II
Chapter 2 and 3 of primary reference 2, and chapter 3 of primary reference 3.
09/19
Basics of affine geometry - Part II
Chapter 3 of primary reference 2.
09/21
The de Casteljau Algorithm
Chapter 4 of primary reference 2.
09/26
Affine maps and Bezier Curves
Chapter 5 of primary reference 2.
09/28
Bezier curves and a look at a formal definition of a curve.
Chapter 5 of primary reference 2.
10/03
Uniform cubic b-spline curves
Slides.
10/05
Nonuniform b-splines curves
Chapter 3 of (complementary) reference 4.
10/11
Nonuniform Rational B-splines (NURBS) curves
Chapter 12 of primary reference 2.
10/13
Nonuniform Rational B-splines (NURBS) curves
Chapter 4 of (complementary) reference 4.
10/19
The derivative of a Bezier curve
Chapter 5 of primary reference 2.
10/24
The derivative of a spline curve
Chapter 3 of (complementary) reference 4.
10/26
Tensor product Bezier surfaces
Chapter 14 of primary reference 2.
10/31
NO CLASS
  
11/02
NO CLASS
 
11/07
Triangular Bezier surfaces
Chapter 17 of primary reference.
11/09
Uniform bicubic b-spline surfaces
Slides
11/14
Nonuniform b-splines curves
Slides
11/16
Nonuniform Rational B-splines (NURBS) surfaces
Chapter 3 of (complementary) reference 4.
11/16
Nonuniform Rational B-splines (NURBS) surfaces
Chapter 3 of (complementary) reference 4.
11/21
Derivatives of tensor product Bezier surfaces
Chapter 14 of primary reference 2.
11/23
Derivatives of triangular Bezier surfaces
Chapter 17 of primary reference 2.
11/28
Geometric continuity for surfaces
Chapter 20 of primary reference 2.
11/30
Surfaces with arbitrary topology
Chapter 21 of primary reference 2.
12/05
Surfaces with arbitrary topology
Chapter 21 of primary reference 2.
12/07
Surfaces with arbitrary topology
Chapter 18 of primary reference 2.

Handouts

# Titlle
1)
An introduction to geometric modeling of curves, surfaces, and solids - Slides
2)
Basics of affine geometry - Part I - Slides
3)
Basics of affine geometry - Part II - Slides
4)
The de Casteljau algorithm - Slides
5)
Animation of the de Casteljau algorithm applied to a control polygon with three vertices (*.mov)
6)
Matlab code (lerp.m, decas.m, plotdecas2D.m)
7)
Bezier curves - Slides
8)
What is a curve? - Slides
9)
Spline curves - Slides
10)
Matlab code (findinterval.m, basisfunc.m)
11)
Tensor product Bezier surfaces - Slides
12)
Triangular Bezier surfaces - Slides
13)
Uniform bicubic b-spline surfaces - Slides
14)
Nonuniform b-spline surfaces - Slides
15)
16)
Nonuniform rational b-spline surfaces - Slides
17)
Derivatives of tensor product Bezier surfaces - Slides
18)
Derivatives of triangular Bezier surfaces - Slides
19)
Geometric continuity - Slides
20)
Chaikin's algorithm- Slides
21)
Subdivision surfaces - Slides

 Homeworks

Due Date Homework
09/28
Homework 1 - Basics of affine geometry.
10/26
Homework 2 - Basics of affine geometry and Bezier curves.
11/14
Homework 3 - Spline curves
11/30
Homework 4 - Bezier and spline surfaces
12/14
Homework 5 - Derivatives and curve subdivision

 Project

  • Please, form groups of at most two students, choose one of the topics below, and let me know what topic you chose. Each group must choose a distinct topic, and I will use a FIFO system to assign the project. So, the earlier you decide for a topic, the better. Once you have a topic, you must read and understand the corresponding papers, and then fully implement the algorithm in the paper. If you make some improvement to the algorithm, I will consider the improvement a bonus. In fact, I really encourage you to think about some improvement.
    1. Improving Visual Quality of Triangle-Based Meshes

      • A. Vlachos, J. Peters, C. Boyd, and J. L. Mitchell. "Curved PN Triangles". ACM Symposium on Interactive 3D Graphics, 2001.



    2. Mesh Simplification




    3. Mesh Decomposition




    4. Mesh Parametrization




    5. Ray Tracing of Subdivision Surfaces




    6. Tesselation of Subdivision Surfaces

Textbook

Unfortunately, there is no book that covers all topics listed in the syllabus of the course. Furthermore, some of the topics are in research papers rather than books. So, I will three books which cover most of the topics of the entire course and to which I shall refer as primary references:

  • Primary references:
    1. Max K. Agoston. Computer Graphics and Geometric Modeling. Springer-Verlag, 2005. (Call number: T385 A395 2005, Penn Engineering Library)

    2. Gerald Farin. Curves and Surfaces for CAGD: A Practical Guide. Morgan-Kaufmann, 5th edition, 2001. (Call number: T385 F37 2002, Penn Engineering Library)

    3. Jean Gallier. Curves and Surfaces in Geometric Modeling: Theory and Algorithms. Morgan-Kaufmann, 2000. (Call number: QA567 G28 2000, Penn Math/Physics/Astronomy Library)

All primary references are on reserve in the respective libraries. This means that they are available for use inside the library, i.e., you cannot take them home.

I will also use several other references along the course to which I shall refer as complementary references. Some of them are listed below:

  • Complementary references:
    1. Les Piegl and Wayne Tiller. The NURBS Book. Springer-Verlag, 2nd edition, 1997. (Call number: QA224 P54 1997, Penn Engineering Library)

    2. Jules Bloomenthal (Ed.). Introduction to Implicit Surfaces. Morgan-Kaufmann, 1997.

    3. David Luebke et al. Level of Detail for 3D Graphics. Morgan-Kaufmann, 2002.

Related links:

The following links are just a very small set of interesting links to courses on geometric modeling in the US and abroad. Please, visit the corresponding sites and browse their available lecture notes. They all have very nice reading materials and pointers to several other related links.