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.

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 Dec 10, 2005.

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.