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

ECSE-4750 Computer Graphics, Fall 2007, W. Randolph Franklin
Rensselaer Polytechnic Institute, Troy NY USA



moved aside to Syllabus.

(:showhide div=modules init=show lshow='Show Possible lecture modules' lhide='Hide Possible lecture modules':)

Possible lecture modules

Computational geometry

ECSE-6800 will contain modules in topics like these:

  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


Something from SIGGRAPH

  1. SIGGRAPH 2000 course

Migrating to an Object Oriented Graphics API c15color.pdf


  1. Geographic Information Systems and Science, including an intro to ESRI's ArcGIS.


Graphics HW including GPUs

  1. e.g. http://en.wikipedia.org/wiki/Radeon_R520
  2. programmable GPUs


Architecture of a simple graphics system

(:showhide div=modules lshow='Show Possible lecture modules' lhide='Hide Possible lecture modules':)


I'll write a one sentence summary of each lecture, after the class, and also use this for announcements.

No Date Summary
1 Mon Jan 14
  1. Intro, syllabus
  2. povray: http://povray.org/, local site with assorted files.
  3. mention SIGGRAPH student interns
  4. homework 1 online
2 Thu Jan 17
  1. Email me at least 3 choices of labs and dates by 1/24 that you'd like to present. I'll pick 2. Earlier emails get first choices.
  2. Computational Geometry
3 Thu Jan 24
  1. homework 1 due
  2. Start CGAL - the Computational Geometry Algorithms Library.
    1. Implementing Geometric Algorithms - LEDA and CGAL
4 Mon Jan 28
  1. FloatingPoint notes.
  2. Run some CGAL demos cgal_windows_demos.zip
  3. Examine some source code.
  4. See some of this tutorial: CGAL_tutorial.pdf. Read it for Thurs.
5 Thu Jan 31
  1. more CGAL
  2. Pixar presented by Chris Stuetzle.
  3. ZKM presented by Eric Ameres.
6 Mon Feb 4
  1. Intel's Visual Computing Group asked me to recommend Software Graphics Engineers with at least a Masters degree. Interested? This lead came from a former student who is now at Intel.
  2. Next student presentation set: you pick a new tech or idea, such as Ajax, and a date.
  3. interactive study of the data structures and algorithms embedded in a handheld GPS unit. E.g., the road network is probably stored in vector form, and the elevations as a compressed scalar field from which the contour lines are derived with marching cubes. Path planning uses graph theory including heuristics, like try the interstates first, to handle such a big graph.
  4. IBM presented by Jon Muckell.
  5. Microsoft Research, Reconstruction of 3d surfaces presented by Dan Hathaway.
7 Thu Feb 7
  1. I'd like to schedule makeup classes. Could you please put your schedules into google calendar and permit them readable to wrfranklin@gmail.com . I'll use them to suggest times.
  2. What I'll be doing next Thurs. The NSF Cyber-Enabled Discovery (CDI) program intends to use money to make people in different areas to work together on important problems. The program was announced with workshops around the country, including at RPI and here. (I wasn't asked to speak at the RPI one, but was paid expenses to go speak at that one at NSF.)
  3. more CGAL.
    1. Dan Halperin's CGAL tutorial.
    2. Demos: Voronoi_2, Min_circle_2, Partition_2, Straight_skeleton_2, Alpha_shape_2
  4. Start homework 2, due Feb 18.
  5. Start several lectures on graphics HW, based initially on Foley et al, 2nd edition in C, chapter 18.
  6. Raindrop Geomagic presented by Chris Stuetzle.
Mon Feb 11

no class

  1. Waterloo presented by Eric Ameres.
  2. Santa Cruz presented by Dan Tracy.
Thu Feb 14
  1. No class - prof at NSF panelizing
8 Tues Feb 19
  1. MIT, Automatic rigging and animation of 3d characters presented by Dan Hathaway.
  2. U Washington presented by Daniel Wojcik.
  3. I would still like to hold a faculty-student lunch at a time convenient to you. Would 2/20, 2/25, 3/3 or 3/6 work?
  4. Features in OpenGL not well covered last fall, using example programs in http://www.opengl.org/resources/code/samples/redbook/ local copy with some linux executables
    1. fog - compare fog modes
    2. alpha - show effect of order of blending
    3. accanti - antialiasing by jittering into accumulation buffer
    4. bezcurve - using evaluators to draw a Bezier curve
    5. bezmesh - using evaluators to draw a Bezier surface
    6. checker - texture mapping
  5. Gfiles:GLSLOverview2005.pdf
9 Thu Feb 21
  1. Utah presented by Daniel Wojcik.
  2. Caltech presented by Dan Tracy.
  3. OpenGL examples from the OpenGL SuperBible - under $40 at Amazon
    1. chapt17
      1. bumpmap using shaders
      2. lighting
      3. imageproc
      4. fragmentshaders
      5. proctex
    2. chapt18
10 Mon Feb 25
  1. Stanford presented by Jon Muckell.
  2. Georgia Tech presented by Zach Barth.
  3. Example: TOPO Adirondacks SW.
  4. OpenGL Shading Language Tutorials
  5. Wikipedia:
    1. http://en.wikipedia.org/wiki/Shader
11 Thu Feb 28
  1. lab presented by Zach Barth.
  2. Homework 3 available
  3. General purpose computing with a GPG.
    1. Wikipedia on General-purpose computing on graphics processing units
    2. http://www.gpgpu.org/
    3. gpgpu.org Wiki
    4. SIGGRAPH 2005 GPGPU course
12 Fri Feb 29


DREAMWORKS ANIMATION COMPANY OVERVIEW with Marilyn Friedman, Head of Outreach

Friday, February 29th, 2008  4:00 - 5:00 PM, Sage 3303

This presentation will give an overview of how movies are made at DreamWorks Animation and the skills and experiences necessary to work in the CG Animation field.  Marilyn will show clips from some upcoming films, explain the DreamWorks Animation production workflow and talk about how to present yourself in your resumes and demo reels to grab the attention of employers.  She will also be showing examples of successful demo reels so you can see what will land you a job in the CG Animation, Visual Effects and Gaming industry.

The presentation is open to all students. DreamWorks Animation is particularly interested in meeting EMAC, EART, CSCI, ARCH &  PDI/DIS students.  While they have a limited number of interview slots for this visit, they will take submissions of resumes and reels from any students interested in employment or internships back with them.  Please come by for this exciting event!

For more information about DreamWorks Animation SKG, please visit http://www.dreamworksanimation.com

13 Mon Mar 3
  1. Continue with the SIGGRAPH course on GPGPUs
  2. Start thinking about your term projects.
14 Thu Mar 6
  1. Homework 3 due
  2. Start several lectures on CAD - splines, patches.
    1. one ref is Angel, chapter 11.
    2. another is by an author I usually agree with: bezier.pdf
    3. Mathematica has some good spline demos, playable with free MathematicaPlayer
      1. http://demonstrations.wolfram.com/RungesPhenomenon/ This shows how counterintuitive curvefitting can be. When finding a polynomial approx to this curve, the more equally-spaced points you add, the WORSE the max error is!
  3. Continue to start thinking about your term projects.
15 Mon Mar 17
  1. Special lecture by Dongarra on advances in parallel computation.
  2. Hand in a title, team, and paragraph on your proposed term project.
16 Thu Mar 20

See my notes at Splines.

17 Mon Mar 24

Continue with CAD splines and patches.

18 Thu Mar 27

Class replaced by Yahoo talk.

19 Mon Mar 31

CAD concluded

20 Thu Apr 3

Class replaced by John Hopcroft talk on future of CS

21 Mon Apr 7

Start GIS.

  1. GIS: The acronym GIS has two meanings. Originally it meant Geographic Information Systems. A few years ago, it was retargeted to mean Geographic Information Science. I don't know all the implications. However, the intent apparently was to distinguish between the commercial products and the academic research.
    I'll cover both meanings superficially. I'll do the computer aspects of the subject. The term geography covers primarily social sciences; see the NSF program on it. When I helped create the Computational Algorithms and Representations for Geometric Objects (CARGO) solicitation at NSF, http://www.nsf.gov/publications/pub_summ.jsp?ods_key=nsf01111 , I never used the word geography, but rather said computational cartography. I wanted to cover only computer issues.
  2. Definition: Wikipedia's Geographic information system article is reasonable.
  3. SW:
    1. Environmental Systems Research Institute, Inc. (ESRI)'s ArcGIS http://esri.com/ is the standard commercial product. They sell everything from courses, course materials, books, SW, to finished maps.
      The name ArcGIS comprises a family of products with time-varying names, like ArcView, ArcInfo, etc.
      Every university with a geography or cartography program has an ArcGIS license.
      The best way to learn ArcGIS is to buy ESRI's intro book for $35, which includes a CD with 6-month license.
    2. There are also niche commercial products.
    3. GRASS is the best known free product. See http://grass.osgeo.org/ .
      A 1-page intro to the topic is here: http://grass.osgeo.org/intro/general.php
  4. Conferences
    1. Symposium on Spatial Data Handling
    2. Autocarto
    3. ACM-GIS
  5. Journals
    1. IJGIS
    2. etc
  6. Topic summary for the field, from the National Center for Cartographic Information and Analysis, http://www.ncgia.ucsb.edu/giscc/
  7. Current government-funded research
    1. NSF funds largely social science work
    2. DARPA Geo* program
  8. Some scientific points and questions
    1. GIS draws on Computer Graphics and Computational Geometry
    2. vector vs raster
    3. gravity potential
    4. compressing data
22 Thu Apr 10

Continue GIS with a big computing example - finding the areas of the nonempty polygons of two overlaid planar graphs.

Details: Overlaying Two Maps.

23 Mon Apr 14

Ctd. See also geo_ops_millions-jul2004/.

No Date Summary
24 Thu Apr 17
  1. Student presentation:
    1. Chris Stuetzle
  2. Sweep-line edge intersection algorithm. Finds all K intersections of N edges in time {$T=\theta((N+K)\log N)$} Ref: Shamos and Preparata and many other places. Comments on the algorithm:
    1. This shows the sweep line idea.
    2. This uses priority queue sorted by X and a balanced binary tree of the active edges, sorted by Y.
    3. The keys for the tree are not stored explicitly, since they change, but are computed as needed.
    Comments on the time:
    1. If {$K=N^2$}, the naive algorithm, with {$T=\theta(N^2)$} is faster than this with {$T=\theta(N^2\log N)$}
    2. The uniform grid, with expected {$T=\theta(N+K)$} is faster for reasonable input, but has worse worst case time, {$T_{max}=\theta(N^2)$} even in {$K=0$}.
    3. However, the uniform grid can do the red-blue case fast, which the sweep-line algorithm cannot. That is, given red edges and blue edges, to find all the red-blue intersections when those are few, but there are many red-red and blue-blue intersections.
25 Mon Apr 21

Prof at NSF panelizing for 2 days.

26 Thu Apr 24

Student presentations:

  1. Dan Wojcik
  2. Zach Barth
  3. Jon Muckell
27 Mon Apr 28

Student presentations:

  1. Dan Hathaway
  2. Eric Ameres
  3. Dan Tracy

(:showhide init=show div=hw lshow='Show homeworks' lhide='Hide homeworks' :)


Homework 3 - due Thurs Mar 6

  1. Install and try some of the vertex and fragment shaders showed in class.
  2. Create a new vertex shader that perturbs vertex positions and normals in a wavy fashion.
    Map your initials in the waves made in a formerly regular grid of vertices.
  3. Create a new fragment shader to do bump mapping to fragment normals.
    Map your initials in the bumps.
  4. Email or hand in some sample output.

Homework 2 - due Mon Feb 18

  1. Install CGAL on your favorite system.
  2. Find or write a program that reads a list of 2D points and computes the 2D Voronoi diagram. Measure its execution time on input sets with 10, 100, 1000, 10000, 100000 random points. Graph the execution time. Include sample output plots of the Voronoi diagrams for each size.
  3. What is a Nef polyhedron (in the context of CGAL)?

Homework 1 - due Jan 24

In this exercise, you need to generate a few pictures with increasing complexity using POV-Ray. We will, in particular, look at how to input a mesh into the scene, and how to improve the rendering of meshes. We use a simplified version of a famous model - Stanford bunny - with 880 triangles.

Helpful links

  1. POV-Ray Tutorial.pdf
  2. POV-Ray
  3. POV-Ray documentation


  1. We start with an empty scene.
    1. Template file: start.pov. Download, read, and render it.
    2. Some details about Camera setup.
    3. Some details about Light source.
    4. Plane: replace the floor with checker board.
    5. Try the different colors specified in colors.inc (list of colors). Notice the first line the beginning of start.pov.
  2. We next add a sphere and a cone to the scene.
    1. Put the center of the sphere at (x,y,z)=(-2, 0, 0), and radius=1.
    2. Put one end of the cone at the center (x,y,z)=(2, -1, 0), and with radius=1. Put the other end of the cone at the center (x,y,z)=(2, 1, 0), and with radius=1.
    3. Notice that you only see half the sphere. Try modifying the plane to see the entire sphere and cone.
    4. Adjust your camera so that your output and the relative positions of sphere and cone are as follows:
    5. Is the image too dark? Try adding another light source.
    6. Try out some highlights and glass effects.
  3. We add a simple cube using mesh between the sphere and the cone.
    1. Put the content of cube_triangle into your .pov file.
    2. Read the code and understand how the cube is constructed out of triangles.
    3. Render your image, you should get something similar to:
  4. Replace the cube mesh with the Stanford bunny.
    1. Replace the triangles with the content of bunny_1.
    2. Render the image and notice the flat surface.
    3. Again replace the triangles with the content of bunny_2.
    4. Render the image and compare the result with the previous one. Explain why.
    5. Experiment with texture mapping with simple and advanced options.
  5. Hand in or email some screen dumps showing that you got it to work.

(:showhide div=hw lshow='Show homeworks' lhide='Hide homeworks' :)

(:showhide div=topics init=show lshow='Show Possible student presentation topics' lhide='Hide Possible student presentation topics':)

Possible student presentation topics

Research labs

  1. Brown University - Computer Graphics Group (available)
  2. U North Carolina - Graphics and Image Analysis Research (available)
  3. Duke - Visualization Technology Group (available)
  4. U Texas/Austin - Graphics Lab, Department of the Computer Sciences (available)
  5. U Washington - Computer Graphics, Computer Vision and Animation (available)
  6. Microsoft - Research - Graphics (available)
  7. IBM Research - Graphics & Visualization (available)
  8. Caltech - Computer Graphics and Multi-Res Modeling. (Al Barr is an RPI alum.) (available)
  9. U Waterloo - Computer Graphics Lab (available)
  10. Georgia Tech - Graphics, Visualization & Usability Center, including Animation Lab (available)
  11. Ohio State - Computer Graphics Research, Computer Animation, Geometric Modeling, & Volume Visualization (available)
  12. ICASE - Visualization and Graphics. This lab has closed, but it's still interesting. (available)
  13. Stanford - Computer Graphics Lab (available)
  14. UC Berkeley - Multimedia, Human Computer Interaction and Computer Graphics (available)
  15. UC Santa Cruz - Lab for Visualization and Graphics (available)
  16. U Utah - Computer Graphics (available)
  17. U Geneva - MIRAlab (available)
  18. MIT (available)
  19. Pixar (available)
  20. Raindrop Geomagic (available)
  21. Princeton (available)
  22. Any other interesting place - you pick. (available)

Misc presentable ideas

  1. PenroseTilings
  2. StereoGraphs
  3. AlumniPatents
  4. MayaSW
  5. Z-Corp
  6. Augmented Reality Gaming

(:showhide div=topics lshow='Show Possible student presentation topics' lhide='Hide Possible student presentation topics':)

Computational Geometry

  1. Implementing geometry is totally different from doing it on paper and proving theorems. Ex: convex hull.
  2. 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 will do some of it.
  3. Mathworld on Computational Geometry