Association for Computing Machinery (ACM)

In the course of developing a system for fitting smooth curves to camera input we have developed several direct (i.e. noniterative) methods for fitting a shape (line, circle, conic, cubic, plane, sphere, quadric, etc.) to a set of points, namely exact fit, simple fit, spherical fit, and blend fit. These methods are all dimension-independent, being just as suitable for 3D surfaces as for the 2D curves they were originally developed for.Exact fit generalizes to arbitrary shapes (in the sense of the term defined in this paper) the well-known determinant method for planar exact fit. Simple fit is a naive reduction of the general overconstrained case to the exact case. Spherical fit takes advantage of a special property of circles and spheres that permits robust fitting; no prior direct circle fitters have been as robust, and there have been no previous sphere fitters. Blend fit finds the best fit to a set of points of a useful generalization of Middleditch-Sears blending curves and surfaces, via a nonpolynomial generalization of planar fit.These methods all require ( am + bn ) n ² operations for fitting a surface of order n to m points, with a = 2 and b = 1/3 typically, except for spherical fit where b is larger due to the need to extract eigenvectors. All these methods save simple fit achieve a robustness previously attained by direct algorithms only for fitting planes. All admit incremental batched addition and deletion of points at cost an ² per point and bn ³ per batch.

We describe and demonstrate an algorithm that takes as input an unorganized set of points {x _l , . . . . x _n } ⊂ R ³ on or near an unknown manifold M, and produces as output a simplicial surface that approximates M. Neither the topology, the presence of boundaries, nor the geometry of M are assumed to be known in advance - all are inferred automatically from the data. This problem naturally arises in a variety of practical situations such as range scanning an object from multiple view points, recovery of biological shapes from two-dimensional slices, and interactive surface sketching.

The mathematical description of three dimensional surfaces usually falls in one of two classifications: parametric and algebraic. The form is defined as all points which satisfy some equation: F(x,y,z)=0. This form is ideally suited for image space shaded picture drawing, the pixel coordinates are substituted for x and y and the equation is solved for z. Algorithms for drawing such objects have been developed primarily for first and second order polynomial functions. This paper presents a new algorithm applicable to other functional forms, in particular to the summation of several gaussian density distributions. The algorithm was created to model electron density maps of molecular structures but can be used for other artistically interesting shapes.

We present a new algorithm, called marching cubes , that creates triangle models of constant density surfaces from 3D medical data. Using a divide-and-conquer approach to generate inter-slice connectivity, we create a case table that defines triangle topology. The algorithm processes the 3D medical data in scan-line order and calculates triangle vertices using linear interpolation. We find the gradient of the original data, normalize it, and use it as a basis for shading the models. The detail in images produced from the generated surface models is the result of maintaining the inter-slice connectivity, surface data, and gradient information present in the original 3D data. Results from computed tomography (CT), magnetic resonance (MR), and single-photon emission computed tomography (SPECT) illustrate the quality and functionality of marching cubes . We also discuss improvements that decrease processing time and add solid modeling capabilities.

Juno is a system that harmoniously integrates a language for describing pictures with a what-you-see-is-what-you-get image editor. Two of Juno's novelties are that geometric constraints are used to specify locations, and that the text of a Juno program is modified in response to the interactive editing of the displayed image that the program produces.

The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar part of the natural world. But this type of complex motion is rarely seen in computer animation. This paper explores an approach based on simulation as an alternative to scripting the paths of each bird individually. The simulated flock is an elaboration of a particle systems, with the simulated birds being the particles. The aggregate motion of the simulated flock is created by a distributed behavioral model much like that at work in a natural flock; the birds choose their own course. Each simulated bird is implemented as an independent actor that navigates according to its local perception of the dynamic environment, the laws of simulated physics that rule its motion, and a set of behaviors programmed into it by the "animator." The aggregate motion of the simulated flock is the result of the dense interaction of the relatively simple behaviors of the individual simulated birds.

A process for creating repeating patterns of the hyperbolic plane is described. Unlike the Euclidean plane, the hyperbolic plane has infinitely many different kinds of repeating patterns. The Poincare circle model of hyperbolic geometry has been used by the artist M. C. Escher to display interlocking, repeating, hyperbolic patterns. A program has been designed which will do this automatically. The user enters a motif, or basic subpattern, which could theoretically be replicated to fill the hyperbolic plane. In practice, the replication process can be iterated sufficiently often to appear to fill the circle model. There is an interactive “boundary procedure” which allows the user to design a motif Which will be replicated into a completely interlocking pattern. Duplication of two of Escher's patterns and some entirely new patterns are included in the paper.

A software environment is described which provides facilities at a variety of levels for “animating” algorithms: exposing properties of programs by displaying multiple dynamic views of the program and associated data structures. The system is operational on a network of graphics-based, personal workstations and has been used successfully in several applications for teaching and research in computer science and mathematics. In this paper, we outline the conceptual framework that we have developed for animating algorithms, describe the system that we have implemented, and give several examples drawn from the host of algorithms that we have animated.