Many graphics applications, and interactive systems in particular, rely on hierarchical surface representations to efficiently process very complex models. Considerable attention has been focused on hierarchies of surface approximations and their construction via automatic surface simplification. Such representations have proven effective for adapting the level of detail used in real time display systems. However, other applications such as raytracing, collision detection, and radiosity benefit from an alternative multiresolution framework: hierarchical partitions of the original surface geometry. We present a new method for representing a hierarchy of regions on a polygonal surface which partition that surface into a set of face clusters. These clusters, which are connected sets of faces, represent the aggregate properties of the original surface a different scales rather than providing geometric approximations of varying complexity. We also describe the combination of an effective error metric and a novel algorithm for constructing these hierarchies.

There are a variety of application areas in which there is a need for simplifying complex polygonal surface models. These models often have material properties such as colors, textures, and surface normals. Our surface simplification algorithm, based on iterative edge contraction and quadric error metrics, can rapidly produce high quality approximations of such models. We present a natural extension of our original error metric that can account for a wide range of vertex attributes.

Many applications in computer graphics require complex, highly detailed models. However, the level of detail actually necessary may vary considerably. To control processing time, it is often desirable to use approximations in place of excessively detailed models. We have developed a surface simplification algorithm which can rapidly produce high quality approximations of polygonal models. The algorithm uses iterative contractions of vertex pairs to simplify models and maintains surface error approximations using quadric matrices. By contracting arbitrary vertex pairs (not just edges), our algorithm is able to join unconnected regions of models. This can facilitate much better approximations, both visually and with re-spect to geometric error. In order to allow topological joining, our system also supports non-manifold surface models.

We present a new particle-based approach to sampling and controlling implicit surfaces.A simple constraint locks a set of particles onto a surface while the particles and the surface move.We use the constraint to make surfaces follow particles, and to make particles follow surfaces.We implement control points for direct manipulation by specifying particle motions, then solving for surface motion that maintains the constraint.For sampling and rendering, we run the constraint in the other direction, creating floater particles that roam freely over the surface.Local repulsion is used to make floaters spread evenly across the surface.By varying the radius of repulsion adaptively, and fissioning or killing particles based on the local density, we can achieve good sampling distributions very rapidly, and maintain them even in the face of rapid and extreme deformations and changes in surface topology.

Abstract The radiosity method for the simulation of interreflection of light between diffuse surfaces is such a common image synthesis technique that its derivation is worthy of study. We here examine the radiosity method in a two dimensional, flatland world. It is shown that the radiosity method is a simple finite element method for the solution of the integral equation governing global illumination. These two‐dimensional studies help explain the radiosity method in general and suggest a number of improvements to existing algorithms. In particular, radiosity solutions can be improved using a priori discontinuity meshing , placing mesh boundaries on discontinuities such as shadow edges. When discontinuity meshing is used along with piecewise‐linear approximations instead of the current piecewise‐constant approximations, the accuracy of radiosity simulations can be greatly increased.

We present a rendering method designed to provide accurate, general simulation of global illumination for realistic image synthesis. Separating surface interaction into diffuse plus specular, we compute the specular component on the fly, as in ray tracing, and store the diffuse component (the radiosity) for later-reuse, similar to a radiosity algorithm. Radiosities are stored in adaptive radiosity textures (rexes)1 that record the pattern of light and shadow on every diffuse surface in the scene. They adaptively subdivide themselves to the appropriate level of detail for the picture being made, resolving sharp shadow edges automatically.We use a three-pass, bidirectional ray tracing algorithm that traces rays from both the lights and the eye. The "size pass" records visibility information on diffuse surfaces; the "light pass" progressively traces rays from lights and bright surfaces to deposit photons on diffuse surfaces to construct the radiosity textures; and the "eye pass" traces rays from the eye, collecting light from diffuse surfaces to make a picture.

Ray tracing has established itself in recent years as the most general image synthesis algorithm. Researchers have investigated ray-surface intersection calculations for a number of surface primitives, including checkerboards, glass balls, green fractal hills, mandrills, abstract blue surfaces, more glass balls, robot arms, pool balls, low-resolution clouds, morphine molecules, aquatic blobby things making strange noises, fantastic cities, and running skeletons. Unfortunately, nobody has ray traced any food. The Dessert Realism Project here at Pixar is addressing this problem. This paper presents new technology for ray tracing Jell-O® brand gelatin. We believe the method may have application to other brands of gelatin and perhaps pudding as well.

Many applications of digital filtering require a space variant filter - one whose shape or size varies with position. The usual algorithm for such filters, direct convolution, is very costly for wide kernels. Image prefiltering provides an efficient alternative. We explore one prefiltering technique, repeated integration, which is a generalization of Crow's summed area table.We find that convolution of a signal with any piecewise polynomial kernel of degree n--1 can be computed by integrating the signal n times and point sampling it several times for each output sample. The use of second or higher order integration permits relatively high quality filtering. The advantage over direct convolution is that the cost of repeated integration filtering does not increase with filter width. Generalization to two-dimensional image filtering is straightforward. Implementations of the simple technique are presented in both preprocessing and stream processing styles.

Ray tracing has produced some of the most realistic computer generated pictures to date. They contain surface texturing, local shading, shadows, reflections and refractions. The major disadvantage of ray tracing results from its point-sampling approach. Because calculation proceeds ab initio at each pixel it is very CPU intensive and may contain noticeable aliasing artifacts. It is difficult to take advantage of spatial coherence because the shapes of reflections and refractions from curved surfaces are so complex.

Algorithms for adaptive, tapered quantization of color images are described. The research is motivated by the desire to display high-quality reproductions of color images with small frame buffers. It is demonstrated that many color images which would normally require a frame buffer having 15 bits per pixel can be quantized to 8 or fewer bits per pixel with little subjective degradation. In most cases, the resulting images look significantly better than those made with uniform quantization.