We extend the efficient high-order method of [Veerapaneni et al., 2008] to the axisymmetric flows with immersed vesicles of spherical or toroidal topology. In this case, the bending and fluid forces require a siginficantly different (for bending forces, nonlinear, vs. linear in 2D) case computation. The qualitative numerical behavior of the problem is also different: with a nonlinear semi-implicit scheme needed to eliminate the CFL-type restriction in the toroidal case. We present an unconditionally stable scheme with low cost per time step, and spectrally accurate in space and third-order accurate in time. An important part of the algorithm is a novel numerical scheme for evaluation of the 3D Stokes single-layer potential on an axisymmetric surface, needed to achieve optimal complexity. As an application, we explore the motion of axisymmetric vesicles under gravity

We present an extension of recently developed Loop and Schaefer's approximation of Catmull-Clark surfaces (ACC) for surfaces with creases and corners which are essential for most applications. We discuss the integration of ACC into Valve's Source game engine and analyze performance of our implementation

This paper presents a system deployed on parallel clusters to manage a collection of parallel simulations that make up a computational study. It explores how such a system can extend traditional parallel job scheduling and resource allocation techniques to incorporate knowledge specific to the study. Using a UINTAH-based helium gas simulation code (ARCHES) and the SimX system for multi-experiment computational studies, this paper demonstrates that, by using application-specific knowledge in resource allocation and scheduling decisions, one can reduce the run time of a computational study from over 20 hours to under 4.5 hours on a 32-processor cluster, and from almost 11 hours to just over 3.5 hours on a 64-processor cluster.

We present a kernel-independent, adaptive fast multipole method (FMM) of arbitrary order accuracy for solving elliptic PDEs in three dimensions with radiation boundary conditions. The algorithm requires only a Green's function evaluation routine for the governing equation and a representation of the source distribution (the right-hand side) that can be evaluated at arbitrary points. The performance of the FMM is accelerated in two ways. First, we construct a piecewise polynomial approximation of the right-hand side and compute far-field expansions in the FMM from the coefficients of this approximation. Second, we precompute tables of quadratures to handle the near-field interactions on adaptive octree data structures, keeping the total storage requirements in check through the exploitation of symmetries. We present numerical examples for the Laplace, modified Helmholtz and Stokes equations.

We consider the approximation properties of a class of bases defined on refined polygonal complexes. This class includes many bases used in geometric modeling for surfaces of arbitrary topology, subdivision surfaces in particular. We show that under moderately weak assumptions, the approximation rate of the bases in our class is no worse than the approximation rate of these bases restricted to regular complexes, coinciding with the approximation rate of spline spaces for commonly used subdivision schemes.

We present a manifold-based surface construction extending the C1 construction of Ying and Zorin (2004a). Our surfaces allow for pircewise-smooth boundaries, have user-controlled arbitrary degree of smoothness and improved derivative and visual behavior. 2-flexibility of our surface construction is confirmed numerically for a range of local mesh configurations.

We present a new method for the evolution of inextensible vesicles immersed in a Stokesian fluid. We use a boundary integral formulation for the fluid that results in a set of nonlinear integro-differential equations for the vesicle dynamics. The motion of the vesicles is determined by balancing the nonlocal hydrodynamic forces with the elastic forces due to bending and tension. Numerical simulations of such vesicle motions are quite challenging. On one hand, explicit time-stepping schemes suffer from a severe stability constraint due to the stiffness related to high-order spatial derivatives and a milder constraint due to a transport-like stability condition. On the other hand, an implicit scheme can be expensive because it requires the solution of a set of nonlinear equations at each time step. We present two semi-implicit schemes that circumvent the severe stability constraints on the time step and whose computational cost per time step is comparable to that of an explicit scheme. We discretize the equations by using a spectral method in space, and a multistep third-order accurate scheme in time. We use the fast multipole method (FMM) to efficiently compute vesicle-vesicle interaction forces in a suspension with a large number of vesicles. We report results from numerical experiments that demonstrate the convergence and algorithmic complexity properties of our scheme.

We present a system for free-form surface modeling that allows a user to modify a shape by changing its rendered, shaded image using stroke-based drawing tools. User input is translated into a set of tangent and positional constraints on the surface. A new shape, whose rendered image closely approximates user input, is computed using an efficient and stable surface optimization procedure. We demonstrate how several types of free-form surface edits which may be difficult to cast in terms of standard deformation approaches can be easily performed using our system.

The standard bilinear interpolation on normal maps results in visual artifacts along sharp features, which are common for surfaces with creases, wrinkles, and dents. In many cases, spatially varying features, like the normals near discontinuity curves, are best represented as functions of the distance to the curve and the position along the curve. For high-quality interactive rendering at arbitrary magnifications, one needs to interpolate the distance field preserving discontinuity curves exactly. We present a real-time, GPU-based method for distance function and distance gradient interpolation which preserves discontinuity feature curves. The feature curves are represented by a set of quadratic Bezier curves, with minimal restrictions on their intersections. We demonstrate how this technique can be used for real-time rendering of complex feature patterns and blending normal maps with procedurally defined profiles near normal discontinuities.

This paper presents a system supporting reuse of simulation results in multi-experiment computational studies involving independent simulations and explores the benefits of such reuse. Using a SCIRun-based defibrillator device simulation code (DefibSim) and the SimX system for computational studies, this paper demonstrates how aggressive reuse between and within computational studies can enable interactive rates for such studies on a moderate-sized 128-node processor cluster; a brute-force approach to the problem would require two thousand nodes or more on a massively parallel machine for similar performance. Key to realizing these performance improvements is exploiting optimization opportunities that present themselves at the level of the overall workflow of the study as opposed to focusing on individual simulations. Such global optimization approaches are likely to become increasingly important with the shift towards interactive and universal parallel computing.

Hinge-based bending models are widely used in the physically-based animation of cloth, thin plates and shells. We propose a hinge-based model that is simpler to implement, more efficient to compute, and offers a greater number of effective material parameters than existing models. Our formulation builds on two mathematical observations: (a) the bending energy of curved flexible surfaces can be expressed as a cubic polynomial if the surface does not stretch; (b) a general class of anisotropic materials–-those that are orthotropic – is captured by appropriate choice of a single stiffness per hinge. Our contribution impacts a general range of surface animation applications, from isotropic cloth and thin plates to orthotropic fracturing thin shells.

Many common objects have highly reflective metallic or painted finishes. Their appearance is primarily defined by the distortion the curved shape of the surface introduces in the reflections of surrounding objects. Reflection lines are commonly used for surface interrogation, as they capture many essential aspects of reflection distortion directly, and clearly show surface imperfections that may be hard to see with conventional lighting. In this paper, we propose the use of functionals based on reflection lines for mesh optimization and editing. We describe a simple and efficient discretization of such functionals based on screen-space surface parameterization, and we demonstrate how such discrete functionals can be used for several types of surface editing operations.

Many applications require the extraction of isolines and isosurfaces from scalar functions defined on regular grids. These scalar functions may have many different origins: from MRI and CT scan data to terrain data or results of a simulation. As a result of noise and other artifacts, curves and surfaces obtained by standard extraction algorithms often suffer from topological irregularities and geometric noise. While it is possible to remove topological and geometric noise as a post-processing step, in the case when a large number of isolines are of interest there is a considerable advantage in filtering the scalar function directly. While most smoothing filters result in gradual simplification of the topological structure of contours, new topological features typically emerge and disappear during the smoothing process. In this paper, we describe an algorithm for filtering functions defined on regular 2D grids with controlled topology changes, which ensures that the topological structure of the set of contour lines of the function is progressively simplified.

We present a family of discrete isometric bending models (IBMs) for triangulated surfaces in 3-space. These models are derived from an axiomatic treatment of discrete Laplace operators, using these operators to obtain linear models for discrete mean curvature from which bending energies are assembled. Under the assumption of isometric surface deformations we show that these energies are quadratic in surface positions. The corresponding linear energy gradients and constant energy Hessians constitute an efficient model for computing bending forces and their derivatives, enabling fast time-integration of cloth dynamics with a two- to three-fold net speedup over existing nonlinear methods, and near-interactive rates for Willmore smoothing of large meshes.

Advances in high-performance computing have led to the broad use of computational studies in everyday engineering and scientific applications. A single study may require thousands of computational experiments, each corresponding to individual runs of simulation software with different parameter settings; in complex studies, the pattern of parameter changes is complex and may have to be adjusted by the user based on partial simulation results. Unfortunately, existing tools have limited high-level support for managing large ensembles of simultaneous computational experiments. In this paper, we present a system architecture for interactive computational studies targeting two goals. The first is to provide a framework for high-level user interaction with computational studies, rather than individual experiments; the second is to maximize the size of the studies that can be performed at close to interactive rates. We describe a prototype implementation of the system and demonstrate performance improvements obtained using our approach for a simple model problem.

We present a high-order boundary integral equation solver for 3D elliptic boundary value problems on domains with smooth boundaries. We use Nystrom's method for discretization, and combine it with special quadrature rules for the singular kernels that appear in the boundary integrals. The overall asymptotic complexity of our method is O(N-3/2), where N is the number of discretization points on the boundary of the domain, and corresponds to linear complexity in the number of uniformly sampled evaluation points. A kernel-independent fast summation algorithm is used to accelerate the evaluation of the discretized integral operators. We describe a high-order accurate method for evaluating the solution at arbitrary points inside the domain, including points close to the domain boundary. We demonstrate how our solver, combined with a regular-grid spectral solver, can be applied to problems with distributed sources. We present numerical results for the Stokes, Navier, and Poisson problems. (c) 2006 Elsevier Inc. All rights reserved.

Efficient computation of curvature-based energies is important for practical implementations of geometric modeling and physical simulation applications. Building on a simple geometric observation, we provide a version of a curvature-based energy expressed in terms of the Laplace operator acting on the embedding of the surface. The corresponding energy–being quadratic in positions–gives rise to a constant Hessian in the context of isometric deformations. The resulting isometric bending model is shown to significantly speed up common cloth solvers, and when applied to geometric modeling situations built onWillmore flow to provide runtimes which are close to interactive rates.

In this paper we describe an approach to the construction of curvature-continuous surfaces with arbitrary control meshes using subdivision. Using a simple modification of the widely used Loop subdivision algorithm we obtain perturbed surfaces which retain the overall shape and appearance of Loop subdivision surfaces but no longer have flat spots or curvature singularities at extraordinary vertices. Our method is computationally efficient and can be easily added to any existing subdivision code.

Discrete curvature and shape operators, which capture complete information about directional curvatures at a point, are essential in a variety of applications: simulation of deformable two-dimensional objects, variational modeling and geometric data processing. In many of these applications, objects are represented by meshes. Currently, a spectrum of approaches for formulating curvature operators for meshes exists, ranging from highly accurate but computationally expensive methods used in engineering applications to efficient but less accurate techniques popular in simulation for computer graphics. We propose a simple and efficient formulation for the shape operator for variational problems on general meshes, using degrees of freedom associated with normals. On the one hand, it is similar in its simplicity to some of the discrete curvature operators commonly used in graphics; on the other hand, it passes a number of important convergence tests and produces consistent results for different types of meshes and mesh refinement.

The creation of most models used in computer animation and computer games requires the assignment of texture coordinates, texture painting, and texture editing. We present a novel approach for texture placement and editing based on direct manipulation of textures on the surface. Compared to conventional tools for surface texturing, our system combines UV-coordinate specification and texture editing into one seamless process, reducing the need for careful initial design of parameterization and providing a natural interface for working with textures directly on 3D surfaces.A combination of efficient techniques for interactive constrained parameterization and advanced input devices makes it possible to realize a set of natural interaction paradigms. The texture is regarded as a piece of stretchable material, which the user can position and deform on the surface, selecting arbitrary sets of constraints and mapping texture points to the surface; in addition, the multi-touch input makes it possible to specify natural handles for texture manipulation using point constraints associated with different fingers. Pressure can be used as a direct interface for texture combination operations. The 3D position of the object and its texture can be manipulated simultaneously using two-hand input.

Many diverse applications in different areas of computer graphics, including geometric modeling, rendering and animation, require dealing with sets which cannot be easily represented with a single function on a simple domain in a Euclidean space: Examples include surfaces of nontrivial topology, environment maps, reflection/transmission functions, light fields, configuration spaces of animation skeletons, and others. In most cases these objects are described as collections of functions defined on multiple simple domains, with the functions satisfying various constraints (e.g., join smoothly). The unified mathematical view of many such structures is provided by the theory of smooth manifolds. While the concept is standard in mathematics, it is not broadly known in the graphics community and is often perceived as an impractical and complex abstraction. The goal of this half-day course is to present the basic concepts and definitions of manifold theory, demonstrate their computational nature and close connection to applications, and survey a variety of computer graphics applications in which manifolds appear, with a focus on modeling of surfaces and functions on surfaces.

Subdivision surfaces have become a standard geometric modeling tool for a variety of applications. This survey is an introduction to subdivision algorithms for arbitrary meshes and related mathematical theory; we review the most important subdivision schemes the theory of smoothness of subidivision surfaces, and known facts about approximation properties of subdivision bases.

Curvature-based energy and forces are used in a broad variety of contexts, ranging from modeling of thin plates and shells to surface fairing and variational surface design. The approaches to discretization preferred in different areas often have little in common: engineering shell analysis is dominated by finite elements, while spring-particle models are often preferred for animation and qualitative simulation due to their simplicity and low computational cost. Both types of approaches have found applications in geometric modeling. While there is a well-established theory for finite element methods, alternative discretizations are less well understood: many questions about mesh dependence, convergence and accuracy remain unanswered. We discuss the general principles for defining curvaturebased energy on discrete surfaces based on geometric invariance and convergence considerations. We show how these principles can be used to understand the behavior of some commonly used discretizations, to establish relations between some well-known discrete geometry and finite element formulations and to derive new simple and efficient discretizations.

Subdivision surfaces have emerged as a powerful representation for surface modeling and design. They address important limitations of traditional spline-based methods, such as the ability to handle arbitrary topologies and to support multiscale editing operations. In this paper we survey existing subdivision-based modeling methods with emphasis on interactive tools for styling and decoration of 3D models.

Volume textures aligned with a surface can be used to add topologically complex geometric detail to objects in an efficient way, while retaining an underlying simple surface structure. Adding a volume texture to a surface requires more than a conventional two-dimensional parameterization: a part of the space surrounding the surface has to be parameterized. Another problem with using volume textures for adding geometric detail is the difficulty in rendering implicitly represented surfaces, especially when they are changed interactively. In this paper we present algorithms for constructing and rendering volume-textured surfaces. We demonstrate a number of interactive operations that these algorithms enable.

We present a smooth surface construction based on the manifold approach of Grimm and Hughes. We demonstrate how this approach can relatively easily produce a number of desirable properties which are hard to achieve simultaneously with polynomial patches, subdivision or variational surfaces. Our surfaces are C-infinity-continuous with explicit nonsingular C-infinity parameterizations, high-order flexible at control vertices, depend linearly on control points, have fixed-size local support for basis functions, and have good visual quality.

Subdivision-based representations are recognized as important tools for the generation of high-quality surfaces for Computer Graphics. In this paper we describe two parameterizations of Catmull-Clark subdivision surfaces that allow a variety of algorithms designed for other types of parametric surfaces (i.e., B-splines) to be directly applied to subdivision surfaces. In contrast with the natural parameterization of subdivision surfaces characterized by diverging first order derivatives around extraordinary vertices of valence higher than four, the derivatives associated with our proposed methods are defined everywhere on the surface. This is especially important for Computer-Aided Design (CAD) applications that seek to address the limitations of NURBS-based representations through the more flexible subdivision framework.

Lofting is a traditional technique for creating a curved shape by first specifying a network of curves that approximates the desired shape and then interpolating these curves with a smooth surface. This paper addresses the problem of lofting from the viewpoint of subdivision. First, we develop a subdivision scheme for an arbitrary network of cubic B-splines capable of being interpolated by a smooth surface. Second, we provide a quadrangulation algorithm to construct the topology of the surface control mesh. Finally, we extend the Catmull-Clark scheme to produce surfaces that interpolate the given curve network. Near the curve network, these lofted subdivision surfaces are C2 bicubic splines, except for those points where three or more curves meet. We prove that the surface is C1 with bounded curvature at these points in the most common cases; empirical results suggest that the surface is also C1 in the general case.

We present a new fast multipole method for particle simulations. The main feature of our algorithm is that it does not require the implementation of multipole expansions of the underlying kernel, and it is based only on kernel evaluations. Instead of using analytic expansions to represent the potential generated by sources inside a box of the hierarchical FMM tree. we use a continuous distribution of an equivalent density on a surface enclosing the box. To find this equivalent density, we match its potential to the potential of the original sources at a surface, in the far field, by solving local Dirichlet-type boundary value problems. The far-field evaluations are sparsified with singular value decomposition in 2D or fast Fourier transforms in 3D. We have tested the new method on the single and double layer operators for the Laplacian, the modified Laplacian, the Stokes, the modified Stokes, the Navier, and the modified Navier operators in two and three dimensions. Our numerical results indicate that our method compares very well with the best known implementations of the analytic FMM method for both the Laplacian and modified Laplacian kernels. Its advantage is the (relative) simplicity of the implementation and its immediate extension to more general kernels.

We introduce a method for simulating the inelastic deformation of thin shells: we model plasticity and fracture of curved, deformable objects such as light bulbs, egg-shells and bowls. Our novel approach uses triangle meshes yet evolves fracture lines unrestricted to mesh edges. We present a novel measure of bending strain expressed in terms of surface invariants such as lengths and angles. We also demonstrate simple techniques to improve the robustness of standard timestepping as well as collision response algorithms.

We present a new adaptive fast multipole algorithm and its parallel implementation. The algorithm is kernel-independent in the sense that the evaluation of pairwise interactions does not rely on any analytic expansions, but only utilizes kernel evaluations. The new method provides the enabling technology for many important problems in computational science and engineering. Examples include viscous flows, fracture mechanics and screened Coulombic interactions. Our MPI-based parallel implementation logically separates the computation and communication phases to avoid synchronization in the upward and downward computation passes, and thus allows us to fully exploit computation and communication overlapping. We measure isogranular and fixed-size scalability for a variety of kernels on the Pittsburgh Supercomputing Center's TCS-1 Alphaserver on up to 3000 processors. We have solved viscous flow problems with up to 2.1 billion unknowns and we have achieved 1.6 Tflops/s peak performance and 1.13 Tflops/s sustained performance.

We present a new method for the solution of the Stokes equations. The main features of our method are: (1) it can be applied to arbitrary geometries in a black-box fashion; (2) it is second-order accurate; and (3) it has optimal algorithmic complexity. Our approach, to which we refer as the embedded boundary integral method (EBI), is based on Anita Mayo's work for the Poisson's equation: 'The Fast Solution of Poisson's and the Biharmonic Equations on Irregular Regions', SIAM Journal on Numerical Analysis, 21 (1984) 285-299. We embed the domain in a rectangular domain, for which fast solvers are available, and we impose the boundary conditions as interface (jump) conditions on the velocities and tractions. We use an indirect boundary integral formulation for the homogeneous Stokes equations to compute the jumps. The resulting equations are discretized by Nystrom's method. The rectangular domain problem is discretized by finite elements for a velocity-pressure formulation with equal order interpolation bilinear elements (Q1-Q1). Stabilization is used to circumvent the inf-sup condition for the pressure space. For the integral equations, fast matrix-vector multiplications are achieved via an N log N algorithm based on a block representation of the discrete integral operator, combined with (kernel independent) singular value decomposition to sparsity low-rank blocks. The regular grid solver is a Krylov method (conjugate residuals) combined with an optimal two-level Schwartz-preconditioner. For the integral equation we use GMRES. We have tested our algorithm on several numerical examples and we have observed optimal convergence rates.

In this paper we describe a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of user-defined curves. Operations such as engraving, embossing, and trimming are important in many surface modeling applications. Their implementation, however, is nontrivial due to computational, topological, and smoothness constraints that the underlying surface has to satisfy. The novelty of our work lies in the ability to create sharp features anywhere on a surface and in the fact that the resulting representation remains within the multiresolution subdivision framework. Preserving the original representation has the advantage that other operations applicable to multiresolution subdivision surfaces can subsequently be applied to the edited model. We also introduce an extended set of subdivision rules for Catmull-Clark surfaces that allows the creation of creases along diagonals of control mesh faces.

We present a new method for the solution of the unsteady incompressible Navier-Stokes equations. Our goal is to achieve a robust and scalable methodology for two and three dimensional incompressible flows. The discretization of the Navier-Stokes operator is done using boundary integrals and structured-grid finite elements. We use finite-differences to advance the equations in time. The convective term is discretized via a semi-Lagrangian formulation which not only results in a spatial constant-coefficient (modified) Stokes operator, but in addition is unconditionally stable. The Stokes operator is inverted by a double-layer boundary integral formulation. Domain integrals are computed via finite elements with appropriate forcing singularities to account for the irregular geometry. We use a velocity-pressure formulation which we discretize with bilinear elements (Q1-Q1), which give equal order interpolation for the velocities and pressures. Stabilization is used to circumvent the div-stability condition for the pressure space. The integral equations are discretized by Nystrom's method. For the specific approximation choices the method is second order accurate. Our code is built on top of PETSc, an MPI based parallel linear algebra library. We will present numerical results and discuss the performance and scalability of the method in two dimensions.

Cutting and pasting to combine different elements into a common structure are widely used operations that have been successfully adapted to many media types. Surface design could also benefit from the availability of a general, robust, and efficient cut-and-paste too], especially during the initial stages of design when a large space of alternatives needs to be explored. Techniques to support cut-and-paste operations for surfaces have been proposed in the past, but have been of limited usefulness due to constraints on the type of shapes supported and the lack of real-time interaction. In this paper, we describe a set of algorithms based on multiresolution subdivision surfaces that per-form at interactive rates and enable intuitive cut-and-paste operations.

In this paper we consider the constant-time evaluation of subdivision surfaces at arbitrary points. Our work extends the work of J. Stam by considering the subdivision rules for piecewise smooth surfaces with boundaries depending on parameters. The main innovation described in this paper is the idea of using a different set of basis vectors for evaluation, which, unlike eigenvectors, depend continuously on the coefficients of the subdivision rules. The advantage of this approach is that it becomes possible to define evaluation for parametric families of rules without considering an excessive number of special cases and while improving the numerical stability of calculations. We demonstrate how such bases are computed for a particular parametric family of subdivision rules extending Loop subdivision to meshes with boundaries, and we provide a detailed description of the evaluation algorithms.

In this paper we describe a method for computing approximate results of boolcan operations (union, intersection, difference) applied to free-form solids bounded by multiresolution subdivision surfaces. We present algorithms for generating a control mesh for a multiresolution surface approximating the result, optimizing the parameterization of the new surface with respect to the original surfaces, and fitting the new surface to the geometry of the original surfaces. Our algorithms aim to minimize the size and optimize the quality of the new control mesh. The original control meshes are modified only in a neighborhood of the intersection. While the main goal is to obtain approximate results, high-accuracy approximations are also possible at additional computational expense, if the topology of the intersection curve is resolved correctly.

We present a simple denoising technique for geometric data represented as a semiregular mesh, based on locally adaptive Wiener filtering. The degree of denoising is controlled by a single parameter (an estimate of the relative noise level) and the time required for denoising is independent of the magnitude of the estimate. The performance of the algorihm is sufficiently fast to allow interactive local denoising.

Commonly-used subdivision schemes require manifold control meshes and produce manifold surfaces. However, it is often necessary to model nonmanifold surfaces, such as several surface patches meeting at a common boundary.In this paper, we describe a subdivision algorithm that makes it possible to model nonmanifold surfaces. Any triangle mesh, subject only to the restriction that no two vertices of any triangle coincide, can serve as an input to the algorithm. Resulting surfaces consist of collections of manifold patches joined along nonmanifold curves and vertices. If desired, constraints may be imposed on the tangent planes of manifold patches sharing a curve or a vertex.The algorithm is an extension of a well-known Loop subdivision scheme, and uses techniques developed for piecewise smooth surfaces.

We present a novel method for texture synthesis on surfaces from examples. We consider a very general type of textures, including color, transparency and displacements. Our method synthesizes the texture directly on the surface, rather than synthesizing a texture image and then mapping it to the surface. This approach avoids many problems associated with texture mapping, such as seams, distortion, and repeating patterns. The synthesized textures have the same qualitative visual appearance as the example texture, and cover the surfaces seamlessly, without distortion. We describe two synthesis methods, based on the work of Wei and Levoy and Ashikhmin; our techniques produce similar results but directly on surfaces.

In this paper we introduce 4-8 subdivision, a new scheme that generalizes the four-directional box spline of class C-4 to surfaces of arbitrary topological type. The crucial advantage of the proposed scheme is that it uses bisection refinement as an elementary refinement operation, rather than more commonly used face or vertex splits. In the uniform case, bisection refinement results in doubling, rather than quadrupling of the number of faces in a mesh. Adaptive bisection refinement automatically generates conforming variable-resolution meshes in contrast to face and vertex split methods which require a postprocessing step to make an adaptively refined mesh conforming. The fact that the size of faces decreases more gradually with refinement allows one to have greater control over the resolution of a refined mesh. It also makes it possible to achieve higher smoothness while using small stencils (the size of the stencils used by our scheme is similar to Loop subdivision). We show that the subdivision surfaces produced by the 4-8 scheme are C-4 continuous almost everywhere, except at extraordinary vertices where they are is C-1-continuous.

Quadrilateral subdivision schemes come in primal and dual varieties, splitting faces or respectively vertices. The scheme of Catmull-Clark is an example of the former, while the Doo-Sabin scheme exemplifies the latter. In this paper we consider the construction of an increasing sequence of alternating primal/dual quadrilateral subdivision schemes based on a simple averaging approach. Beginning with a vertex split step we successively construct variants of Doo-Sabin and Catmull-Clark schemes followed by novel schemes generalizing B-splines of bidegree up to nine. We prove the schemes to be C-1 at irregular surface points, and analyze the behavior of the schemes as the number of averaging steps increases. We discuss a number of implementation issues common to all quadrilateral schemes. In particular we show how both primal and dual quadrilateral schemes can be implemented in the same code, opening up new possibilities for more flexible geometric modeling applications and p-versions of the Subdivision Element Method. Additionally we describe a simple algorithm for adaptive subdivision of dual schemes.

In this paper we introduce improved rules for Catmull-Clark and Loop subdivision that overcome several problems with the original schemes, namely, lack of smoothness at extraordinary boundary vertices and folds near concave corners. In addition, our approach to rule modification allows the generation of surfaces with prescribed normals, both on the boundary and in the interior, which considerably improves control of the shape of surfaces.

In composing hand-drawn images of 3D scenes, artists often alter the projection for each object in the scene independently, thereby generating multiprojection images. We present a tool for creating such multiprojection images and animations, consisting of two parts: a multiprojection rendering algorithm and an interactive interface for attaching local cameras to the scene geometry. We describe a new set of techniques for resolving visibility between geometry rendered with different local cameras. We also develop several camera constraints that are useful when initially setting local camera parameters and when animating the scene. We demonstrate applications of our methods for generating a variety of artistic effects in still images and in animations.

We present a new set of algorithms for line-art rendering of smooth surfaces. We introduce an efficient, deterministic algorithm for finding silhouettes based on geometric duality, and an algorithm for segmenting the silhouette curves into smooth parts with constant visibility. These methods can be used to find all silhouettes in real time in software. We present an automatic method for generating hatch marks in order to convey surface shape. We demonstrate these algorithms with a drawing style inspired by A Topological Picturebook by G. Francis.

A sufficient condition for C-1-continuity of subdivision surfaces was proposed by Reif [Comput. Aided Geom. Design, 12 (1995), pp. 153-174.] and extended to a more general setting in [D. Zorin, Constr. Approx., accepted for publication]. In both cases, the analysis of C-1-continuity is reduced to establishing injectivity and regularity of a characteristic map. In all known proofs of C-1-continuity, explicit representation of the limit surface on an annular region was used to establish regularity, and a variety of relatively complex techniques were used to establish injectivity. We propose a new approach to this problem: we show that for a general class of subdivision schemes, regularity can be inferred from the properties of a sufficiently close linear approximation, and injectivity can be veri ed by computing the index of a curve. An additional advantage of our approach is that it allows us to prove C-1-continuity for all valences of vertices, rather than for an arbitrarily large but finite number of valences. As an application, we use our method to analyze C-1-continuity of most stationary subdivision schemes known to us, including interpolating butterfly and modified butterfly schemes, as well as the Kobbelt's interpolating scheme for quadrilateral meshes.

We derive necessary and sufficient conditions for tangent plane and C-k-continuity of stationary subdivision schemes near extraordinary vertices. Our criteria generalize most previously known conditions. We introduce a new approach to analysis of subdivision surfaces based on the idea of the universal surface. Any subdivision surface can be locally represented as a projection of the universal surface, which is uniquely defined by the subdivision scheme. This approach provides us with a more intuitive geometric understanding of subdivision near extraordinary vertices.

This course provides an introduction to Subdivision, a technique to generate smooth curves and surfaces, which extends classical spline modeling approaches. The course will cover the basic ideas of subdivision as well as the particulars of a number of different subdivision algorithms; we will present the most recent contributions to the area in a form accessible to a wide audience. The emphasis will be on practical issues in using subdivision for geometric modeling and animation.

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.

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 initialmesh. 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 C1 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.

We suggest an approach for correcting several types of perceived geometric distortions in computer-generated and photographic images. The approach is based on a mathematical formalization of desirable properties of pictures. From a small set of simple assumptions we obtain perceptually preferable viewing transformations and show that these transformations can be decomposed into a perspective or parallel projection followed by a planar transformation. The decomposition is easily implemented and provides a convenient framework for further analysis of the image mapping. We prove that two perceptually important properties are incompatible and cannot be satisfied simultaneously. It is impossible to construct a viewing transformation such that the images of all lines are straight and the images of all spheres are exact circles. Perceptually preferable tradeoffs between these two types of distortions can depend on the content of the picture. We construct parametric families of transformations with parameters representing the relative importance of the perceptual characteristics. By adjusting the settings of the parameters we canminimize the overall distortion of the picture. It turns out that a simple family of transformations produces results that are sufficiently close to optimal. We implement the proposed transformations and apply them to computer-generated and photographic perspective projection images. Our transformations can considerably reduce distortion in wide-angle motion pictures and computer-generated animations.

We describe a set of functional universal constraints for classification algorithms that correspond to particular systems of symmetric universal constraints.