24-786  Geometric Modeling  Spring 98
Carnegie Mellon University

Place: 220 Scaife Hall  Time: Mon&Wed 9:30-11:20am  Instructor: Kenji Shimada 
 Course Information
 
Announcements
(last modified on 4/19/98,  Old Announcements)

Course Description

This course teaches concepts and tools to design and implement three dimensional geometric modeling systems for curves, surfaces and solids. Handling three dimensional geometric information on the computer is essential in many application areas, such as computer-aided design (CAD), computer-aided manufacturing (CAM), computer-aided engineering (CAE), robotics, computer vision, and computer graphics. The course covers geometry representations, algorithms, and the underlying theoretical framework, essential to solving geometric problems encountered in these application areas. The topics include: (1) geometric and topological representation of three dimensional objects, (2) curve and surface representation, (3) geometric algorithms and operations on curves, surfaces, and solids, and (4) real-world problems in geometric modeling. Selected advanced research issues, such as mesh generation, shape reconstruction, data compression, feature-based modeling, data conversion, non-manifold geometry, and variational surface modeling are also studied.

Instructor

Recommended Background Textbook Students Syllabus and Schedule

The subject matter to be presented in this course may roughly be divided into 4 categories.  These categories and the approximate time to be devoted to each are:

( The coverage and the schedule are subject to change based on students' needs. )
 
Date Content Handouts Reading PS Out/Due
<1>1/12M 1.INTRODUCTION 
 1.1 Background 
 		 Class home page 
Useful references 
3D CAD trends 
PS1 		 p.1-18(intro.) 
p.431-437(vector)
PS1 Out
<2>1/14W  1.2 Vectors and Matrices 
 1.3 Lines and Planes 
(PS1, VRML)		 p.431-437(matrix) 
 
<3>1/19M  1.4 Coordinate Transformations General rotation matrix p.439-471(transf.)
<4>1/21W  1.4 ... 
(PS2)		 PS2
PS1 Due
PS2 Out
<5>1/26M  1.5 Areas and Volumes 
(PS1 Review) 
(C Macros for Vectors and Rotations)		 C Macros 
Graded PS1
<6>1/28W 2.SOLID MODELING 
 2.1 Introduction 
 2.2 Mathematical Model of Solids 
  2.2.1 Mathematical Object 
  2.2.2 Point-Set Models		 p.281-373
<7>2/2M   2.2.3 Boundary-Based Models
PS2 Due
 
<8>2/4W    2.2.3 ... 
(PS2 review)		 Plane model examples 
Graded PS2
<9>2/9M <QUIZ 1: INTRODUCTION> PS3
PS3 Out
<10>2/11W  2.3 Constructive Solid Geometry 
(Q1 review)		 Regularized Boolean Set Op. 
Graded Q1		 p.318-356(CSG)
 
<11>2/16M  2.3 ... 
<12>2/18W  2.4 Decomposition Model 
  2.4.1 Spatial Occupancy Enumeration 
  2.4.2 Octrees		 PS4 
Tree traversal
PS3 Due
PS4 Out
<13>2/23M   2.4.3 kD Tree 
(PS3 review) 
(PS4 comments)		 PS3 Solutions 
Graded PS3 
Half edge data structure
 
<14>2/25W  2.5 Boundary Representation 
  2.5.1 Data Structure 
  2.5.2 Euler Operators		 Euler operators worksheet
 
 
<15>3/4W   2.5.2 ... 
  2.5.3 Modeling Operations
PS4 Due
<16>3/9M 3.CURVES AND SURFACES 
 3.1 Basic Curves 
  3.1.1 Explicit, Implicit, and Parametric Forms 
  3.1.2 Algebraic & Geometric Forms 
  3.1.3 Analytic Curves in 3D 
(PS4 review) 
(PS5 comments)		 Graded PS4 
PS5		 p.19-38
PS5 Out
<17>3/11W  3.2 Hermite Curves 
  3.2.1 Algebraic & Geometric Forms 
  3.2.2 Matrix Forms 
  3.2.3 Tangent Vectors and Controllability 
  3.2.4 Four Point Interpolation 
  3.2.5 Continuity		 p.39-80
<18>3/16M (Solid Modeling review) 
(PS5-2&3 review)		 Project
PS5 Due
 
<19>3/18W
<QUIZ 2: SOLID MODELING>
 
3/23 & 3/25
:-) :-) :-) SPRING BREAK :-) :-) :-)
:-) :-) :-) :-) :-) :-)
:-) :-) :-)
:-) :-) :-)
<20>3/30M (PS5-1 review) 
(QUIZ 2 review) 
 3.3 Bezier Curves 
  3.3.1 Hermite-Bezier Conversion 
(PS6 comments)		 Graded PS5 
Graded Q2 
PS6		 p.81-112
PS6 Out 
<21>4/1W   3.3.2 Bezier Basic Functions 
  3.3.3 Properties of Bezier Curves 
  3.3.4 The de Casteljau Algorithm 
  3.3.5 Composite Bezier Curves
<22>4/6M OFF
Prj Proposal Due
<23>4/8W <ST1: Morphing (Prof. Suzuki, Univ. of Tokyo)> 
 3.4 B-Spline Curves 
  3.4.1 Introduction 
  3.4.2 B-Spline Basis Function 
<ST2: Sheet Metal Part Stacking (Venkat Ayyadevara)>		 p.113-142
PS6 Due
<24>4/13M (PS6 review) 
  3.4.3 Multiplicity and Continuity 
  3.4.4 Bezier vs B-Spline 
  3.4.3 Open B-Spline Curves
<25>4/15W  3.5 Hermite Surfaces 
  3.5.1 Algebraic & Geometric Forms 
  3.5.2 Geometry Vectors 
 3.6 Bezier Surfaces 
  3.6.1 Geometry Vectors 
  3.6.2 Converting Hermite to Bezier 
  3.6.3 Composite Bezier Surfaces 
<ST3: Robotic Path Planning (Ercan Acar)>
 
<26>4/20M Review: Curves and Surfaces 
<ST4: (Su Yin)>
<27>4/22W
<QUIZ 3: CURVES AND SURFACES>
<28>4/27M
PROJECT PRESENTATION
Prj Report Due
<29>4/29W
PROJECT PRESENTATION

Assignments

8 problem sets, some with hands-on programming, are given to help students better understand the course material. The programming part of the assignments is not too intensive, and the introduction to necessary programming environments and software tools is provided by the instructor. Reading materials are occasionally given from textbook chapters, technical journals and conference papers.

The solutions to the Problem Sets that you hand in should be generated by your individual effort.  It is ok to discuss the problems with other students, but the written solutions and programs must be your own work and not copied from someone else.

Hand in your solutions to the problem sets at the beginning of the class (9:30am) on the due date. Program source codes and results should be copied to the following afs directory by the same due date and time:
     /afs/andrew/cit/meche/cie01/gm98/your_name/
Late policy:  10% off for one CMU class day, 20% off for two CMU class days, 30% off for three CMU class days, and 50% off afterward.  For example, suppose the due date is 9:30am Thursday morning, you will lose 10% if you hand it in by 9:30am Friday, 20% by 9:00am next Monday, 30% by 9:00am next Tuesday, and 50% afterward.

Pictures from the Problem Sets

Estimated Workload

Time management is a critical factor to your academic success, as to any professional environment.  Being a 12 unit course it is expected that each student will devote approximately 12 hours a week in completing: (1) assigned reading, (2) attending lectures, (3) problem sets, (4) reviewing lecture materials, and (5) preparation for quizzes.  While the exact time devoted by individuals would vary depending on the background, a suggested time budget follows:

Lectures 3.7 hours
Review of Lectures and Reading 2.3 hours
Problem Sets 6.0 hours
Evaluation of Student Performance

The final grade will be determined by an absolute method of grading.  This is to allow you to obtain a grade based on your individual performance without having to compete with each other.  It is thus possible for the whole class to get an A grade or in the other case for the whole class to get a C grade.  (Of course we hope that you all will work hard and get an A :-)  The evaluation of your work in the course will consist of the following items:

Item Percent of Final Grade
Class Participation 10%
Problem Sets 1--8 40%
Quizzes 1--3 30%
Project 20%
There will be no final exams.

How am I doing with Problem Sets and Quizzes?

Project

The following is the tentative description of the project that you will do toward the end of this course.  The due dates and the mission statement are subject to change.

Old Announcements
shimada@cmu.edu