This document outlines a number of projects available for Honours and MBC students in 2000. The projects are generally in the areas of computer graphics, human computer interaction, computational geometry and distributed computing.
The approach of calling for volunteers to assist in distributed computation efforts has seen several applications recently (SETI, DES cracking). Typically these programs must be downloaded and installed on the volunteers machines.
This project is to use Java and applets so that volunteers may join a community computational effort by accessing a web page.
Molecular dynamics is used to investigate the behaviour and properties of molecular systems. Typically, molecular dynamics is computationally intensive.
This project is to implement a distributed version of a molecular dynamics code. The distributed implementation may use Java and MPI (message passing interface) and a community computing idea (above). It could also use C, C++ or Fortran 95.
We, together with a number of honours and masters students, have been exploring 3D user interfaces for several years. So far the work has used a tunnel metaphor for a window manager combined with a 3D cursor for direct manipulation.
This project is turn the existing implementation into a working GUI by reimplementing it for Linux using the appropriate Open Source components (SGI OpenGL SI or Mesa, XFree 4.0, GLX).
The Tunnel 3D GUI project (above) uses a tunnel metaphor. However, other metaphors, or indeed, non-metaphor designs, will most likely prove superior 3D interfaces.
The project is to design, implement and evaluate a different 3D GUI prototype to the tunnel. See the NYSE 3D trading floor designed by Aysmptote as an example of a 3D user interface.
At present the most common geometric modelling formats are polygon based. This includes VRML. Typically it makes sense to display models at a level of detail appropriate to a particular viewing situation. In particular, when objects are far away there is little point in rendering lots of polygons. Similarly, when transmitting large models it may be advantageous to use a progressive approach where an initial simple model is gradually improved.
The project is to investigate levels of detail and progressive transmission of polygonal models in VRML using the Kirkpatrick data structure.
The Kirkpatrick data structure for representing convex polygons is the basis for a number of worst-case or near worst-case optimal intersection detection algorithms. However, the algorithms are difficult to implement compared to simple bounding volumes such as boxes as sphere, and their practical value is unclear.
The project is to investigate the practical performance of the Kirkpatrick data structure for detecting intersections of convex hull (i.e. convex polyhedron) bounding volumes of polyhedral objects. This project build on work done by Sean O'Sullivan (Honours 1999) on myself.
Graphs are a central structure in computer science. Algorithms for laying them out in two dimensions 2D have been investigated over a long period. More recently, algorithms for laying graphs out in 3D and associated browsers have been investigated.
The project is to investigate a 3D graph layout based on orthogonal line segments. Orthogonal line segments are line segments restricted to being parallel to one of the principal axes. One familiar 2D example is the typical organisational hierarchy chart. This project builds on work done by two former students --- Tony Saveski (Honours, 1995) and David Drummond (Masters by Coursework, 1996) --- who considered other approaches to 3D graph layout . It is anticipated that the project will use VRML and Java.
A need which arises in computer based design and modelling applications is to precisely position two objects in relation to each other. For instance putting a key inside a lock or positioning a lamp on a table.
The project is to investigate techniques for interactive docking of polygonal objects. The project continues work begun by Chris Chen (Masters by Coursework, 1997). It will involve using C or C++ and OpenGL or Open Inventor.
2D font description is a mature technology. Typically some form of spline based representation is used for fonts which are intended to scale. As the point size (scale factor) increases, the spline representation typically needs to change to include more detail. This is a variant of what is termed the level of detail problem.
In 3D applications, particularly 3D publishing applications (using VRML for example), 3D fonts are needed. Typically these are extruded versions of 2D fonts. The project is to investigate true 3D font design and the issues of representation and level of detail description. The project will use VRML 2 and Java.
Molecular dynamics is a widespread technique for simulating the motion of molecular structures over time. For a molecular structure of, say, a hundred atoms, using a one femtosecond time step and saving the atom positions every 20 femtoseconds for a one nanosecond simulation requires: 100x50000x3x4 =~ 60MB. This assumes the positions are saved as 4 byte single precision floating point numbers. Typically the trajectories are actually saved as ascii with 8 characters per number - doubling the space requirements.
The project is to investigate geometric compression techniques for molecular dynamics trajectories. In particular the compression of molecular dynamics trajectories saved in the VRML 97 modelling format for publication on the web - where minimising the size of files is particularly important. The project would involve the use of C or C++, perhaps Perl, Java and VRML 97.
It builds on work in 1998 by James Gilbert (Honours) and myself which was presented at VRML 99 (Fourth Symposium on the Virtual Reality Modeling Language).
Virtual worlds can be quite large. Typically though, only a small fraction is seen by a viewer in a particular location. The project is to investigate an approach based on efficient data structures for handling orthogonal bounding boxes may be used to cull as much detail from virtual worlds as possible.
The project continues work done by James Walker (Honours, 1994). His results show that an approach to the colour quantisation problem based on nearest neighbour clustering algorithm is promising. The challenge now is to implement the approach efficiently. Implementing the data structure we have in mind (worst-case optimal nearest neighbour data structure) to do this is a challenge --- due to the sophistication of the data structure rather than the amount of code (which should in fact be quite small, say around one thousand lines of code) --- and requires someone who enjoys complex programming.
One of the important considerations for virtual worlds and objects, including 3D games, is dynamical behaviour (motion). For entertainment purposes the dynamics need not be based on real world dynamics --- in fact, more entertaining behaviour is achieved by deliberately not using real world dynamics.
The project is to investigate the design and implementation of approaches to describing toy, cartoon or "blocks world" system dynamics.
Geoff Leach