January 6, 2000

Computer representations of 3-D objects are widely used in Computer Science and various scientific and engineering disciplines. 3-D computer graphics is becoming ubiquitous: most desktop machines are expected to bundle support for 3-D applications in the near future, and the use of 3-D in multimedia and the Web is burgeoning. Graphic rendering techniques are well developed and implemented in hardware and in software browsers. The bottleneck is becoming the construction of the geometric models of the objects to be rendered. This course addresses basic concepts of geometric modeling, and attempts to strike a balance between applications in two areas: (i) graphics and multimedia, and (ii) robotics and automation.

Programming assignments involve graphics using Java3D, which is a new technology designed primarily to help provide 3D content for the web. The course will use the Java programming language and its Swing user interface facilities. Information on Java resources is available in the course's home page (see below). Information on what is expected in programming assignments is posted in the course's home page.

Instructor: Prof. Aristides A. G. Requicha, SAL 202; requicha@lipari.usc.edu.

Office hours: Mondays and Wednesdays 1 - 2 p.m. or by appointment.

Time: Mondays and Wednesdays, 2 - 3:20 p.m.

Location: GFS 107

Home Page: http://www-lmr.usc.edu/cs582/. (The '5' is not an error; the page is shared with cs582.)

Course account: ~cs582/ in the scf machines

Prerequisites: CS 101 and 102 or equivalent, and some elementary linear algebra (e.g., how to multiply matrices). Knowledge of C or C++, or Java is required. Students who do not know Java are expected to learn it on their own.

Texts: None. About 2/3 of the material is available on-line, in Acrobat .pdf format, by following links from the course's web page.

TA: Nick Montoya, SAL 209, nmontoya@lipari.usc.edu, office hours - Tuesdays and Thursdays, 2-3 p.m.

I will not be following closely any of the cited books. These materials are on reserve in the Seaver Science Library under cs582. The first two books are also available on line, in Java's web site.

K. Walrath and M. Campione, The JFC Swing Tutorial: a Guide to Constructing GUIs. Reading, MA: Addison Wesley, 2nd Ed., 1999.

H. Sowizral, K. Rushforth and M. Dearing, The Java 3D API Specification. Reading, MA: Addison Wesley, 1998.

C. M. Hoffmann, Geometric and Solid Modeling: An Introduction. San Mateo, CA: Morgan Kaufmann, 1989.

M. Mäntylä, An Introduction to Solid Modeling. Rockville, Maryland: Computer Science Press, 1988

M.E. Mortenson, Geometric Modeling. New York: Wiley, 1985

G. Farin, Curves and Surfaces for Computer Aided Geometric Design. San Diego, CA: Academic Press, 4th ed., 1997.

A. Rockwood and P. Chambers, Interactive Curves and Surfaces. S. Francisco, CA: Morgan Kaufmann, 1996.

A. A. G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys, Vol. 12, No. 4, pp. 437-464, December 1980.

A. A. G. Requicha and H. B. Voelcker, "Solid Modeling: A Historical Summary and Contemporary Assessment", IEEE Computer Graphics and Applications, Vol. 2, No. 2, pp. 9-24, March 1982

R.B. Tilove, "Set Membership Classification: A Unified Approach to Geometric Intersection Problems", IEEE Trans. on Computers, Vol. C-29, No. 10, pp. 874-883, October 1980.

A. A. G. Requicha and H. B. Voelcker, "Boolean Operations in Solid Modelling: Boundary Evaluation and Merging Algorithms", Proc. IEEE, Vol. 73, No. 1, pp. 30-44, January 1985.

Y. T. Lee and A. A. G. Requicha, "Algorithms for Computing the Volume and other Integral Properties of Solids", Part I and Part II, Comm. ACM, Vol. 25, No. 9, pp. 635-641, and pp. 642-650, September 1982.

J. R. Rossignac and A. A. G. Requicha, "Depth-Buffering Display Techniques for Constructive Solid Geometry", IEEE Computer Graphics and Applications, Vol. 6, No. 9, pp. 29-39, September 1986.

There will be a midterm on March 1st during the regular class time, and a final exam on May 3rd, 2-4 p.m., as specified in the USC class schedule. The exams will be closed book. Several programming assignments and a term project, due April 28, will be required. Program design and implementation must be done independently by each student. Team work will not be allowed. Cheating in all its forms-such as presenting the work of others as your own, using unauthorized references in an exam, and so on-constitutes a serious breach of academic integrity, and will be reported to the appropriate university authorities, who may impose severe penalties including expulsion from the university. Do not expect clemency from the instructor! After all, integrity is something you owe to yourself and to the scientific community: it is more important to be honest than to get an A or a Ph.D... For more information on what is considered proper and improper conduct see the Trojans for Integrity site.

Assignment due dates are firm. Late homework will be accepted without penalty only in cases of major, documented mishap (e.g., getting run over by a truck...). Lateness penalties are 10% of the total value (i.e., what you would get if you had done a perfect and on-time project) of the assignment per day. The final grade will be determined by the weighted average of the grades in all of the assignments and exams. The weights will be assigned by the instructor at the end of the term. Roughly, each exam will be worth about 25% of the grade, and the complete set of programming assignments about 50%.

Not finishing the project on time is not an acceptable reason to get an incomplete. This is forbidden by the University, which specifically requires that incompletes be given only for serious health problems and similar reasons.

1. Introduction ( About 2 lectures. )

1.1 Preamble

1.2 The Role of Geometry in CAD/CAM

1.3 The Role of Geometry in Graphics

1.4 Models, Representations, Algorithms and Systems

1.5 Historical Summary

2. Motions and projections ( About 3 lectures. )

2.1 Points and Vectors

2.2 Transformations

2.3 Free and Applied Vectors

2.4 Change of Basis

2.5 Homogeneous Coordinates

2.6 Applications in Robotics and Simulation

2.7 Applications in Rendering

3. Representations ( About 2 lectures. )

3.1 Representation Schemes

3.2 Methods for Representing Geometric Entities

3.2.1 Primitive Instancing

3.2.2 Spatial Decomposition

3.2.3 Constructive Methods

3.2.4 Sweeping

3.2.5 Interpolation and Approximation

3.2.6 Boundary Methods

4. Curves and Surfaces ( About 4 lectures. )

4.1 Mathematical Models for Curves and Surfaces

4.1.1 Lines and Planes

4.1.2 Curves

4.1.3 Surfaces

4.2 Representations for Curves

4.2.1 Vector Spaces of Polynomials

4.2.2 Blossoms

4.2.3 Bezier Curves

4.2.4 B-Spline Curves

4.3 Representations for Surfaces

4.3.1 Bezier and B-Spline Patches

4.3.2 Quadrics

5. Solids ( About 2 lectures. )

5.1 Mathematical Models for Rigid and Homogeneous Solids

5.2 Boundary Representations for Solids

5.2.1 Boundary Graphs

5.2.2 Validity of BReps

5.2.3 Euler Operators

6. Fundamental Algorithms ( About 4 lectures. )

6.1 Algorithms and Representations

6.2 Point-Solid Classification

6.2.1 Point Membership Classification

6.2.2 Point Classification for CSG Solids

6.2.3 Point Classification for BRep Solids

6.3 Curve-Solid Classification

6.3.1 General Membership Classification

6.3.2 Line Classification for CSG Solids

6.3.3 Line Classification for BRep Solids

6.4 Neighborhoods

6.4.1 Representation and Combination

6.4.2 Transition Evaluation

6.5 Boolean Operations

6.5.1 Boundary Evaluation and Merging

6.5.2 The Generate-and-Test Paradigm for Edges

6.5.3 Incremental Boundary Evaluation

6.5.4 Boundary Merging

6.5.5 Low-Level Routines

6.6 Curve and Surface Intersections

6.7 Distance Calculations

7. Application Algorithms ( About 4 lectures. )

7.1 Graphics and Kinematic Simulation

7.1.1 Overview

7.1.2 Depth Buffering

7.1.3 Ray Casting

7.1.4 Graphic Interaction

7.2 Mass Property Calculation

7.2.1 Applications and Definitions

7.2.2 CSG Algorithms

7.2.3 BRep Algorithms

7.3 Interference Detection