Previous accelerated volume rendering techniques have used auxiliary hierarchical datastructures to skip empty and homogeneous regions. Although some recent research has taken advantage of more efficient direct encoding techniques to skip empty regions, no work has been done to directly encode homogeneous but not empty regions. 3D distance transforms previously used to encode empty space can be extended to preprocess homogeneous regions as well, and these regions can be efficiently encoded and incorporated into volume ray-casting and back projection algorithms with a high degree of flexibility.

Presents a method for constructing tensor product Bezier surfaces from contour (cross-section) data. Minimal area triangulations are used to guide the surface construction, and the final surface reflects the optimality of the triangulation. The resulting surface differs from the initial triangulation in two important ways: it is smooth (as opposed to the piecewise planar triangulation), and it is in tensor product form (as opposed to the irregular triangular mesh). The surface reconstruction is efficient because we do not require an exact minimal surface. The triangulations are used as strong hints, but no more than that. The method requires the computation of both open and closed isoparametric curves of the surface, using triangulations as a guide. These isoparametric curves form a tensor product Bezier surface. We show how to control sampling density by filling and pruning isoparametric curves, for accuracy and economy. A rectangular grid of points is produced that is compatible with the expected format for a tensor product surface interpolation, so that a host of well-supported methods are available to generate and manipulate the surface.

This paper is concerned with the problem of reconstructing the surfaces of three-dimensional objects, given a collection of planar contours representing cross-sections through the objects. This problem has important aplications in biomedical research and instruction, solid modeling, and industrial inspection. The method we describe produces a triangulated mesh from the data points of the contours which is then used in conjunction with a piecewise parametric surface-fitting algorithm to produce a reconstructed surface. The problem can be broken into four subproblems: the correspondence problem (which contours should be connected by the surface?), the tiling problem (how should the contours be connected?), the branching problem (what do we do when there are branches in the surface?), and the surface-fitting problem (what is the precise geometry of the reconstructed surface?) We describe our system for surface reconstruction from sets of contours with respect to each of these subproblems. Special attention is given to the correspondence and branching problems. We present a method that can handle sets of contours in which adjacent contours share a very contorted boundary, and we describe a new approach to solving the correspondence problem using a Minimum Spanning Tree generated from the contours.

We describe an antialiasing system for ray tracing based on adaptive progressive refinement. The goals of the system are to produce high quality antialiased images at a modest average sample rate, and to refine the image progressively so that the image is available in a usable form early and is refined gradually toward the final result.The method proceeds by adaptive stochastic sampling of the image plane, evaluation of the samples by ray tracing, and image reconstruction from the samples. Adaptive control of the sample generation process is driven by three basic goals: coverage of the image, location of features, and confidence in the values at a distinguished "pixel level" of resolution.A three-stage process of interpolation, filtering, and resampling is used to reconstruct a regular grid of display pixels. This reconstruction can be either batch or incremental.

A particular style of search is considered that is motivated by the problem of reconstructing the surface of three-dimensional objects given a collection of planar contours representing cross-sections through the objects. An improvement on the simple divide-and-conquer method is presented. The key idea is to locate bottlenecks (minimal separators), which markedly reduces the number of searches required but reduces other measures (e.g. nodes expanded) by only a constant factor. It is observed that for well-behaved search spaces, the search efficiency can be improved further by making 'pessimal guesses'. This suggests a style of search in which the region of the search space thought to be close to the optimal solution (on whatever grounds are available) is examined last, while the outlying regions (the pessimal guesses) are examined first.>

The modular multiplication algorithm (MMA) was presented as a method of calculating " the smallest nonnegative integer R congruent modulo M to the product AB of two nonegative integers without dividing by M."1 The claim that division is avoided is technically correct, but misleading. A minor modification calculates both R and Q such that AB = MQ + R. A simplified version of the new algorithm is given and an alternate derivation is shown to illustrate the key ideas behind the method.

Two new data structures are defined for use in multidimensional histogramming. Their purpose is to cover a parameter space with a limited number of histogram bins so that fine precision is maintained where it is needed. The original motivation for these data structures was to implement Hough-like transforms in high-dimensional parameter spaces. The two data structures share the ability to adapt to distributions that change with time.

A convenient representation for blob-like figures in an image consists of the orientation, length, and width of a bounding rect-angle. One fast algorithm for producing such a bounding rectangle is based upon a dot product space. The analysis of the dot product space shape representation is improved to handle certain pathological cases, and it is shown how to generalize this analysis to accommodate different criteria for the goodness of the representation.

The transmission of high resolution raster images over low-bandwidth communication lines requires a great amount of time. User interaction in such a transmission environment can be frustrating. The problem can be eased somewhat by transmitting a series of low resolution approximations which converge to the final image. Several methods of computing such a series of images are presented. Each is related to a particular type of pyramid data structure. They rely on the ability of the local display device to overpaint an existing image, and generally require some transmission and computation overhead. However, one of the methods requires no transmission overhead and only a small amount of local computation. A notation is introduced that permits concise descriptions of the image refinement processes.