Scene Representation Technologies for 3DTV—A Survey
---
paper_title: Layered depth images

paper_content:

In this paper we present a set of efficient image based rendering methods capable of rendering multiple frames per second on a PC. The first method warps Sprites with Depth representing smooth surfaces without the gaps found in other techniques. A second method for more general scenes performs warping from an intermediate representation called a Layered Depth Image (LDI). An LDI is a view of the scene from a single input camera view, but with multiple pixels along each line of sight. The size of the representation grows only linearly with the observed depth complexity in the scene. Moreover, because the LDI data are represented in a single image coordinate system, McMillan’s warp ordering algorithm can be successfully adapted. As a result, pixels are drawn in the output image in back-to-front order. No z-buffer is required, so alphacompositing can be done efficiently without depth sorting. This makes splatting an efficient solution to the resampling problem.
---
paper_title: Interactive 3-D Video Representation and Coding Technologies

paper_content:

Interactivity in the sense of being able to explore and navigate audio-visual scenes by freely choosing viewpoint and viewing direction, is an important key feature of new and emerging audio-visual media. This paper gives an overview of suitable technology for such applications, with a focus on international standards, which are beneficial for consumers, service providers, and manufacturers. We first give a general classification and overview of interactive scene representation formats as commonly used in computer graphics literature. Then, we describe popular standard formats for interactive three-dimensional (3-D) scene representation and creation of virtual environments, the virtual reality modeling language (VRML), and the MPEG-4 BInary Format for Scenes (BIFS) with some examples. Recent extensions to MPEG-4 BIFS, the Animation Framework eXtension (AFX), providing advanced computer graphics tools, are explained and illustrated. New technologies mainly targeted at reconstruction, modeling, and representation of dynamic real world scenes are further studied. The user shall be able to navigate photorealistic scenes within certain restrictions, which can be roughly defined as 3-D video. Omnidirectional video is an extension of the planar two-dimensional (2-D) image plane to a spherical or cylindrical image plane. Any 2-D view in any direction can be rendered from this overall recording to give the user the impression of looking around. In interactive stereo two views, one for each eye, are synthesized to provide the user with an adequate depth cue of the observed scene. Head motion parallax viewing can be supported in a certain operating range if sufficient depth or disparity data are delivered with the video data. In free viewpoint video, a dynamic scene is captured by a number of cameras. The input data are transformed into a special data representation that enables interactive navigation through the dynamic scene environment.
---
paper_title: Depth image-based representations for static and animated 3D objects

paper_content:

We describe a novel depth image-based representation (DIBR) that has been adopted into the MPEG-4 animation framework extension (AFX). The idea of this approach is to build a compact representation of a 3D object or scene without storing the geometry information in traditional polygonal form. The main formats of the DIBR family are simple texture (an image together with depth array), point texture (a view of a scene from a single input camera but with multiple pixels along each line of sight), and octree image (octree data structure together with a set of images and their viewport parameters). The designed node specifications and rendering algorithms are addressed. The experimental results show the efficacy and fidelity of the proposed approach.
---
paper_title: An Evolutionary and Optimised Approach on 3D-TV

paper_content:

In this paper we will present the concept of a system that allows for an evolutionary introduction of depth perception into the existing 2D digital TV framework. The work is part of the European Information Society Technologies (IST) project “Advanced Three-Dimensional Television System Technologies” (ATTEST), an activity where industries, research centers and universities have joined forces to design a backwardscompatible, flexible and modular broadcast 3D-TV system, where all parts of the 3D processing chain are optimised to one another. This includes content creation, coding and transmission, display and research in human 3D perception, which be will used to guide the development process. The goals of the project comprise the development of a novel broadcast 3D camera, algorithms to convert existing 2D-video material into 3D, a 2Dcompatible coding and transmission scheme for 3D-video using MPEG2/4/7 technologies and the design of two new autostereoscopic displays.
---
paper_title: High-quality video view interpolation using a layered representation

paper_content:

The ability to interactively control viewpoint while watching a video is an exciting application of image-based rendering. The goal of our work is to render dynamic scenes with interactive viewpoint control using a relatively small number of video cameras. In this paper, we show how high-quality video-based rendering of dynamic scenes can be accomplished using multiple synchronized video streams combined with novel image-based modeling and rendering algorithms. Once these video streams have been processed, we can synthesize any intermediate view between cameras at any time, with the potential for space-time manipulation.In our approach, we first use a novel color segmentation-based stereo algorithm to generate high-quality photoconsistent correspondences across all camera views. Mattes for areas near depth discontinuities are then automatically extracted to reduce artifacts during view synthesis. Finally, a novel temporal two-layer compressed representation that handles matting is developed for rendering at interactive rates.
---
paper_title: Estimation of Depth Fields Suitable for Video Compression Based on 3-D Structure and Motion of Objects

paper_content:

Intensity prediction along motion trajectories removes temporal redundancy considerably in video compression algorithms. In three-dimensional (3-D) object-based video coding, both 3-D motion and depth values are required for temporal prediction. The required 3-D motion parameters for each object are found by the correspondence-based E-matrix method. The estimation of the correspondences-two-dimensional (2-D) motion field-between the frames and segmentation of the scene into objects are achieved simultaneously by minimizing a Gibbs energy. The depth field is estimated by jointly minimizing a defined distortion and bit-rate criterion using the 3-D motion parameters. The resulting depth field is efficient in the rate-distortion sense. Bit-rate values corresponding to the lossless encoding of the resultant depth fields are obtained using predictive coding; prediction errors are encoded by a Lempel-Ziv algorithm. The results are satisfactory for real-life video scenes.
---
paper_title: Hierarchical stochastic diffusion for disparity estimation

paper_content:

This paper proposes a stochastic approach to estimate the disparity field combined with line field. In the maximum a posteriori (MAP) method based on Markov random field (MRF) model, it is important to optimize and converge the Gibbs potential function corresponding to the perturbed disparity field. The proposed optimization method, stochastic diffusion, takes advantage of the probabilistic distribution of the neighborhood fields, and diffuses the Gibbs potential space to be stable iteratively. By using the neighborhood distribution in the non-random and non-deterministic diffusion, the stochastic diffusion improves both the estimation accuracy and the convergence speed. In the paper, the hierarchical stochastic diffusion is also applied to the disparity field. The hierarchical approach reduces the memory and computational load, and increases the convergence of the potential space. The line field is the discontinuity model of the disparity field. The paper also proposes an effective configuration of the neighborhood to be suitable for the hierarchical disparity structure. According to the experiments, the stochastic diffusion shows good estimation performance. The line field improves the estimation at the object boundary, and the estimated line field coincides with the object boundary with the useful contours. Furthermore, the stochastic diffusion with line field embeds the occlusion detection and compensation. And, the stochastic diffusion converges the estimated fields very fast in the hierarchical scheme. The stochastic diffusion is applicable to any kind of field estimation given the appropriate definition of the field and MRF models.
---
paper_title: Interactive 3-D Video Representation and Coding Technologies

paper_content:

Interactivity in the sense of being able to explore and navigate audio-visual scenes by freely choosing viewpoint and viewing direction, is an important key feature of new and emerging audio-visual media. This paper gives an overview of suitable technology for such applications, with a focus on international standards, which are beneficial for consumers, service providers, and manufacturers. We first give a general classification and overview of interactive scene representation formats as commonly used in computer graphics literature. Then, we describe popular standard formats for interactive three-dimensional (3-D) scene representation and creation of virtual environments, the virtual reality modeling language (VRML), and the MPEG-4 BInary Format for Scenes (BIFS) with some examples. Recent extensions to MPEG-4 BIFS, the Animation Framework eXtension (AFX), providing advanced computer graphics tools, are explained and illustrated. New technologies mainly targeted at reconstruction, modeling, and representation of dynamic real world scenes are further studied. The user shall be able to navigate photorealistic scenes within certain restrictions, which can be roughly defined as 3-D video. Omnidirectional video is an extension of the planar two-dimensional (2-D) image plane to a spherical or cylindrical image plane. Any 2-D view in any direction can be rendered from this overall recording to give the user the impression of looking around. In interactive stereo two views, one for each eye, are synthesized to provide the user with an adequate depth cue of the observed scene. Head motion parallax viewing can be supported in a certain operating range if sufficient depth or disparity data are delivered with the video data. In free viewpoint video, a dynamic scene is captured by a number of cameras. The input data are transformed into a special data representation that enables interactive navigation through the dynamic scene environment.
---
paper_title: Dense matching of multiple wide-baseline views

paper_content:

This paper describes a PDE-based method for dense depth extraction from multiple wide-baseline images. Emphasis lies on the usage of only a small amount of images. The integration of these multiple wide-baseline views is guided by the relative confidence that the system has in the matching to different views. This weighting is fine-grained in that it is determined for every pixel at every iteration. Reliable information spreads fast at the expense of less reliable data, both in terms of spatial communications within a view and in terms of information exchange between the views. Changes in intensity between images can be handled in a similar fine grained fashion.
---
paper_title: 1 1-1 Dense Disparity Map Estimation Respecting Image Discontinuities: A PDE and Scale-Space Based Approach

paper_content:

We present an energy based approach to estimate a dense disparity map from a set of two weakly calibrated stereoscopic images while preserving its discontinuities resulting from image boundaries. We first derive a simplified expression for the disparity that allows us to estimate it from a stereo pair of images using an energy minimization approach. We assume that the epipolar geometry is known, and we include this information in the energy model. Discontinuities are preserved by means of a regularization term based on the Nagel-Enkelmann operator. We investigate the associated Euler-Lagrange equation of the energy functional, and we approach the solution of the underlying partial differential equation (PDE) using a gradient descent method. The resulting parabolic problem has a unique solution. In order to reduce the risk to be trapped within some irrelevant local minima during the iterations, we use a focusing strategy based on a linear scalespace. Experimental results on both synthetic and real images are presented to illustrate the capabilities of this PDE and scale-space based method.
---
paper_title: View-dependent refinement of progressive meshes

paper_content:

Level-of-detail (LOD) representations are an important tool for realtime rendering of complex geometric environments. The previously introduced progressive mesh representation defines for an arbitrary triangle mesh a sequence of approximating meshes optimized for view-independent LOD. In this paper, we introduce a framework for selectively refining an arbitrary progressive mesh according to changing view parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and screen-space geometric error, and develop a real-time algorithm for incrementally refining and coarsening the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover, for continuous motions this work can be amortized over consecutive frames. In addition, smooth visual transitions (geomorphs) can be constructed between any two selectively refined meshes. A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes. CR Categories: I.3.3 [Computer Graphics]: Picture/Image Generation Display algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling surfaces and object representations. Additional
---
paper_title: Progressive simplicial complexes

paper_content:

In this paper, we introduce the progressive simplicial complex (PSC) representation, a new format for storing and transmitting triangulated geometric models. Like the earlier progressive mesh (PM) representation, it captures a given model as a coarse base model together with a sequence of refinement transformations that progressively recover detail. The PSC representation makes use of a more general refinement transformation, allowing the given model to be an arbitrary triangulation (e.g. any dimension, non-orientable, non-manifold, non-regular), and the base model to always consist of a single vertex. Indeed, the sequence of refinement transformations encodes both the geometry and the topology of the model in a unified multiresolution framework. The PSC representation retains the advantages of PM’s. It defines a continuous sequence of approximating models for runtime level-of-detail control, allows smooth transitions between any pair of models in the sequence, supports progressive transmission, and offers a space-efficient representation. Moreover, by allowing changes to topology, the PSC sequence of approximations achieves better fidelity than the corresponding PM sequence. We develop an optimization algorithm for constructing PSC representations for graphics surface models, and demonstrate the framework on models that are both geometrically and topologically complex. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling surfaces and object representations. Additional
---
paper_title: Progressive multiresolution meshes for deforming surfaces

paper_content:

Time-varying surfaces are ubiquitous in movies, games, and scientific applications. For reasons of efficiency and simplicity of formulation, these surfaces are often generated and represented as dense polygonal meshes with static connectivity. As a result, such deforming meshes often have a tremendous surplus of detail, with many more vertices and polygons than necessary for any given frame. An extensive amount of work has addressed the issue of simplifying a static mesh: however, these methods are inadequate for time-varying surfaces when there is a high degree of non-rigid deformation. We thus propose a new multiresolution representation for deforming surfaces that, together with our dynamic improvement scheme, provides high quality surface approximations at any level-of-detail, for all frames of an animation. Our algorithm also gives rise to a new progressive representation for time-varying multiresolution hierarchies, consisting of a base hierarchy for the initial frame and a sequence of update operations for subsequent frames. We demonstrate that this provides a very effective means of extracting static or view-dependent approximations for a deforming mesh over all frames of an animation.
---
paper_title: Efficient compression of non-manifold polygonal meshes

paper_content:

We present a method for compressing non-manifold polygonal meshes, i.e. polygonal meshes with singularities, which occur very frequently in the real-world. Most efficient polygonal compression methods currently available are restricted to a manifold mesh: they require a conversion process, and fail to retrieve the original model connectivity after decompression. The present method works by converting the original model to a manifold model, encoding the manifold model using an existing mesh compression technique, and clustering, or stitching together during the decompression process vertices that were duplicated earlier to faithfully recover the original connectivity. This paper focuses on efficiently encoding and decoding the stitching information. By separating connectivity from geometry and properties, the method avoids encoding vertices (and properties bound to vertices) multiple times; thus a reduction of the size of the bit-stream of about 10% is obtained compared with encoding the model as a manifold.
---
paper_title: Geometry Coding and VRML

paper_content:

The virtual-reality modeling language (VRML) is rapidly becoming the standard file format for transmitting three-dimensional (3-D) virtual worlds across the Internet. Static and dynamic descriptions of 3-D objects, multimedia content, and a variety of hyperlinks can be represented in VRML files. Both VRML browsers and authoring tools for the creations of VRML files are widely available for several different platforms. In this paper, we describe the topologically assisted geometric compression technology included in our proposal for the VRML compressed binary format. This technology produces significant reduction of file sizes and, subsequently, of the time required for transmission of such filed across the Internet. Compression ratios of 50:1 or more are achieved for large models. The proposal also includes a binary encoding to create compact, rapidly parsable binary VRML files. The proposal is currently being evaluated by the Compressed Binary Format Working Group of the VRML consortium as a possible extension of the VRML standard. In the topologically assisted compression scheme, a polyhedron is represented using two interlocking trees: a spanning tree of vertices and a spanning tree of triangles. The connectivity information represented in other compact schemes, such as triangular strips and generalized triangular meshes, can be directly derived from this representation. Connectivity information for large models is compressed with storage requirements approaching one bit per triangle. A variable-length, optionally lossy compression technique is used for vertex positions, normals, colors, and texture coordinates. The format supports all VRML property binding conventions.
---
paper_title: Progressive forest split compression

paper_content:

In this paper we introduce the Progressive Forest Split (PFS) representation, a new adaptive refinement scheme for storing and transmitting manifold triangular meshes in progressive and highly compressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one specifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refinement operation which can, at the expense of reduced granularity, be encoded more efficiently. A forest split operation doubling the number n of triangles of a mesh requires a maximum of approximately 3:5n bits to represent the connectivity changes, as opposed to approximately (5 + log2(n))n bits in PM. We describe algorithms to efficiently encode and decode the PFS format. We also show how any surface simplification algorithm based on edge collapses can be modified to convert single resolution triangular meshes to the PFS format. The modifications are simple and only require two additional topological tests on each candidate edge collapse. We show results obtained by applying these modifications to the Variable Tolerance method of Gueziec. CR
---
paper_title: Compressed Progressive Meshes

paper_content:

Most systems that support visual interaction with 3D models use shape representations based on triangle meshes. The size of these representations imposes limits on applications for which complex 3D models must be accessed remotely. Techniques for simplifying and compressing 3D models reduce the transmission time. Multiresolution formats provide quick access to a crude model and then refine it progressively. Unfortunately, compared to the best nonprogressive compression methods, previously proposed progressive refinement techniques impose a significant overhead when the full resolution model must be downloaded. The CPM (compressed progressive meshes) approach proposed here eliminates this overhead. It uses a new technique, which refines the topology of the mesh in batches, which each increase the number of vertices by up to 50 percent. Less than an amortized total of 4 bits per triangle encode where and how the topological refinements should be applied. We estimate the position of new vertices from the positions of their topological neighbors in the less refined mesh using a new estimator that leads to representations of vertex coordinates that are 50 percent more compact than previously reported progressive geometry compression techniques.
---
paper_title: Layered depth images

paper_content:

In this paper we present a set of efficient image based rendering methods capable of rendering multiple frames per second on a PC. The first method warps Sprites with Depth representing smooth surfaces without the gaps found in other techniques. A second method for more general scenes performs warping from an intermediate representation called a Layered Depth Image (LDI). An LDI is a view of the scene from a single input camera view, but with multiple pixels along each line of sight. The size of the representation grows only linearly with the observed depth complexity in the scene. Moreover, because the LDI data are represented in a single image coordinate system, McMillan’s warp ordering algorithm can be successfully adapted. As a result, pixels are drawn in the output image in back-to-front order. No z-buffer is required, so alphacompositing can be done efficiently without depth sorting. This makes splatting an efficient solution to the resampling problem.
---
paper_title: Fitting smooth surfaces to dense polygon meshes

paper_content:

Recent progress in acquiring shape from range data permits the acquisition of seamless million-polygon meshes from physical models. While dense polygon meshes are an adequate representation for some applications, many users prefer smooth surface representations for reasons of compactness, control, manufacturability, or appearance. In this thesis, we present algorithms and an end-to-end software system for converting dense irregular polygon meshes of arbitrary topology into tensor product B-spline surface patches with accompanying displacement maps. This choice of representation yields a coarse but efficient model suitable for interactive modification and animation and a fine but more expensive model suitable for rendering. ::: The first step in our process consists of interactively painting patch boundaries onto the polygonal surface. In many applications, the placement of patch boundaries is considered part of the creative process and is not amenable to automation. We present efficient techniques for representing, creating and editing curves on dense polygonal surfaces. ::: The second step in our process consists of finding a gridded resampling of each bounded section of the mesh. Our resampling algorithm lays a grid of springs across the polygon mesh, then iterates between relaxing this grid and subdividing it. This grid provides a parameterization for the mesh section, which is initially unparameterized. Our parameterization algorithm is automatic, efficient, and robust, even for complex polygonal surfaces. Prior algorithms have lacked one or more of these properties, making them unusable for dense meshes. Our strategy also provides the user a flexible method to design parameterizations--an ability that previous literature in surface approximation does not address. ::: The third and final step of our process consists of fitting a hybrid of B-spline surfaces and displacement maps to our gridded re-sampling. The displacement map is an image representation of the error between the fitted B-spline surfaces and our spring grid. Since displacement maps are just images our hybrid representation facilitates the use of image processing operators for manipulating the geometric detail of an object. ::: Our resampling and fitting steps are fast enough to surface a million polygon mesh in under 10 minutes--important for an interactive system.
---
paper_title: Automatic reconstruction of B-spline surfaces of arbitrary topological type

paper_content:

Creating freeform surfaces is a challenging task even with advanced geometric modeling systems. Laser range scanners offer a promising alternative for model acquisition—the 3D scanning of existing objects or clay maquettes. The problem of converting the dense point sets produced by laser scanners into useful geometric models is referred to as surface reconstruction. In this paper, we present a procedure for reconstructing a tensor product B-spline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single B-spline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of B-spline patches. A key ingredient in our solution is a scheme for automatically constructing both a network of patches and a parametrization of the data points over these patches. In addition, we define the B-spline surface using a surface spline construction, and demonstrate that such an approach leads to an efficient procedure for fitting the surface while maintaining tangent plane continuity. We explore adaptive refinement of the patch network in order to satisfy user-specified error tolerances, and demonstrate our method on both synthetic and real data. CR
---
paper_title: Fast Dynamic Tessellation of Trimmed NURBS Surfaced1

paper_content:

Trimmed NURBS (non-uniform rational B-splines) surfaces are being increasingly used and standardized in geometric modeling applications. Fast graphical processing of trimmed NURBS at interactive speeds is absolutely essential to enable these applications. which poses some unique challenges in software, hardware, and algorithm design. This paper presents a technique that uses graphical compilation to enable fast dynamic tessellation of trimmed NURBS surfaces under highly varying transforms. ::: ::: ::: ::: We use the concept of graphical data compilation. through which we preprocess the NURBS surface into a compact, view-independent form amenable for fast per-frame extraction of triangles. Much of the complexity of processing is absorbed during compilation. Arbitrarily complex trimming regions are broken down into simple regions that are specially designed to facilitate tessellation before rendering. Potentially troublesome cases of degeneracies in the surface are detected and dealt with during compilation. Compilation enables a clean separation of algorithm-intensive and compute-intensive operations, and provides for parallel implementations of the latter. Also, we exercise a classification technique while processing trimming loops. which robustly takes care of geometric ambiguities and deals with special cases while keeping the compilation code simple and concise.
---
paper_title: The NURBS Book

paper_content:

The book covers all aspects of non-uniform rational B-splines necessary to design geometry in a computer-aided environment. Basic B-spline features, curve and surface algorithms, and state-of-the-art geometry tools are all discussed. Detailed code for design algorithms and computational tricks are covered too, in a lucid, easy-to-understand style, with a minimum of mathematics and using numerous worked examples. The book will be a must for students, researchers, and implementors whose work involves the use of splines.
---
paper_title: Surface fitting with hierarchical splines

paper_content:

We consider the fitting of tensor product parametric spline surfaces to gridded data. The continuity of the surface is provided by the basis chosen. When tensor product splines are used with gridded data, the surface fitting problem decomposes into a sequence of curve fitting processes, making the computations particularly efficient. The use of a hierarchical representation for the surface adds further efficiency by adaptively decomposing the fitting process into subproblems involving only a portion of the data. Hierarchy also provides a means of storing the resulting surface in a compressed format. Our approach is compared to multiresolution analysis and the use of wavelets.
---
paper_title: Interpolating Subdivision for meshes with arbitrary topology

paper_content:

Subdivision is a powerful paradigm for the generation of surfaces of arbitrary topology. Given an initial triangular mesh the goal is to produce a smooth and visually pleasing surface whose shape is controlled by the initial mesh. Of particular interest are interpolating ::: schemes since they match the original data exactly, and play an important role in fast multiresolution and wavelet techniques. Dyn, Gregory, and Levin introduced the Butterfly scheme, which yields C^1 surfaces in the topologically regular setting. Unfortunately it ::: exhibits undesirable artifacts in the case of an irregular topology. We examine these failures and derive an improved scheme, which retains the simplicity of the Butterfly scheme, is interpolating, and results in smoother surfaces.
---
paper_title: Multiresolution analysis of arbitrary meshes

paper_content:

In computer graphics and geometric modeling, shapes are often represented by triangular meshes. With the advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace. Such meshes are notoriously expensive to store, transmit, render, and are awkward to edit. Multiresolution analysis offers a simple, unified, and theoretically sound approach to dealing with these problems. Lounsbery et al. have recently developed a technique for creating multiresolution representations for a restricted class of meshes with subdivision connectivity. Unfortunately, meshes encountered in practice typically do not meet this requirement. In this paper we present a method for overcoming the subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to multiresolution form. The method is based on the approximation of an arbitrary initial mesh M by a mesh MJ that has subdivision connectivity and is guaranteed to be within a specified tolerance. The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain. We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches. CR
---
paper_title: Multiresolution signal processing for meshes

paper_content:

We generalize basic signal processing tools such as downsampling, upsampling, and filters to irregular connectivity triangle meshes. This is accomplished through the design of a non-uniform relaxation procedure whose weights depend on the geometry and we ::: show its superiority over existing schemes whose weights depend only on connectivity. This is combined with known mesh simplification methods to build subdivision and pyramid algorithms. We demonstrate the power of these algorithms through a number of application examples including smoothing, enhancement, editing, and texture mapping.
---
paper_title: Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology

paper_content:

A simple interpolatory subdivision scheme for quadrilateral nets with arbitrary topology is presented which generates C 1 surfaces in the limit. The scheme satisfies important requirements for practical applications in computer graphics and engineering. These requirements include the necessity to generate smooth surfaces with local creases and cusps. The scheme can be applied to open nets in which case it generates boundary curves that allow a C 0 -join of several subdivision patches. Due to the local support of the scheme, adaptive refinement strategies can be applied. We present a simple device to preserve the consistency of such adaptively refined nets.
---
paper_title: Multiresolution analysis for surfaces of arbitrary topological type

paper_content:

Multiresolution analysis and wavelets provide useful and efficient tools for representing functions at multiple levels of detail. Wavelet representations have been used in a broad range of applications, including image compression, physical simulation, and numerical analysis. In this article, we present a new class of wavelets, based on subdivision surfaces, that radically extends the class of representable functions. Whereas previous two-dimensional methods were restricted to functions difined on R 2 , the subdivision wavelets developed here may be applied to functions defined on compact surfaces of arbitrary topological type. We envision many applications of this work, including continuous level-of-detail control for graphics rendering, compression of geometric models, and acceleration of global illumination algorithms. Level-of-detail control for spherical domains is illustrated using two examples: shape approximation of a polyhedral model, and color approximation of global terrain data.
---
paper_title: Globally smooth parameterizations with low distortion

paper_content:

Good parameterizations are of central importance in many digital geometry processing tasks. Typically the behavior of such processing algorithms is related to the smoothness of the parameterization and how much distortion it contains. Since a parameterization maps a bounded region of the plane to the surface, a parameterization for a surface which is not homeomorphic to a disc must be made up of multiple pieces. We present a novel parameterization algorithm for arbitrary topology surface meshes which computes a globally smooth parameterization with low distortion. We optimize the patch layout subject to criteria such as shape quality and metric distortion, which are used to steer a mesh simplification approach for base complex construction. Global smoothness is achieved through simultaneous relaxation over all patches, with suitable transition functions between patches incorporated into the relaxation procedure. We demonstrate the quality of our parameterizations through numerical evaluation of distortion measures and the excellent rate distortion performance of semi-regular remeshes produced with these parameterizations. The numerical algorithms required to compute the parameterizations are robust and run on the order of minutes even for large meshes.
---
paper_title: Progressive geometry compression

paper_content:

We propose a new progressive compression scheme for arbitrary topology, highly detailed and densely sampled meshes arising from geometry scanning. We observe that meshes consist of three distinct components: geometry, parameter, and connectivity information. The latter two do not contribute to the reduction of error in a compression setting. Using semi-regular meshes, parameter and connectivity information can be virtually eliminated. Coupled with semi-regular wavelet transforms, zerotree coding, and subdivision based reconstruction we see improvements in error by a factor four (12dB) compared to other progressive coding schemes.
---
paper_title: Interactive multiresolution mesh editing

paper_content:

We describe a multiresolution representation for meshes based on subdivision, which is a natural extension of the existing patch-based surface representations. Combining subdivision and the smoothing algorithms of Taubin [26] allows us to construct a set of algorithms for interactive multiresolution editing of complex hierarchical meshes of arbitrary topology. The simplicity of the underlying algorithms for refinement and coarsification enables us to make them local and adaptive, thereby considerably improving their efficiency. We have built a scalable interactive multiresolution editing system based on such algorithms.
---
paper_title: Recursively generated B-spline surfaces on arbitrary topological meshes

paper_content:

Abstract This paper describes a method for recursively generating surfaces that approximate points lying-on a mesh of arbitrary topology. The method is presented as a generalization of a recursive bicubic B-spline patch subdivision algorithm. For rectangular control-point meshes, the method generates a standard B-spline surface. For non-rectangular meshes, it generates surfaces that are shown to reduce to a standard B-spline surface except at a small number of points, called extraordinary points. Therefore, everywhere except at these points the surface is continuous in tangent and curvature. At the extraordinary points, the pictures of the surface indicate that the surface is at least continuous in tangent, but no proof of continuity is given. A similar algorithm for biquadratic B-splines is also presented.
---
paper_title: Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values

paper_content:

In this paper we disprove the belief widespread within the computer graphics community that Catmull-Clark subdivision surfaces cannot be evaluated directly without explicitly subdividing. We show that the surface and all its derivatives can be evaluated in terms of a set of eigenbasis functions which depend only on the subdivision scheme and we derive analytical expressions for these basis functions. In particular, on the regular part of the control mesh where Catmull-Clark surfaces are bi-cubic B-splines, the eigenbasis is equal to the power basis. Also, our technique is both easy to implement and efficient. We have used our implementation to compute high quality curvature plots of subdivision surfaces. The cost of our evaluation scheme is comparable to that of a bi-cubic spline. Therefore, our method allows many algorithms developed for parametric surfaces to be applied to Catmull-Clark subdivision surfaces. This makes subdivision surfaces an even more attractive tool for free-form surface modeling. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Curve, Surface, Solid, and Object Representations J.6 [Computer Applications]: Computer-Aided Engineering—Computer Aided Design (CAD)
---
paper_title: Subdivision surfaces in character animation

paper_content:

The creation of believable and endearing characters in computer graphics presents a number of technical challenges, including the modeling, animation and rendering of complex shapes such as heads, hands, and clothing. Traditionally, these shapes have been modeled with NURBS surfaces despite the severe topological restrictions that NURBS impose. In order to move beyond these restrictions, we have recently introduced subdivision surfaces into our production environment. Subdivision surfaces are not new, but their use in high-end CG production has been limited. Here we describe a series of developments that were required in order for subdivision surfaces to meet the demands of high-end production. First, we devised a practical technique for constructing provably smooth variable-radius fillets and blends. Second, we developed methods for using subdivision surfaces in clothing simulation including a new algorithm for efficient collision detection. Third, we developed a method for constructing smooth scalar fields on subdivision surfaces, thereby enabling the use of a wider class of programmable shaders. These developments, which were used extensively in our recently completed short film Geri’s game, have become a highly valued feature of our production environment. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; I.3.3 [Computer Graphics]: Picture/Image Generation.
---
paper_title: Displaced subdivision surfaces

paper_content:

In this paper we introduce a new surface representing, the displaced subdivision surface . It represents a detailed surface model as a scalar-valued displacement over a smooth domain surface. Our representation defines both the domain surface and the displacement function using a unified subdivision framework, allowing for simple and efficient evaluation of analytic surface properties. We present a simple, automatic scheme for converting detailed geometric models into such a representation. The challenge in this conversion process is to find a simple subdivision surface that still faithfully expresses the detailed model as its offset. We demonstrate that displaced subdivision surfaces offer a number of benefits, including geometry compression, editing, animation, scalability, and adaptive rendering. In particular, the encoding of fine detail as a scalar function makes the representation extremely compact.
---
paper_title: Multilevel representation and transmission of real objects with progressive octree particles

paper_content:

We present a multilevel representation scheme adapted to storage, progressive transmission, and rendering of dense data sampled on the surface of real objects. Geometry and object attributes, such as color and normal, are encoded in terms of surface particles associated to a hierarchical space partitioning based on an octree. Appropriate ordering of surface particles results in a compact multilevel representation without increasing the size of the uniresolution model corresponding to the highest level of detail. This compact representation can progressively be decoded by the viewer and transformed by a fast direct triangulation technique into a sequence of triangle meshes with increasing levels of detail. The representation requires approximately 5 bits per particle (2.5 bits per triangle) to encode the basic geometrical structure. The vertex positions can then be refined by means of additional precision bits, resulting in 5 to 9 bits per triangle for representing a 12-bit quantized geometry. The proposed representation scheme is demonstrated with the surface data of various real objects.
---
paper_title: QSplat: a multiresolution point rendering system for large meshes

paper_content:

Advances in 3D scanning technologies have enabled the practical creation of meshes with hundreds of millions of polygons. Traditional algorithms for display, simplification, and progressive transmission of meshes are impractical for data sets of this size. We describe a system for representing and progressively displaying these meshes that combines a multiresolution hierarchy based on bounding spheres with a rendering system based on points. A single data structure is used for view frustum culling, backface culling, level-of-detail selection, and rendering. The representation is compact and can be computed quickly, making it suitable for large data sets. Our implementation, written for use in a large-scale 3D digitization project, launches quickly, maintains a user-settable interactive frame rate regardless of object complexity or camera position, yields reasonable image quality during motion, and refines progressively when idle to a high final image quality. We have demonstrated the system on scanned models containing hundreds of millions of samples.
---
paper_title: Efficient High Quality Rendering of Point Sampled Geometry

paper_content:

We propose a highly efficient hierarchical representation for point sampled geometry that automatically balances sampling density and point coordinate quantization. The representation is very compact with a memory consumption of far less than 2 bits per point position which does not depend on the quantization precision. We present an efficient rendering algorithm that exploits the hierarchical structure of the representation to perform fast 3D transformations and shading. The algorithm is extended to surface splatting which yields high quality anti-aliased and water tight surface renderings. Our pure software implementation renders up to 14 million Phong shaded and textured samples per second and about 4 million anti-aliased surface splats on a commodity PC. This is more than a factor 10 times faster than previous algorithms.
---
paper_title: Surface splatting

paper_content:

Modern laser range and optical scanners need rendering techniques that can handle millions of points with high resolution textures. This paper describes a point rendering and texture filtering technique called surface splatting which directly renders opaque and transparent surfaces from point clouds without connectivity. It is based on a novel screen space formulation of the Elliptical Weighted Average (EWA) filter. Our rigorous mathematical analysis extends the texture resampling framework of Heckbert to irregularly spaced point samples. To render the points, we develop a surface splat primitive that implements the screen space EWA filter. Moreover, we show how to optimally sample image and procedural textures to irregular point data during pre-processing. We also compare the optimal algorithm with a more efficient view-independent EWA pre-filter. Surface splatting makes the benefits of EWA texture filtering available to point-based rendering. It provides high quality anisotropic texture filtering, hidden surface removal, edge anti-aliasing, and order-independent transparency.
---
paper_title: Progressive point set surfaces

paper_content:

Progressive point set surfaces (PPSS) are a multilevel point-based surface representation. They combine the usability of multilevel scalar displacement maps (e.g., compression, filtering, geometric modeling) with the generality of point-based surface representations (i.e., no fixed homology group or continuity class). The multiscale nature of PPSS fosters the idea of point-based modeling. The basic building block for the construction of PPSS is a projection operator, which maps points in the proximity of the shape onto local polynomial surface approximations. The projection operator allows the computing of displacements from smoother to more detailed levels. Based on the properties of the projection operator we derive an algorithm to construct a base point set. Starting from this base point set, a refinement rule using the projection operator constructs a PPSS from any given manifold surface.
---
paper_title: Progressive multilevel meshes from octree particles

paper_content:

We present a multilevel object modeling scheme adapted to storage and progressive transmission of complex 3D objects. Geometry and texture are encoded in terms of surface particles associated to a hierarchical space partitioning via an octree. Proper ordering of surface particles results in a compact multilevel representation without increasing the size of the uni-resolution model which provides the highest level of detail. This compact representation can be progressively decoded by the viewer and transformed by a fast direct triangulation technique into a sequence of triangle meshes of increasing levels of detail. The proposed scheme is demonstrated with 3D models of real objects constructed by a shape from silhouette technique.
---
paper_title: Pointshop 3D: an interactive system for point-based surface editing

paper_content:

We present a system for interactive shape and appearance editing of 3D point-sampled geometry. By generalizing conventional 2D pixel editors, our system supports a great variety of different interaction techniques to alter shape and appearance of 3D point models, including cleaning, texturing, sculpting, carving, filtering, and resampling. One key ingredient of our framework is a novel concept for interactive point cloud parameterization allowing for distortion minimal and aliasing-free texture mapping. A second one is a dynamic, adaptive resampling method which builds upon a continuous reconstruction of the model surface and its attributes. These techniques allow us to transfer the full functionality of 2D image editing operations to the irregular 3D point setting. Our system reads, processes, and writes point-sampled models without intermediate tesselation. It is intended to complement existing low cost 3D scanners and point rendering pipelines for efficient 3D content creation.
---
paper_title: The digital Michelangelo project: 3D scanning of large statues

paper_content:

We describe a hardware and software system for digitizing the shape and color of large fragile objects under non-laboratory conditions. Our system employs laser triangulation rangefinders, laser time-of-flight rangefinders, digital still cameras, and a suite of software for acquiring, aligning, merging, and viewing scanned data. As a demonstration of this system, we digitized 10 statues by Michelangelo, including the well-known figure of David, two building interiors, and all 1,163 extant fragments of the Forma Urbis Romae, a giant marble map of ancient Rome. Our largest single dataset is of the David - 2 billion polygons and 7,000 color images. In this paper, we discuss the challenges we faced in building this system, the solutions we employed, and the lessons we learned. We focus in particular on the unusual design of our laser triangulation scanner and on the algorithms and software we developed for handling very large scanned models.
---
paper_title: Confetti: object-space point blending and splatting

paper_content:

We present Confetti, a novel point-based rendering approach based on object-space point interpolation of densely sampled surfaces. We introduce the concept of a transformation-invariant covariance matrix of a set of points which can efficiently be used to determine splat sizes in a multiresolution point hierarchy. We also analyze continuous point interpolation in object-space and we define a new class of parameterized blending kernels as well as a normalization procedure to achieve smooth blending. Furthermore, we present a hardware accelerated rendering algorithm based on texture mapping and /spl alpha/-blending as well as programmable vertex and pixel-shaders.
---
paper_title: Surface modeling with oriented particle systems

paper_content:

Splines and deformable surface models are widely used in computer graphics to describe free-form surfaces. These methods require manual preprocessing to discretize the surface into patches and to specify their connectivity. We present a new model of elastic surfaces based on interacting particle systems, which, unlike previous techniques, can be used to sptiL join, or extend surfaces without the need for manual intervention. The particles we use have longrange attraction forces and short-range repulsion forces and follow Newtonian dynamics, much tiie recent computational models of fluids and solids. To enable our particles to model surface elements instead of point masses or volume elements, we add an orientation to each particle’s state. We devise new interaction potentials for our oriented particles which favor locally planar or spherical arrangements. We atso develop techniques for adding new particles automatically, which enables our surfaces to stretch and grow. We demonstrate the application of our new particle system to modefing surfaces in 3-D and the interpolation of 3-D point sets.
---
paper_title: Streaming QSplat: a viewer for networked visualization of large, dense models

paper_content:

Steady growth in the speeds of network links and graphics accelerator cards has brought increasing interest in streaming transmission of three-dimensional data sets. We demonstrate how streaming visualization can be made practical for data sets containing hundreds of millions of samples. Our system is based on QSplat, a multiresolution rendering system for dense polygon meshes that employs a bounding sphere hierarchy data structure and splat rendering. We show how to incorporate view-dependent progressive transmission into QSplat, by having the client request visible portions of the model in order from coarse to fine resolution. In addition, we investigate interaction techniques for improving the effectiveness of streaming data visualization. In particular, we explore color-coding streamed data by resolution, examine the order in which data should be transmitted in order to minimize visual distraction, and propose tools for giving the user fine control over download order.
---
paper_title: Point based animation of elastic, plastic and melting objects

paper_content:

We present a method for modeling and animating a wide spectrum of volumetric objects, with material properties anywhere in the range from stiff elastic to highly plastic. Both the volume and the surface representation are point based, which allows arbitrarily large deviations form the original shape. In contrast to previous point based elasticity in computer graphics, our physical model is derived from continuum mechanics, which allows the specification of common material properties such as Young's Modulus and Poisson's Ratio. In each step, we compute the spatial derivatives of the discrete displacement field using a Moving Least Squares (MLS) procedure. From these derivatives we obtain strains, stresses and elastic forces at each simulated point. We demonstrate how to solve the equations of motion based on these forces, with both explicit and implicit integration schemes. In addition, we propose techniques for modeling and animating a point-sampled surface that dynamically adapts to deformations of the underlying volumetric model.
---
paper_title: Surfels: surface elements as rendering primitives

paper_content:

Surface elements (surfels) are a powerful paradigm to efficiently render complex geometric objects at interactive frame rates. Unlike classical surface discretizations, i.e., triangles or quadrilateral meshes, surfels are point primitives without explicit connectivity. Surfel attributes comprise depth, texture color, normal, and others. As a pre-process, an octree-based surfel representation of a geometric object is computed. During sampling, surfel positions and normals are optionally perturbed, and different levels of texture colors are prefiltered and stored per surfel. During rendering, a hierarchical forward warping algorithm projects surfels to a z-buffer. A novel method called visibility splatting determines visible surfels and holes in the z-buffer. Visible surfels are shaded using texture filtering, Phong illumination, and environment mapping using per-surfel normals. Several methods of image reconstruction, including supersampling, offer flexible speed-quality tradeoffs. Due to the simplicity of the operations, the surfel rendering pipeline is amenable for hardware implementation. Surfel objects offer complex shape, low rendering cost and high image quality, which makes them specifically suited for low-cost, real-time graphics, such as games.
---
paper_title: Layered depth images

paper_content:

In this paper we present a set of efficient image based rendering methods capable of rendering multiple frames per second on a PC. The first method warps Sprites with Depth representing smooth surfaces without the gaps found in other techniques. A second method for more general scenes performs warping from an intermediate representation called a Layered Depth Image (LDI). An LDI is a view of the scene from a single input camera view, but with multiple pixels along each line of sight. The size of the representation grows only linearly with the observed depth complexity in the scene. Moreover, because the LDI data are represented in a single image coordinate system, McMillan’s warp ordering algorithm can be successfully adapted. As a result, pixels are drawn in the output image in back-to-front order. No z-buffer is required, so alphacompositing can be done efficiently without depth sorting. This makes splatting an efficient solution to the resampling problem.
---
paper_title: Generalized Voxel Coloring

paper_content:

Image-based reconstruction from randomly scattered views is a challenging problem. We present a new algorithm that extends Seitz and Dyer's Voxel Coloring algorithm. Unlike their algorithm, ours can use images from arbitrary camera locations. The key problem in this class of algorithms is that of identifying the images from which a voxel is visible. Unlike Kutulakos and Seitz's Space Carving technique, our algorithm solves this problem exactly and the resulting reconstructions yield better results in our application, which is synthesizing new views. One variation of our algorithm minimizes color consistency comparisons; another uses less memory and can be accelerated with graphics hardware. We present efficiency measurements and, for comparison, we present images synthesized using our algorithm and Space Carving.
---
paper_title: On visible surface generation by a priori tree structures

paper_content:

This paper describes a new algorithm for solving the hidden surface (or line) problem, to more rapidly generate realistic images of 3-D scenes composed of polygons, and presents the development of theoretical foundations in the area as well as additional related algorithms. As in many applications the environment to be displayed consists of polygons many of whose relative geometric relations are static, we attempt to capitalize on this by preprocessing the environment's database so as to decrease the run-time computations required to generate a scene. This preprocessing is based on generating a “binary space partitioning” tree whose in order traversal of visibility priority at run-time will produce a linear order, dependent upon the viewing position, on (parts of) the polygons, which can then be used to easily solve the hidden surface problem. In the application where the entire environment is static with only the viewing-position changing, as is common in simulation, the results presented will be sufficient to solve completely the hidden surface problem.
---
paper_title: Modelling with implicit surfaces that interpolate

paper_content:

We introduce new techniques for modelling with interpolating implicit surfaces. This form of implicit surface was first used for problems of surface reconstruction and shape transformation, but the emphasis of our work is on model creation. These implicit surfaces are described by specifying locations in 3D through which the surface should pass, and also identifying locations that are interior or exterior to the surface. A 3D implicit function is created from these constraints using a variational scattered data interpolation approach, and the iso-surface of this function describes a surface. Like other implicit surface descriptions, these surfaces can be used for CSG and interference detection, may be interactively manipulated, are readily approximated by polygonal tilings, and are easy to ray trace. A key strength for model creation is that interpolating implicit surfaces allow the direct specification of both the location of points on the surface and the surface normals. These are two important manipulation techniques that are difficult to achieve using other implicit surface representations such as sums of spherical or ellipsoidal Gaussian functions ("blobbies"). We show that these properties make this form of implicit surface particularly attractive for interactive sculpting using the particle sampling technique introduced by Witkin and Heckbert. Our formulation also yields a simple method for converting a polygonal model to a smooth implicit model, as well as a new way to form blends between objects.
---
paper_title: A theory of shape by space carving

paper_content:

In this paper we consider the problem of computing the 3D shape of an unknown, arbitrarily-shaped scene from multiple photographs taken at known but arbitrarily-distributed viewpoints. By studying the equivalence class of all 3D shapes that reproduce the input photographs, we prove the existence of a special member of this class, the photo hull, that (1) can be computed directly from photographs of the scene, and (2) subsumes all other members of this class. We then give a provably-correct algorithm called Space Carving, for computing this shape and present experimental results on complex real-world scenes. The approach is designed to (1) build photorealistic shapes that accurately model scene appearance from a wide range of viewpoints, and (2) account for the complex interactions between occlusion, parallax, shading, and their effects on arbitrary views of a 3D scene.
---
paper_title: A Hierarchical Data Structure for Representing the Spatial Decomposition of 3-D Objects

paper_content:

The polytree, a generalization of the octree data structure, retains most of the desirable features of the octree structure while offering several advantages.
---
paper_title: Reconstruction and representation of 3D objects with radial basis functions

paper_content:

We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair incomplete meshes. An object's surface is defined implicitly as the zero set of an RBF fitted to the given surface data. Fast methods for fitting and evaluating RBFs allow us to model large data sets, consisting of millions of surface points, by a single RBF — previously an impossible task. A greedy algorithm in the fitting process reduces the number of RBF centers required to represent a surface and results in significant compression and further computational advantages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from non-uniformly sampled data. Holes are smoothly filled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform meshes and we show that the RBF representation has advantages for mesh simplification and remeshing applications. Results are presented for real-world rangefinder data.
---
paper_title: Multidimensional binary search trees used for associative searching

paper_content:

This paper develops the multidimensional binary search tree (or k -d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k -d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O (log n ); deletion of the root, O ( n ( k -1)/ k ); deletion of a random node, O (log n ); and optimization (guarantees logarithmic performance of searches), O ( n log n ). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O ( n ( k - t )/ k )] and for nearest neighbor queries [empirically observed average running time of O (log n ).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k -d trees could be quite useful in many applications, and examples of potential uses are given.
---
paper_title: A Simple Method for Color Quantization: Octree Quantization

paper_content:

A new method for filling a color table is presented that produces pictures of similar quality as existing methods, but requires less memory and execution time. All colors of an image are inserted in an octree, and this octree is reduced from the leaves to the root in such a way that every pixel has a well defined maximum error. The algorithm is described in PASCAL notation.
---
paper_title: Efficient, Precise, and Accurate Utilization of the Uniqueness Constraint in Multi-View Stereo

paper_content:

In this paper, the depth cue due to the assumption of texture uniqueness is reviewed. The spatial direction over which a similarity measure is optimized, in order to establish a stereo correspondence, is considered and methods to increase the precision and accuracy of stereo reconstructions are presented. An efficient implementation of the above methods is offered, based on optimizations that evaluate potential correspondences hierarchically, in the spatial and angular dimensions. Furthermore, the expansion of the above techniques in a multi-view framework where calibration errors cause the misregistration of individually obtained reconstructions are considered, and a treatment of the data is proposed for the elimination of duplicate reconstructions of a single surface point. Finally, a processing step is proposed for the increase of reconstruction precision and post-processing of the final result. The above contributions are integrated in a generic and parallelizable implementation of the uniqueness constraint to observe speedup and increase in the fidelity of surface reconstruction.
---
paper_title: Topology and geometry of unorganized point clouds

paper_content:

We present a new method for defining neighborhoods, and assigning principal curvature frames, and mean and Gauss curvatures to the points of an unorganized oriented point-cloud. The neighborhoods are estimated by measuring implicitly the surface distance between points. The 3D shape recovery is based on conformal geometry, works directly on the cloud, does not rely on the generation of polygonal, or smooth models. Test results on publicly available synthetic data, as ground truth, demonstrate that the method compares favorably to the established approaches for quantitative 3D shape recovery. The proposed method is developed to serve applications involving point based rendering and reliable extraction of differential properties from noisy unorganized point-clouds.
---
paper_title: A volumetric method for building complex models from range images

paper_content:

A number of techniques have been developed for reconstructing surfaces by integrating groups of aligned range images. A desirable set of properties for such algorithms includes: incremental updating, representation of directional uncertainty, the ability to fill gaps in the reconstruction, and robustness in the presence of outliers. Prior algorithms possess subsets of these properties. In this paper, we present a volumetric method for integrating range images that possesses all of these properties. Our volumetric representation consists of a cumulative weighted signed distance function. Working with one range image at a time, we first scan-convert it to a distance function, then combine this with the data already acquired using a simple additive scheme. To achieve space efficiency, we employ a run-length encoding of the volume. To achieve time efficiency, we resample the range image to align with the voxel grid and traverse the range and voxel scanlines synchronously. We generate the final manifold by extracting an isosurface from the volumetric grid. We show that under certain assumptions, this isosurface is optimal in the least squares sense. To fill gaps in the model, we tessellate over the boundaries between regions seen to be empty and regions never observed. Using this method, we are able to integrate a large number of range images (as many as 70) yielding seamless, high-detail models of up to 2.6 million triangles.
---
paper_title: Hierarchical and adaptive visualization on nested grids

paper_content:

Modern numerical methods are capable to resolve fine structures in solutions of partial differential equations. Thereby they produce large amounts of data. The user wants to explore them interactively by applying visualization tools in order to understand the simulated physical process. Here we present a multiresolution approach for a large class of hierarchical and nested grids. It is based on a hierarchical traversal of mesh elements combined with an adaptive selection of the hierarchical depth. The adaptation depends on an error indicator which is closely related to the visual impression of the smoothness of isosurfaces or isolines, which are typically used to visualize data. Significant examples illustrate the applicability and efficiency on different types of meshes.
---
paper_title: Modeling in Volume Graphics

paper_content:

In traditional CAD and solid modeling, 3D objects are represented in terms of their geometric components. In contrast, in volume graphics 3D objects are represented by a discrete digital model, which is stored as a large 3D array of unit volume elements (voxels). The rapid progress in hardware, primarily in memory subsystems, has been recently transforming the field of volume graphics into a major trend which offers an alternative to traditional 3D surface graphics. This paper discusses volume graphics and several related modeling techniques.
---
paper_title: Light field mapping: efficient representation and hardware rendering of surface light fields

paper_content:

A light field parameterized on the surface offers a natural and intuitive description of the view-dependent appearance of scenes with complex reflectance properties. To enable the use of surface light fields in real-time rendering we develop a compact representation suitable for an accelerated graphics pipeline. We propose to approximate the light field data by partitioning it over elementary surface primitives and factorizing each part into a small set of lower-dimensional functions. We show that our representation can be further compressed using standard image compression techniques leading to extremely compact data sets that are up to four orders of magnitude smaller than the input data. Finally, we develop an image-based rendering method, light field mapping, that can visualize surface light fields directly from this compact representation at interactive frame rates on a personal computer. We also implement a new method of approximating the light field data that produces positive only factors allowing for faster rendering using simpler graphics hardware than earlier methods. We demonstrate the results for a variety of non-trivial synthetic scenes and physical objects scanned through 3D photography.
---
paper_title: Free viewpoint video extraction, representation, coding, and rendering

paper_content:

Free viewpoint video provides the possibility to freely navigate within dynamic real world video scenes by choosing arbitrary viewpoints and view directions. So far, related work only considered free viewpoint video extraction, representation, and rendering methods. Compression and transmission has not yet been studied in detail and combined with the other components into one complete system. In this paper, we present such a complete system for efficient free viewpoint video extraction, representation, coding, and interactive rendering. Data representation is based on 3D mesh models and view-dependent texture mapping using video textures. The geometry extraction is based on a shape-from-silhouette algorithm. The resulting voxel models are converted into 3D meshes that are coded using MPEG-4 SNHC tools. The corresponding video textures are coded using an H.264/AVC codec. Our algorithms for view-dependent texture mapping have been adopted as an extension of MPEG-4 AFX. The presented results illustrate that based on the proposed methods a complete transmission system for efficient free viewpoint video can be built.
---
paper_title: Modeling and rendering architecture from photographs: a hybrid geometry- and image-based approach

paper_content:

We present a new approach for modeling and rendering existing architectural scenes from a sparse set of still photographs. Our modeling approach, which combines both geometry-based and imagebased techniques, has two components. The first component is a photogrammetricmodeling method which facilitates the recovery of the basic geometry of the photographed scene. Our photogrammetric modeling approach is effective, convenient, and robust because it exploits the constraints that are characteristic of architectural scenes. The second component is a model-based stereo algorithm, which recovers how the real scene deviates from the basic model. By making use of the model, our stereo technique robustly recovers accurate depth from widely-spaced image pairs. Consequently, our approach can model large architectural environments with far fewer photographs than current image-based modeling approaches. For producing renderings, we present view-dependent texture mapping, a method of compositing multiple views of a scene that better simulates geometric detail on basic models. Our approach can be used to recover models for use in either geometry-based or image-based rendering systems. We present results that demonstrate our approach’s ability to create realistic renderings of architectural scenes from viewpoints far from the original photographs. CR Descriptors: I.2.10 [Artificial Intelligence]: Vision and Scene Understanding Modeling and recovery of physical attributes; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism Color, shading, shadowing, and texture I.4.8 [Image Processing]: Scene Analysis Stereo; J.6 [Computer-Aided Engineering]: Computer-aided design (CAD).
---
paper_title: Opacity light fields: interactive rendering of surface light fields with view-dependent opacity

paper_content:

We present new hardware-accelerated techniques for rendering surface light fields with opacity hulls that allow for interactive visualization of objects that have complex reflectance properties and elaborate geometrical details. The opacity hull is a shape enclosing the object with view-dependent opacity parameterized onto that shape. We call the combination of opacity hulls and surface light fields the opacity light field. Opacity light fields are ideally suited for rendering of the visually complex objects and scenes obtained with 3D photography. We show how to implement opacity light fields in the framework of three surface light field rendering methods: view-dependent texture mapping, unstructured lumigraph rendering, and light field mapping. The modified algorithms can be effectively supported on modern graphics hardware. Our results show that all three implementations are able to achieve interactive or real-time frame rates.
---
paper_title: Unstructured lumigraph rendering

paper_content:

We describe an image based rendering approach that generalizes many current image based rendering algorithms, including light field rendering and view-dependent texture mapping. In particular, it allows for lumigraph-style rendering from a set of input cameras in arbitrary configurations (i.e., not restricted to a plane or to any specific manifold). In the case of regular and planar input camera positions, our algorithm reduces to a typical lumigraph approach. When presented with fewer cameras and good approximate geometry, our algorithm behaves like view-dependent texture mapping. The algorithm achieves this flexibility because it is designed to meet a set of specific goals that we describe. We demonstrate this flexibility with a variety of examples.
---
paper_title: Light field rendering

paper_content:

A number of techniques have been proposed for flying through scenes by redisplaying previously rendered or digitized views. Techniques have also been proposed for interpolating between views by warping input images, using depth information or correspondences between multiple images. In this paper, we describe a simple and robust method for generating new views from arbitrary camera positions without depth information or feature matching, simply by combining and resampling the available images. The key to this technique lies in interpreting the input images as 2D slices of a 4D function the light field. This function completely characterizes the flow of light through unobstructed space in a static scene with fixed illumination. We describe a sampled representation for light fields that allows for both efficient creation and display of inward and outward looking views. We hav e created light fields from large arrays of both rendered and digitized images. The latter are acquired using a video camera mounted on a computer-controlled gantry. Once a light field has been created, new views may be constructed in real time by extracting slices in appropriate directions. Since the success of the method depends on having a high sample rate, we describe a compression system that is able to compress the light fields we have generated by more than a factor of 100:1 with very little loss of fidelity. We also address the issues of antialiasing during creation, and resampling during slice extraction. CR Categories: I.3.2 [Computer Graphics]: Picture/Image Generation — Digitizing and scanning, Viewing algorithms; I.4.2 [Computer Graphics]: Compression — Approximate methods Additional keywords: image-based rendering, light field, holographic stereogram, vector quantization, epipolar analysis
---
paper_title: A Real-Time Distributed Light Field Camera

paper_content:

We present the design and implementation of a real-time, distributed light field camera. Our system allows multiple viewers to navigate virtual cameras in a dynamically changing light field that is captured in real-time. Our light field camera consists of 64 commodity video cameras that are connected to off-the-shelf computers. We employ a distributed rendering algorithm that allows us to overcome the data bandwidth problems inherent in dynamic light fields. Our algorithm works by selectively transmitting only those portions of the video streams that contribute to the desired virtual views. This technique not only reduces the total bandwidth, but it also allows us to scale the number of cameras in our system without increasing network bandwidth. We demonstrate our system with a number of examples.
---
paper_title: Interpolating view and scene motion by dynamic view morphing

paper_content:

We introduce the problem of view interpolation for dynamic scenes. Our solution to this problem extends the concept of view morphing and retains the practical advantages of that method. We are specifically concerned with interpolating between two reference views captured at different times, so that there is a missing interval of time between when the views were taken. The synthetic interpolations produced by our algorithm portray one possible physically-valid version of what transpired in the scene during the missing time. It is assumed that each object in the original scene underwent a series of rigid translations. Dynamic view morphing can work with widely-spaced reference views, sparse point correspondences, and uncalibrated cameras. When the camera-to-camera transformation can be determined, the synthetic interpolation will portray scene objects moving along straight-line, constant-velocity trajectories in world space.
---
paper_title: The Plenoptic Function and the Elements of Early Vision

paper_content:

This chapter contains sections titled: The Plenoptic Function, Plenoptic Structures, The Plenoptic Function and Elemental Measurements in Early Vision, Plenoptic Measurements in the Human Visual System, Periodic Tables for Early Vision, Further Computations, Conclusion, Appendix, References
---
paper_title: Novel View Synthesis by Cascading Trilinear Tensors

paper_content:

Presents a new method for synthesizing novel views of a 3D scene from two or three reference images in full correspondence. The core of this work is the use and manipulation of an algebraic entity, termed the "trilinear tensor", that links point correspondences across three images. For a given virtual camera position and orientation, a new trilinear tensor can be computed based on the original tensor of the reference images. The desired view can then be created using this new trilinear tensor and point correspondences across two of the reference images.
---
paper_title: Light field rendering

paper_content:

A number of techniques have been proposed for flying through scenes by redisplaying previously rendered or digitized views. Techniques have also been proposed for interpolating between views by warping input images, using depth information or correspondences between multiple images. In this paper, we describe a simple and robust method for generating new views from arbitrary camera positions without depth information or feature matching, simply by combining and resampling the available images. The key to this technique lies in interpreting the input images as 2D slices of a 4D function the light field. This function completely characterizes the flow of light through unobstructed space in a static scene with fixed illumination. We describe a sampled representation for light fields that allows for both efficient creation and display of inward and outward looking views. We hav e created light fields from large arrays of both rendered and digitized images. The latter are acquired using a video camera mounted on a computer-controlled gantry. Once a light field has been created, new views may be constructed in real time by extracting slices in appropriate directions. Since the success of the method depends on having a high sample rate, we describe a compression system that is able to compress the light fields we have generated by more than a factor of 100:1 with very little loss of fidelity. We also address the issues of antialiasing during creation, and resampling during slice extraction. CR Categories: I.3.2 [Computer Graphics]: Picture/Image Generation — Digitizing and scanning, Viewing algorithms; I.4.2 [Computer Graphics]: Compression — Approximate methods Additional keywords: image-based rendering, light field, holographic stereogram, vector quantization, epipolar analysis
---
paper_title: View Interpolation for Dynamic Scenes

paper_content:

This paper describes a novel technique for synthesizing a dynamic scene from two images without the use of a 3D model. A scene containing rigid or non-rigid objects, in which each object can move in any orientation or direction, is considered. It is shown that such a scene can be converted into several equivalent static scenes, where each scene only includes one rigid object. Our method can generate a series of continuous and realistic intermediate views from only two reference images without 3D knowledge. The procedure consists of three main steps: segmentation, morphing and postwarping. The key frames are first segmented into several layers. Each layer can be realistically morphed after determining its fundamental matrix. Based on the decomposition of 3D rotation matrix, an optimized and unique postwarping path is automatically determined by the least distortion method and boundary connection constraint. Finally, four experiments, which include morphing of a rotating rigid object in presence of occlusion and morphing of non-rigid objects (human), are demonstrated.
---
paper_title: Free viewpoint video synthesis and presentation from multiple sporting videos

paper_content:

This paper introduces two kinds of free viewpoint observation systems for sporting events captured with uncalibrated multiple cameras in a stadium. In the first system (viewpoint on demand system), a user can watch the realistic sporting scenes with the original stadium. In the second system (mixed reality presentation system), a user can virtually watch the scenes overlaid on a desktop stadium model via a video see-through head mounted display (HMD). In the both systems, the user can observe sporting events from his/her favorite viewpoints, where the virtual view images are synthesized and presented by performing view interpolation. As outdoor scenes often have variations in lighting, we develop the systems to handle the changes of lighting condition. If the captured scene contains shadows, we synthesize the virtual view image of the shadows of the background and the foreground independently from real camera images using projective geometry between cameras. The shadows of the foreground objects are then overlaid on the synthesized background of the original stadium or the stadium model in front of the user respectively. The results indicate that the appearance of shadows can produce a realistic mixed reality presentation.
---
paper_title: View interpolation for image synthesis

paper_content:

Image-space simplifications have been used to accelerate the calculation of computer graphic images since the dawn of visual simulation. Texture mapping has been used to provide a means by which images may themselves be used as display primitives. The work reported by this paper endeavors to carry this concept to its logical extreme by using interpolated images to portray three-dimensional scenes. The special-effects technique of morphing, which combines interpolation of texture maps and their shape, is applied to computing arbitrary intermediate frames from an array of prestored images. If the images are a structured set of views of a 3D object or scene, intermediate frames derived by morphing can be used to approximate intermediate 3D transformations of the object or scene. Using the view interpolation approach to synthesize 3D scenes has two main advantages. First, the 3D representation of the scene may be replaced with images. Second, the image synthesis time is independent of the scene complexity. The correspondence between images, required for the morphing method, can be predetermined automatically using the range data associated with the images. The method is further accelerated by a quadtree decomposition and a view-independent visible priority. Our experiments have shown that the morphing can be performed at interactive rates on today’s high-end personal computers. Potential applications of the method include virtual holograms, a walkthrough in a virtual environment, image-based primitives and incremental rendering. The method also can be used to greatly accelerate the computation of motion blur and soft shadows cast by area light sources. CR Categories and Subject Descriptors: I.3.3 [Computer Graphics]: Picture/Image Generation; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism. Additional Keywords: image morphing, interpolation, virtual reality, motion blur, shadow, incremental rendering, real-time display, virtual holography, motion compensation.
---
paper_title: Survey of image-based representations and compression techniques

paper_content:

We survey the techniques for image-based rendering (IBR) and for compressing image-based representations. Unlike traditional three-dimensional (3-D) computer graphics, in which 3-D geometry of the scene is known, IBR techniques render novel views directly from input images. IBR techniques can be classified into three categories according to how much geometric information is used: rendering without geometry, rendering with implicit geometry (i.e., correspondence), and rendering with explicit geometry (either with approximate or accurate geometry). We discuss the characteristics of these categories and their representative techniques. IBR techniques demonstrate a surprising diverse range in their extent of use of images and geometry in representing 3-D scenes. We explore the issues in trading off the use of images and geometry by revisiting plenoptic-sampling analysis and the notions of view dependency and geometric proxies. Finally, we highlight compression techniques specifically designed for image-based representations. Such compression techniques are important in making IBR techniques practical.
---
paper_title: Automatic extraction of Irregular Network digital terrain models

paper_content:

For representation of terrain, an efficient alternative to dense grids is the Triangulated Irregular Network (TIN), which represents a surface as a set of non-overlapping contiguous triangular facets, of irregular size and shape. The source of digital terrain data is increasingly dense raster models produced by automated orthophoto machines or by direct sensors such as synthetic aperture radar. A method is described for automatically extracting a TIN model from dense raster data. An initial approximation is constructed by automatically triangulating a set of feature points derived from the raster model. The method works by local incremental refinement of this model by the addition of new points until a uniform approximation of specified tolerance is obtained. Empirical results show that substantial savings in storage can be obtained.
---
paper_title: Procedural modeling of cities

paper_content:

Modeling a city poses a number of problems to computer graphics. Every urban area has a transportation network that follows population and environmental influences, and often a superimposed pattern plan. The buildings appearances follow historical, aesthetic and statutory rules. To create a virtual city, a roadmap has to be designed and a large number of buildings need to be generated. We propose a system using a procedural approach based on L-systems to model cities. From various image maps given as input, such as land-water boundaries and population density, our system generates a system of highways and streets, divides the land into lots, and creates the appropriate geometry for the buildings on the respective allotments. For the creation of a city street map, L-systems have been extended with methods that allow the consideration of global goals and local constraints and reduce the complexity of the production rules. An L-system that generates geometry and a texturing system based on texture elements and procedural methods compose the buildings.
---
paper_title: The Algorithmic Beauty of Plants-The Virtual Laboratory

paper_content:

A bipartite eyeglass temple including a front section attached to an eyeglass frame and a rear section terminating in an ear engaging portion. Said front and rear sections are adjustably connected together so that the length of the temple can be varied to most comfortably accommodate the temple to a particular wearer. In addition, the rear section can be adjusted to vary the tension of a resilient means which yieldably urges said rear section forwardly for holding its rear part in engagement with the ear. The rear section may also be rotatably adjusted for conformably and most comfortably engaging the head behind the ear.
---
paper_title: The Fractal Geometry of Nature

paper_content:

"...a blend of erudition (fascinating and sometimes obscure historical minutiae abound), popularization (mathematical rigor is relegated to appendices) and exposition (the reader need have little knowledge of the fields involved) ...and the illustrations include many superb examples of computer graphics that are works of art in their own right." Nature
---
paper_title: Instant architecture

paper_content:

This paper presents a new method for the automatic modeling of architecture. Building designs are derived using split grammars, a new type of parametric set grammar based on the concept of shape. The paper also introduces an attribute matching system and a separate control grammar, which offer the flexibility required to model buildings using a large variety of different styles and design ideas. Through the adaptive nature of the design grammar used, the created building designs can either be generic or adhere closely to a specified goal, depending on the amount of data available.
---
paper_title: Spacetime constraints

paper_content:

Spacetime constraints are a new method for creating character animation. The animator specifies what the character has to do, for instance, "jump from here to there, clearing a hurdle in between;" how the motion should be performed, for instance "don't waste energy," or "come down hard enough to splatter whatever you land on;" the character's physical structure---the geometry, mass, connectivity, etc. of the parts; and the physical resources' available to the character to accomplish the motion, for instance the character's muscles, a floor to push off from, etc. The requirements contained in this description, together with Newton's laws, comprise a problem of constrained optimization. The solution to this problem is a physically valid motion satisfying the "what" constraints and optimizing the "how" criteria. We present as examples a Luxo lamp performing a variety of coordinated motions. These realistic motions conform to such principles of traditional animation as anticipation, squash-and-stretch, follow-through, and timing.
---
paper_title: Computer Animation: Algorithms and Techniques

paper_content:

Driven by demand from the entertainment industry for better and more realistic animation, technology continues to evolve and improve. The algorithms and techniques behind this technology are the foundation of this comprehensive book, which is written to teach?you the fundamentals of animation programming. ::: ::: In this third edition, the most current techniques are covered along with the theory and high-level computation that have earned the book a reputation as the best technically-oriented animation resource. Key topics such as fluids, hair, and crowd animation have been expanded, and extensive new coverage of clothes and cloth has been added. New material on simulation provides a more diverse look at this important area and more example animations and chapter projects and exercises are included. Additionally, spline coverage has been expanded and new video compression and formats (e.g., iTunes) are covered. ::: ::: ::: ::: * Includes companion site with contemporary animation examples drawn from research and entertainment, sample animations, and example code * Describes the key mathematical and algorithmic foundations of animation that provide you with a deep understanding and control of technique * Expanded and new coverage of key topics including: fluids and clouds, cloth and clothes, hair, and crowd animation *?Explains the algorithms used for path following, hierarchical kinematic modelling, rigid body dynamics, flocking behaviour, particle systems, collision detection, and more ::: Table of Contents ::: ::: ::: Chapter 1: Introduction ::: ::: Chapter 2: Technical Background ::: ::: Chapter 3: Interpolating Values ::: ::: Chapter 4: Interpolation-Based Animation ::: ::: Chapter 5: Kinematic Linkages ::: ::: Chapter 6: Motion Capture ::: ::: Chapter 7: Physically Based Animation ::: ::: Chapter 8: Fluids: Liquids & Gases ::: ::: Chapter 9: Modeling and Animating Human Figures ::: ::: Chapter 10: Facial Animation ::: ::: Chapter 11: Behavioral Animation ::: ::: Chapter 12: Special Models for Animation ::: ::: Appendix A: Rendering Issues ::: ::: Appendix B: Background Information and Techniques ::: ::: Index
---
paper_title: Elastically deformable models

paper_content:

The theory of elasticity describes deformable materials such as rubber, cloth, paper, and flexible metals. We employ elasticity theory to construct differential equations that model the behavior of non-rigid curves, surfaces, and solids as a function of time. Elastically deformable models are active: they respond in a natural way to applied forces, constraints, ambient media, and impenetrable obstacles. The models are fundamentally dynamic and realistic animation is created by numerically solving their underlying differential equations. Thus, the description of shape and the description of motion are unified.
---
paper_title: Fast animation and control of nonrigid structures

paper_content:

We describe a fast method for creating physically based animationof non-rigid objects. Rapid simulation of non- rigid behavior isbased on global deformations. Con- straints are used to connectnon-rigid pieces to each other, forming complex models. Constraintsalso provide mo- tion control, allowing model points to be movedaccurately along specified trajectories. The use of deformationsthat are linear in the state of the system causes the constraintmatrices to be constant. Pre-inverting these matrices there- foreyields an enormous benefit in performance, allowing reasonablycomplex models to be manipulated at interac- tive speed.
---
paper_title: Physically based models with rigid and deformable components

paper_content:

A class of physically based models suitable for animating flexible objects in simulated physical environments was proposed earlier by the authors (1987). The original formulation works as well in practice for models whose shapes are moderately to highly deformable, but it tends to become numerically ill conditioned as the rigidity of the models is increased. An alternative formulation of deformable models is presented in which deformations are decomposed into a reference component, which may represent an arbitrary shape, and a displacement component, allowing deformation away from this reference shape. The application of the deformable models to a physically based computer animation project is illustrated. >
---
paper_title: Dynamic deformation of solid primitives with constraints

paper_content:

This paper develops a systematic approach to deriving dynamic models from parametrically defined solid primitives, global geometric deformations and local finite- element deformations. Even though their kinematics is styl- ized by the particular solid primitive used, the models be- have in a physically correct way with prescribed mass dis- tributions and elasticities. We also propose efficient con- straint methods for connecting these new dynamic primitives together to make articulated models. Our techniques make it possible to build and animate constrained, nonrigid, unibody or multibody objects in simulated physical environments at interactive rates. 1 Introduction The graphics literature is replete with solid object representa- tions. Unfortunately, it is not particularly easy to synthesize realistic animation through direct application of the geomet- ric representations of solid modeling (5), and the problems are exacerbated when animate objects can deform. Physics- based animation has begun to overcome some of the difficul- ties. We propose a systematic approach for creating dynamic solid models capable of realistic physical behaviors starting from common solid primitives such as spheres, cylinders, cones, or superquadrics. Such primitives can "deform" kine- matically in simple ways; for example, a cylinder deforms as its radius or length is changed. To gain additional model- ing power we allow the primitives to undergo parameterized global deformations (bends, tapers, twists, shears, etc.) of the sort proposed in (2). To further enhance the geometric flexibility, we permit local free-form deformations. Our lo- cal deformations are similar in spirit to the FFDs of (12), but rather than being ambient space warps (12, 10), they are in- corporated directly into the solid primitive as finite element shape functions. Through the application of Lagrangian mechanics and the finite element method our models inherit generalized coor- dinates that comprise the geometric parameters of the solid primitive, the global and local deformation parameters, and the six degrees of freedom of rigid-body motion. Lagrange equations govern the dynamics, dictating the evolution of the
---
paper_title: A modeling system based on dynamic constraints

paper_content:

We present "dynamic constraints," a physically-based technique for constraint-based control of computer graphics models. Using dynamic constraints, we build objects by specifying geometric constraints; the models assemble themselves as the elements move to satisfy the constraints. The individual elements are rigid bodies which act in accordance with the rules of physics, and can thus exhibit physically realistic behavior. To implement the constraints, a set of "constraint forces" is found, which causes the bodies to act in accordance with the constraints; finding these "constraint forces" is an inverse dynamics problem.
---
paper_title: The rendering equation

paper_content:

We present an integral equation which generalizes a variety of known rendering algorithms. In the course of discussing a monte carlo solution we also present a new form of variance reduction, called Hierarchical sampling and give a number of elaborations shows that it may be an efficient new technique for a wide variety of monte carlo procedures. The resulting rendering algorithm extends the range of optical phenomena which can be effectively simulated.
---
paper_title: A Ray tracing algorithm for progressive radiosity

paper_content:

A new method for computing form-factors within a progressive radiosity approach is presented. Previously, the progressive radiosity approach has depended on the use of the hemi-cube algorithm to determine form-factors. However, sampling problems inherent in the hemi-cube algorithm limit its usefulness for complex images. A more robust approach is described in which ray tracing is used to perform the numerical integration of the form-factor equation. The approach is tailored to provide good, approximate results for a low number of rays, while still providing a smooth continuum of increasing accuracy for higher numbers of rays. Quantitative comparisons between analytically derived form-factors and ray traced form-factors are presented.
---
paper_title: Realistic Image Synthesis Using Photon Mapping

paper_content:

The creation of photorealistic images of three-dimensional models is central to computer graphics. Photon mapping, an extension of ray tracing, makes it possible to efficiently simulate global illumination in complex scenes. Photon mapping can simulate caustics (focused light, like shimmering waves at the bottom of a swimming pool), diffuse inter-reflections (e.g., the bleeding of colored light from a red wall onto a white floor, giving the floor a reddish tint), and participating media (such as clouds or smoke). This book is a practical guide to photon mapping; it provides both the theory and the practical insight necessary to implement photon mapping and simulate all types of direct and indirect illumination efficiently.
---
paper_title: Environment Mapping and Other Applications of World Projections

paper_content:

Various techniques have been developed that employ projections of the world as seen from a particular viewpoint. Blinn and Newell introduced reflection mapping for simulating mirror reflections on curved surfaces. Miller and Hoffman have presented a general illumination model based on environment mapping. World projections have also been used to model distant objects and to produce pictures with the fish-eye distortion required for Omnimax frames. This article proposes a uniform framework for representing and using world projections and argues that the best general-purpose representation is the is projection onto a cube. Surface shading and texture filtering are discussed in the context of environment mapping, and methods are presented for obtaining diffuse and specular surface illumination from prefiltered environment maps. Comparisons are made with ray tracing, noting that two problems with ray tracing?obtaining diffuse reflection and antialiasing specular reflection?can be handled effectively by environment mapping.
---
paper_title: Continuous shading of curved surfaces

paper_content:

A procedure for computing shaded pictures of curved surfaces is presented. The surface is approximated by small polygons in order to solve easily the hidden-parts problem, but the shading of each polygon is computed so that the discontinuities of shade are eliminated across the surface and a smooth appearance is obtained. In order to achieve speed efficiency, the technique developed by Watkins is used which makes possible a hardware implementation of this algorithm.
---
paper_title: Illumination for computer generated pictures

paper_content:

The quality of computer generated images of three-dimensional scenes depends on the shading technique used to paint the objects on the cathode-ray tube screen. The shading algorithm itself depends in part on the method for modeling the object, which also determines the hidden surface algorithm. The various methods of object modeling, shading, and hidden surface removal are thus strongly interconnected. Several shading techniques corresponding to different methods of object modeling and the related hidden surface algorithms are presented here. Human visual perception and the fundamental laws of optics are considered in the development of a shading rule that provides better quality and increased realism in generated images.
---
paper_title: Simulation of wrinkled surfaces

paper_content:

Computer generated shaded images have reached an impressive degree of realism with the current state of the art. They are not so realistic, however, that they would fool many people into believing they are real. One problem is that the surfaces tend to look artificial due to their extreme smoothness. What is needed is a means of simulating the surface irregularities that are on real surfaces. In 1973 Ed Catmull introduced the idea of using the parameter values of parametrically defined surfaces to index into a texture definition function which scales the intensity of the reflected light. By tying the texture pattern to the parameter values, the texture is guaranteed to rotate and move with the object. This is good for showing patterns painted on the surface, but attempts to simulate rough surfaces in this way are unconvincing. This paper presents a method of using a texturing function to perform a small perturbation on the direction of the surface normal before using it in the intensity calculations. This process yields images with realistic looking surface wrinkles without the need to model each wrinkle as a separate surface element. Several samples of images made with this technique are included.
---
paper_title: Layered construction for deformable animated characters

paper_content:

A methodology is proposed for creating and animating computer generated characters which combines recent research advances in robotics, physically based modeling and geometric modeling. The control points of geometric modeling deformations are constrained by an underlying articulated robotics skeleton. These deformations are tailored by the animator and act as a muscle layer to provide automatic squash and stretch behavior of the surface geometry. A hierarchy of composite deformations provides the animator with a multi-layered approach to defining both local and global transition of the character's shape. The muscle deformations determine the resulting geometric surface of the character. This approach provides independent representation of articulation from surface geometry, supports higher level motion control based on various computational models, as well as a consistent, uniform character representation which can be tuned and tweaked by the animator to meet very precise expressive qualities. A prototype system (Critter) currently under development demonstrates research results towards layered construction of deformable animated characters.
---
paper_title: Digital Representations of Human Movement

paper_content:

There are many different approaches to the representation, wlthm a digital computer, of mformatlon describing the movement of the human body. The general Issue of movement representatmn is approached from two points of vmw: notatmn systems designed for recording movement and ammation systems designed for the display of movement. The interpretation of one partmular notation system, Labanotatlon, is examined to extract a set of "primitive movement concepts" which can be used to animate a realistic human body on a graphics display The body is represented computatlonally as a network of specml-purpose processors--one processor situated at each joint of the body--each with an instructmn set demgned around the movement concepts derived from Labanotatlon Movement Is achmved by slmulatmg the behawor of these processors as they interpret their respective programs.
---
paper_title: Real time muscle deformations using mass-spring systems

paper_content:

We propose a method to simulate muscle deformation in real-time, still aiming at satisfying visual results; that is, we are not attempting perfect simulation but building a useful tool for interactive applications. Muscles are represented at 2 levels: the action lines and the muscle shape. The action line represents the force produced by a muscle on the bones, while the muscle shapes used in the simulation consist of a surface based model fitted to the boundary of medical image data. The algorithm to model muscle shapes is described. To physically simulate deformations, we used a mass-spring system with a new kind of springs called "angular springs" which were developed to control the muscle volume during simulation. Results are presented as examples at the end of the paper.
---
paper_title: 3-D model-based tracking of humans in action: a multi-view approach

paper_content:

We present a vision system for the 3-D model-based tracking of unconstrained human movement. Using image sequences acquired simultaneously from multiple views, we recover the 3-D body pose at each time instant without the use of markers. The pose-recovery problem is formulated as a search problem and entails finding the pose parameters of a graphical human model whose synthesized appearance is most similar to the actual appearance of the real human in the multi-view images. The models used for this purpose are acquired from the images. We use a decomposition approach and a best-first technique to search through the high dimensional pose parameter space. A robust variant of chamfer matching is used as a fast similarity measure between synthesized and real edge images. We present initial tracking results from a large new Humans-in-Action (HIA) database containing more than 2500 frames in each of four orthogonal views. They contain subjects involved in a variety of activities, of various degrees of complexity, ranging from the more simple one-person hand waving to the challenging two-person close interaction in the Argentine Tango.
---
paper_title: Ballerinas generated by a personal computer

paper_content:

Beautiful 3-D figures of ballerinas have been generated by a non-professional artist using a personal computer with commercially available ray-tracing software and metaballs. This paper describes how these beautiful artistic creations have been drawn using very limited computational tools.
---
paper_title: Human skin model capable of natural shape variation

paper_content:

In the production of character animation that treats living things moving at will, as in the case of humans and animals, it is important to express natural action and realistic body shape. If we can express these freely and easily, we will be able to apply character animation to many fields, such as the simulation of dances and sports, and electronic stand-ins. The computer graphics technique may be one of the most effective means to achieve such goals. We have developed human skin model capable of natural shape variation. This model has a skeleton structure, and free form surfaces cover the skeleton just like skin. The model permits continuous motion of every components of the skeleton according to actions. During such movements, the skin retains smoothness and naturalness. We are verifying the human skin model by producing several short animation pieces.
---
paper_title: Real-time Display of Virtual Humans: Levels of Details and Impostors

paper_content:

Rendering and animating in real-time a multitude of articulated characters presents a real challenge, and few hardware systems are up to the task. Up to now, little research has been conducted to tackle the issue of real-time rendering of numerous virtual humans. This paper presents a hardware-independent technique that improves the display rate of animated characters by acting on the sole geometric and rendering information. We first review the acceleration techniques traditionally in use in computer graphics and highlight their suitability to articulated characters. We then show how impostors can be used to render virtual humans. We introduce concrete case studies that demonstrate the effectiveness of our approach. Finally, we tackle the visibility issue.
---
paper_title: Subdivision surfaces in character animation

paper_content:

The creation of believable and endearing characters in computer graphics presents a number of technical challenges, including the modeling, animation and rendering of complex shapes such as heads, hands, and clothing. Traditionally, these shapes have been modeled with NURBS surfaces despite the severe topological restrictions that NURBS impose. In order to move beyond these restrictions, we have recently introduced subdivision surfaces into our production environment. Subdivision surfaces are not new, but their use in high-end CG production has been limited. Here we describe a series of developments that were required in order for subdivision surfaces to meet the demands of high-end production. First, we devised a practical technique for constructing provably smooth variable-radius fillets and blends. Second, we developed methods for using subdivision surfaces in clothing simulation including a new algorithm for efficient collision detection. Third, we developed a method for constructing smooth scalar fields on subdivision surfaces, thereby enabling the use of a wider class of programmable shaders. These developments, which were used extensively in our recently completed short film Geri’s game, have become a highly valued feature of our production environment. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; I.3.3 [Computer Graphics]: Picture/Image Generation.
---
paper_title: Layered construction for deformable animated characters

paper_content:

A methodology is proposed for creating and animating computer generated characters which combines recent research advances in robotics, physically based modeling and geometric modeling. The control points of geometric modeling deformations are constrained by an underlying articulated robotics skeleton. These deformations are tailored by the animator and act as a muscle layer to provide automatic squash and stretch behavior of the surface geometry. A hierarchy of composite deformations provides the animator with a multi-layered approach to defining both local and global transition of the character's shape. The muscle deformations determine the resulting geometric surface of the character. This approach provides independent representation of articulation from surface geometry, supports higher level motion control based on various computational models, as well as a consistent, uniform character representation which can be tuned and tweaked by the animator to meet very precise expressive qualities. A prototype system (Critter) currently under development demonstrates research results towards layered construction of deformable animated characters.
---
paper_title: Understanding Motion Capture for Computer Animation and Video Games

paper_content:

From the Publisher: ::: In Understanding Motion Capture for Computer Animation and Video Games, industry insider Alberto Menache tells the complete story of motion capture, examining its technical details as well as its growth as an industry. Menache's narrative voice and in-depth technical discussions allow the reader not only to learn motion capture, but also to understand the reasons behind its successes, failures, and increasing role in such blockbuster films as Batman Forever and Batman and Robin. With its careful balance between technical analysis and industry trends, Understanding Motion Capture for Computer Animation and Video Games is the first book to explore the controversial art and practice of modern character animation using motion capture.
---
paper_title: Articulated Figure Positioning by Multiple Constraints

paper_content:

A problem that arises in positioning an articulated figure is the solution of 3D joint positions (kinematics) when goal positions, rather than joint angles, are given. If more than one such goal is o be achived, tge problem is often solved interactively by positioning or solving one component of the linkage, then adjusting another, then redoing the first, and so on. This iterative process us skiw abd tedious. We present a method that automatically solves multiple simultaneous joint position goals. The user interface offers a six-degree-of-freedom input device to specify joint angles and goal positions interactively. Examplesare used to demonstrate the power and efficiency of this method for keypositon animation.
---
paper_title: Making Them Move: Mechanics, Control & Animation of Articulated Figures

paper_content:

Making Them Move: Mechanics, Control, and Animation of Articulated Figures Edited by Norman I. Badler, Brian A. Barsky, and David Zeltzer PART ONE -- INTERACTING WITH ARTICULATED FIGURES Chapter 1 Task-level Graphical Simulation: Abstraction, Representation, and Control David Zeltzer Chapter 2 Composition of Realistic Animation Sequences for Multiple Human Figures Tom Calvert Chapter 3 Animation from Instructions Norman I. Badler, Bonnie L. Webber, Jugal Kalita, and Jeffrey Esakov PART TWO -- ARTIFICIAL AND BIOLOGICAL MECHANISMS FOR MOTOR CONTROL ARTIFICIAL MOTOR PROGRAMS Chapter 4 A Robot that Walks: Emergent Behaviors from a Carefully Evolved Network Rodney A. Brooks BIOLOGICAL MOTOR PROGRAMS Chapter 5 Sensory Elements in Pattern-Generating Networks K.G. Pearson Chapter 6 Motor Programs as Units of Movement Control Douglas E. Young and Richard A. Schmidt Chapter 7 Dynamics and Task-specific Coordinations M.T. Turvey, Elliot Saltzman, and R.C. Schmidt Chapter 8 Dynamic Pattern Generation and Recognition J.A.S. Kelso and A.S. Pandya LEARNING MOTOR PROGRAMS Chapter 9 A Computer System for Movement Schemas Peter H. Greene and Dan Solomon PART THREE -- MOTION CONTROL ALGORITHMS Chapter 10 Constrained Optimization of Articulated Animal Movement in Computer Animation Michael Girard Chapter 11 Goal-directed Animation of Tubular Articulated Figures or How Snakes Play Golf Gavin Miller Chapter 12 Human Body Deformations Using Joint-dependent Local Operators and Finite-Element Theory Nadia Magnenat-Thalmann and Daniel Thalmann PART FOUR -- COMPUTING THE DYNAMICS OF MOTION Chapter 13 Dynamic Experiences Jane Wilhelms Chapter 14 Using Dynamics in Computer Animation: Control and Solution Issues Mark Green Chapter 15 Teleological Modeling Alan H. Barr Appendix A: Video Notes Appendix B: About the Authors Index
---
paper_title: Interactive animation of parametric models

paper_content:

This paper describes a program which allows parametric models of three-dimensional characters and scenes to be interactively controlled for computer animation. The system attempts to span the two most common approaches to animation: language-driven or programmed and visually-driven or interactive. Models are designed in a geometry language which supports vector and matrix arithmetic, transformations and instancing of primitive parts. As a result, constraints and functional dependencies between different parts can be programmed. Control is achieved by parameterizing the model. Subsets of parameters can be connected to different logical input devices, establishing an input mode to control the model's shape. Parameter sets can be stored to form a database of positions. Positions then can be mapped to frames and interpolated to animate the model.
---
paper_title: Parametric keyframe interpolation incorporating kinetic adjustment and phrasing control

paper_content:

Parametric keyframing is a popular animation technique where values for parameters which control the position, orientation, size, and shape of modeled objects are determined at key times, then interpolated for smooth animation. Typically the parameter values defined by the keyframes are interpolated by spline techniques with the result that the parameter change kinetics are implicitly defined by the given keyframe times and data points. Existing interpolation systems for animation are examined and found to lack certain desirable features such as continuity of acceleration or convenient kinetic control. The requirements of interpolation for animation are analyzed in order to determine the characteristics of a satisfactory system. A new interpolation system is developed and implemented which incorporates second-derivative continuity (continuity of acceleration), local control, convenient kinetic control, and joining and phrasing of successive motions. Phrasing control includes the ability to parametrically control the degree and extent of smooth motion flow between separately defined motions.
---
paper_title: A Real Time Face Tracking And Animation System

paper_content:

In this paper, a novel system for real time face tracking and animation is presented. The system is composed of two major components: (1) real time infra-red (IR) based active facial feature tracking, and (2) real time facial expression generation based on a 3D face avatar. Twenty-two feature points, head pose orientation and eye close-open status are effectively extracted through a video input. Based on the detected facial features, a 3D face model is animated by a dynamic inference algorithm and a transformation from facial motion parameters to facial animation parameters. The work can be extended to the fields of real time facial expression analysis and synthesis for applications of human-computer interaction, model-based video conferencing and low bit rate avatar communication. The performance of the developed system is evaluated by its real time implementation for facial expression generation.
---
paper_title: Facial image synthesis using skin texture recording

paper_content:

A significant issue in synthesizing realistic faces is the representation of skin grain and wrinkles. This paper describes a new approach based on the registered body of a real person. This recording allows simultaneously registering of the 3-D coordinates of a point and the corresponding reflected intensity. Using a 4-D B-spline surface to reconstruct the face, we come close to achieving a photographic result.
---
paper_title: Analysis and Synthesis of Facial Image Sequences Using Physical and Anatomical Models

paper_content:

An approach to the analysis of dynamic facial images for the purposes of estimating and resynthesizing dynamic facial expressions is presented. The approach exploits a sophisticated generative model of the human face originally developed for realistic facial animation. The face model which may be simulated and rendered at interactive rates on a graphics workstation, incorporates a physics-based synthetic facial tissue and a set of anatomically motivated facial muscle actuators. The estimation of dynamical facial muscle contractions from video sequences of expressive human faces is considered. An estimation technique that uses deformable contour models (snakes) to track the nonrigid motions of facial features in video images is developed. The technique estimates muscle actuator controls with sufficient accuracy to permit the face model to resynthesize transient expressions. >
---
paper_title: Physically-Based Facial Modeling , Analysis , and Animation

paper_content:

We develop a new 3D hierarchical model of the human face. The model incorporates a physically-based approximation to facial tissue and a set of anatomically-motivated facial muscle actuators. Despite its sophistication, the model is efficient enough to produce facial animation at interactive rates on a high-end graphics workstation. A second contribution of this paper is a technique for estimating muscle contractions from video sequences of human faces performing expressive articulations. These estimates may be input as dynamic control parameters to the face model in order to produce realistic animation. Using an example, we demonstrate that our technique yields sufficiently accurate muscle contraction estimates for the model to reproduce expressions from dynamic images of faces.
---
paper_title: MPEG-4 Facial Animation: The Standard, Implementation and Applications

paper_content:

From the Publisher: ::: This book concentrates on the animation of faces. The Editors put the MPEG-4 FA standard against the historical background of research on facial animation and model-based coding, and provide a brief history of the development of the standard itself. In part 2 there is a comprehensive overview of the FA specification with the goal of helping the reader understand how the standard really works. Part 3, forms the bulk of the book and covers the implementations of the standard on both encoding and decoding side. Several face animation techniques for MPEG-4 FA decoders are presented. While the standard itself actually specifies only the decoder, for applications it is interesting to look at the wide range of technologies for producing and encoding the FA contents. These include video analysis, speech analysis and synthesis, as well as keyframe animation. The last part of the book provides several examples of applications using the MPEG-4 FA standard. ::: It will be useful for companies implementing products and services related to the new standard, researchers in several domains related to facial animation, as well as wider technical audience interested in new technologies and applications.· ::: The main people involved in the standardization process are contributors to the book Provides several examples of applications using the MPEG-4 Facial Animation standard, including video and speech analysis This will become THE reference for the MPEG-4 Facial Animation Aids the understanding of the reasoning behind the standard specification, how it works and what the potential applications are Gives an overview of the technologies directly related to the standard and its implementation ::: Essential reading for the Industry and research community especially engineers, researchers and developers.
---
paper_title: Simulation of Facial Muscle Actions Based on Rational Free Form Deformations

paper_content:

This paper describes interactive facilities for simulating abstract muscle actions using rational free form deformations (RFFD). The particular muscle action is simulated as the displacement of the control points of the control-unit for an RFFD defined on a region of interest. One or several simulated muscle actions constitute a minimum perceptible action (MPA), which is defined as the atomic action unit, similar to action unit (AU) of the facial action coding system (FACS), to build an expression
---
paper_title: Face and 2-d mesh animation in MPEG-4

paper_content:

This paper presents an overview of some of the synthetic visual objects supported by MPEG-4 version-1, namely animated faces and animated arbitrary 2D uniform and Delaunay meshes. We discuss both specification and compression of face animation and 2D-mesh animation in MPEG-4. Face animation allows to animate a proprietary face model or a face model downloaded to the decoder. We also address integration of the face animation tool with the text-to-speech interface (TTSI), so that face animation can be driven by text input.
---
paper_title: Langwidere: a new facial animation system

paper_content:

This paper presents Langwidere, a facial animation system that integrates hierarchical spline modeling with simulated muscles based upon local area surface deformations. The multi-level shape representation of a hierarchical spline provides control over the extent of deformations, while at the same time reducing the amount of data needed to define the surface. The facial model is constructed from a single closed surface defining the entire head and internal structures of the mouth cavity. Simulated muscles are attached to various levels of the surface with more rudimentary levels substituting for bone such as the skull and jaw. The combination of a hierarchical model and simulated muscles provides a smooth surface with precise and flexible control over surface shape. >
---
paper_title: 3DAV exploration of video-based rendering technology in MPEG

paper_content:

New kinds of media are emerging that extend the functionality of available technology. The growth of immersive recording technologies has led to video-based rendering systems for photographing and reproducing environments in motion. This lends itself to new forms of interactivity for the viewer, including the ability to explore a photographic scene and interact with its features. The three-dimensional (3-D) qualities of objects in the scene can be extracted by analysis techniques and displayed by the use of stereo vision. The data types and image bandwidth needed for this type of media experience may require especially efficient formats for representation, coding, and transmission. An overview is presented here of the MPEG activity exploring the need for standardization in this area to support these new applications, under the name of 3DAV (for 3-D audio-visual). As an example, a detailed solution for omnidirectional video is presented as one of the application scenarios in 3DAV.
---
paper_title: Interactive 3-D Video Representation and Coding Technologies

paper_content:

Interactivity in the sense of being able to explore and navigate audio-visual scenes by freely choosing viewpoint and viewing direction, is an important key feature of new and emerging audio-visual media. This paper gives an overview of suitable technology for such applications, with a focus on international standards, which are beneficial for consumers, service providers, and manufacturers. We first give a general classification and overview of interactive scene representation formats as commonly used in computer graphics literature. Then, we describe popular standard formats for interactive three-dimensional (3-D) scene representation and creation of virtual environments, the virtual reality modeling language (VRML), and the MPEG-4 BInary Format for Scenes (BIFS) with some examples. Recent extensions to MPEG-4 BIFS, the Animation Framework eXtension (AFX), providing advanced computer graphics tools, are explained and illustrated. New technologies mainly targeted at reconstruction, modeling, and representation of dynamic real world scenes are further studied. The user shall be able to navigate photorealistic scenes within certain restrictions, which can be roughly defined as 3-D video. Omnidirectional video is an extension of the planar two-dimensional (2-D) image plane to a spherical or cylindrical image plane. Any 2-D view in any direction can be rendered from this overall recording to give the user the impression of looking around. In interactive stereo two views, one for each eye, are synthesized to provide the user with an adequate depth cue of the observed scene. Head motion parallax viewing can be supported in a certain operating range if sufficient depth or disparity data are delivered with the video data. In free viewpoint video, a dynamic scene is captured by a number of cameras. The input data are transformed into a special data representation that enables interactive navigation through the dynamic scene environment.
---
paper_title: An introduction to the MPEG-4 animation framework eXtension

paper_content:

This paper presents the MPEG-4 Animation Framework eXtension (AFX) standard, ISO/IEC 14496-16. Initiated by the MPEG Synthetic/Natural Hybrid Coding group in 2000, MPEG-4 AFX proposes an advanced framework for interactive multimedia applications using both natural and synthetic objects. Following this model, new synthetic objects have been specified, increasing content realism over existing MPEG-4 synthetic objects. The general overview of MPEG-4 AFX is provided on top of the review of MPEG-4 standards to explain the relationship between MPEG-4 and MPEG-4 AFX. Then we give a bird's-eye view of new tools available in this standard.
---

Title: Scene Representation Technologies for 3DTV—A Survey

Section 1: INTRODUCTION
Description 1: Provide an overview of the 3DTV system, its inputs, and the essential role of 3-D scene representation. Discuss the various requirements for scene representation and introduce the organization of the paper.

Section 2: DENSE DEPTH REPRESENTATIONS
Description 2: Discuss the fundamentals and key methods for dense depth representations, including layered depth images, depth image-based rendering, and rate-distortion optimal dense depth representations.

Section 3: SURFACE-BASED REPRESENTATIONS
Description 3: Provide a comparative survey of techniques for representing 3-D surface geometry, including polygonal meshes, NURBS, subdivision surfaces, and point-based modeling.

Section 4: VOLUMETRIC REPRESENTATIONS
Description 4: Explain the notion of volumetric representations and the associated data structures, such as voxels and octrees. Discuss their applications in multiview stereo and space-carving approaches.

Section 5: TEXTURE REPRESENTATIONS
Description 5: Examine the importance of texturing for realistic scene rendering in 3DTV, detailing single texture representation and multitexture representation methods.

Section 6: PSEUDO-3-D REPRESENTATIONS
Description 6: Describe image-based representations that avoid explicit 3-D geometry, such as image interpolation, image warping, and light field representations.

Section 7: OBJECT-BASED 3-D SCENE MODELING
Description 7: Discuss the three basic tasks involved in dynamic 3-D scene modeling: representation, animation, and rendering. Highlight techniques for outdoor environments, complex phenomena, and natural objects.

Section 8: HEAD AND BODY SPECIFIC REPRESENTATIONS
Description 8: Focus on 3-D representation techniques for human faces and bodies, detailing methods for modeling the skeleton, body appearance, and facial animation.

Section 9: STANDARDS FOR 3-D SCENE REPRESENTATIONS
Description 9: Review the importance of interoperability and standards for 3-D scene representations, covering ISO standards, VRML, X3D, and MPEG-4.