CS3451: Computer Graphics Course at Georgia Tech

Instructor: Jarek Rossignac, email. Office hour: Tuesdays and Thursdays 12:30pm to 1:25pm in CCB commons.
TAs: Office hours: Scott McManus: 2-3 MWF CCB Commons, Jesse Swidler: 12-1 MWF Study Area outside Klaus 3303, David Zimmermann: 10:30 - 11:30 CCB Commons

Henry Dooley, email Stephen Pettett, email Jesse Swidler, email David Zimmermann, email Scott McManus, email

Course overview slides.

The course material is posted on the syllabus page, which describes the 15 modules that make up this course and provides links to accompanying slides, reading assignments, and demo applets. Students are responsible for learning all the material that was either covered in class, or on the posted slides, or in the required reading papers and handouts that are posted on the sylabus page. They are also responsible for understanding the implementation of the example applets provided.

Grading: First midterm=15%, quizzes=10%, second midterm=25%, projects=50% (These modified weights reflect the agreement reached in class on October 20, 2009.)
Extra-credit points will be awarded for outstanding projects. There will be no final exam.




Projects are due on the due date before class on T-square uner the corresponding rubrique (project x). Please enter the name of the student, the name of the partners if this is a group project, the link to the web page containing the project (Project number and title, authors' names, report in PDF, interactive applet, zip file with the applet, the source code, the data). Students who plan to use a different language for programing the applet should contact the TA in advance. Students must ensure that their interactive applet runs on a web browser over the Internet, in particular, they must remember to copy the data folder with images, fonts, and models to their applet folder. Note that fonts posted with the starting applets were created on a mac and may not work on other machines. Late submission of projects or missing documentation will result in severe penalty. Copying even parts of a project from another student is strictly forbidden. Publicly available resources may be used, but must be clearly acknowledged and the links provided.

Project 1: Due Thursday September 2 at noon.

  1. Download, decompress, run and study the code provided. Modify it so that your name and face appear on the canvas. Export and try to post the web page to make sure that you are able to do it. (Do not forget to upload the data folder.)
  2. Find the solution to the shortest path joining 3 points problem, modify the code to replace my solution with yours, test it, fix it. Export it into a web applet. Your solution should work for all triangles (clockwise, counter clockwise, skinny, or fat), hence yor code may need to distinguish several cases.
  3. Edit the web page created by Processing as exlpained below.
  4. Post the web page online and verify that it works in the common browsers.
  5. Enter the URL of your project web page in T-square under Project 1

Your web page should contain the following:

For extra credit, include a short and easy to understand justification or proof that your approach works (provide a reference to prior art that contains the inspiration for your short proof) Further extra credit: extensions to more than 3 points. Further theoretic considerations on this constructions. Please clearly describe on the web page what extra credit you did. It may be a good idea to include a separate web page or a separate applet for the extra credit part.

Project 2:


Use the code provided.

1) Replace my name and picture with yours

2) Write a nice filterMouse function that moves a point to follow the mouse but smoothly, with a delay and possibly with inertia. One way is to return a weighted average of the mouse positions during the last 30 frames. Another way is to treat the ball BB[0] as a dynamic object on a spring pulled by the mouse (you may need friction)

3) Change the aim function so that it computes the velocity V of the ball so that it hits the target in 2 seconds assuming constant aceleration G. Use integration of C(t)"=G to derive C'(t) and C(t) as a quadratic function of time so that C(0)=starting corner and C(2)=target Set the velocity V to be C'(0)

4) Change the move method of ball so that it updates the velocity and position to perfectly track the free-fall parabolic motion. Use the full Taylor series expansion of the motion to compute the position C(t+1/30) from C(t) and derivatives

5) Change the predict function to predict where your face will be in 2 seconds. You need a filter to ensure that this prediction is not jumpy. You should do better than the linear prediction I have provided. Take the acceleration into account. For example, if the player moves the face in a cirlce, your prediction should not be too far from the actual future position.

6) Change processcollisions so that you detect collisions between your face and other balls. Update the collision count. Make sure that you do not double count these collisions.

7) Turn this into a nice game

8) Produce a web site with course and project title, your name, your face picture, an interactive applet for your game, instructions on how to play, descriptions (short code snippets or pseudocode for the implementation of the above functions), a description of the extra credit you have done, a link to a zip file with your entire project folder.


a) Implement a bounce-off that changes the "normal components of the velocities) when two balls collide. Check my Sumo game for more details.

b) Explosion when the face ball is hit

c) Additional effects (including sound when there are collisions)

Previous year projects

Assignments and exams schedule
Assignment P1 was due Sept 1 before class: Study the class notes on Processing, Geometry, and Curves. Implement the applet as described in the cyan highlighted sections of Curves. Start with the applet P1. Modify the place-holder (incorrect) implementations marked with "***" in the "action" and "UI" tabs. Make sure that you replace my picture with one of you showing your face clearly in the help pane. When correct, your applet should produce images like the one below. Do not change the GUI.

We will have one more quizz. We will not count your weakest quiz. Your best twoquizz grades will count for 5% each. The next quiz will cover:
- perspective transformations
- arrangement of tangent balls
- light refletions off a Lambertian surface

The second midterm will be on Nov 19. Closed books, no computers or notes of any kind, except for one single-sided sheet of notes that you may bring. It will cover everything we studied until then, including the projects. In particular, it will cover slides from sections 09, 10, and 12.

If you have a conflict with that date (Nov 19), please let the instructor and TA know before Nov 19. (We can make a special arrangement for you to take a final on December 11 from 11:30 to 2:30.
This final will cover all material studied during the semester. It will be closed books. You will be allowed one single-sided cheat sheet as well.)

Project P3 has 3 phases with deliverables and deadlines for each phase and has a fourth phase (animation) for extra credit. The complete project submission will be accepted until November 24. Project description: PDF. If you find the project too ambitious, you may attempt to produce a 2D version for partial credit.

Project presentations will be scheduled on December 1 (if a sufficient number of students wish to present) and on December 3. Please notify the TA before Nov 24 if you wish to present your project. If your final numeric grade puts you at the very top of the B group, an excellent presentation could help you pass the bar to an A grade.

See video demo of Jesse Swidler's project

Past exams:
  • Quiz Q01 (10 points): solution
  • Quiz Q02 (20 points): on Sept 9, solution
  • Quiz Q03 (20 points): on Sept 23, solution
  • Quiz Q04 (20 points): on Oct 16, solution
  • Midterm (150 points): on October 21, solution will be posted here after the exam. Examples of solutions from previous exams: Midterm 07, Midterm 06, Homework 1, Homework 2.

    01 - Graphic Systems
    What students need to know:
  • How the application communicates with the graphics subsystem (API, states changes, rendering commands, interrupts)
  • How to write a simple Processing program that lets the user drag a disk on the screen with the mouse and change its color by pressing keys
  • How to write a simple program that animates the continuous rotation of an ellipse
  • Processing syntax for variable declarations, arrays, block structure, conditionals, loops, logical expressions, functions
  • The use of recursion and stack manipulation for creating 3D scenes, as illustrated in the pyramid function of the inspect applet
  • Printing in the text window and rendering text in the loaded font in the graphics window
  • How to load an image and use it as a texture on a rectangle
  • List of input and output devices and modalities, their capabilities and applications
  • Four strategies for the interactive control of a camera
  • Examples of approaches for human-shape interaction

    02 - Geometry
    What students need to know:
  • The differences between points and vectors: what they represent, allowed operators, effects of transformations
  • Conversions between polar and Caresian coordinates
  • Effect, implementaiton, and applications of operators on points and vectors: n(), a(), D(), R(), A(), Left()...
  • The two formulations of the dot product, its three properties, and its uses for testing and expresing constraints
  • How to test whether two vectors are paralel or orthogonal using vector operators and also using coordinates
  • Tangent and normal components of a vector with respect to a direction and the derivation of the formula for the reflection vector
  • Definition and construction of an orthonormal basis and of a coordinate system (frame)
  • Formulae for changing coordinate systems
  • Rigid transformations, their canonical representation
  • Transformation of points and vectors by a homogeneous matrix
  • Use of rotate, translate, and scale graphic commands to achieve desired results in 2D
  • Use of matrix push and pop commands for rendering hierarchical models
  • Extraction of the rotation angle from a rigid 2D transformation
  • How to rotate a portion of the scene around a fixed point
  • Parametric form of a ray and of an edge
  • Implicit form of a line and of a half-space
  • Computing the closest point to P on Edge(A,B)
  • Edge/edge intersection test and the derivation of the formula for edge/edge intersection calculation
  • Definition of a triangle
  • Tests whether a triangle is clockwise and whether it contains a given point
  • Implicit equation and parametric form of a circle
  • Tests whether two circles, or two disks, intersect
  • Intuitive understanding, computation, and uses of the cross product for testing parallelism
  • Computation of the normal of a triangle
  • Computation of point-to-plane distance in 3D
  • Computation of line/plane intersection
  • Formula and intuition behind the mixed product
  • Use of the mixed prodct for testing whether a triangle is front-facing

    03 - Topology
    What students need to know:
  • Why we study topology here
  • Symbols, notation, and definitions for operations on points and pointsets (union, complement, xor, containment, empty, set definition, quantifiers...)
  • deMorgan laws
  • Intuitive understanding of the concept of neighborhoods and its use for defining the boundary, interior, exterior and for testing whether a set is open or closed
  • Definition of interior, boundary, exterior, closure, regularization
  • Definition of a connected set, of a simply connected set, and of the components of a set
  • The difference between a hole and a handle in a 3D shape and the concept of the genus
  • Manifold and non-manifold points and sets
  • Definition of a polygon and of a simple polygon
  • Representation of a simple polygon by a polyloop

    04 - Arrangements
    What students need to know:
  • Two algorithms for testing whether a point is inside a polygon (shoot ray, XOR of containment in triangles)
  • XOR fill of a polygon (algorithm and why it works)
  • Definition of a convex set and of a convex hull and proof that a stringing is not necessarily a convex hull
  • How to compute the orientation of a polyloop and identify concave vertices
  • Why decimating concave vertices does not necessarily produce a convex hull
  • How to interpret point clouds to produce polygons and dangling edges
  • Algorithm for computing the best place to live (furthest away from nuclear plants)
  • Definition and computation of a Delaunay triangle
  • General position assumptions
  • Naive algorithm for computing a Delaunay triangulation and its asymptotic complexity
  • Definition of a Voronoi region anexamples of practical applications
  • Formula for counting the cells in a planar arrangement of lines
  • Cost of specifying regions by enumerating cells
  • BSP tree representation of regions, its construction, and its use for point-classification
  • Use of BSP for back-to-fron ordering of edge in 2D or faces in 3D
  • CSG representation of regions, its construction, and its use for point-classification
  • CSG with 3D primitives, rigid transforms, and scaling
  • Non uniqueness of BSP and CSG
  • Definition of a redundant primitive in CSG
  • Positive form of a CSG and algorithm for obtaining it

    05 - Curves
    What students need to know:
  • How to evaluate a point on a Bezier curve for a given parameter value
  • How to draw a Bezier curve
  • How to animate a frame on a Bezier curve
  • How to compute the arc-length of a polyloop
  • How to uniformely resample a polyloop and its application to animation
  • How to compute the area of a simple polygon from its enclosing polyloop
  • Difference between smoothing and subdivision and which one is needed when
  • Formulae enad their justification for the velocity, normal, acceleration, and jerk at an element of a polyloop
  • Implementation and limitations of smoothing by successive tucks and their expression in terms of duals
  • Tuck-tuck smoothing
  • Implementation of quadratic and cubic B-spline smoothing using combinations of refine and dual
  • Local control of B-spline curves
  • Four-point subdivision rule and its advantages/drawbacks over cubic B-spline
  • Drawing by hand the cubic B-spline and the Four-point of a simple polyloop

    06 - Animation
    What students need to know:
  • List several types of animations and give examples of applications
  • Overall strategy and geometric details for simulating a walking bug in 3D
  • How to compute and animate a circular motion that interpolates between two frames in 2D
  • How the circular motion differs from a linear position and angle interpolation, and what are its advantages
  • Split and tweak smothing of piecewise circular motions in 2D
  • Computing a spiral motion that interpolates two edges and applying it to animation design
  • How to detect interference/contact between disks and between polygons
  • Explain how to use static interference tests for collision and why it may not work
  • Derive the formula for computing the collision time for disks with constant velocity
  • Formulae for computing the position of the disks at collision and their subsequent velocities (elastic shock, equal radii and masses)
  • Algorithm for detecting the interference between two polygons in 2D
  • Difference between morphing and deformation
  • Formulaiton of the Minkowski morph and its implementation for convex polyloops in 2D
  • Definition and construction of the tangent ball morph in 2D between compatible shapes

    07 - Morphology
    What students need to know:
  • Difference between distance and discrepancy between shapes (including the love soty metaphor) and examples of their applications
  • Formulae and algorithms for computing the minimum distance and Hausdorff discrepancy between two point-clouds
  • Use of smapling for approximating these measures for continnuous shapes
  • Definition and other terms for of dilation, contraction, and tolerance zone
  • Formulation of minimum distance and maximum discrepancy in terms of dilations
  • Limitations of the Hausdorff discrepancy and examples where it underestimates the disparity between shapes
  • The definition and advantages of the Frechet distance
  • The definition and advantages of the ball distance
  • The definition of the cut locus of a 2D shape and the medial axis
  • The medial axis transform and its use for defining the local and minimum feature size
  • Distance transform inside a polygon
  • Definitions of rounding and fileting of shapes by growing and shrinking

    08 - Triangulation
    What students need to know:
  • How to represente a triangle mesh using geometry and incidence
  • How to compute and store a consistent triangle representation
  • The difference between incidence and adjacency
  • Corner Table representation
  • Corner operators and their implementation
  • Naive algorithm for computing the O table
  • How to construct a triangle mesh for a regular grid
  • Recursive algorithm for visiting all triangles of a shell and its use for identifying and orienting shells
  • Algorithm for identifying which vertices are used by a shell
  • Algorithm and geometric construction for estimating the normal at a vertex
  • Formula and algorithm for computing the genus of a manifold shell
  • Algorithm for point-in-solid test and its justification
  • How to test whether an edge is concave
  • Algorithm for computing the border loops of a mesh
  • Algorithm for computing the exact volume of a solid using the mixed product

    09 - Mesh processing
    What students need to know:
  • Overall strategy for computing the distance between a point and a triangle mesh
  • Algorithm for flipping an edge and why ysing it for smoothing does not work
  • Algorithm for collapsing an edge
  • Algorithm for finding the shortest edge
  • Algorithm for detecting the intersection between two triangle meshes
  • Definition of geodesic distance and path
  • Algorithms and geometric constructions for tracing a geodesic path along a curve
  • Computation of geodesic graph distance and its applications to the isolation measure an to tip detection
  • Algorithm and details of geometric constructions for mesh smoothing

    10 - Light, perception
    What students need to know:
  • Why is it imortant to treat light both as a wave and as a particle
  • Sort colors according to their frequency
  • Definition and example of white light
  • Motivate and explain the gamma correction
  • Explain what the letters mean in HLS
  • Explain the tristimulus theory
  • How many fully saturated hues can an average human distinguish
  • Compare the human sensitivity to green and to blue
  • Explain what the Y, X, and Z coefficient of the CIE measure
  • Explain how to form yellow, magenta, and cyan using additive RGB
  • Explain why reflected colors should be computed using composition of subtractive colors and not additive colors
  • Define radience and explain how knowing it everywhere may be used to render the scene from any angle
  • What happens to light as it hits a surface separating two materials
  • Formula for computing the mirror reflection of an incoming ray
  • Spacify the properties of a Lambertian surface and give examples
  • Specify properties of a specular surface and give examples
  • Provide the light reflection equation, explain and justify each term
  • Identify the iris, lense, and retina in the human eye
  • Describe what the back layer of the retina is composed of and what is its function
  • What is the feovial region
  • How many rods and cones does a human have (roughly)
  • How are rods distributed and what are they good for
  • How are cones distributed and what are they good for
  • What is the average human acquity, how is it measured, what does it meean in practice
  • What horizontal resolution panoramic screen is needed to saturate human acquity

    11 - Photorealism and NPR
    What students need to know:
  • Explain how to set up the virtual screen and viewpoint so that the image look correct to the viewer
  • Explain how to generate models of the rays for each pixel on the graphics window
  • Provide the overall algorithm for ray-casting
  • What is the difference between ray-tracing and ray-casting and why does it matter
  • Explain how to perform hidden-surface removal in ray-casting
  • Explain how to compute the light reflected by an illuminated visible surface
  • Provide the algorithm for correctly rendering shadows
  • Explain why ray-casting plus shadow feelers does not produce correct images
  • Define NPR and list some of its objectives
  • List 3 attributes for edge segments and indicates how they may be used to enhance shading
  • Provide an algorithm for finding the silhouette edges
  • What is the difference between photorealistic rendering and visualization

    12 - Graphics pipeline
    What students need to know:
  • Provide the high level scan conversion algorithm
  • Compare scan-conversion and ray-casting algorithms and discuss their similarities/differences List the steps of the graphics pipeline and explain what each one does
  • What is the viewing frustum and why do geometric primmitives need to be clipped against it
  • What is the role of perspective projection
  • Define triangle rasterization and provide a simple but slow algorithm for it
  • Provide a high-level algorithm for rasterizing an edge and explain which pixels will be turned on and why
  • Explain how hidden surfaces are removed during rasterization
  • Explain and justify double buffering
  • What is the shape of the projection of the moon on your window and why
  • How to draw a correct perspective projection of a box
  • What are vanishing points and how many are there
  • What is the equation of perspective projection and how was it derived
  • Why is the perspective projection of a triangle a (possibly degenerate) triangle
  • Why can't we use perspective projection for 3D rendering
  • What is the equation of perspective transform
  • Explain z-contention and what may be attempted to reduce its effects
  • How to draw the shadow of an synthetic vertical pole in an image of 2 real ones

    13 - Image-based rendering
    What students need to know:
  • What is texture mapping and why is it so popular
  • List and explain the steps that a developer must go through to use texture mapping
  • Discuss different strategies for texture creation
  • Give examples when texture coordinates can be assigned algorithmically
  • Discuss several ways of combining texture colors and shading colors
  • Define the term billboard and explain when it is useful
  • Explain Phong shading and compare it to Gouraud shading
  • Explain bumpmapping and suggest good applications. Discuss its limitations.

    14 - Acceleration techniques
    What students need to know:
  • List two categories of costs of rendering with a graphics pipeline and suggest experiments identifying which one is the bottleneck
  • list five performance acceleration techniques and explain what type of cost it addresses and how much speed up may be hoped for
  • Suggest a test for establishing whether a projected triangle is front facing
  • Why does the use of short triangle strips improve performance
  • Why may very long triangle strips not improve performance on contemporary GPUs
  • Suggest strategies or quick frustum culling
  • Provide an algorithm for using vertex clusters for mesh simplification and discuss its advantages
  • Define conservative occlusion testing and explain how it can be used to accelerate rendering

    15 - GPU shaders and advanced effects
    What students need to know:
  • List the different stges of the GPU and expain the role of each module
  • What are shaders and what functionality they offer that was not available in old generation graphic adapters
  • What is translucency good for
  • Why are floor shadows important and how can they be easily rendered
  • Why are floor shadows insufficient
  • Explain the shadow map approch and its limitations
  • Explain why soft shadows are desired and suggest a simple implementation that approximates them
  • List several realistic visualization effects that can be programed efficiently on the GPU

    Projects given in 2008

    Search this site    or the Web