ECSE-6800 Advanced Computer Graphics, Spring 2009, W. Randolph Franklin
Rensselaer Polytechnic Institute, Troy NY USA

Class meets Mon and Thurs 4-5:20 in JEC4107.

Possible lecture modules

ECSE-6800 will contain modules in topics like these:

1. Computational geometry
1. Theory
1. Shamos & Preparata
2. Lee & Preparata paper
2. Practice
1. Computational Geometry Algorithms Library, (CGAL)
2. LEDA
3. st from Edelsbrunner?
3. homework
1. implement spacewar
2. Color
3. Something from SIGGRAPH
1. SIGGRAPH 2000 course Migrating to an Object Oriented Graphics API c15color.pdf
4. GIS
1. Geographic Information Systems and Science, including an intro to ESRI's ArcGIS.
6. Graphics HW including GPUs
2. programmable GPUs
7. L-systems
8. Architecture of a simple graphics system

Lectures day-by-day

 No Date Summary 1 Mon Jan 12 Topics: Intro. Povray http://povray.org/ local site Rendering terrain with povray Main/povray-terrain-1.tz shows how to render images of terrain in povray. Main/povray-terrain-2.tz has more test data and the corresponding images. Quaternions More on rotation: Rotation3D 2 Thu Jan 15 Topics: Povray and quaternions, ctd. 3 Thu Jan 22 Topics: Floating Point - motivation for robustness in Computational Geometry. End class earlier to go to Stallman's lecture at 4 in DCC308. Announcements: Quaternions updated. Homework 1 out. 4 Mon Jan 26 Topics: New topics: I'll do Computational Geometry and CGAL in parallel for a few days. brief points from http://www.cs.wustl.edu/~pless/506/lecture1.html which defines Computational Geometry. Oswin Aichholzer's Tutorial Reading: Install CGAL, preferably 3.3.1 (since 3.4.0 seems to have some problems). Browse the tutorials in http://www.cgal.org/Tutorials/ . Note that the CGAL API has changed, so those examples probably don't compile now. Announcements: CANCELLED Blue Sky Animation Studios: Come and hear Blue Sky Studio's Steve Martino, director of Dr. Seuss~s ~Horton Hears a Who~ and "Robots"! Steve will be presenting on the design and direction of computer animation. Wednesday, January 28, 2009; 3:00-4:00PM, Center for Biotechnology, Auditorium. Is anyone interested in these topics for a term project: helping a bobsledder analyze bobsled partial timings during races, to determine how to improve. helping someone who is trying to visualize hygrographic data to locate Atlantis. 5 Thu Jan 29 Topics: continue Aichholzer's tutorial. CGAL Announcements: Rescheduled Blue Sky Animation Studios: Come and hear Blue Sky Studio's Steve Martino, director of Dr. Seuss~s ~Horton Hears a Who~ and "Robots"! Steve will be presenting on the design and direction of computer animation. Wednesday, Feb 4, 2009; 3:00-4:00PM, Center for Biotechnology, Bruggeman room 6 Mon Feb 2 Topics: Questions raised recently: How do you represent a polygon (or polyhedron)? Constructive Solid Geometry (CSG) Q: What do you want the boolean combination of two polygons (or polyhedra) to mean when they overlap on an edge or a vertex? A: You probably don't want isolated spikes and cuts in the answer. Therefore, define regularized set operations: take the closure of the interior of the resulting set of points. Advantages of CSG: Builds complex objects from a small set of primitives The result is always watertight Easy to visualize the result Easy to compute approximate volume Easy to test whether a point is contained. Easy to do boolean ops. Easy to get a simple system working. Disadvantages of CSG: The 'small set of primitives' idea fails for more general surfaces like parametric patches. Hard to compute exact volumes. Hard to compute edges of the resulting object. There is not one unique canonical representation of an object. Determining whether an object is the empty set can be hard. Therefore CSG was more popular in the past. Note to people reading this section: additions are welcome. B-rep (boundary representation): The major competitor to CSG. Describe the object's boundary using whatever primitives you like, e.g., trimmed surfaces. Faces and shells, edges and loops, vertices. Geometry and topology. OpenGL facilitates this. Trimming happens when you intersect 2 patches. The trim lines on the two relevant patches are usually slightly different, leading to a non-watertight object. Difficult to ensure that the polygon is legal. What is a legal polygon? Multiple components, nested components, holes, overlaps, non-manifold cases? Your answer determines, e.g., whether the union of two polygons is always a legal polygon, i.e., closure under union. People like Mike Wesley (DBLP) doing operations like fleshing out wire frames and fleshing out projections first resolve this in tedious detail. CGAL has Nef-polyhedron: intersection and complement of a finite number of open half-spaces. Voronoi diagram The most important geometric data structure; it orders points in 2-D, 3-D, etc. applet Dual to Delauney triangulation. Many methods, such as randomized incremental insertion. Inserting points in random order keeps the average time down. This requires quickly locating the new point in the current diagram. In {$E^d$}, {$T=\theta\left(N^{\lceil d/2 \rceil}\right)$} possibly times {$\log N$}. Steve Fortune has an efficient sweep line method to construct the Voronoi diagram. The code is free. That link is to the Steve Skiena's Stony Brook Algorithm Repository. Here is an applet showing it. Fortune later worked on WiSE - A Wireless System Engineering Tool to compute the coverage of, and optimize, micro cells for cellphones inside buildings. Note that one of WISE's co-authors is Brian Kernighan. It was Kernighan who, as a pun, named a new OS being developed at Bell Labs Unix. 7 Thu Feb 5 Topics: Another nice CGAL intro Discussion on stereo and 3D video Superbowl commercial Red-cyan glasses polarized glasses shutter glasses separate display for each eye, in a headset Wii. graphics cards like NVidia have driver support Lenticular monitors Vibrating mirror MERL 3D TV Start a new topic: Splines and patches. My notes. This is a natural followon to CSG and B-rep. Announcements: Homework 2 out, in Homeworks. 8 Mon Feb 9 Topics: CGAL demos: Voronoi_2, Min_circle_2, Partition_2, Straight_skeleton_2, Boolean_set_operations_2, Polygon_2 Continue curves. Reading: http://www.engineeringchallenges.org/ (Scan it)Announcements: What do you want next? color HW shaders 9 Thu Feb 12 Topics: Color: Maureen Stone: Representing Colors as 3 Numbers Wikipedia:XYZ_color_space Wikipedia:Color_temperature http://hyperphysics.phy-astr.gsu.edu/hbase/geoopt/refr.html http://hyperphysics.phy-astr.gsu.edu/hbase/phyopt/reflectcon.html http://hyperphysics.phy-astr.gsu.edu/hbase/phyopt/freseq.html SIGGRAPH 2002 course 21: A Field Guide to Digital Color. Reading: the course notes. The slides start on page 59. 10 Tues Feb 17 Topics: behind-the-scenes tour of EMPAC by Eric Ameres 11 Thu Feb 19 Topics: Brigada on Stratosys Li on Microsoft surfaces SIGGRAPH 2002 course 2: Advanced Global Illumination 12 Mon Feb 23 Topics: Continue SIGGRAPH 2002 course 2: Advanced Global Illumination 13 Thu Feb 26 Topics: Scalability in computer games talk by Johannes GehrkeCornell University, in JEC3117. 14 Mon Mar 2 Topics: Brigada on Utah continue SIGGRAPH 2002 course 2: Advanced Global Illumination from page 134. Reading: Announcements: Just ask if you'd like to change dates. Future invited speakers may force you to change your dates. If you asked for a topic that someone else asked for first, I left your topic blank in this calendar. You may either do the topic you asked for (but please pick a different subtopic) or pick a new one. My next topic: Qt. 15 Thu Mar 5 Topics: Ching on Pixar Lau on e.g. Chinese U of Hong Kong Reading:Announcements: (nothing to do with graphics, but everything to do with engineering) The reported cause of the Turkish airlines plane crash at Schipol airport: The altimeter, which was known to be faulty, reported an altitude of zero. The plane was on autopilot. The autopilot inferred that the plane had landed and shut down the engines. The plane crashed before the crew could restart them. http://news.bbc.co.uk/2/hi/europe/7923782.stm Mon Mar 9 no class; spring break. Thu Mar 12 no class; spring break; prof day hiking Grand Canyon (4800 ft down South Kaibab Trail, 4600 ft up Bright Angel Trail; 16 miles total in 11 hours including time spent sunning by the Colorado River) 16 Mon Mar 16 Topics: Calcutt on MIT DeCell on Stanford WRF on Tcl/Tk /usr/lib64/tcl/tk8.5/demos/timer (on my machine) /usr/lib64/tcl/tk8.5/demos/widget Reading:Announcements: 17 Thu Mar 19 Topics: Franz on Brown Ching on Smith on IBM Reading:Announcements: 18 Mon Mar 23 Topics: Reading:Announcements: Next topics: HW shaders and VTK 19 Thu Mar 26 Topics: Smith on artificial retina Lau on simulating Chinese painting Start HW shaders Reading:Announcements: Term project details online here Note the line about emailing me your preferred dates. 20 Mon Mar 30 Topics: Li on NPR Now we have a few days on HW (vertex and fragment) shaders, which I briefly introduced last fall. I'll teach with examples from the excellent Open GL SuperBible. See also http://www.pdf-search-engine.com/the-opengl-superbible-pdf.html. The example programs are here.Reading:Announcements: 21 Thu Apr 2 Topics: Reading: Announcements: term project proposal due 22 Mon Apr 6 Topics: GPU Programming For The Rest Of Us Note the matrix multiplication example. http://gpgpu.org/s2005 Tues Apr 7 Topics: 4-6 pm in the Biotech auditorium. Tobi Saulnier, BS, MS, PhD, RPI/EE on Penguins, Pirates and Polytechics 23 Thu Apr 9 Topics:Intro to cartographic data intro video Geographic Information Systems - USGS What is GIS? major packages: ArcGIS from ESRI (commercial), GRASS (open) geoid, projections, coordinates raster, vector data generic database systems don't work (and they tried!) http://terrainmap.com/ - John Childs' (Masters, ECSE, RPI, 2003) excellent allround site (Disclaimer: I know his advisor well) GRASS Geographic Information System Reading:Announcements: 24 Mon Apr 13 Topics:Special guest lecturer: Tobi Saulnier, PhD, ECSE, CEO, 1st PlayableReading:Announcements: 25 Thu Apr 16 Topics: class cancelled; prof sick. Reading:Announcements: term project progress report due 26 Mon Apr 20 Topics: term project presentations Smith (this space for rent) demo of retrieving data from the USGS seamless data server and displaying it in GRASS. 27 Thu Apr 23 Topics: term project presentations Lau and You Franz Ching 28 Mon Apr 27 Topics: term project presentations DeCell Calcutt Brigada term project report due

Computational Geometry

1. Implementing geometry is totally different from doing it on paper and proving theorems. Ex: convex hull.
2. Here is a concise intro by Robert Pleiss from David Mount: http://www.cs.wustl.edu/~pless/506/lecture1.html I'll do the start of this in class.
3. http://www.industrial-geometry.at/events/strobl2006/cg_edu_aichholzer_a4.pdf I'll do this in class.
4. The book Computational Geometry by Preparata and Shamos remains one of the most understandable intros to Computational Geometry. The only concern is that is old enough that some recent topics are not covered. We may do some of it.
5. http://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
6. http://www.cs.unc.edu/~lin/COMP290-72/
7. The Stony Brook Algorithm Repository
8. http://www.mpi-inf.mpg.de/LEDA/leda.html
9. http://cgtutorial.sourceforge.net/ Computational Geometry Tutorial in Java
10. http://reference.wolfram.com/mathematica/ComputationalGeometry/tutorial/ComputationalGeometry.html

Term project

1. Write a 6-8 page paper in an academic style on any topic even vaguely related to the course. It could be either
1. research,
2. implementation, or
3. survey.
2. Format it using LateX or Word using the Symposium on Computational Geometry 2009 style guide here: http://www.sheridanprinting.com/typedept/scg.htm with these simplifications:
1. I want only the PDF result, not any input files.
2. Don't worry about the copyright; you may explicitly list yourself as the copyright holder if you wish.
3. Teams are ok.
4. Combining with another course is ok, if you tell everyone concerned.
5. Building on existing work is ok, if you tell me.
6. Give a 20 minute talk in class, to be followed by 5 minutes of questions. Use visual aids, such as HTML, powerpoint, or wimpypoint.
7. Email me to reserve a slot to present your talk on one of the last 4 class days. Give a first and second choice of dates.
8. Schedule:
1. Apr 2: project summary: date, authors, title, 100 word abstract.
2. Apr 16: progress report.
3. Apr 20, 23, 27: presentations, 3 per day. Email me your ranked preferred dates.
4. Apr 27: final report.
9. Two possible projects are:
1. Analyzing bobsled statistics
2. Helping someone who thinks that Google Earth shows evidence of Atlantis on the bottom of the Atlantic.