CS6491: Computer Graphics Course at Georgia Tech
Instructor: Jarek Rossignac, email. Office hour: Tuesdays and Thursdays 12:30 pm to 1:25 pm in CCB commons.
TA: TBD Office hours: TBD
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 the material covered in the slides and 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.
The grade will be based on two midterms (20% each) and on 3 projects (20% each).
Projects: Projects are due before class via email with subject "6491 Px" where "x" is the project number (for example "01").
The email should contain 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 (with: project number and title, authors' names, report in PDF, interactive applet, zip file with the applet, the source code, the data).
Project 1: Due as a web page with a running applet on Sept 8 before class (details to be discussed in class)
I suggest that you implement it in Processing or Java, so that you have an applet that you can post.
The problem is to produce a constrained Delaunay triangulation of a 2D polygonal region ("loop") that the designer may edit.
You may start from scratch or from the following simple source code, for editing a curve. However, you may be better off by starting from a more elaborate program (zip) that I have written, which computes the Delaunay triangulations of the vertices (the O(n^4) algorithm you invented in class) and constructs a Corner Table representation of it ("mesh"). I also classify the triangles (cyan/yellow) by testing whether their center lies inside (the polygonal region bounded by) the loop.
Your job is to find all the intersections between the edges of the loop and the edges of the mesh and to subdivide both the loop and the mesh so that they are compatible (no edge of the mesh crosses an edge of the loop). Try to produce a simple and elegant code for doing this refinement. Then, modify the process by creating a hexagonal grid (or a random cloud) of points inside the loop and adding them as mesh vertices.
You may explore a different approach if you find a simpler one.
Finally, for extra credit, try to produce an implementation that has lower assymptotic worst case complexity or that at least in practice performs much faster as the number of vertices in the loop or inside it grow.
Your web page should contain:
- The header:
"CS6491--Fall 2010 -- Rossignac"
"Project 1: Triangulation"
"by First LAST NAME"
- A photo (headshot) of you which will help meremember your name and face
- A short problem statement
- An overview of your solution (major steps) and some explanations on how you handled non trivial details
- An argument convincing me that your algorithm is correct (if one ignores singular cases)
- A description of the limitations and additional features or speed up for extra credit
Please email me the URL and also bring a print-outof that web page to class.
Previous year assignments and exams schedule
Assignment P1 is due Sept 1 before class: Study the class notes on Processing, Geometry, and Curves.
Implement the applet highlighted in cyan in Curves.
Write PDF report with solutions to questions highlighted in grey in 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.
Assignment P2 is due Sept 24 before class: Implement a robust point-in-polygon algorithm in the applet provided. Produce a video (up to 5 mns, convenient fomrat for fast downloading). explaining (1) the definitino of a polygon, (2) three different representations, (3) three algorithms for point-in-polygon, and (4) the details of the one you have implemented. Post the applet and the video along wiht the appropriate header, team members names and photos. (Teams of 2 or 1 students only).
Assignment P3 (individual) Phase 1 is due October 27 before class. Phase 2 is due November 17 before class (no extension).
Project description: PDF.
Events and exams:
Midterm: TBD
Final: November
24 in class. You may bring up to two single-sided pages of notes.
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
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
Definitions of linear, affine, and convex combinations
Rapid implementation of a rotation transform
Composition of transformations via matrix multiplication
Inverse of a rigid transformation
Use of rotate, translate, and scale graphic commands to achieve desired results in 3D
Use of recursion with the matrix stack for rendering trees
Formula for the area and center of a triangle
Computation and use of Barycentric coordinates
Computation of edge/triangle intersection and aproaches for dealing with loss of numeric accuracy
Derivation of the formula for line/triangle intersection in 3D
Algorithm for testing whether an edge intersects a triangle
Computation of the distance between an edge and a point in 3D
Algorithm for testing whether a ray hits a triangle
Algorithm for testing whether a given point is contained in a tetrahedron
Computation of the intersection of three planes
Derivation of a frame from the viewpoint, the target, and the up-vector
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
Computing the area of a polygon
Decomposition of the boundary into skin, hair, wound, and cut and their definitions
Decomposition of the boundary of a polygon into edges, vertices, and crossings
Circuits of a polygon and their computation from an edge soup
Definitino of a face and why it is important to distinguish faces from polygons
When is the set of edges the boundary of a polygon
Algorithm for identifying the faces defined by an arrangement of edge (split, loops, containment tree)
Algorithm for regularizing a face
Definition of a Selective Geometric Complex and topological, Boolean, and simplification operations on it
Algorithms for computing a regularized Boolean comination of polygons
Winding number of a polyloop and its applications for orientation and trimming self-intersecting polyloops
How to represent a polygon by a self-intersecting polyloop and how to compute its boundary
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
Examples of representations for polygons (boundary, triangulation, CSG, XOR)
Strategies for dealing with singular cases
How to fix the concave vertex decimation algoithm so that it computes the convex hull
What is the complexity of that algorithm and how it compares to the complexity of computing the convex hull
Properties of Delaunay triangulations and their applications to closest pair computation
How to use the Delaunay triangulation to extract polygons and dangling edges from a point cloud
Properties of the Voronoi diagram
Insertion algorithm for Voronoi diagrams
Optimization and performance comparison between CSG and BSP
Conversion between BSP and CSG
I-zone, U-zone and Active Zone of a primitive in CSG
Their applications for rendering faces of CSG primitives
Converting a CSG expression to its Blist form and using the Blist form for piont classification
Peeling and Blister
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
Definition of the Hermite problem and of the two (point and tangent) end-condition interpolation
How to compute the control points of a Bezier span to solve the Hermite problem
Strategies for resampling a polyloop so as to have uniform edge length
How to compute the centroid of a simple polygon from its a polyloop
How to estimate the principal direction of a polygon
Smoothing via cubic fit and its relation to tuck-tuck
Where do original vertices converge to under cubic B-spline subdivision
Formula for splitting a control polygon of a cubic B-spline into polygons for equivalent cubic Bezier spans
Convex hull properties of B-spline and Bezier and their applications to intersection testing
Four-point subdivision formula and its derivation from a cubic fit
Split and Tweak subdivision: cubic B-spline, four point, jarek, and others
Strategy for subdividing open curves
Deciding which level of subdivision to use
Strategies for reducing popping effects when switching levels of subdivision
How to produce smooth animations and surfaces through curve subdivision
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
How to compute and animate a screw motion that interpolats between two frames in 3D
Split and tweak smothing of piecewise spiral motions in 3D
Formulation of the volume swept by a solid during a screw motion and classification of a point against that volume
High level formulation of a space warp based on a screw motion
Benefit of using relative screw motions for predicting collision between polyhedra and between balls
User interface design for editing 3D motions
Definition of quaternions and their relation to screw motions
Derivation of the formulae for simulating the elastic collisions between disks of different radii
Algorithm and geometric tests for point/triangle collision detection in 3D
Derivation of the collision time of two edges, each moving at constant velocity
Acceleration techniques for speeding up collision detection
Using swept volumes and 4D formulations for collision analysis
Overall algorithm, data structure, and implementation details of the Minkowski morph in 3D
Applications of the tangent-ball morph to the problem of slice interpolation
Application of the tangent-ball morph to the exageration of discrepancies
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
List of various complexity measures for shapes and scenes and their significance for applications
Computation of the exact distance between two polygons
Computation of the exact Hausdorff discrepancy between two polygons
Analysis of the error bound when using sampling for computing minimum distance and Hausdorff discrepancy
Algorithm and formulae for computing point/triangle distance in 3D
Algorithm for computing point/mesh distance in 3D and its applications for point/solid distance
Algorithm for computing the minimum distance between two triangle meshes
The difference between Hausdorff discrepancies of solids and of their boundaries
Definition and computation of the normal offset
Definition and computation of the bal offset
Definition of the r-mortar and of the r-tightening of a shape
Definition of relative roundingand its applications to design, shape analysis, and morphing
Ball transform inside a 2D region
Relation between Filleting, Mortar, and alpha shapes
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
How to organize a triangle soup into solids and shells
The outline and essence of a fast algorithm for computing the O table
Algoritm for a robust normal estimation based on tracing the intersection with a cylinder
Detecting non-orientable shells
Comparison of the corner table with other representations (for example vertex-star) in terms of storage and efficiency
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
Algorithms for identifying non-manifold edges and isolated non-manifold vertices in a mesh
Why collapsing the shortest edge does not yeild good simplifications
Better approaches for deciding which edge to collapse next (including the max and quadratic error estimators)
Algorithm for computing the distance between a point and a tiangle mesh
Algorithm for computing the minimum distance between two triangle meshes
Algorithm for compacting the Corner Table
Algorithm for finding and filling a holes
Challenges and strategies of shape segmentation
Definition and properties of hamiltonian cycle
Algorithm for mesh subdivision
Strategies for adaptive mesh subdivision
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
How does perceived light depend on the distance to a point source
Why is the light reflected by a Lambertian surface independent of the viewer's position
When can we assume that light is constant along a ray
Define the term BRDF and give examples of it for simple surfaces
Why is perceived intensity relative and what are the consequences on computer graphics
What is the Mach band effect and why is it important in graphics
Explain laterla inhibition and give an example of a simple optical illusion if causes
Explain the Herman grid illusion
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
Explain how to perform ray-casting on a CSG model
Explain how to augment the ray-casting plus shadow feelers approach to improve image quality
Discuss how to precisely trim silhouette edges to their visible part
Explain the challenges of rendering shapes with hatching during animation and view manipulation
Outline the essence of the approach for consistent hatching
Suggest a technique for showing the differnces between two similar and interfering surfaces
Explain the differences and overlaps between graphics and volume rendering
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
Describe a simple clipping algorithm for trimming a triangle against a viewing frustum
Why is scanconversion more popular than ray-casting
Explain the stages and the essence of rasterization
Given the perspective image of a box, how to compute the proper eye position for looking at it
How to draw by hand (geometric construction with ruler) the image of a point by a perspective transform
Why do we have to use the perspective transform of z rather than z
How is the space behind the screen transformed by perspective transform and where do the vanishing points lie
How does the use of near and far clipping planes affect the depth accuracy
Derive the inverse of a perspective transform and explain applications
Prove that a perspective transform maps triangles to triangles
What is the homogeneous matrix form of perspective transformation
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.
Define mip-mapping and explain its purpose
Explain the perspective distortion of texture maps
Provide a software algorithm and geometric constructions for rendering textured shapes correctly
Explain environmental mapping, what it accomplishes, and suggest how it could b implemented
Define solid textures and suggest an application
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
Discuss the limitations of vertex clustering
Discuss mesh simplification by successive edge collapses
Explain strategies for estimating the error of an edge collapse and for selecting the next edge to be collapsed
Explain how to test whether a ball is occluded by a triangle and vice versa, and how these may be used to accelerate rendering
Explain the difference between from-point visibility and from-cell visibility
List several visibility techniques and discuss their advantages and drawbacks
Explain cell-to-cell visibility and how to test whether a triangle mesh occludes one cell from the other
What is occluder fusion, when is it necessary, and how can it be done
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
Give examples of fragment operations
What are stencil buffers and what are they used for
Explain shadow volumes and how they are used for rendering
Expain why it is possible to see curved shadow boundaries even though the occluders and light sources are linear
Discuss read/write limitations of fragment and vertex shaders
Define scattering and explain why it is important and how it may be implemented
2008 projects
- P01, due Tuesday August 26: Animation of student's photo and name. Suggested starting applet. Example of solution applet by Matt Weber (zip). Other fun examples from 3451.
In class, students are arranged into groups of 3, write the common specification for their second animation, and give the specification with their names to the instructor.
The rest of the projet is individual, even though students in a team can help each other get Processing to run/export, and to edit/post their personal project page (PPP).
Each student should edit the provided code to create two new animations using his/her name and picture.
The first animation should start when the program starts and each time SPACE is pressed. The picture should start as a small dot in the middle of the screen and grow while rotating around its center parallel to the screen. The name should rotate around its center in 3D. It should end in a configuration where the name and face of the student are clearly visible and centered on the screen, the name below the picture (as shown in the image below).
The second animation should follow the common specification deliverd in class. It should show and hold its initial configuration while the mouse button is pressed. That initial configuration should depend on where the mouse is in an intuitive manner but should remain visible. The animation should start when the user releases the mouse button. It should produce an "artistic" 3D animation of both text and images, including a non-linear dynamic motion that shows an anticipation step and soft landing. Each animation should last less than 10 seconds. Your personal web page should contain a version of the team specification for animation 2. You are welcome to edit it for conciseness and precision, but it should remain true to what your team has turned in in class.
Your project page should also contain the link to a short (one page) report in PDF format, written in a formal style (with title, author, date, abstract, text, and bibliographic references) discussing a vocabulary for describing 3D motions in animations. List examples of verbs, nouns, adjectives, group them in categories. Try to impose a logical framework.
Grading: 10 pts for replacing my name and photo with yours, posting the apple, and correctly delivering the first animation, as described above. 10 points for programming an interesting second animation and providing a clear specification for it true to the original. 10 points for the report. Up to 15 extra credit points if the specification is extremely ambitious or original (for example if the animation is physically realistic or funny), if it is formulated in a concise and precise manner, and if it is implemented correctly, and if the report is excellent.
- P02, due Thursday September 11: Regularized Booloean between triangles in 2D. Solution (assuming general position).
Suggested starting applet. Additional applets which may be of use: simple edge/edge intersection, edge/edge intersection including overlaps.
Students may also want to check the slides on booleans (module 03) and the paper on Booleans by Margalit (module 04). You may also want to read Chapter 2 of deBerg et al.
The user should be able to drag the vertices of two tiangles, A and B. The screen should be split in 4 quadrant. In the upper-left quadrant the two triangles should be displayed in different semi-transparent colors. The user should be able to click and drag their corners. In the upper-right quadrant, we should see the original triangles shaded as pale blue background and the regularized intersection filled in red with its boundary drawn in black. In the lower-left we should also see the pale blue copies of the triangles again and, drawn over them, the regularized difference A-B between the two triangles, filled in blue with its boundary drawn in black. In the lower-right quadrant, we should see a copy of the two background triangles and their regularized union filled in green with its boundary drawn in black. To allow the user to easily produce singular situations, where a vertex happens to exactly coincide with another vertex or lie on an edge, or where two edges are exactly colinear, your program should use a tolerance to detect such near singularities and treat them as such.
Grading (point allocation will be adjusted if a different method is used, provided that it computes the correct result):
- 10 points: Email the TA before the deadline with the link to your your personal project page, which should contain your name, email, photo, and links to all your projects for this class. The link to project P02 should lead to a web page with the project title and author's name, a brief project description, the applet running that shows the 4 quadrants and lets the user edit the two triangles in the top left quadrant, while the other quadrants also show the translated versions of the blue-painted triangles.
- 10 points: A short PDF report desribing the problem, explaining how you have solved it, showing a few images, and referencing relevant prior art.
- 10 points: Code for detecting near singularities and a brief description of how this is done posted on the web page or in the PDF report.
- 10 points: Running code for correctly segmenting the edges of each triangle at their intersections with the boundary of the other triangle and a brief explanation of how this is done.
- 10 points: Correct code and clear description in the report for classifying the edge segments according to the regularized Boolean operations in each quadrant and for drawing the segments that bound the resulting set.
- 10 points: Correct code and clear description in the report for linking the edge segments into loops and for filling the regions they enclose as prescribed.
- 20 extra credit points: Correctly implemented extension to simple polygonal regions (i.e. bounded by a single non-self-intersecting loop) with 4 or more vertices each and a discussion in the report of how this extension was implemented.
- P03, due Tuesday September 30: Study of collision and interactive game. (Teams of 2.) Suggested starting applet: Collision detection (zip) , Jarek's Tring (Three ball carom billiard on a RING).
The project has 2 parts:
A - Produce and post a joint paper in a formal style with title, reference to course and project, affiliation, authors (with photos and URLs), abstract, explanations, illustrations, references, conclusion. The paper should explain in details how to animate a 2D scene with 3 disks that each move at a constant (possibly null) velocity. It should provide and explain the derivation and impolementation of the formulae for prediting the time to first collision, for checking static interferences, and for computing the new velocities after an elastic shock. The explanations should be clear (include figures where appropriate). Then, the paper should explain two animation techniques: PIT and PIC. PIT (Periodic Interference Test) checks which pairs of disks interfere at each frame and for these pairs, computes new velocities. PIC (Predicted Instant of Collision) computes the time t of first collision (if one occurs before the next frame), advances the animation to t, computes new velocities after the shock, and then does it again. If no collision occurs before the next frame, it advances the balls to the next frame. Finally, the paper must present 4 or more clear cases where PIT is wrong for different reasons (one disk is delayed, one disk moves in a wrong direction after the shock, a collision is missed, multiple collisions that should happen between two frames are not handled properly. For each case, you need to produce images of the good and bad trajectory showing how bad PIT is and you need to explain why this happens. The images may be generated with a program or drawn by hand, but must clearly show what is going on. Conclude and explain under what conditions using PIT may be acceptable (because it would produce results close to PIC's) and explain why PIC is much harder when the disks do not move at constant velocity or are not disks and are subjects to motions that include rotations. The paper needs not be long, but it should be written in a formal style. For example, the abstract may start with something like: We investigate 2D animation of colliding disks without friction or acceleration that are subject to elastic shocks. We compare two approaches: PIT and PIC. At each frame, PIT (Periodic Interference Test) computes new velocities for all pairs of interfering disks. PIC (Predicted Instant of Collision) simulates the aniamtion between frames by computing the time t to first collision (if any) between the frames, rolling the animation till t, computing new velocities for the colliding pair, and iterating until the time for the next frame is reached. We illustrate and explain four different artifacts that may be produced by PIT: delay, wrong direction, missed collisions, and incorrect handling of nearly simultaneous collisions.
B - Produce and post an interesting interactive game or application that involves one or more players acting upon 3 or more disks and that uses proper collision handling.
- P04, due Tuesday October 28: In-betweening. (Teams of 2.) Suggested starting applet: polymorph
Extend the polymorph program to support the following: (1) When the user presses 'i' capture a line-segment between the location of the mouse press and the location of the mouse release and associate it with the current keyframe. This line segment defines the origin O (center of the line segment) and I vector (direction of th eline segment) of the local coordinate system associated with that keyframe. Be default, all key-frames should have some line-segment. Ensure that the line segment end-points are stored on file and retrieved along with the control vertices of the frames. (2) Compute a pure rotation transform between the coordinate systems of consecutive key-frames and use it to produce an animation (style 1) and the rendering of the intermediate frames. For each intermediate frame that you display during your animation ('a') or during the rendering of all the frames superimposed ('f') render a cross-fade of the two surrounding keyframes curves. (3) Provide the option (style 2) to produce a smooth version of the animatino of the coordinate system, by performing a four-point subdivision of the consecutive rotations (see Screwbender paper). (4) Instead of using the program to drawing smooth curves for keyframes and the cross-fade for the intermediate frames, use images of the keyframe. A set is provided for you to play with. (5) Get 8 images representing the time-volution of some object that not only moves but also deforms a bit. These could be pencil and paper drawings that you made or copied, images of people's faces, stroboscopic images of a flying bird... Use your tool to create an animation of them. (6) Post the applet that shows your animation and lets people edit the line segments. Include a zip of the whole thing (source code, data folder with fonts, points, images). Also include a short report that explains how you have implemented the computation of the rotations and of their smoothing.
Extra credit: (1) You may implement a four-point interpolation of the end-points of the lines and use them to define the lines of the intermediate frames. Discuss the advantagees/drawbacks of these two approaches. You may also propose other approaches. (2) You may implement other interpolation schemes and compare them to these two. (3) Try to automate the creation of the linesegments. You may read the images and from them compute the center of mass of the non-white pixels and the principal direction.
Make sure that you clearly point out the various extra credit contributions on your project page and explain them in your write up.
As an alternative, you may implement a full dynamic system in 2D, wioth gravity and total friction, where the user can raw a curve, put a disk on one end of it, and have your program animate the physically correct behavior of the disk, as it ROLLS down the curve (pulled by gravity), jumps, and falls back on the curve, possibly bouncing off with a semi elastic chock. Make sure that you render the disk in a fashion that shows how it is rotating (put a dot off center on it). Provide a description of the dynamic equations you used and of their implementation. Post the running applet and your report.
- P05 (Bulge). In teams of 3 or less. Due Nov 25 before class (post and email TA). Demos on Dec 2 (submit request by Nov 25).
You may (but do not have to) use the code provided on the /demo applets page. You do not have to use Processing. You may use publically available code (such as the one provided by CGAL for the constrained Delaunay triangulation), but if you do so, you must clearly state what code you are using, where you got it from, how you interfaced with it.
(1) Provide closed-loop curve-editing capability (drawing when the 'd' key is pressed or editing/inserting control points) and the option to resample the current polyloop P with a user-controlled number of evenly distributed vertices (use keys '<' or '>' to double or half the vertex count).
(2) Compute and show the constrained Delaunay triangulation of the interior of P. Use a sufficiently dense resempling to ensure that each Delaunay triangle is either in the interior or in the exterior of P. Keep only the triangles in the interior of P.
(3) Compute sample points on the MAT (Medial Axis Transform) of P. Store their location and radius. Show them by first displaying the corresponding (filled) disks (which should nearly fill the interior of P) and by overlaying in a different color the centers of these disks (medial axis sample points).
(4) Spray random points in P ( use ',' or '.' keys to double or half the number of interior vertices). Compute the constrained Delaunay triangulation of the union of the vertices of P with these interior vertices.
(5) Store the triangulation as a corner table (compute the V and O tables) and verify that all corner operators work (use keys 'n', 'p', 'o', 's' to navigate the mesh...)
(6) Use Laplace smoothing to distribute the interior points evenly (key 'S'). This is a 2D redistribution of the interior vertices, which may not yield an even distribution of the vertices on the final 3D bulge surface. Note that you may also execute a smoothing later (once you have constructed the 3D mesh) and discuss the additional benefits/drawbacks of doing it in 3D.
(7) Bulge the interior points into 3D (when key 'b' is pressed), setting their height (z-coordinate) to the maximum of their height at containing MAT balls. It is easy to compute the height of a ball at some point Q that it contains. Implement this using a loop on all balls (MAT samples) for each interior vertex.
(8) Make a mirror image of the mesh (when key 'm' is pressed), stitch the two meshes together into a watertight mesh (by adding the interior vertices and the reoriented triangle of the mirror mesh and recomputing the O table).
(9) Save the bulged mesh to a file ('W' key). Load a saved mesh (key 'L'). Integrate with a 3D view manipulation so that the user can inspect the mesh from all directions. Support an automatic animation (key 'a' turns animation on and off) that rotates the bulged mesh in 3D (around the y-axis).
(10) Compute the isolation measure (key 'I') of that bulged mesh and color code the triangles accordingly (lighter tips).
(11) Provide help text (' ') explaining how to use the program and a report describing the functionality and how it was implemented (include title, class, date, authors, head-shots, references to materials used and other sources...). Specifically include references to TEDDY and PLUSHIE and discuss the similarities/differences between your approach and the one used in TEDDY and PLUSHIE for computing the bulge.
(12) Post web page where users can draw their own curve and view the 3D bulged mesh. Include title, link to class web page, author's names and headshots, links to the authors' home pages, the report, links to references and software used, and a zip file with the whole directory/folder, including the html web pages, the applet, the source code, the data, the report).
(13) Merge the bulge project with a 2D animation tool that automatically computes the frames of a cyclic animation from a series of keyframe polyloops. Apply the bulge to each frame of the 2D animation. Save the results. Play the animation (by swapping meshes at each frame) as you rotate the model automatically around the Y axis (key 'a').
(14) Design a cool 3D animation and post an applet that loads and play it when it is started.
(15) Make a short (200 frames, 400x400 resolution, standard format) video of your animation and include in your web page and in the zip file.
Links to videos: TEDDY, PLUSHIE.
Links to papers: TEDDY, PLUSHIE
Useful code: Circum-circle and centers, Naive Delaunay, Mesh viewer and Corner Table, Delaunay/Voronoi, Bulge, Stitching
