Independent Study Projects

David Mount's
Independent Study Projects

Here are links to some independent study projects that I have supervised. If you are interested in working with me on an independent study project, please send me email. You should have completed either CMSC 420 (Data Structures) or CMSC 451 (Algorithms) and have good programming skills.

Spherical Maze Generation by Xue Li (Fall 2016).

In this paper, we proposed an automatic spherical maze generation framework. Traditional mazes are generated on two or three dimensional spaces, with regular grids as walls and paths. Instead, we automatically generate a maze on the surface of a sphere, which provides a unique and fresh maze solving experience. Because regular grids on a spherical surface result in nonuniform room spaces, we randomly generate uniformly distributed points on the sphere. Then we automatically create the wall mesh structures by triangulation and Voronoi graph generation. Gift-wrapping algorithm and incremental construction are both conducted for the spherical triangulation. To create the spherical maze, the union-find algorithm is applied to remove parts of the walls, build the paths and join all the rooms.

VR Outrun Shooter by Andrew Dilks (Fall 2016).

This is an implementation of a virtual-reality game in Unity based on table-top style gameplay, inspired by the classical game Geometry Wars. The main objective is to control a ship on a 2D plane and destroy the incoming obstacles, scoring the as many points as possible before being destroyed. Directional control and motion are implemented using head movement tracking provided by a VR headset. Here is a Sample Video showing the gameplay.

Autonomous Vehicle Intersection Management by Robert Adkins (Spring 2016).

This paper explores the use of game theory to design an efficient algorithm for routing self-driving cars through intersections. Despite the discouraging exponential naive solution to this problem, there are some efficient optimizations which are exposed.

Algorithmic Game Theory by Robert Adkins (Fall 2015).

This paper introduces some fundamental concepts to the field of algorithmic game theory. It also explores some of the known algorithms for calculating various kinds of equilibria in games, like the Lemke-Howson algorithm for finding mixed Nash equilibria and the Ellipsoid-against-Hope algorithm for finding correlated equilibria. After these ideas are introduced, potential applications towards autonomous vehicle tracerc routing are explored. This latter section yields the motivation behind my study of algorithmic game theory over the course of this semester.

Implementing the Held-Karp Lower Bound Algorithm in Python by Taylor Moore (Fall 2015).

The Traveling Salesman Problem is a fundamental problem that arises in many diverse fields, from vehicle routing to genome sequencing to circuit design. Because it is an NP-Hard problem, it is primarily calculated via heuristics for graphs of non-trivial size. The Held-Karp lower bound provides a lower bound for the cost of the optimal TSP tour of a graph. Having the lower bound for a particular graph is useful for checking the performance of a given heuristic. This report details an implementation of the Held-Karp lower bound algorithm in Python. The implementation is based on the work of Valenzuela and Jones.

LPT Codes used with ROAM Splitting Algorithm by Joe Brosnihan (Fall 2015).

Simplicial meshes are commonly used to represent regular triangle grids. Of many areas, simplicial meshes are useful in the area of terrain rendering within computer graphics. This project presents an implementation of Atalay and Mount's LPT code algorithm for representating a hierarchical mesh of simplices. In addition, part of the ROAM terrain algorithm that splits simplices down to a desired level of detail. Several modifications to the LPT code representation are also made and tested in several scenarios.

Water Simulation by Aharon Turpie (Spring 2014).

This project attempts to render real-time the optical effects of the surface of water; such as reflection, refraction, and caustics. This is not a physical model, but only tries to render believable effects of them. The project was implemented using C++, OpenGL 4.4, and GLSL.

Euclidean Minimum Spanning Trees Based on Well Separated Pair Decompositions by Chaojun Li (Spring 2014).

In this report we consider the implementation of an efficient algorithm for computing Euclidean minimum spanning trees, which is based in part on the well-separated pair decomposition, introduced by Callahan and Kosaraju. In order to compute the Euclidean Minimum Spanning Tree of n points in the space, one can naively link each pair of edges to build the complete Euclidean graph G=(P,E), where P stands for the vertex set, and E stands for set of edges, which consist of all pairs (p, q) for p, q in P. For such a graph we have |E|=O(n²), and combining this with the (E log V) = (n² log n) running time for the execution of Kruskals Algorithm, would result in an overall running time of O(n² log n). In this paper we present a more efficient solution.

Rigid Body Simulation by Jeremy Ulrich (Fall 2013).

This paper describes a real-time 3D rigid body physics engine, and is the result of an Independent Study on collision detection and response in the context of rigid body dynamics. The simulation produces realistic motion, collisions, friction and resting contact between multiple bodies. The engine works mostly with convex polyhedra, and employs several tools in order to efficiently perform convexity-based queries and calculations. The collision detection system consists of a broad phase and narrow phase. The broad phase uses a uniform grid and bounding spheres, and the narrow phase includes the Separating Axis Test for determining intersection between convex polyhedra. The dynamics system employs a velocity-based constraint model for contact and friction constraints, resolves the constraints using an iterative Sequential Impulse solver, and calculates the motion of the rigid bodies.

Seeing Dual: Developing a Tool for Visualizing the Relationships between Convex Hulls, Upper Envelopes, Voronoi Diagrams, and Delaunay Triangulations by John Ingraham (Spring 2013).

The Delaunay Triangulation, Voronoi Diagram, Convex Hull, and Upper (or Lower) Envelope are widespread geometric structures seen in many fields such as computational geometry and computer graphics. Their ubiquity and usefulness in various scenarios make them important constructs to examine and study if possible, but they can be difficult to visualize or draw without some sort of aid. In addition, there are some important and intuitive relationships between the different structures that are most easily conveyed with a cohesive and complete visualization. This paper describes a program that attempts to provide this visualization.

Particle Systems: Theory and Practice by Ciara Belle (Spring 2012).

Modeling non-deterministic, complex objects is difficult using general techniques in computer graphics. Particles systems are used to overcome the difficulty of modeling these "fuzzy" objects, including clouds, fire, and water. Particle systems differ in three ways from normal modeling techniques. The first difference is that particle systems are not sets of primitive shapes and surface elements, instead they are clouds of primitive particles that define an object's volume. Second, particle systems are dynamic and are constantly changing form with the passage of time. The last difference is that the objects that particle systems attempt to represent are generally non-deterministic. In this paper, we provide a general introduction to the topic of particle systems, their definition and implementation, and we discuss various applications of particle systems.

Fluid Dynamics and the Navier-Stokes Equation by Steven Dobek (Spring 2012).

Modeling and computing the motion of fluids is problem of fundamental importance in science and engineering. This paper presents a brief introduction to the topic. We begin by providing an introduction to vector calculus. Next, we give the Navier-Stokes equation and present an intuitive description of its terms. Finally, we present Stam's algorithm for performing stable simulations of fluid motion.

Rendering Crystal Glass Caustics by Alisa Chen (Spring 2011).

While glassmaking and glass arts have been known since ancient times, it was not until George Ravenscroft added lead oxide that lead glass was invented, also called lead crystal or crystal glass. The attractiveness of crystal glass is due to its higher index of refraction and its dispersion of light. This results in a distortion of reflections of its surroundings and a creation of rainbows. Of particular interest to this study are caustics, the beautiful patterns the light formed due to the curved surface of crystal. Chromatic dispersion is included among these patterns. To render crystal glass caustics, this independent study researched photon mapping to enhance a basic ray tracer.

Circular Trapezoidal Decomposition by William Mennell (Fall 2007).

Given a collection of line segments in the plane, a trapezoidal decomposition is a subdivision of the plane formed by shooting a bullet path upwards and downwards from each endpoint and each intersection point until it hits another segment. This is a structure of fundamental importance in comptutational geometry. This concept can be generalized to other sorts of geometric curves, by applying the bullet-shooting process not only to endpoints and intersection points, but also to points of vertical tangency on the curve. This project involves a C++ implementation of the Mulmuley's randomized trapezoidal decomposition algorithm, but for circles, rather than line segments. It uses a history DAG to store trapezoids. It is based on numerical computations using floating-point arithmetic, and some care has been taken to handle a considerable number of degenerate cases.

God: Object Oriented Programming in Macromedia Flash MX by Jordan Richardson (Fall 2005).

This project is a study of object-oriented programming in Macromedia Flash MX. The concept for the project was to build an interactive environment that allows the user to control objects in space. These bodies behave similarly as they would under the natural forces of gravity. Each body contributes to the forces that influence every other body in real-time. The user is given the ability to create, size, and move these bodies around the stage. The user can also navigate through the spacial plane shifting it in any direction or scaling it causing the view to zoom in or out. The user is also given the power to advance the power of gravity thereby increasing the total energy of the system.

Revealing New Perspectives: Retrieving the Details of High Dynamic Range Images on Low Dynamic Range Displays through Tone Mapping by Chihiro Hirai (Fall 2005).

Traditional monitors and printers are capable of displaying images in which luminances (that is, brightnesses) range over a small number of values (typically 256). Many modern digital cameras and computer graphics software are capable of producing luminance values over a much greater range, and so are called high dynamic-range (HDR) images. In order to display an HDR image on a low dynamic-range device, some transformation must be performed to avoid wash-out effects that arise when the high dynamic range is clamped to a the small dynamic range supported by the device. One such transformation is called tone mapping. We present an implementation of a tone mapping algorithm due to Larson, Rushmeier, and Piatko, and test it on a number of images. We show that out program often leads to a much more faithful representation the scene from the perspective of how it appears to a human observer.

Rediscovering Fire: A Survey of Current Fire Models and Applications to 3D Studio Max by Yulia Eyman (Spring 2004).

Fire is arguably the most visually impressive natural phenomenon. It is also one of the most destructive and difficult to predict. Its physical properties vary with the fuel and temperature, and have been studied extensively by combustion researchers. In the field of computer science, fire's complexity is still an elusive problem. Many attempts have been made to model fire, both for visual and functional purposes, with increasingly successful results. The approaches can be subdivided into attempts to model fire as a texture, and the use of physical formulas to simulate its behavior. This paper presents a survey of existing research into fire representations and the fundamental components of 3D Studio Max that can be used to create animated fire simulations.

The Democratization of GIS and Applications in Community Planning: Development of the GURTIE System by Steven Helfand (Spring 2004).

The Gemstone Urban Revitalization Team Interactive Environment (GURTIE) is a tool designed to overcome the political, social, and technological barriers that often prevent community leaders and residents from effectively utilizing information technology tools in neighborhood planning and management. GURTIE utilizes traditional GIS spatial data indexing, combined with non-traditional, non-spatial data capabilities for handling things such as contact information and event-based data. This report describes the system's architecture and implementation.

Roadmap-Based Methods for Flocking Motion with Obstacles by Tzu-hsiu (Kevin) Chiou (Spring 2004).

The goal of this project is to create algorithms for controlling the motion of a group of entities in an environment with obstacles. In our research, we added new rules for flocking behavior, devised our own path-finding algorithm, and incorporated a number of optimizations. The result is an algorithm that allows accurate and efficient simulation of autonomous groups of objects in a complex environment.

Moons of Mars Explorer by Istvan Laszlo (Spring 2004).

Mars' Moons Explorer is a realistic and accurate rendering of Mars' two moons, Phobos and Deimos. It is so because it makes use of shape models from Dr. Peter C. Thomas at Cornell University to provide the underlying shape of the moons. Mars' Moons Explorer gives you the opportunity to hover over Phobos and Deimos, orbit them, and zoom, while also providing orbital animation.

3D Physics Engine for Elastic and Deformable Bodies by Liliya Kharevych and Rafi (Mohammad) Khan (Fall 2002).

The purpose of this project is to create 3D engine that displays the interaction of non-rigid bodies. As a part of our project we researched existing models for elastic and deformable bodies and algorithms for their collision detection and collision response. We have created a model of the object as a set of points connected by springs of given elasticity factor k. The model uses spring forces and damping to give elasticity to the objects. Object collisions are determined using our collision detection engine. After collision occurs the response is calculated using physics laws.

Path Sensitivity by Jawad Muaddi (Fall 2002).

Path planning for minefields requires a consideration of risk and distance. Optimal paths through a minefield consider both factors. The sensitivity of a path indicates the likelihood of the path to change when mines are added or removed. This project studies the calculation and representation of path sensitivity. As a result of the experiments conducted in this study, we conclude that edges of a graph that are closer to the shortest path tend to be more sensitive, meaning that a change in these edges could result in a redirection of the shortest path. We found that shortest path edges tend to be sensitive to change in edge cost; these edges redirect with slight changes in cost.

Kinetic PR Quadtree by Ransom Kershaw Winder (Fall 2000).

This project involved the design and animation of a new data structure called a kinetic PR quadtree. The impetus for this project was the desire to grant the traditional PR quadtree the ability to hold non-stationary data points with velocity vectors in finite, 2-dimensional space. The movement of the data points over time would change the structure of the PR quadtree's subtrees. The main focus of the project was implementing this ability for the PR quadtree and animating the changes in quadtree structure during the data points' movement.

A Ray Tracing Algorithm for Sphere Rendering by Aleksey Martynov (Spring 2000).

This project involved a new algorithm for performing ray-object intersections involving spheres. It implements this algorithm as part of a ray-tracing program. The goal of the new algorithm is to minimize the rendering time by improving the average time of the ray-object intersection tests. The algorithm focuses on rendering spheres and presents spheres in 4-dimensional (sphere) space in order to optimize the structure of the resulting data structure for searching purposes. The results of the algorithm are compared against simple brute-force search method and enhancements to the algorithm are discussed.

On the Effective Use of a Web Page Design by Carina Hassan (Spring 2000).

To design a web site that is attractive and easy to use site requires some organization. There are many different combinations of Web page design that the developers can choose to use for their sites. In this report of the effective use of the different types of Web page layouts, we discussed what determines the basic elements of a good web-page design. The basic elements include color contrast, text organization, font selection, style of a page, page size, graphics used, and consistency.

Image Flaw Removal by Amy Yuan (Fall 1998).

This project dealt with designing a program to perform flaw-removal in images. Given an image, the user specifies a rectangular region. The program removes this region of the image and attempts to fill it in as smoothly as possible based on the intensities of the surrounding area. This project studied a particular method of filling in the removed region, based on a dynamic programming algorithm. The objective function is to link together regions of equivalent intensity by the shortest possible paths.

Design and Implementation of an Interactive Ray Tracer by Maria Jump (Summer 1998).

This project dealt with designing a ray-tracing program for computer graphics, which runs in real-time. Ray tracing produces very realistic images, but it is computationally very time consuming. In order to produce images in real-time, this program attempts to estimate the contents of the image, based on prior images, and then it redraws the image to increasingly higher levels of resolution. This project was funded by the Senior Summer Scholars Program.

An Implementation of a Recursive Ray Tracer that Renders Caustic Lighting Effects by Shu Cheah (Summer 1996).

The project involves a rendering technique that takes into consideration caustic effects. These effects occur when light passes through some refractive medium, such as water or glass, which causes the light rays to bend.

Graphics Applets by Connie Peng (Fall 1996).

This project involved implementing a collection of applets to implement perspective viewing of a rotating object. This includes a simple wireframe viewer, a solid surface viewer, and an shaded surface viewer.

A Sampling of Applets by Ed Craft (Fall 1996).

This project involved implementing a collection of simple applets. They include an applet for the Towers of Hanoi, and a simple calculator.

Back to Dave Mount's home page.

Last updated on Nov 26, 2017.

Spherical Maze Generation by Xue Li (Fall 2016).
	In this paper, we proposed an automatic spherical maze generation framework. Traditional mazes are generated on two or three dimensional spaces, with regular grids as walls and paths. Instead, we automatically generate a maze on the surface of a sphere, which provides a unique and fresh maze solving experience. Because regular grids on a spherical surface result in nonuniform room spaces, we randomly generate uniformly distributed points on the sphere. Then we automatically create the wall mesh structures by triangulation and Voronoi graph generation. Gift-wrapping algorithm and incremental construction are both conducted for the spherical triangulation. To create the spherical maze, the union-find algorithm is applied to remove parts of the walls, build the paths and join all the rooms.
VR Outrun Shooter by Andrew Dilks (Fall 2016).
	This is an implementation of a virtual-reality game in Unity based on table-top style gameplay, inspired by the classical game Geometry Wars. The main objective is to control a ship on a 2D plane and destroy the incoming obstacles, scoring the as many points as possible before being destroyed. Directional control and motion are implemented using head movement tracking provided by a VR headset. Here is a Sample Video showing the gameplay.
Autonomous Vehicle Intersection Management by Robert Adkins (Spring 2016).
	This paper explores the use of game theory to design an efficient algorithm for routing self-driving cars through intersections. Despite the discouraging exponential naive solution to this problem, there are some efficient optimizations which are exposed.
Algorithmic Game Theory by Robert Adkins (Fall 2015).
	This paper introduces some fundamental concepts to the field of algorithmic game theory. It also explores some of the known algorithms for calculating various kinds of equilibria in games, like the Lemke-Howson algorithm for finding mixed Nash equilibria and the Ellipsoid-against-Hope algorithm for finding correlated equilibria. After these ideas are introduced, potential applications towards autonomous vehicle tracerc routing are explored. This latter section yields the motivation behind my study of algorithmic game theory over the course of this semester.
Implementing the Held-Karp Lower Bound Algorithm in Python by Taylor Moore (Fall 2015).
	The Traveling Salesman Problem is a fundamental problem that arises in many diverse fields, from vehicle routing to genome sequencing to circuit design. Because it is an NP-Hard problem, it is primarily calculated via heuristics for graphs of non-trivial size. The Held-Karp lower bound provides a lower bound for the cost of the optimal TSP tour of a graph. Having the lower bound for a particular graph is useful for checking the performance of a given heuristic. This report details an implementation of the Held-Karp lower bound algorithm in Python. The implementation is based on the work of Valenzuela and Jones.
LPT Codes used with ROAM Splitting Algorithm by Joe Brosnihan (Fall 2015).
	Simplicial meshes are commonly used to represent regular triangle grids. Of many areas, simplicial meshes are useful in the area of terrain rendering within computer graphics. This project presents an implementation of Atalay and Mount's LPT code algorithm for representating a hierarchical mesh of simplices. In addition, part of the ROAM terrain algorithm that splits simplices down to a desired level of detail. Several modifications to the LPT code representation are also made and tested in several scenarios.
Water Simulation by Aharon Turpie (Spring 2014).
	This project attempts to render real-time the optical effects of the surface of water; such as reflection, refraction, and caustics. This is not a physical model, but only tries to render believable effects of them. The project was implemented using C++, OpenGL 4.4, and GLSL.
Euclidean Minimum Spanning Trees Based on Well Separated Pair Decompositions by Chaojun Li (Spring 2014).
	In this report we consider the implementation of an efficient algorithm for computing Euclidean minimum spanning trees, which is based in part on the well-separated pair decomposition, introduced by Callahan and Kosaraju. In order to compute the Euclidean Minimum Spanning Tree of n points in the space, one can naively link each pair of edges to build the complete Euclidean graph G=(P,E), where P stands for the vertex set, and E stands for set of edges, which consist of all pairs (p, q) for p, q in P. For such a graph we have \|E\|=O(n²), and combining this with the (E log V) = (n² log n) running time for the execution of Kruskals Algorithm, would result in an overall running time of O(n² log n). In this paper we present a more efficient solution.
Rigid Body Simulation by Jeremy Ulrich (Fall 2013).
	This paper describes a real-time 3D rigid body physics engine, and is the result of an Independent Study on collision detection and response in the context of rigid body dynamics. The simulation produces realistic motion, collisions, friction and resting contact between multiple bodies. The engine works mostly with convex polyhedra, and employs several tools in order to efficiently perform convexity-based queries and calculations. The collision detection system consists of a broad phase and narrow phase. The broad phase uses a uniform grid and bounding spheres, and the narrow phase includes the Separating Axis Test for determining intersection between convex polyhedra. The dynamics system employs a velocity-based constraint model for contact and friction constraints, resolves the constraints using an iterative Sequential Impulse solver, and calculates the motion of the rigid bodies.
Seeing Dual: Developing a Tool for Visualizing the Relationships between Convex Hulls, Upper Envelopes, Voronoi Diagrams, and Delaunay Triangulations by John Ingraham (Spring 2013).
	The Delaunay Triangulation, Voronoi Diagram, Convex Hull, and Upper (or Lower) Envelope are widespread geometric structures seen in many fields such as computational geometry and computer graphics. Their ubiquity and usefulness in various scenarios make them important constructs to examine and study if possible, but they can be difficult to visualize or draw without some sort of aid. In addition, there are some important and intuitive relationships between the different structures that are most easily conveyed with a cohesive and complete visualization. This paper describes a program that attempts to provide this visualization.
Particle Systems: Theory and Practice by Ciara Belle (Spring 2012).
	Modeling non-deterministic, complex objects is difficult using general techniques in computer graphics. Particles systems are used to overcome the difficulty of modeling these "fuzzy" objects, including clouds, fire, and water. Particle systems differ in three ways from normal modeling techniques. The first difference is that particle systems are not sets of primitive shapes and surface elements, instead they are clouds of primitive particles that define an object's volume. Second, particle systems are dynamic and are constantly changing form with the passage of time. The last difference is that the objects that particle systems attempt to represent are generally non-deterministic. In this paper, we provide a general introduction to the topic of particle systems, their definition and implementation, and we discuss various applications of particle systems.
Fluid Dynamics and the Navier-Stokes Equation by Steven Dobek (Spring 2012).
	Modeling and computing the motion of fluids is problem of fundamental importance in science and engineering. This paper presents a brief introduction to the topic. We begin by providing an introduction to vector calculus. Next, we give the Navier-Stokes equation and present an intuitive description of its terms. Finally, we present Stam's algorithm for performing stable simulations of fluid motion.
Rendering Crystal Glass Caustics by Alisa Chen (Spring 2011).
	While glassmaking and glass arts have been known since ancient times, it was not until George Ravenscroft added lead oxide that lead glass was invented, also called lead crystal or crystal glass. The attractiveness of crystal glass is due to its higher index of refraction and its dispersion of light. This results in a distortion of reflections of its surroundings and a creation of rainbows. Of particular interest to this study are caustics, the beautiful patterns the light formed due to the curved surface of crystal. Chromatic dispersion is included among these patterns. To render crystal glass caustics, this independent study researched photon mapping to enhance a basic ray tracer.
Circular Trapezoidal Decomposition by William Mennell (Fall 2007).
	Given a collection of line segments in the plane, a trapezoidal decomposition is a subdivision of the plane formed by shooting a bullet path upwards and downwards from each endpoint and each intersection point until it hits another segment. This is a structure of fundamental importance in comptutational geometry. This concept can be generalized to other sorts of geometric curves, by applying the bullet-shooting process not only to endpoints and intersection points, but also to points of vertical tangency on the curve. This project involves a C++ implementation of the Mulmuley's randomized trapezoidal decomposition algorithm, but for circles, rather than line segments. It uses a history DAG to store trapezoids. It is based on numerical computations using floating-point arithmetic, and some care has been taken to handle a considerable number of degenerate cases.
God: Object Oriented Programming in Macromedia Flash MX by Jordan Richardson (Fall 2005).
	This project is a study of object-oriented programming in Macromedia Flash MX. The concept for the project was to build an interactive environment that allows the user to control objects in space. These bodies behave similarly as they would under the natural forces of gravity. Each body contributes to the forces that influence every other body in real-time. The user is given the ability to create, size, and move these bodies around the stage. The user can also navigate through the spacial plane shifting it in any direction or scaling it causing the view to zoom in or out. The user is also given the power to advance the power of gravity thereby increasing the total energy of the system.
Revealing New Perspectives: Retrieving the Details of High Dynamic Range Images on Low Dynamic Range Displays through Tone Mapping by Chihiro Hirai (Fall 2005).
	Traditional monitors and printers are capable of displaying images in which luminances (that is, brightnesses) range over a small number of values (typically 256). Many modern digital cameras and computer graphics software are capable of producing luminance values over a much greater range, and so are called high dynamic-range (HDR) images. In order to display an HDR image on a low dynamic-range device, some transformation must be performed to avoid wash-out effects that arise when the high dynamic range is clamped to a the small dynamic range supported by the device. One such transformation is called tone mapping. We present an implementation of a tone mapping algorithm due to Larson, Rushmeier, and Piatko, and test it on a number of images. We show that out program often leads to a much more faithful representation the scene from the perspective of how it appears to a human observer.
Rediscovering Fire: A Survey of Current Fire Models and Applications to 3D Studio Max by Yulia Eyman (Spring 2004).
	Fire is arguably the most visually impressive natural phenomenon. It is also one of the most destructive and difficult to predict. Its physical properties vary with the fuel and temperature, and have been studied extensively by combustion researchers. In the field of computer science, fire's complexity is still an elusive problem. Many attempts have been made to model fire, both for visual and functional purposes, with increasingly successful results. The approaches can be subdivided into attempts to model fire as a texture, and the use of physical formulas to simulate its behavior. This paper presents a survey of existing research into fire representations and the fundamental components of 3D Studio Max that can be used to create animated fire simulations.
The Democratization of GIS and Applications in Community Planning: Development of the GURTIE System by Steven Helfand (Spring 2004).
	The Gemstone Urban Revitalization Team Interactive Environment (GURTIE) is a tool designed to overcome the political, social, and technological barriers that often prevent community leaders and residents from effectively utilizing information technology tools in neighborhood planning and management. GURTIE utilizes traditional GIS spatial data indexing, combined with non-traditional, non-spatial data capabilities for handling things such as contact information and event-based data. This report describes the system's architecture and implementation.
Roadmap-Based Methods for Flocking Motion with Obstacles by Tzu-hsiu (Kevin) Chiou (Spring 2004).
	The goal of this project is to create algorithms for controlling the motion of a group of entities in an environment with obstacles. In our research, we added new rules for flocking behavior, devised our own path-finding algorithm, and incorporated a number of optimizations. The result is an algorithm that allows accurate and efficient simulation of autonomous groups of objects in a complex environment.
Moons of Mars Explorer by Istvan Laszlo (Spring 2004).
	Mars' Moons Explorer is a realistic and accurate rendering of Mars' two moons, Phobos and Deimos. It is so because it makes use of shape models from Dr. Peter C. Thomas at Cornell University to provide the underlying shape of the moons. Mars' Moons Explorer gives you the opportunity to hover over Phobos and Deimos, orbit them, and zoom, while also providing orbital animation.
3D Physics Engine for Elastic and Deformable Bodies by Liliya Kharevych and Rafi (Mohammad) Khan (Fall 2002).
	The purpose of this project is to create 3D engine that displays the interaction of non-rigid bodies. As a part of our project we researched existing models for elastic and deformable bodies and algorithms for their collision detection and collision response. We have created a model of the object as a set of points connected by springs of given elasticity factor k. The model uses spring forces and damping to give elasticity to the objects. Object collisions are determined using our collision detection engine. After collision occurs the response is calculated using physics laws.
Path Sensitivity by Jawad Muaddi (Fall 2002).
	Path planning for minefields requires a consideration of risk and distance. Optimal paths through a minefield consider both factors. The sensitivity of a path indicates the likelihood of the path to change when mines are added or removed. This project studies the calculation and representation of path sensitivity. As a result of the experiments conducted in this study, we conclude that edges of a graph that are closer to the shortest path tend to be more sensitive, meaning that a change in these edges could result in a redirection of the shortest path. We found that shortest path edges tend to be sensitive to change in edge cost; these edges redirect with slight changes in cost.
Kinetic PR Quadtree by Ransom Kershaw Winder (Fall 2000).
	This project involved the design and animation of a new data structure called a kinetic PR quadtree. The impetus for this project was the desire to grant the traditional PR quadtree the ability to hold non-stationary data points with velocity vectors in finite, 2-dimensional space. The movement of the data points over time would change the structure of the PR quadtree's subtrees. The main focus of the project was implementing this ability for the PR quadtree and animating the changes in quadtree structure during the data points' movement.
A Ray Tracing Algorithm for Sphere Rendering by Aleksey Martynov (Spring 2000).
	This project involved a new algorithm for performing ray-object intersections involving spheres. It implements this algorithm as part of a ray-tracing program. The goal of the new algorithm is to minimize the rendering time by improving the average time of the ray-object intersection tests. The algorithm focuses on rendering spheres and presents spheres in 4-dimensional (sphere) space in order to optimize the structure of the resulting data structure for searching purposes. The results of the algorithm are compared against simple brute-force search method and enhancements to the algorithm are discussed.
On the Effective Use of a Web Page Design by Carina Hassan (Spring 2000).
To design a web site that is attractive and easy to use site requires some organization. There are many different combinations of Web page design that the developers can choose to use for their sites. In this report of the effective use of the different types of Web page layouts, we discussed what determines the basic elements of a good web-page design. The basic elements include color contrast, text organization, font selection, style of a page, page size, graphics used, and consistency.
Image Flaw Removal by Amy Yuan (Fall 1998).
	This project dealt with designing a program to perform flaw-removal in images. Given an image, the user specifies a rectangular region. The program removes this region of the image and attempts to fill it in as smoothly as possible based on the intensities of the surrounding area. This project studied a particular method of filling in the removed region, based on a dynamic programming algorithm. The objective function is to link together regions of equivalent intensity by the shortest possible paths.
Design and Implementation of an Interactive Ray Tracer by Maria Jump (Summer 1998).
	This project dealt with designing a ray-tracing program for computer graphics, which runs in real-time. Ray tracing produces very realistic images, but it is computationally very time consuming. In order to produce images in real-time, this program attempts to estimate the contents of the image, based on prior images, and then it redraws the image to increasingly higher levels of resolution. This project was funded by the Senior Summer Scholars Program.
An Implementation of a Recursive Ray Tracer that Renders Caustic Lighting Effects by Shu Cheah (Summer 1996).
	The project involves a rendering technique that takes into consideration caustic effects. These effects occur when light passes through some refractive medium, such as water or glass, which causes the light rays to bend.
Graphics Applets by Connie Peng (Fall 1996).
This project involved implementing a collection of applets to implement perspective viewing of a rotating object. This includes a simple wireframe viewer, a solid surface viewer, and an shaded surface viewer.
A Sampling of Applets by Ed Craft (Fall 1996).
This project involved implementing a collection of simple applets. They include an applet for the Towers of Hanoi, and a simple calculator.