Project 4: Final Project

Project 4: Final Project
Assigned: Tuesday, March 5
Due: Wednesday, March 20
Artifact/web page due: Thursday, March 21

Project Description

The topic of the final project is open to you. You get to define your own final project. It should be ambitious enough to demonstrate a significant result, but not so hard that you aren't confident about shipping a reasonably complete product. The project ideas below are for your reference... feel free to come up with your own idea. You can leaf through recent SIGGRAPH proceedings in Grail for additional inspiration.
Some Project Ideas

(Note that some of the pictures below don't correspond to the algorithm suggested, though they all depict the idea described.)
NPR and Image Processing

Morphing Morphing is a useful technique for generating smooth transitions between two objects. Implement the morphing algorithm introduced in Thaddeus Beier and Shawn Neely's SIGGRAPH 92 paper on Feature-Based Image Metamorphosis.

Non-photorealistic lighting model
Technical illustration has some important characteristics which makes it very different from realistic rendering. Therefore, the popular shading model like Phong shading is not appropriate for technical illustrations. Gooch et al. introduced a shading model for technical illustrations in their SIGGRAPH '98 paper. Another option is to make a cel shader (cartoon style), or art-based rendering to make Dr. Seuss-like pictures.

Intelligent scissors with alpha matting. Image matting is the process of extracting a foreground element from the background so that the foreground can be placed over a novel background. Intelligent scissors is a method for interactively drawing along the contour of a foreground object while the computer tries to "snap" the curve to the nearest edge. The result of intelligent scissoring is a nice separation, but it doesn't model fractional mixing of foreground and background colors, i.e., alpha computation. In this project, you would combine intelligent scissors with alpha estimation. You could start from the intelligent scissors project in 490CV and enhance it to include a simple variant of Chuang's digital image matting method.

Arcimboldo NPR. Take a photograph (e.g., of a person's face) and try to render it using smaller images of distinct objects (e.g., vegetables). Rennaisance painter Giuseppe Arcimboldo was famous for such compositions. This project is cool, if half-baked at the moment.

Rendering

Distribution ray tracing. Implement semi-diffuse reflections and refractions by distributing the secondary rays emanating from each surface according to a bidirectional reflectance distribution function (BRDF) of your own choosing. Allow slider control over one or more parameters of the BRDF. Stop ray recursion if the weight for a ray's color drops below a slider-selectable threshold. You can refer Ward's paper as an example of BRDF representation. You can also implement distribution ray tracing for area light sources to simulate penumbrae, for a finite aperture to simulate depth of field, and for a finite shutter interval to simulate motion blur. This extension to the ray tracing project should be combined with another extension, such as advanced material properties.

Texture/Bump mapping. Add texture mapping to your ray-tracer spheres, triangle meshes, and planar quadrilaterals. Textures may be 2D or 3D (solid textures), and may be procedurally generated or optically scanned. To map a texture onto a surface, you must compute texture indices at each ray-surface intersection. Methods for spheres, quadrilaterals, and triangles are described by Eric Haines in sections 2.5 and 3.3 of chapter 2 in Glassner. For a triangle mesh, you can convert from publically available meshes (3D Cafe has many).
Use your texture to modulate something besides just reflectance (i.e. color). Experiment with transparency, specularity, or orientation (i.e. bump mapping). Alternatively, try modulating an interpolation between two other textures or between two entirely different shading models. See Cook's SIGGRAPH '84 paper on shade trees and Perlin's SIGGRAPH '85 paper on texture synthesis (FvDFH, p. 1047) for ideas.
Depending on the extent of your texture-mapping extension, you may need to combine this with another extension such as advanced material properties.

Ray-tracing geometric primitives. Implement a class of more complicated primitives (e.g., from Hanrahan's chapter in Glassner's book). Choose wisely. Quadrics are too easy; deformed surfaces are too hard. Recommended are general swept surfaces, bicubic patches, CSG models, or fractals. Fractals are relatively easy to implement and fun to use. For extra fun, map textures onto your patches or fractals. Other primitives that can be used for terrific visual effect are particle systems (e.g., for fire and water) and L-systems (great for modeling plants).

Ray tracing volumes. Start by implementing spatially inhomogeneous atmospheric attenuation. Divide each ray into intervals. For each interval, interpolate between the ray's color and some constant fog color based on a procedurally computed opacity for that location in space. Experiment with opacity functions. Once you get this working, try defining a solid texture (probably procedurally) that gives color and opacity for each interval. See Perlin and Hoffert's and Lewis's SIGGRAPH '89 papers on solid texture synthesis and Kajiya and Kay's teddy bear paper (also SIGGRAPH '89) for ideas. For smoke and clouds, you should also cast a ray to the light source to capture (one bounce of) the scattering. If you want to make your volume renderer fast, use hierarchical spatial subdivision (e.g. an octree).

Hierarchical radiosity. This is actually not as hard as it sounds. To implement the Hanrahan hierarchical solver , the main ingredients are a simple polygonal scene, a routine to break a triangle or rectangle into a few smaller pieces, a patch to patch visibility solver (your ray tracer already does this), and a simple mechanism for traversing a hierarchy of polygons. The simplest way to visualize your results would be to write out a file in the obj format accepted by your subdivision editor extended with an rgb triple for each point in addition to the xyz values, and extend your subdivision modeler to read and render the vertex color. Alternatively, you can do a "final gather" ray-tracing pass to achieve smooth shading. For best results, combine the radiosity solution with a ray-tracing pass that incorporates specular highlights and textures.

Light field renderer. Ray tracing, especially for complex models and many interreflections, is generally not real-time. An alternative approach is to ray trace a set of images and then reuse these rays when generating new images. This idea is called light field or lumigraph rendering. Using some simple tricks with graphics hardware and ray traced images for viewpoints on a regular grid, it is actually possible to reuse rays in real-time to create new renderings quickly. See Levoy and Hanrahan's paper for details. A more complex method when geometry is also available (in addition to the images) is described by Grzeszczuk, et al.

Geometric modeling

Subdivision surface. Subdivision surfaces gain more and more attention from industry and have been widely used in animation production, like "Geri's Game" and "Toy Story II". As a final project, you are required to implement both non-interpolating (Loop) and interpolating (Butterfly) subdivision. Use the evaluation mask to calculate final vertex positions if necessary, and the tangent masks to calculate vertex normals. You also need to have support for feature edges and vertices. Your subdivision editor should have an interface for selecting a vertex or an edge and then marking (or unmarking) it as a feature. You can start from a previous quarter's subdivision surface skeleton code (in MFC only).
Sketch interface for modeling. Teddy is a sensational system introduced in SIGGRAPH''99 and presents a new paradigm for modeling. In Teddy, users scrabble on the panel and the system automatically infers the underline 3D model reasonablly. As a final project, you can design your own interface for modeling or follow Teddy's design (you are not required to implement all operations introduced in the paper).

Multi-resolution curves for keyframing. Create a multiresolution keyframing system which can edit the motion curves at different levels of detal. The curves should be able to interpolate the keyframe constraints by changing the coefficients at a specific level of detail. Devise a scheme which can interpolate at non-integer levels of detail. There is a paper by Finkelstein and Salesin on multiresolution curves.

Physically based vegetation. Design a dynamic model of a tree that would move realistically (e.g. for wind blowing or a person brushing through). The tree could be built using L-system rules. Different parts of the tree would have different amounts of elasticity. For a sufficiently complex tree (or lots of trees), you may need to explore efficient ways of simulating the tree physics in order to get rapid simulation.

Procedural architecture and cities. Design a general L-system for modeling buildings (simple structure and image-based facades) and cityscapes. Explore ways of parameterizing the buildings by attributes such as age, style, and location. This SIGGRAPH '01 paper can be used as a guide.

Animation

Cartoon physics simulation. Design a simulation environment that would model various aspects of cartoon physics. Augment the traditional simulation of Newtonian physics with additional constraints, damping parameters and other modifications which would produce an exaggerated cartoon-like behavior.
Inverse kinematics. Implement inverse kinematics for character modeling and animation. Given a sequence of trajectories for a few end-effectors on the character's body construct the character's joint angle which would interpolate the end-effector trajectories while ensuring that the character moves "naturally". See lecture on inverse kinematics for details. There is a section on IK in the CSE558 course notes from 2000.
Cloth Simulator. Design a cloth simulation model. Design a methodology and determine the parameters of the cloth model which will mimic the behavior of wool, cotton, silk.
Rigid body simulation. Incorporate rigid body simulation with the keyframe animator. The keyframed character should be able to interact in realistic ways with the simulated objects in the scene. See this set of course notes to get you started.
Motion Warping. Implement a technique for editing already existing animations, by warping the motion curves to meet the new constraints. See Zoran's paper for more information.
Explosions. Develop a particle system approach to modeling and rendering realistic explosions (fire, dust plumes, etc.)

Water Flow. Simulate and render the flow of whitewater rapids.

Bird Flight. Develop a dynamics model for bird flight.

Crowds and cars. Design a model of pedestrian crowds and/or vehicular rush-hour traffic. The crowd model should be parameterized by the number of people, demographics (age, sex, etc), and general direction. The pedestrians should exhibit some variations in behavior as well (speed, interacting with others, etc.). Lower level human movement could be built from hand-animated examples or from human captured motion data. Vehicular traffic can be parameterized by time of day, volume, source and destination. In either case, intersections between people and/or crowds must be avoided.

Demos

You should prepare in advance for the demo, since you'll be the expert, not us. If you choose a rendering project you should have precomputed some images. If you project is interactive you may not need precomputed images, but you'll want to have inputs ready that effectively demonstrate your work. In any case, please generate an artifact to show off your project. It can be a rendering or a model or a visualization of your results.

	Morphing Morphing is a useful technique for generating smooth transitions between two objects. Implement the morphing algorithm introduced in Thaddeus Beier and Shawn Neely's SIGGRAPH 92 paper on Feature-Based Image Metamorphosis.
	Non-photorealistic lighting model Technical illustration has some important characteristics which makes it very different from realistic rendering. Therefore, the popular shading model like Phong shading is not appropriate for technical illustrations. Gooch et al. introduced a shading model for technical illustrations in their SIGGRAPH '98 paper. Another option is to make a cel shader (cartoon style), or art-based rendering to make Dr. Seuss-like pictures.
	Intelligent scissors with alpha matting. Image matting is the process of extracting a foreground element from the background so that the foreground can be placed over a novel background. Intelligent scissors is a method for interactively drawing along the contour of a foreground object while the computer tries to "snap" the curve to the nearest edge. The result of intelligent scissoring is a nice separation, but it doesn't model fractional mixing of foreground and background colors, i.e., alpha computation. In this project, you would combine intelligent scissors with alpha estimation. You could start from the intelligent scissors project in 490CV and enhance it to include a simple variant of Chuang's digital image matting method.
	Arcimboldo NPR. Take a photograph (e.g., of a person's face) and try to render it using smaller images of distinct objects (e.g., vegetables). Rennaisance painter Giuseppe Arcimboldo was famous for such compositions. This project is cool, if half-baked at the moment.

	Distribution ray tracing. Implement semi-diffuse reflections and refractions by distributing the secondary rays emanating from each surface according to a bidirectional reflectance distribution function (BRDF) of your own choosing. Allow slider control over one or more parameters of the BRDF. Stop ray recursion if the weight for a ray's color drops below a slider-selectable threshold. You can refer Ward's paper as an example of BRDF representation. You can also implement distribution ray tracing for area light sources to simulate penumbrae, for a finite aperture to simulate depth of field, and for a finite shutter interval to simulate motion blur. This extension to the ray tracing project should be combined with another extension, such as advanced material properties.
	Texture/Bump mapping. Add texture mapping to your ray-tracer spheres, triangle meshes, and planar quadrilaterals. Textures may be 2D or 3D (solid textures), and may be procedurally generated or optically scanned. To map a texture onto a surface, you must compute texture indices at each ray-surface intersection. Methods for spheres, quadrilaterals, and triangles are described by Eric Haines in sections 2.5 and 3.3 of chapter 2 in Glassner. For a triangle mesh, you can convert from publically available meshes (3D Cafe has many). Use your texture to modulate something besides just reflectance (i.e. color). Experiment with transparency, specularity, or orientation (i.e. bump mapping). Alternatively, try modulating an interpolation between two other textures or between two entirely different shading models. See Cook's SIGGRAPH '84 paper on shade trees and Perlin's SIGGRAPH '85 paper on texture synthesis (FvDFH, p. 1047) for ideas. Depending on the extent of your texture-mapping extension, you may need to combine this with another extension such as advanced material properties.

	Ray-tracing geometric primitives. Implement a class of more complicated primitives (e.g., from Hanrahan's chapter in Glassner's book). Choose wisely. Quadrics are too easy; deformed surfaces are too hard. Recommended are general swept surfaces, bicubic patches, CSG models, or fractals. Fractals are relatively easy to implement and fun to use. For extra fun, map textures onto your patches or fractals. Other primitives that can be used for terrific visual effect are particle systems (e.g., for fire and water) and L-systems (great for modeling plants).
	Ray tracing volumes. Start by implementing spatially inhomogeneous atmospheric attenuation. Divide each ray into intervals. For each interval, interpolate between the ray's color and some constant fog color based on a procedurally computed opacity for that location in space. Experiment with opacity functions. Once you get this working, try defining a solid texture (probably procedurally) that gives color and opacity for each interval. See Perlin and Hoffert's and Lewis's SIGGRAPH '89 papers on solid texture synthesis and Kajiya and Kay's teddy bear paper (also SIGGRAPH '89) for ideas. For smoke and clouds, you should also cast a ray to the light source to capture (one bounce of) the scattering. If you want to make your volume renderer fast, use hierarchical spatial subdivision (e.g. an octree).
	Hierarchical radiosity. This is actually not as hard as it sounds. To implement the Hanrahan hierarchical solver , the main ingredients are a simple polygonal scene, a routine to break a triangle or rectangle into a few smaller pieces, a patch to patch visibility solver (your ray tracer already does this), and a simple mechanism for traversing a hierarchy of polygons. The simplest way to visualize your results would be to write out a file in the obj format accepted by your subdivision editor extended with an rgb triple for each point in addition to the xyz values, and extend your subdivision modeler to read and render the vertex color. Alternatively, you can do a "final gather" ray-tracing pass to achieve smooth shading. For best results, combine the radiosity solution with a ray-tracing pass that incorporates specular highlights and textures.
	Light field renderer. Ray tracing, especially for complex models and many interreflections, is generally not real-time. An alternative approach is to ray trace a set of images and then reuse these rays when generating new images. This idea is called light field or lumigraph rendering. Using some simple tricks with graphics hardware and ray traced images for viewpoints on a regular grid, it is actually possible to reuse rays in real-time to create new renderings quickly. See Levoy and Hanrahan's paper for details. A more complex method when geometry is also available (in addition to the images) is described by Grzeszczuk, et al.

	Subdivision surface. Subdivision surfaces gain more and more attention from industry and have been widely used in animation production, like "Geri's Game" and "Toy Story II". As a final project, you are required to implement both non-interpolating (Loop) and interpolating (Butterfly) subdivision. Use the evaluation mask to calculate final vertex positions if necessary, and the tangent masks to calculate vertex normals. You also need to have support for feature edges and vertices. Your subdivision editor should have an interface for selecting a vertex or an edge and then marking (or unmarking) it as a feature. You can start from a previous quarter's subdivision surface skeleton code (in MFC only).
	Sketch interface for modeling. Teddy is a sensational system introduced in SIGGRAPH''99 and presents a new paradigm for modeling. In Teddy, users scrabble on the panel and the system automatically infers the underline 3D model reasonablly. As a final project, you can design your own interface for modeling or follow Teddy's design (you are not required to implement all operations introduced in the paper).
	Multi-resolution curves for keyframing. Create a multiresolution keyframing system which can edit the motion curves at different levels of detal. The curves should be able to interpolate the keyframe constraints by changing the coefficients at a specific level of detail. Devise a scheme which can interpolate at non-integer levels of detail. There is a paper by Finkelstein and Salesin on multiresolution curves.
	Physically based vegetation. Design a dynamic model of a tree that would move realistically (e.g. for wind blowing or a person brushing through). The tree could be built using L-system rules. Different parts of the tree would have different amounts of elasticity. For a sufficiently complex tree (or lots of trees), you may need to explore efficient ways of simulating the tree physics in order to get rapid simulation.
	Procedural architecture and cities. Design a general L-system for modeling buildings (simple structure and image-based facades) and cityscapes. Explore ways of parameterizing the buildings by attributes such as age, style, and location. This SIGGRAPH '01 paper can be used as a guide.

	Cartoon physics simulation. Design a simulation environment that would model various aspects of cartoon physics. Augment the traditional simulation of Newtonian physics with additional constraints, damping parameters and other modifications which would produce an exaggerated cartoon-like behavior.
	Inverse kinematics. Implement inverse kinematics for character modeling and animation. Given a sequence of trajectories for a few end-effectors on the character's body construct the character's joint angle which would interpolate the end-effector trajectories while ensuring that the character moves "naturally". See lecture on inverse kinematics for details. There is a section on IK in the CSE558 course notes from 2000.
	Cloth Simulator. Design a cloth simulation model. Design a methodology and determine the parameters of the cloth model which will mimic the behavior of wool, cotton, silk.
	Rigid body simulation. Incorporate rigid body simulation with the keyframe animator. The keyframed character should be able to interact in realistic ways with the simulated objects in the scene. See this set of course notes to get you started.
	Motion Warping. Implement a technique for editing already existing animations, by warping the motion curves to meet the new constraints. See Zoran's paper for more information.
	Explosions. Develop a particle system approach to modeling and rendering realistic explosions (fire, dust plumes, etc.)
	Water Flow. Simulate and render the flow of whitewater rapids.
	Bird Flight. Develop a dynamics model for bird flight.
	Crowds and cars. Design a model of pedestrian crowds and/or vehicular rush-hour traffic. The crowd model should be parameterized by the number of people, demographics (age, sex, etc), and general direction. The pedestrians should exhibit some variations in behavior as well (speed, interacting with others, etc.). Lower level human movement could be built from hand-animated examples or from human captured motion data. Vehicular traffic can be parameterized by time of day, volume, source and destination. In either case, intersections between people and/or crowds must be avoided.