May 7, 2013
Fall 2013
CS 582 GEOMETRIC MODELING
Geometric models are computational (symbol) structures that capture the spatial aspects of the objects of interest for an application or range of applications. Traditionally, computer graphics has used simplified geometric models that can be rendered at interactive speeds but may not reflect accurately the objects’ geometries. On the other hand, applications such as CAD/CAM (Computer Aided Design and Manufacture) and robotics have required from the outset models that are faithful and accurate, and that can be used to reason about the physics of the objects. But computation with such models has tended to be too slow for interactive applications.
With the tremendous increase in computational resources we have been experiencing over the last decades, the situation is changing: models used for graphics are becoming more physically correct, and models used for robotics and automation are being processed at interactive speeds. A very important part of a physically adequate model is its underlying geometry. (There is a lot more to physical models besides geometry, and we teach a course on such issues at USC.) CS 582, Geometric Modeling, is primarily concerned with geometric models for three-dimensional objects, and with the associated computer algorithms for constructing and querying the models.
The course develops mathematical models and computer representations for solid objects and other pratically-useful spatial entities from basic principles of set theory, geometry, and topology. This theoretical basis is used to develop algorithms for important applications, which include the automatic generation of graphical displays and drawings, the calculation of mass properties (e.g., volume and moments of inertia), the detection of spatial interferences, and the computation of collision-free paths for robots in the midst of obstacles. Application emphasis is in two general areas: (i) graphics and multimedia, and (ii) robotics and automation.
The intended audience are engineering and computer science graduate students who are interested in the mathematical and computational aspects of three-dimensional geometry, and in the use of geometry in computer graphics, games, robotics, computer vision, and computer-aided (or -automated) design and production. The course attempts to strike a balance between basic theory and practical applications. Because it is not possible to cover in reasonable depth the entire field of geometric modeling in one term, the emphasis is on “combinatorial” (rather than “numerical”) issues, and on polyhedral (rather than curved) objects. Also, we attempt to complement the material covered in related courses such as computer graphics, computational geometry and physically-based modeling.
Programming assignments involve graphics using Java3D, which is a 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 “At’ usc.edu.
Office hours: Tuesdays and Thursdays, 3:30-4:50 pm or by appointment.
Time: Tuesdays and Thursdays, 11:00-12:20.
Location: KAP 138.
Home Page: http://www-bcf.usc.edu/~requicha/Courses/cs582/
Course account: ~cs582 in the scf machines. This is a regular Unix account, not a web server.
Prerequisites: Linear Algebra and Data Structures. Programming skills are essential. Students who are not familiar with Java are expected to learn it on their own. Computer Graphics is not a prerequisite.
Texts: None. Most of the material is available on-line in Acrobat PDF format by following links from the course’s web page.
TA: TBD.
REFERENCES
I will not be following closely any of the cited books. The books are on reserve in the Seaver Science Library under cs582. The first two books are also available on line, in Java’s web site. The journal papers are available at Seaver and, in many cases, are online on the corresponding journal web sites. Note that journal web sites normally need to be accessed from USC machines or through a remote proxy — click here for additional information — otherwise you will be asked to pay for downloads.
- Walrath and M. Campione,The JFC Swing Tutorial: a Guide to Constructing GUIs. Reading, MA: Addison Wesley, 2nd Ed., 1999.
- Sowizral, K. Rushforth and M. Dearing,The Java 3D API Specification. Reading, MA: Addison Wesley, 1998.
- M. Hoffmann,Geometric and Solid Modeling:An Introduction. San Mateo, CA: Morgan Kaufmann, 1989.
- Mäntylä,An Introduction to Solid Modeling. Rockville, Maryland: Computer Science Press, 1988
M.E. Mortenson, Geometric Modeling. New York: Wiley, 1985
P.R. Halmos, Finite Dimensional Vector Spaces. New York: Van Nostrand, 2nd ed., 1958.
- Nomizu,Fundamentals of Linear Algebra.New York: Chelsea, 2nd ed., 1979.
- M. Bloom,Linear Algebra and Geometry. Cambridge: Cambridge University Press, 1979.
- Mendelson,Introduction to Topology. Boston, MA: Allyn and Bacon, 3rd ed., 1975.
- Henle,A Combinatorial Introduction to Topology. San Francisco: Freeman, 1979.
- K. Agoston,Algebraic Topology: A First Course. New York, Marcel Dekker, 1976
- D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes,Computer Graphic Principles and Practice.Reading, MA: Addison-Wesley, 2nd ed., 1990.
- Farin,Curves and Surfaces for CAGD. S, Diego, CA: Academic Press, 4th ed., 1997 (or latest edition).
- Rockwood and P. Chambers,Interactive Curves and Surfaces. S. Francisco, CA: Morgan Kaufmann, 1966.
- A. G. Requicha, “Representations for Rigid Solids: Theory, Methods, and Systems”,ACM Computing Surveys, Vol. 12, No. 4, pp. 437-464, December 1980.
- 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.
- A. G. Requicha, “Mathematical Models of Rigid Solid Objects”, Tech. Memo. No. 28, Production Automation Project, Univ. of Rochester, November 1977. Availablehere.
- 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.
- 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.
- 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.
THE RULES OF THE GAME
There will be a mid-term exam, on October 10, in class (or at a place to be announced), at the regular time. A second midterm will be held at the end of the semester, on December 5. The second exam will cover only the material discussed after the first midterm. The exams will be closed book. Several programming assignments and a term project, due approximately one week before the end of classes, on November 26, 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 Academic 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 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 1/3 of the grade, and the final assignment another 1/3. Note: Since I do not have a TA in 2013, only the final homework (project) will be graded. However, the other assignments are necessary as a build up for the final one, and therefore I highly recommend that you do them, and on time, or you will have a very difficult time with the final project.
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.
COURSE OUTLINE
- Introduction
1.1 Preamble
1.2 The Role of Geometry in CAD/CAM
1.3 The Role of Geometry in 3-D Graphics
1.4 Models, Representations, Algorithms and Systems
1.5 Historical Summary
- Motions and Projections
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
2.8 Mathematical Underpinnings
- Representations
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
3.2.7 Hybrid Methods
3.3 Mathematical Underpinnings
3.3.1 Mathematical Models and Computational Representations
3.3.2 General Topology and Regular Sets
- Curves and Surfaces
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
4.3.3 Subdivision Surfaces
- Solids
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
5.3 Mathematical Underpinnings
- Fundamental Algorithms
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
6.8 Efficiency Enhancements
6.8.1 Enclosures
6.8.2 Spatial Data Structures
6.8.3 Sweeping
- Application Algorithms
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 Robot Path Planning
7.3.1 Configuration Space
7.3.2 Cell Decomposition Algorithms
7.3.3 Roadmap Algorithms
7.3.4 Potential Fields
