Student Project Proposals
When I was a student at McGill University in Canada, I worked on a wide variety of undergraduate projects, that ranged from cellular automata to genetic algorithms, from mathematical visualization to flame animation. In one of my projects, I developed a novel algorithm for rendering of stained glass effects. Only recently the problem has attracted the attention of other researchers in computer graphics.
My Stained Glass Program
Project Proposals 2002-2003
Adapting Partition to Fit A Data Set: How can Voronoi diagrams segment an image into homogeneous regions? The Voronoi diagram is the fundamental spatial data structure of computer science. Given a list of sites in the plane, a Voronoi diagram assigns each point in the plane to its nearest site. The result is a subdivision of the plane. The Voronoi region around each site consists of the points closer to that site than to any other site. When proximity is measured by Euclidean distance, these Voronoi regions are convex polygons which partition the plane. Now suppose a Voronoi diagram is being used to represent a grayscale image by coloring the Voronoi region of each site according to the grayscale value sampled at that site. Alternatively, the color of a Voronoi region may be determined by the average grayscale value of the part of the image covered by it. How can N sample sites be placed on an image so that it is optimally approximated by a Voronoi diagram? Given an image and a Voronoi diagram with the first N sampling sites, what is the optimal location to place the N+1 sample site? Since Voronoi diagrams are known to provide a flexible and efficient way of segmenting an image based on a given point sampling of the image plane, an adaptive sampling scheme that yields an optimal segmentation would prove quite useful in many practical situations. Such a complex optimization problem is unlikely to have a simple analytic solution. Hence it is worthwhile to consider physics-based simulation methods. Another approach is to apply stochastic optimization techniques, such as evolutionary strategies, genetic algorithms and simulated annealing. To learn more about Voronoi diagrams go to Geometry in Action and to know more about possible optimization strategies visit the Hitch-Hiker's Guide to Evolutionary Computation.
Efficient Calculation of Spatial Partitions: What is the quickest method of updating a Voronoi diagram whenever a new site is added? In practical applications, algorithms that calculate discrete approximations to the Voronoi diagram are often preferred for their simplicity and speed. While there are efficient algorithms for calculating the entire discrete Voronoi diagram from scratch, much less is known about how best to progressively update a Voronoi diagram. A good algorithm would take advantage of existing hardware, such as a graphics card or a second processor. I have an idea for just such an algorithm and perhaps you could compare its performance to existing solutions. The implementation would be good exercise in optimizing low-level code, where every arithmetic operation counts.
User Interface Design:
Visual Transitions for Navigating the Web: What would be the appearance of a web site if it understood what its reader is looking for? In the competition for attention, the presentation of information requires the design of engaging interfaces that facilitate creative exploration and foster a sense of community among users. Beyond the traditional graphical effects of multimedia, there is a need to define dynamic transitions between web pages that are more effective at conveying a sense of navigation. A simple analogy: what I see in the brief time it takes me to walk from one room to another not only gives me a sense of the layout of the entire house but may also influence where I choose to go next. Between the time that a user clicks on an web link and the time when the new page is finally loaded, there is an opportunity to display animated effects that would communicate context-sensitive information, bringing to the user's attention such features as keywords, title headings, thumbnail images and alternative links. Another possibility is to design animated previews for web pages that could act as visual tooltips to be displayed when the mouse hovers over a web link. For a tour of visual representations of the web, visit The Atlas of Cyberspaces.
Ben Fry's Information Visualization
And Everything Else:
Here is a list of some of my favorite publications and tutorials to serve as starting points for your projects:
Painting with Natural Textures
by Michael Ashikhmin
Also here is the original natural texture synthesis article and sample images.
Another approach is described in the image quilting article as well as these PowerPoint slides and sample images.
Decorative Printing by Shape Blending
by Victor Ostromoukhov and Roger Hersch
Also here is the original artistic screening article and video.
Automatic painting with brush strokes
by Michio Shiraishi and Yasushi Yamaguchi
Also here is a quick summary of a related technique.
Creative design of decorative patterns
by Eiji Ito and Shun Ishizaki
Also here is an online course about nature-inspired design.
Draw Celtic Knots
by Steven Abbot
Also here is a knot drawing tutorial.
Project Proposals 2001-2002
Simulating Collective Motion: What is the motion of a flock of birds or a school of fish? Take a look at Craig Renold's Boids Model where simple local interactions between individuals give rise to the complex global behavior of the entire group. Each autonomous individual adopts a steering strategy to stay close enough to its immediate neighbors so that it does not get separated from the group, while being far enough from its neighbors to avert being an obstacle in their way. At the same, its choice of motion may be motivated by one or more goals. For example, a migrating bird tries follow a set flight path while seeking food and avoiding predators. Many possibilities can be explored, such as a sheep dog tending sheep, a pack of lions hunting a herd of zebra, or a crowd of people hurrying along a busy thoroughfare. In many computer games such algorithms provide the artificial intelligence needed to control simple virtual characters.
Craig Renold's Flock of Boids
Creating Decorative Mosaics: How would you transform an image into a decorative tile mosaic? The goal is to represent an image by an arrangement of geometric tiles orientated to emphasize image features, such as edges, while maximizing the area covered by the tiles. In SIGGRAPH 2001, Alejo Hausner presented one method. Can you improve or generalize it? In what order is it best to place the tiles? What if every tile was a trapezoid of a different size instead of a rectangle? Could an animation be created out of moving tiles? What if the tiles were made out of chipped stone or glass instead of monochromatic plastic? What would be a good user interface for interactive tiling? Take a look at Alejo Hausner's Simulated Decorative Mosaics paper to find out more.
Alejo Hausner's Mosaic
Copyright © 2002 Mark Grundland. All rights reserved.