HomeDo You KnowWho we arePast projectsResearchContact infoRelated Sites

Project Descriptions

Over the past several decades, our work has had many facets. It has included analysis and implementation of computer graphics, mapping and geographic information system techniques and applications, user interface design, specifications and prototypes. Here are some highlights:

  Demonstrations and Gallery Exhibitions

  Cartographic Symbolization

  Evaluation of Software Applications and Systems

  Spatial Database Design

  User Documentation and Help Systems

 

Selected Demos and Exhibits

American Graph Fleeting

The first (and perhaps only) animated thematic map to be produced as an integral hologram, a rotating celluloid cylinder within which a 3D demographic map of the United States hovers. US Census counts of population by county from 1790 to 1970 were uniformly interpolated to an equal-area grid and displayed as statistical surfaces. The grids were interpolated to one-year intervals, yielding 181 maps. These were filmed in sequence along with titles and the 16-mm animation was transferred in three batches to integral holograms, which are wrapped around a plexiglass cylinder 18 inches across. A clear light bulb below the cylinder provides illumination for reconstructing the images, which rotate and change in time as the display revolves. American Graph Fleeting was produced for the 1979 Harvard Computer Graphics Week Conference, and has been displayed at The Computer Museum in Boston, Place Pompidou in Paris and on public television.

US Population Surfaces

Upto Top

American Air Lines

Patterns of air transport across America are the theme of this animation, which presents time-lapse views of 7,500 daily scheduled flights between 35 major U.S. cities, based on data from Official Airline Guide for Winter 1980. The AIR (Animated Information Retrieval) program, written in FORTRAN to drive a Tektronix 4027 color display, "launches" airplane icons at scheduled departure times and follows their approximated courses to their destination city. Cylindrical towers rise from each city to symbolize the number of incoming flights. Time is incremented in user-specified intervals to update the positions of all active flights, and the background US map portrays time zones colored to indicate time of day or night. AIR played at Harvard Computer Graphics Week in 1981, and images from it were subsequently displayed in other exhibitions as a slide show.

Animated Airplane Schedules

Upto Top

The Computer and the Image

The Computer Musueum of Boston relocated to its current quarters and opened to the public in 1985. Curator (now Director) Dr. Oliver Strimpel and Geoffrey Dutton planned and executed a number of exhibits for the computer graphics gallery, "The Computer and the Image." Static exhibits he produced included a display of early computer graphic input and output devices, examples of digital typography, the holographic animation American Graph Fleeting (see above) and A Visualizer's Bestiary, a tableau of real-world objects that have vexed programmers attempts to render them naturalistically. Dynamic exhibits included Tempest over a Teapot, featuring Allan Newell's original ceramic teapot alongside an Adage frame buffer display of a Bezier model of it, both responding to changes in lighting that viewers create with switches. The exhibit A Window full of Polygons depicted the view of downtown Boston that visitors see from the gallery on a large pen plotter that renders the buildings' silhouettes with changing colors and patterns. We also composed descriptive text panels and technical documentation and guided Museum staff, vendors and volunteers.

visit The Computer Museum

Upto Top

Fuzzy Features Theater

This demonstration of the effects of locational uncertainty for digitized lines was prepared for a research symposium on visualizing the quality of spatial data in 1991. Programmed in HyperTalk in the HyperCard environment (a Macintosh O-O scripting utility), Fuzzy Features Theater described and illlustrated a model of positional error for lines, and simulated its practical consequences using polylines and polygons sketched by the user. The theory was illustrated via monte carlo simulation of a straight line, endpoints of which were randomly, independently perturbed in a circular Gaussian distribution. From this simulation data, confidence intervals were constructed to show the probable locus of the line segment for a given

Fuzzy Features Theater

user-specified error tolerance. How this model might effect the handling of map data was communicated by constructing error circles around hand-digitized points and confidence bands around the lines connecting them. Such user-conducted experiments demonstrated the consequences of attempting to make precise area measurements using uncertain geometric data; this was underscored by computing and displaying statistical moments, and generating by animations tracking equiprobable Gaussian realizations of the sketched figures.

Upto Top

Cartographic Symbolization

Fractal Enhancement of Cartographic Lines

In collaboration with Dr. Benoit Mandelbrot, Geoffrey Dutton developed software to measure and manipulate fractal/self-similar qualities of cartographic shapes in 1979 and 1980. In a series of experiments, polylines were analyzed using the "walking divider" method to estimate their dimensionality and degree of self-similarity. A geometric method was devised to add deterministic self-similar detail to lines at a specified fractal dimension, and smoothing was applied to soften the jagged appearance of lines that often resulted from such treatment. The method works by inserting vertices at the midpoints of segments along a polyline (potentially doubling the number of points along it), then adjusting the angles at existing vertices to correspond to the target fractal dimension. The procedure could be iteratively applied to new vertices introduced at midpoints to create finer and finer self-similar details, under the control of six parmeters. The goal of the work was to better understand the fractal characteristics of different types of map data, and to provide a controllable, deterministic way to enhance the detail of cartographic lines when zooming into a map database beyond its limit of resolution.

Fractal Line Enhancement

Upto Top

Multi-color Hillshading

Named after the most famous pointilist painter, Georges Seurat, the Seurat program rendered gridded digital elevation models (DTMs) using 2x2 blocks of "pure" color pixels to symbolize four parameters of terrain at each grid location across an image. Pixels coding intensities of Elevation (usually in red), Slope (blue), Roughness (green) and Aspect (yellow) were interlaced in a regular pattern that allowed the eye to optically mix their colors, yielding a perception of a continuously varying field of natural-appearing hues that communicated shaded relief. Images were 2D only, and were limited in size and resolution by the display devices available at the time (1980), which typically could address 512x512 pixels with a programmable palette of 256 colors. Nowadays, of course, even PC displays allow millions of colors at two or three times the resolution, and this would allow Seurat's images to be even more detailed and striking.

Seaurat four-color hillshading

Upto Top

Terrain Perspective Viewer

In 1985, we developed a workstation for Air Force pilots to use for planning missions involving unfamiliar terrain that they might subsequently fly over at low altitudes. The Terrain Perspective Viewer (TPV) displayed 3-arc-second DEMs in shaded relief in a 2D flight-planning window, and the field of view in a 3D viewing window. Users could input flight parameters via a control panel, and set aircraft locations and azimuths directly in the 2D window, as they plotted their flight path. The system, based on a Sun 2 Unix workstation, could then animate the field of view, stepping along the flight path to render the terrain outside the windshield. The application was written in C using Sun's SunView and SunCore libraries. A photo hardcopy unit was attached for users to print terrain images to refer to during during flights. The TPV was taken into the field for use during Operation Desert Storm.

Upto Top

Software System Specifications and Evaluations

Tactical Flight Simulation System

In 1986, after winning a bid to enhance the Terrain Perspective Viewer (see above), we led a team of software analysts in the specification of an object-oriented mission planning system. In addition to displaying terrain relief, this platform was designed to overlay satellite and airborne imagry, along with data for boundaries, obstacles and hostile installations on the displayed 3D surface. The system was composed of core utility modules and "manager" modules that communicated via messaging. Objects were specified using C syntax, pending final decision on an O-O programming language, and system architecture was specified via SADT methodology.

Upto Top

Polygon Processing Specification

In 1990, a functional specification was prepared for Prime-Wild GIS, Inc. to guide development of a spatial overlay capability, most of which was subsequently implemented in the System 9 GIS. The report specified a comprehensive set of criteria for manipulating the geometry, topology and attributes of GIS data encoded as "complex features" consisting of point, line and area primitive elements. Requirements for intersecting lines and polygons and for computing containment of point entities were specified, including the capability to employ multiple "fuzzy tolerances" to handle positional uncertainty. The specification was implemented in the System 9 Polygon Processing module, released in 1991.

Upto Top

Linear Reference System Evaluation

The need to understand how transportation agencies model locations along highways and to make these approaches more interoperable was the focus of a study performed for the Federal Highway Adminstration in 1992-93. The study determined that three basic approaches were in use, but each state DOT implemented them slightly differently. To facilitate sharing of highway data at various levels of government using dynamic segmentation GIS technology, the study recommended a set of guidelines that would make different linear referencing systems more compatible with one another without requiring DOTs to completely reorganize their data formats and existing software. The study was used as input to a project to develop a national digital highway network map to be made available to all interested state and federal agencies.

Upto Top

Spatial Data Modeling

GEM Global Terrain Model

A search for ways to represent terrain and other continuous geographic surfaces led to the invention of a global, recursively triangulated structure named GEM (geodesic elevation model) in 1982. Following some ideas of R, Buckminster Fuller, the earth was treated like a giant geodesic dome, constructed by first triangulating an initial octahedron by forming new triangles connecting its vertices and face centroids, and continuing this process recursively until the resultant vertex spacing approached the limit of horizontal accuracy given for whatever set of spot heights served as input data. Exploiting the insight that in any regular DEM vertical accuracy is constrained by horizontal grid spacing, the heights of GEM vertices above or below sea level were adjusted upwards, downwards or not at all in fixed increments that decreased as resolution increased. This allowed elevation coding to be standardized at two bits per vertex, and segmenting the structure into sub-trees enabled resolution to vary from place to place. GEM was never fully implemented, but inspired later developments in spatial data modeling.

Upto Top

Lightning Event Database

Also in 1986, another customer asked us to design a database system for meterological data collected via modem from a facility that monitored strikes of lightning across the U.S. eastern seaboard and provided their locations in real time. In its source format the data had little utility; the customer desired a database to be designed allowing easy retrieval of lightning events across specifiable extents of space and time. A quadtree store for the point events was designed that maintained sorted lists of observations, each coded with the time and severity of events across a hierarchy of scales, emulating an octtree. A command-line user interface was added to enter input files into the database, report global statistics, and plot TTY graphics of events at discrete steps of distance and time, as well as a facility to generate formatted summaries of query results. The software was written in C and operated on a s standalone 386 DOS PC. It successfully handled several millions of lightning event records.

Lightning Strike Database

Upto Top

QTM Hierarchical Coordinate System

Building on the geodesic elevation model described above, Dutton proposed a GEM variant for storing and retrieving planimetric data at differing spatial resolutions in 1989. The octahedral quaternary triangular mesh (QTM) modeled a planet as a recursively triangulated octahedron, organizing data as a forest of eight triangular quadtrees. Each quadtree address ("QTM ID") identifies a specific triangular region of the earth's surface that never changes; longer IDs describe smaller regions, and average face area decreases by half at each level of detail, with four child triangles nesting within each parent face. The number of quaternary digits in a QTM ID specifies the precision with which a location is known, related to the accuracy and scale of source data from which it was digitized. Some applications of QTM stress its role as a spatial indexing scheme (because it partitions locational data across a range of scales), others have developed variants to access rasterized data (such as global terrain data), similar to an image pyramid, but using triangular pixels that subdivide a sphere. Dutton's own work with QTM has focused on its ability to determine the useful resolution of vector map data, and to retrieve it at coarser scales than it was encoded at. This has resulted in a set of line generalization techniques that relate spatial resolution to map scale, and provide a number of alternatives for reconstructing line vectors across a range of scales. By storing QTM IDs in place of geographic coordinates, scale-specific retrieval is possible, and by including coded qualifiers in the IDs, information about the role of each point in a line can be communicated to applications, without the need to specifically allocate storage for such metadata. Dutton has published fundamental algorithms for encoding and decoding hierarchical coordinates, and QTM spatial indexing has been implemented in a number of commercial mapping products.

For more about QTM, please see our Research pages.

Upto Top

User Documentation and Help Systems

The Picture Environment

For a continuing education course in computer graphics that Denis White and I taught between 1980 and 1982, we developed an on-line teaching environment for students to use during lab sessions. The Picture Environment provided a shell program and a set of comands to access software and demos, a text editor for preparing code and data and a detailed hierarchical help system. The shell was written in VAX DCL (DEC's interpreted scripting language), and made use of various VAX/VMS utilities including compilers, the linker, an editor and the help system. Native VAX commands were called from a keyword interpreter, and VAX commands that users should not use (like MAIL or DELETE) or only use in certain ways (like CREATE or DIR) were filtered. The environment provided a friendly place to concentrate on exercises, and provided a separate workspace for each student, which other students could "visit" (in read-only mode). Denis's Picture program was the central application; it also interpreted declarative commands that let users specify elements of pictures (points, lines, circles, polygons, text) along with their positions, size, orientation, color, etc. properties. Students would prepare text files and then view them in Picture (written in Fortran and called from the environment). More advanced students could code graphics programs themselves in several languages, calling on our device-independent graphics library (modeled after the SIGGRAPH Core Library), which was linked in automatically for them.

Upto Top

Odyssey Tutorial System

Odyssey was a vector-topological geoprocessing system developed at Harvard between 1978 and 1984, a proto-GIS. Among its many features and modules was a choropleth mapping program, Polyps. Like all Odyssey modules, it was command-driven, using an English-like command language interpreted by a lexical and semantic analyzer. Commands could be input interactively, or read from a text file. We modified the command interpreter to treat certain comment lines (which were normally thrown away before parsing) that began with the symbol "$." as command imperatives to present text to the user, obtain responses from her to conditionally execute commands, index sections of tutorials hierarchically, and several other functions. Users could type their own commands to Polyps at any time while executing tutorials. Lessons were divided into topics, andthese could be revisited. Most topics included commands to Polyps to define aspects of maps or draw them. As tutorials were just extensions of batch command files (which already could call one another), it was simple to turn any Odyssey batch procedure into a demonstration by adding strategic comments containing text messages or control statements.

Upto Top

Home