W Randolph Franklin home page
... (old version) Login


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.

Contents (hide)

  1.   1.  External links
  2.   2.  Possible lecture modules
  3.   3.  Lectures day-by-day
  4.   4.  Computational Geometry
  5.   5.  Term project

1.  External links

2.  Possible lecture modules

ECSE-6800 will contain modules in topics like these:

  1. Computational geometry
    1. Theory
      1. Shamos & Preparata
      2. Lee & Preparata paper
      3. some newer review
    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.
  5. CAD
  6. Graphics HW including GPUs
    1. e.g. Wikipedia:Radeon_R520
    2. programmable GPUs
  7. L-systems
  8. Architecture of a simple graphics system

3.  Lectures day-by-day

No Date Summary
1 Mon Jan 12 Topics:
  1. Intro.
  2. Povray
    1. http://povray.org/
    2. local site
    3. Rendering terrain with povray
      1. Main/povray-terrain-1.tz shows how to render images of terrain in povray.
      2. Main/povray-terrain-2.tz has more test data and the corresponding images.
  3. Quaternions
  4. More on rotation: Rotation3D
2 Thu Jan 15 Topics: Povray and quaternions, ctd.
3 Thu Jan 22 Topics:
  1. Floating Point - motivation for robustness in Computational Geometry.
  2. End class earlier to go to Stallman's lecture at 4 in DCC308.

Announcements:

  1. Quaternions updated.
  2. Homework 1 out.
4 Mon Jan 26 Topics:
  1. New topics: I'll do Computational Geometry and CGAL in parallel for a few days.
  2. brief points from http://www.cs.wustl.edu/~pless/506/lecture1.html which defines Computational Geometry.
  3. Oswin Aichholzer's Tutorial

Reading:

  1. 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:

  1. 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.
  2. Is anyone interested in these topics for a term project:
    1. helping a bobsledder analyze bobsled partial timings during races, to determine how to improve.
    2. helping someone who is trying to visualize hygrographic data to locate Atlantis.
5 Thu Jan 29 Topics:
  1. continue Aichholzer's tutorial.
  2. CGAL

Announcements:

  1. 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:
  1. Questions raised recently:
    1. How do you represent a polygon (or polyhedron)?
    2. Constructive Solid Geometry (CSG)
      1. Q: What do you want the boolean combination of two polygons (or polyhedra) to mean when they overlap on an edge or a vertex?
      2. A: You probably don't want isolated spikes and cuts in the answer.
      3. Therefore, define regularized set operations: take the closure of the interior of the resulting set of points.
      4. Advantages of CSG:
        1. Builds complex objects from a small set of primitives
        2. The result is always watertight
        3. Easy to visualize the result
        4. Easy to compute approximate volume
        5. Easy to test whether a point is contained.
        6. Easy to do boolean ops.
        7. Easy to get a simple system working.
      5. Disadvantages of CSG:
        1. The 'small set of primitives' idea fails for more general surfaces like parametric patches.
        2. Hard to compute exact volumes.
        3. Hard to compute edges of the resulting object.
        4. There is not one unique canonical representation of an object.
        5. Determining whether an object is the empty set can be hard.
      6. Therefore CSG was more popular in the past.
      7. Note to people reading this section: additions are welcome.
    3. B-rep (boundary representation):
      1. The major competitor to CSG.
      2. Describe the object's boundary using whatever primitives you like, e.g., trimmed surfaces.
      3. Faces and shells, edges and loops, vertices.
      4. Geometry and topology.
      5. OpenGL facilitates this.
      6. 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.
      7. Difficult to ensure that the polygon is legal.
    4. What is a legal polygon?
      1. Multiple components, nested components, holes, overlaps, non-manifold cases?
      2. Your answer determines, e.g., whether the union of two polygons is always a legal polygon, i.e., closure under union.
      3. People like Mike Wesley (DBLP) doing operations like fleshing out wire frames and fleshing out projections first resolve this in tedious detail.
      4. CGAL has Nef-polyhedron: intersection and complement of a finite number of open half-spaces.
  2. Voronoi diagram
    1. The most important geometric data structure; it orders points in 2-D, 3-D, etc.
    2. applet
    3. Dual to Delauney triangulation.
    4. Many methods, such as randomized incremental insertion. Inserting points in random order keeps the average time down.
    5. This requires quickly locating the new point in the current diagram.
    6. In {$E^d$}, {$T=\theta\left(N^{\lceil d/2 \rceil}\right) $} possibly times {$\log N$}.
    7. 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.
    8. 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:
  1. Another nice CGAL intro
  2. Discussion on stereo and 3D video
    1. Superbowl commercial
    2. Red-cyan glasses
    3. polarized glasses
    4. shutter glasses
    5. separate display for each eye, in a headset
    6. Wii.
    7. graphics cards like NVidia have driver support
    8. Lenticular monitors
    9. Vibrating mirror
    10. MERL 3D TV
  3. Start a new topic: Splines and patches. My notes. This is a natural followon to CSG and B-rep.

Announcements:

  1. Homework 2 out, in Homeworks.
8 Mon Feb 9 Topics:
  1. CGAL demos: Voronoi_2, Min_circle_2, Partition_2, Straight_skeleton_2, Boolean_set_operations_2, Polygon_2
  2. Continue curves.

Reading: http://www.engineeringchallenges.org/ (Scan it)
Announcements: What do you want next?

  1. color
  2. HW shaders
9 Thu Feb 12 Topics: Color:
  1. Maureen Stone: Representing Colors as 3 Numbers
  2. Wikipedia:XYZ_color_space
  3. Wikipedia:Color_temperature
  4. http://hyperphysics.phy-astr.gsu.edu/hbase/geoopt/refr.html
  5. http://hyperphysics.phy-astr.gsu.edu/hbase/phyopt/reflectcon.html
  6. http://hyperphysics.phy-astr.gsu.edu/hbase/phyopt/freseq.html
  7. 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:
  1. Brigada on Stratosys
  2. Li on Microsoft surfaces
  3. 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:
  1. Brigada on Utah
  2. continue SIGGRAPH 2002 course 2: Advanced Global Illumination from page 134.

Reading:

  1. Wikipedia:Qt_toolkit
  2. Qt Reference Documentation - scan
  3. Qt Quarterly

Announcements:

  1. Just ask if you'd like to change dates.
  2. Future invited speakers may force you to change your dates.
  3. 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.
  4. My next topic: Qt.
15 Thu Mar 5 Topics:
  1. Ching on Pixar
  2. Lau on e.g. Chinese U of Hong Kong

Reading:
Announcements:

  1. (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:
  1. Calcutt on MIT
  2. DeCell on Stanford
  3. WRF on Tcl/Tk
    1. /usr/lib64/tcl/tk8.5/demos/timer (on my machine)
    2. /usr/lib64/tcl/tk8.5/demos/widget

Reading:
Announcements:

17 Thu Mar 19 Topics:
  1. Franz on Brown
  2. Ching on
  3. Smith on IBM

Reading:
Announcements:

18 Mon Mar 23 Topics:
  1. Calcutt on MIRA
  2. DeCell on
  3. Franz on
  4. QT videos:
    1. Qt Creator - 01 An Introduction
    2. Qt Creator - 02 My first creation
    3. Qt Creator - 03 Smart Code Completion
    4. Qt 4.4 Features Walkthrough
    5. This is Qt 4.5
    6. Layout Animations with Qt Kinetic
    7. Introduction to Qt
    8. Creating interactive QT hello world GUI application using QT Creator

Reading:
Announcements: Next topics: HW shaders and VTK

19 Thu Mar 26 Topics:
  1. Smith on artificial retina
  2. Lau on simulating Chinese painting
  3. Start HW shaders

Reading:
Announcements:

  1. Term project details online here
  2. Note the line about emailing me your preferred dates.
20 Mon Mar 30 Topics:
  1. Li on NPR
  2. 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:
  1. GPUs:
    1. Wikipedia:Graphics_processing_unit
    2. Wikipedia:Radeon_R700
    3. http://ati.amd.com/products/radeonhd4800/overview-4890.html
    4. http://www.anandtech.com/printarticle.aspx?i=3354
    5. http://hardware.slashdot.org/article.pl?sid=09/04/02/193256
    6. http://www.extremetech.com/article2/0,2845,2344294,00.asp
    7. http://www.phoronix.com/scan.php?page=article&item=amd_radeon_hd4890&num=1
    8. http://www.gpureview.com/
  2. GPGPU:
    1. http://www.gpgpu.org/
    2. http://graphics.stanford.edu/%7Ekayvonf/papers/fatahalianCACM.pdf - A closer look at GPUs
    3. http://gates381.blogspot.com/
    4. http://graphics.stanford.edu/~kayvonf/official/index.html
    5. http://s08.idav.ucdavis.edu/
    6. http://s08.idav.ucdavis.edu/luebke-nvidia-gpu-architecture.pdf
    7. http://s08.idav.ucdavis.edu/luebke-cuda-fundamentals.pdf

Reading:

  1. SIGGRAPH 91 and 92 preliminary programs
  2. Raytracing jello brand gelatin
  3. Wikipedia on shaders:
    1. Wikipedia:Shader
    2. Wikipedia:Vertex_shader
    3. Wikipedia:Geometry_shader
    4. Wikipedia:Pixel_shader
    5. Wikipedia:Unified_shader_model
    6. Wikipedia:Shading_language
    7. Wikipedia:OpenGL_Shading_Language
    8. Wikipedia:Comparison_of_OpenGL_and_Direct3D

Announcements:

  1. term project proposal due
22 Mon Apr 6 Topics:
  1. GPU Programming For The Rest Of Us Note the matrix multiplication example.
  2. 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
  1. intro video
  2. Geographic Information Systems - USGS
  3. What is GIS?
  4. major packages:
    1. ArcGIS from ESRI (commercial),
    2. GRASS (open)
  5. geoid, projections, coordinates
  6. raster, vector data
  7. generic database systems don't work (and they tried!)
  8. http://terrainmap.com/ - John Childs' (Masters, ECSE, RPI, 2003) excellent allround site (Disclaimer: I know his advisor well)
  9. GRASS Geographic Information System

Reading:
Announcements:

24 Mon Apr 13 Topics:
Special guest lecturer: Tobi Saulnier, PhD, ECSE, CEO, 1st Playable
Reading:
Announcements:
25 Thu Apr 16 Topics:

class cancelled; prof sick. Reading:
Announcements: term project progress report due

26 Mon Apr 20 Topics:
  1. term project presentations
    1. Smith
    2. (this space for rent)
  2. demo of retrieving data from the USGS seamless data server and displaying it in GRASS.
27 Thu Apr 23 Topics:

term project presentations

  1. Lau and You
  2. Franz
  3. Ching
28 Mon Apr 27 Topics:
  1. term project presentations
    1. DeCell
    2. Calcutt
    3. Brigada
  2. term project report due

4.  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

5.  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.