Project Ideas

Spring 2000

  1. Lars Nyland, Lightning Reconstruction

  2. Anselmo Lastra, Audio Capture and Voice-Over Program

  3. Prasun Dewan, Undergrad Advising support system

  4. Stephen Aylward, CSA Five Star WWW

  5. Jack Snoeyink, TIN Digital Terrain Models.

  6. Jack Snoeyink, Map Drawing Tool

  7. Russ Taylor, Web-based meeting/submeeting scheduler

  8. Guido Gerig, User-guided 3-D Image Segmentation

  9. Guido Gerig, 3D Blob Detection for Psychiatry Research

  10. Laura Duggan, Web-based Punch Clock

  11. Ming Lin, Algorithm Animation (for COMP122)

  12. Ming Lin, Animation Toolkits for Physics-based Simulation

  13. Dinesh Manocha, Java Interface to Geometric Algorithm Libraries

  14. John Halton, CCE Exam Scheduler

  15. J. S. Marron, Statistical Image Analysis in Movies

  16. Carl Hatchell, Basketball Camp Scheduler

  17. Graham Gash, Crypto tool

Picks Page

Here are the project descriptions as sent to me

Feel free to ask me questions about the ideas, but please do not yet contact the proposers by email.
Lightning Reconstruction

From: "Lars S. Nyland" (

Lightning Reconstruction

Of interest to meteoroligists is the structure of lightning channels (the path of the bolt). Several researchers have developed methods of reconstructing the meso structure (1-5m resolution) of lightning, using audio information (thunder) from multiple disparate points with good success. The goal of this project is to create and end-to-end system that records, reconstructs and displays lightning from a complete storm. There are 3 major parts of this project, each is discussed below.

Thunder data acquisition. At least 3 (perhaps as many as 6) waterproof microphones and amplifiers will have to be set up with known positions to record the thunder. The microphones will be attached to sound cards in 1 or more PC's where the audio data can be digitized for further analysis. Software will need to be developed that allows a person to start the recoding of a storm, and data formats will have to be designed that not only record the audio information, but synchronization of the data between the microphones as well (timing is everything).

Thunder data analysis. The data, once collected (or perhaps during collection) will be processed to yield the physical structure of the lightning channel, along with the time that it occurred. This is an intensive mathematical problem, and should not be attempted by those without experience in linear algebra and differential equations.

Storm visualization. Finally, the physical and temporal data should be displayed using 3d graphics such as Open Inventor on the SGI's. Additionally, models and texture maps of the surrounding landscape may add interesting features to the display. Not only should the user be able to move through the storm spatially, but also temporally, replaying the storm as it develops and declines.

This project is suitable for only the most highly motivated developers, as it is a large task to complete in one semester. It requires at least one person to tinker with hardware, one mathematically inclined person to do the analysis, and at least two graphically oriented people to do the display. Additionally, thunder simulators may have to be developed, since there will (probably) be no thunder storms until late in the Spring. All hardware will be provided.

WE did this project last year... we will be extended it this year and making it work better.

Lightning Reconstruction (from Spring 1999 team)


From: "Anselmo Lastra" (

I'd like to have a team design and build an audio capture program to create
voice-overs for our new non-linear video editing setup. First let me explain
the typical way in which one of us creates a video to go along with a paper

First, you create a "storyboard". That's basically the outline of a script,
with some indication of what you'd like to show and the information you'd
like to provide with the voice-over. Then you write a script for the audio,
which usually consists of short segments. For example, in one segment you
might show a user in a HMD and describe how you use the mouse buttons to
"fly" in a virtual world. In the next segment you might cut to the video the
user would see and have some other information in the voice-over. Then you
get someone with a good radio voice, such as Mary Whitton, or Kevin Wolf
from WUNC, to record the audio snippets. You might time these snippets to
see how much video you need to cover the voice-over. You capture some raw
video footage and go edit the tape, cutting your video and synchronizing the
audio with the video.

The product I'd like is for the "talent", the person doing the voice-over. I
imagine that it will show the snippet of text to be read, capture the audio,
then allow the reader to indicate (say with a keystroke) whether it was OK.
It might allow the reader to record several versions. The output is a list
of WAV files labeled appropriately to go with the segments. The system
should run on a Windows PC.

This might be a good project for a team of undergrads because it doesn't
seem too difficult.


From: Prasun Dewan (

Yes, I am willing to be a client for a sync/async system for supporting
undergrad advising.

I want them to use the Bus Java infrastructure to do this.

Students who have taken my 290 will be ideal candidates for this.


From: "Stephen R. Aylward" (

I'd like to see the CSA recommendations info converted to searchable WWW
pages and forms.   You know, the database of comments on area


CSA Five Star WWW

The CS Departments Student Association (CSA) has been maintaining a
"database" on local area businesses.   CS members can add comments on
local businesses to this database, and search it for recommendations.  
Currently, the database is merely a directory of aptly named text

Proposal: Convert the CSA Local Area Business Database to a WWW-base
system.   The system will provide a star-based rating scheme, free-field
comments, multiple categories per comment, and searching.   The system
will be extensible and self maintaining.


From: "Jack Snoeyink" (

I can manufacture GIS problems, and try to find NC data for them; students
seem to like that.  Here is a project description and data description for
one that I have done before.

The files in this directory are for a project on 
TIN Digital Terrain Models.  
These have been assembled by Jack Snoeyink, 22 Jan 1999.


Let me start by describing one data file: 1/92g014-1.txt
This file contains a list of x,y,z coordinates as follows:
/* Facet_XDR_text_file - version 8 */
. 650 lines omitted.

These numbers are UTM coordinates (Universal Transverse Mercator),
which are roughly in meters from a standard reference point.  The file
name 92g014 says that this is UTM zone 9, map sheet 2g, and tile
number 14.  A map sheet is divided into 10x10 = 100 tiles, numbered
001 to 100, starting with the lower left corner. For more detail on
UTM, see


There are three directories: 1, 2, and 3.  Here is 
>ls 1
92g014-1.txt      92g033-1.txt.gz   92g045-1.txt.gz   92g064-1.txt.gz
92g015-1.txt.gz   92g034-1.txt.gz   92g046-1.txt.gz   92g065-1.txt.gz
92g016-1.txt.gz   92g035-1.txt.gz   92g053-1.txt.gz   92g066-1.txt.gz
92g024-1.txt      92g036-1.txt.gz   92g054-1.txt.gz   92g067-1.txt.gz
92g025-1.txt.gz   92g043-1.txt.gz   92g055-1.txt.gz   92g075-1.txt.gz
92g026-1.txt.gz   92g044-1.txt.gz   92g056-1.txt.gz   92g077-1.txt.gz

Each directory contains the same map tile, but has different numbers
of points so that the data for that map tile can be displayed with
different levels of detail.  We intended that there would be about 3
times more data in 2 than 1, and 3 times more data in 3 than 2.
Depending on results, we might increase this range. 
We can also supply some more map tiles.
You will note that all of the files are gzipped except for 14 and 24,
which contain Vancouver and are good ones to start with.  (They are
also smaller than most, since they have a higher proportion of water.)


I've included nnsort.c, by David Watson, for triangulation. This is
not the fastest nor the clearest code, but is portable and is
something I had laying around.  We have faster stuff that we've
written here, but it would take more time to set up a clean interface
and make it portable.

compile as: 
cc -o triangulate -O nnsort.c 
and you can run as:
triangulate inputfile outputfile junkfile 2

inputfile should consist of a list of just X AND Y coordinates.
For example, for 92g024-1.txt would become.
481525.0 5458163.0
481802.0 5458432.0
482062.0 5458547.0
. 654 lines omitted
481667.0 5456958.0
481214.0 5450455.0

The output file will then consist of lists of triples of vertex
indices that correspond to triangles.
To continue the example, 92g024-1.txt would give:
45 69 46
6 14 15
. 7 lines omitted
314 372 408
0 1 6
. 1273 lines omitted
173 183 658
174 658 183

The line 0 1 6 means that vertices 0, 1, and 6 form a triangle.  Going
back to the original file, this means we want a triangle with points:

Note the counting from zero.

The comments in the code mention a file of circle centers.  I've
changed this to the junkfile and commented out the commands to write
the entries in the junkfile which was writing out stuff that is not
relevant for this project (His circles would needed for an
interpolation method). The code still opens and erases the file, so
don't give it the name of anything important.

 D1. data quality issues: adjacent tiles overlap on the edges, so you
     may find that some points are repeated when you combine tiles.
     I'm not sure if the code handles this gracefully.  Don't forget
     to strip off the bounding box at the top of each file.
 D2. interface issues: Note that vertices are counted starting from 0,
     and that map tiles are started counting from 1.  (This is how you
     tell computer scientists from the rest of the world.) 
 D3. speed issues: If speed of triangulation becomes a problem, we can
     try to replace Watson's code with something faster. The fact
     that nnsort/triangulate works through files will slow things
     down---conversion to ascii and reading/writing files are
     sometimes slower than processing. Some timing from the unix time
	  #   real user sys
	 659   0.3  0.1 0.0
	1161   0.6  0.4 0.0
	3262   3.5  3.1 0.0
 D4. robustness issues: This code uses floating point and epsilons to
     compare numbers to zero, so there is a small posibility that it
     may make wrong decisions. If you ever observe a point set where
     it computes the wrong answer (e.g. overlapping triangles) save it
     for me, please.  

I don't recommend trying to read the code other than for curiousity.
It was clearly written by a FORTRAN programmer, and handles 3-d
tetrahedralizations as well as triangulations.

If any graphics-inclined group wants to draw things in 3-d, you'll
probably want to exagerate the heights by a factor of 2.

My email: Prof. Jack Snoeyink (  I'm doing a fair
amount of traveling this term, so I may not always be able to respond
promptly.  PhD student Michael McAllister ( is also
an expert in GIS and these data sets.

Thanks are due to Facet Decision Systems for giving the UBC
Computational Geometry lab access to the BC TRIM data, and to Shinjiro
Sueda and James Slack for extracting the data at different levels of
detail, and to David Watson for making his code available.


Project Title: Map Drawing Tool

Initial concept by Jack Snoeyink of The Department of Computer Science, UBC. Project Description written and adapted for CPSC319 by Peter = Smith.


A common application in the realm of GIS (Geographical Information = Systems) is the ability to  interpret a set of data points. These = 3-dimensional data points would have been obtained from satellite images and stored in large data files. To be useful, it is often necessary to view this data using a map visualization tool.

The purpose of this project is to develop a tool that can  be = used as a demonstration program,  rather than as a fully functional = visualization tool. It is intended to be used during the Department of Computer = Science's annual "Open House", to demonstrate the idea of Geographical Information Systems.

Functional Requirements

The user must be able to:

Non-functional Requirements

This software should be written in ANSI C++, using Tcl/Tk to provide a graphical user interface.

The data values describing the terrain are stored in multiple input files. Your software will need to scan these files to determine which = data points fall within the map being generated. In some cases, several = different files may need to be merged in order to draw a single map.

The basic data files contain a set of points. The client has provided prewritten code that will calculate a set of triangles from the point = set. To draw a map, you must simply plot these triangles in the appropriate colours.

Although the 2-dimensional drawing can be implemented using Tcl/Tk, the 3-dimensional drawing option should call upon an existing = visualization tool. For example, the map could be translated into VRML and then = displayed using a VRML visualization tool.

Due to the interactive nature of this tool, the time take to draw a map must be minimal (as perceived by the user).


From: "Russell M. Taylor II" (

A web-based meeting/submeeting scheduler.

This would be a web page where people could get together and schedule 
a set of meetings.

User view:
Each user fills in a schedule. You can add yourself as a user and add a
schedule. Schedule: Each 1/2-hour block from 8am to 6pm Monday through
Friday would have a field that says FREE or says BUSY. When you click
on a box, it toggles. They all start out saying "FREE".

The second part of each user's page lets them express interest in
subgroup meetings. Subgroups can also be added once the page has been
set up (wish list).

Scheduler view:
This page displays a matrix of the users down the side and the times
along the top. At the top of each line is the number of users who have
a conflict on that particular block. There is one page for the main
meeting and an additional page for each subgroup.

It is possible to click on times in the group/subgroup pages to
schedule the meeting. Whenever a meeting is scheduled, the blocks for
all users who expressed interest in that meeting become BUSY at that
time (this over-rides the value as long as the meeting is scheduled.
When the meeting is unscheduled, the value goes back to whatever it was

Also on the page for each meeting is a number showing the minimum
number of conflicts for any time, and the five least-contested times in
sorted order (to help the person doing the scheduling know what are the
best times).

The pages are intended to live throughout the semester, be kept up to
date, and thus be usable to schedule impromptu meetings between members
of the group.  


From: Guido Gerig (

User-guided 3-D Image Segmentation

3D imaging followed by image processing
to extract information about anatomical structures
is becoming a routine procedure in medical
diagnosis, surgical planning and even image-guided
Extracting structures from 3D image data requires
special tools which are appropriate to process
3D input data and to support the user with a
graphical visualization of the segmentation results.
A previous project developed the tool IRIS 
(interactive image segmentation) with some basic
functionality. This software prototype needs a
considerate redesign and significant extensions to become
useful for clinical research: 

- 3D graphical visualization of multiple anatomical
  objects in different colors
- improved quality of renderings by smoothing of
  binary data and/or by postprocessing of 
  the triangle mesh
- painting not only on image slices but also
  on the 3D surfaces of segmented structures
- providing a framework for selecting anatomical
  landmarks for coordinate transform
- embedding new approaches for volumetric data 
  manipulation rather than 2D region and contour 
- adding alternative contour drawing methods
- additional input and output image formats 

The software should be written following open standards
and software libraries already in use by our research
group (C++, OpenGL, FLTK-GUI, VTK) and should run on
PC's and under UNIX. The project would include a
review of the existing prototype, planning of the
significant extensions, addressing the challenging 
problem of user-interaction between graphical models
and the corresponding image data volume, and getting 
exposed to some driving problems in brain research at
UNC and Duke.


From: Guido Gerig (

3D Blob Detection for Psychiatry Research

The detection of blobby structures in 3D medical
images is essential for characterizing diseases
like multiple sclerosis and vascular lesions 
in age-related depression. The simple problem of
detecting and quantifying blobs in 2D becomes a
difficult task in 3D as 3D image data can only be
presented as a series of slices. An automated and
reproducible system could have a high impact on
patient studies and would give a much better insight
into the course of the disease and the statistics of
the spatial distribution.
A prototype system for automatic blob characterization
has been implemented in AVS (application visualization
system), including detection of blob center candidates
(seeds), inspecting level-sets around these seeds, 
testing and verifying the sought shape, and providing 
some limited user-interaction and visualization for 
manually adding and deleting blobs.  
A clinically useful system would require a complete
redesign of the software and a wrapping into a modern
GUI with visualization of original medical image data 
and 3D graphical visualization and manipulation
of the segmented structures. Further, blobs are 
characterized by a list of morphometric attributes like
position, size, shape features and contrast which is
the resulting output for further data analysis.

The software should be written following open standards
and software libraries already in use by our research
group (C++, OpenGL, FLTK-GUI, VTK) and should run on
PC's and under UNIX. A prototype tool for interactive
3-D image visualization and segmentation, IRIS, is 
available and could be used as a template. 

The project would include a review of the existing 
prototype system, the planning of a redesign of
the necessary modules and components, the design of
a suitable visualization for verification of the
automatic segmentation in comparison with the original
image data, the development of user-interaction
to edit the segmented blobby structures, and the
development of suitable datastructures for manipulating
the list of segmented objects with their attributes.


From: Laura Duggan (

We have a suggestion for a class project. Facilities needs a web based
punch clock for our students.
Basically, we'd like a simple web form that lists the student
employee's name, in/out status and a field where they can enter their
current location. We'd like the data itself to be stored in an ODBC
database (since we may wind up in a year or two using an AIS database
to store the data). For authentication, ideally it would hit against
the NT or Unix passwords, and also be on an encrypted connection
(although the latter may well not be possible), so that a user could
change their own data, but not anyone else's. Additionally, we'd need:

1) Web based administration:  Such that the administrator could
add/delete users names and override data entries. We'd want to have a
list of administrators, who would be facilities full time staff.

2) Logging ability - track who made what changes, the machine they
logged in from.

3) Notification of failure to check in or out. We'd like to have a
schedule online against which this system would check such that if a
student failed to show up for a shift or check out, the system could
send mail to student/supervisor.


From: Ming Lin (

Project:  ALGORITHM ANIMATION (for COMP122:  Algorithms & Analysis)

Short Description: To develop and implement algorithm animation toolkits
or Java Applets to illustrates how an algorithm (within the scope of COMP122) 
actually works.  Here are a few simple examples:

* Sorting Methods: Implement a collection of ordering and sorting methods 
(select $k$-th smallest element, insertion sort, quick sort, etc.)

* Red-Black Tree:  Implement a suite of red-black tree operations
described in the 122 book and the lectures.  Display the program output with a
graphical display (similar to those pictures in the book), so the user can
view the insertion, deletion, search of a key to an existing red-black tree.

* Graph Algorithms:  Implement graph algorithms taught in COMP122 and 
display its working step by step.  

How:  You may use whatever existing programs (such as those offered by
the 122 instructor from her previous courses, etc.) and other available
algorithm animation software such as Polka/Samba developed at Georgia
Tech to enable the user to view how the algorithms (covered under the
scope of COMP122) work step by step VIA THE WEB.  Or, You can write the 
entire algorithm animation by yourself.  There are many other possibilities, 
such as applications of the algorithms to a ``real-world'' problem and the 
animation of the algorithms solving the problems.  Be as creative as you 
want with your team members.  

Skills Required:  Ability to program in JAVA and have taken 
COMP122 (Algorithms and Analysis) or COMP202.


From: Ming Lin (


Short Description: To develop and implement algorithm animation toolkits
or Java Applets to illustrates how some simple PHYSICS-BASED MOTIONS can 
be generated with different numerical methods.  Here is a simple example:

* Given the mathematical model of the spring forces, develop a simulation
program using various numerical methods:  Euler, midpoint, RK4.  These
mathematical formula will be given by the client.   

Skills Required:  Ability to program in JAVA, knowledge of basic
calculus, have taken a computer graphics course such as COMP136 
or COMP235/236.

Recommended Background:  Have taken a numerical analysis course
at any level or COMP205


From: Dinesh Manocha (

(for physics-based simulation)

Short Description: To develop and implement a JAVA interface
or to develop a Java3D implementation of the popular existing
collision detection software libraries, RAPID, V-COLLIDE or PQP
(developed at UNC). Some of the applications of this package will 
applications simulating  game dynamics and interaction with virtual world.

Skills Required: Ability to program in JAVA or JAVA3D;
basic understanding of computer graphics and geometric

Recommended Background: Have taken COMP136 or COMP235/236
and like geometric algorithms.


From: John Halton (

Subject: Re: COMP 145.. last call

This is to request a team to work on an automated scheduler for the
QUAL.  Completion is due shortly before last class day.  I am willing 
to collaborate with the team to produce a truly usable product 

The programming should be in "C", so that I can understand it!  
(Fortran or Pascal are ok, too; but C++ and Java are out.)

Input will be data-tables giving (i) all (<60) candidates' sets of six
courses each, (ii) all (<30) professors' sets of course-competencies in
all (<40) courses.

Output will be exam schedules (date, time, location, candidate, 3
examiners, 2 courses).

The algorithm will be given in outline; details to be agreed on.
Special provisions must be honored; each candidate has 3 exams (no two
on same half-day), 9 different examiners in all, at least two examiners
in each exam must have competency over given threshhold for the two
given courses.  Examiners may have exceptions (few) and load must be
reasonably balanced.  The goal is to lessen the total duration of the
exam.  Some situations are impossible to solve; minimization is too hard
to achieve; but pretty tight exams have been scheduled by hand with a
similar algorithm to that proposed.


From: "J. S. Marron" (

Background material is on my web page:

I am doing image analysis, using scale space methods (essentially just
a family of smooths of the underlying image, of the type that Pizer &
Co. work with a lot).  My particular angle is to highlight "which
features in the image are really there?", as opposed to being
"background noise artifacts".

There is some reasonably well developed Matlab software that is posted

An improvement that I would like to make (but I am not a good enough
programmer to do it) is to the "streamlines" version of my method
(that is the one that ookes like "green hair" on the web page).  If
you run the movie that is labelled sss1fig6b.mpg (click the "here" on
the web page), then you will note that the effect is not visually
pleasing (while some of the other movies on that web page are much
nicer).  The problem is that the important green lines herk and jerk
as the movie runs.  This is caused by the fact that a randomization
method is used for the green lines, and I currently re-randomize for
each movie frame.

What I would like to suggest as a class project is an implementation
where these lines evolve smoothly through the scale space.  This means
that as time goes by in the movie, the lines will appropriately grow
and shrink.  I think some careful data structure work is needed to get
this right, and wonder if that is the right level of problem for your


From: "Carl Hatchell" (

The basketball camp scheduling program again.

e-mail --


From: Graham Gash (

I am interested in cryptography and recently read Simon Singh's
"The Code Book", which contains a lengthy, multi-part encoded
message for the reader to solve.  There is a $15,000 prize for
the solution, incidentally.

Being presented with this puzzle, it occurred to me that it
would be fun to write a program to solve it (and also much
easier than doing it by hand).  What I envision is a toolkit
of decryption algorithms and a user interface for coupling
them together, reviewing the output at various stages, and
providing guidance for how the program should proceed in
successive stages.

The interface should probably be in FLTK (to assure machine
independence) and should not be difficult to implement.  A
number of text-manipulation algorithms will be needed for
transposition, alphabetic substitution, frequency analysis,
etc.  Slightly more sophisticated algorithms will be needed
to implement such methods as Vigeniere, Playfair, and enigma
machine ciphers.  I would prefer that the code be in C++, or
possibly C, but would entertain suggestions for the use of
other languages that may be more appropriate.