Denis ZorinVision, Learning and Graphics GroupComputer Science Department Mathematics Department Courant Institute of Mathematical Sciences New York University 719 Broadway, 12th floor New York, NY 10003

Scientific computing: Fast multipole methods, numerical solution of integral equations, fluid and deformable membrane simulation, parallel algorithms and software tools.
QuadMesh Generation and Processing: A Survey David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, MarcoTarini, Denis Zorin Computer Graphics Forum vol. 32, 6, 2013, pp. 5176 Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semiregular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrisation and remeshing
 
An O (N) direct solver for integral equations on the plane Eduardo Corona, PerGunnar Martinsson, Denis Zorin arXiv preprint arXiv:1303.5466 An efficient direct solver for volume integral equations with O(N) complexity for a broad range of problems is presented. The solver relies on hierarchical compression of the discretized integral operator, and exploits that offdiagonal blocks of certain dense matrices have numerically low rank. Technically, the solver is inspired by previously developed direct solvers for integral equations based on "recursive skeletonization" and "Hierarchically SemiSeparable" (HSS) matrices, but it improves on the asymptotic complexity of existing solvers by incorporating an additional level of compression. The resulting solver has optimal O(N) complexity for all stages of the computation, as demonstrated by both theoretical analysis and numerical examples. The computational examples further display good practical performance in terms of both speed and memory usage. In particular, it is demonstrated that even problems involving 10^{7} unknowns can be solved to precision 10^{10} using a simple Matlab implementation of the algorithm executed on a single core.
 
Subspace integration with local deformations David Harmon, Denis Zorin ACM Transactions on Graphics (TOG) vol. 32, 4, 2013 (Proceedings of SIGGRAPH 2013) Subspace techniques greatly reduce the cost of nonlinear simulation by approximating deformations with a small custom basis. In order to represent the deformations well (in terms of a global metric), the basis functions usually have global support, and cannot capture localized deformations. While reducedspace basis functions can be localized to some extent, capturing truly local deformations would still require a very large number of precomputed basis functions, significantly degrading both precomputation and online performance. We present an efficient approach to handling local deformations that cannot be predicted, most commonly arising from contact and collisions, by augmenting the subspace basis with custom functions derived from analytic solutions to static loading problems. We also present a new cubature scheme designed to facilitate fast computation of the necessary runtime quantities while undergoing a changing basis. Our examples yield a two order of magnitude speedup over fullcoordinate simulations, striking a desirable balance between runtime speeds and expressive ability.
video
 
Controlleddistortion constrained global parametrization Ashish Myles, Denis Zorin ACM Transactions on Graphics (TOG) vol. 32, 4, 2013 (Proceedings of SIGGRAPH 2013) The quality of a global parametrization is determined by a number of factors, including amount of distortion, number of singularities (cones), and alignment with features and boundaries. Placement of cones plays a decisive role in determining the overall distortion of the parametrization; at the same time, feature and boundary alignment also affect the cone placement. A number of methods were proposed for automatic choice of cone positions, either based on singularities of crossfields and emphasizing alignment, or based on distortion optimization. In this paper we describe a method for placing cones for seamless global parametrizations with alignment constraints. We use a close relation between variationminimizing crossfields and related 1forms and conformal maps, and demonstrate how it leads to a constrained optimization problem formulation. We show for boundaryaligned parametrizations metric distortion may be reduced by cone chains, sometimes to an arbitrarily small value, and the tradeoff between the distortion and the number of cones can be controlled by a regularization term. Constrained parametrizations computed using our method have significantly lower distortion compared to the stateofthe art fieldbased method, yet maintain feature and boundary alignment. In the most extreme cases, parametrization collapse due to alignment constraints is eliminated.
 
Worstcase structural analysis Qingnan Zhou, Julian Panetta, Denis Zorin ACM Transactions on Graphics (TOG) vol. 32, 4, 2013 (Proceedings of SIGGRAPH 2013) Direct digital manufacturing is a set of rapidly evolving technologies that provide easy ways to manufacture highly customized and unique products. The development pipeline for such products is radically different from the conventional manufacturing pipeline: 3D geometric models are designed by users often with little or no manufacturing experience, and sent directly to the printer. Structural analysis on the user side with conventional tools is often unfeasible as it requires specialized training and software. Trialanderror, the most common approach, is timeconsuming and expensive. We present a method that would identify structural problems in objects designed for 3D printing based on geometry and material properties only, without specific assumptions on loads and manual load setup. We solve a constrained optimization problem to determine the "worst" load distribution for a shape that will cause high local stress or large deformations. While in its general form this optimization has a prohibitively high computational cost, we demonstrate that an approximate method makes it possible to solve the problem rapidly for a broad range of printed models. We validate our method both computationally and experimentally and demonstrate that it has good predictive power for a number of diverse 3D printed shapes.
 
A massively parallel adaptive fast multipole method on heterogeneous architectures Ilya Lashuk, Aparna Chandramowlishwaran, Harper Langston, Nguyen, Anh Tuan Rahul Sampath, Aashay Shringarpure, Richard Vuduc, Lexing Ying, Denis Zorin, George Biros Communications of the ACM, vol. 55, 5, 2012, pp. 101109 We describe a parallel fast multipole method (FMM) for highly nonuniform distributions of particles. We employ both distributed memory parallelism (via MPI) and shared memory parallelism (via OpenMP and GPU acceleration) to rapidly evaluate twobody nonoscillatory potentials in three dimensions on heterogeneous high performance computing architectures. We have performed scalability tests with up to 30 billion particles on 196,608 cores on the AMD/CRAYbased Jaguar system at ORNL. On a GPUenabled system (NSF's Keeneland at Georgia Tech/ORNL), we observed 30x speedup over a single core CPU and 7x speedup over a multicore CPU implementation. By combining GPUs with MPI, we achieve less than 10 ns/particle and six digits of accuracy for a run with 48 million nonuniformly distributed particles on 192 GPUs.
 
Fields on symmetric surfaces Daniele Panozzo, Yaron Lipman, Enrico Puppo, Denis Zorin ACM Transactions on Graphics (TOG), vol. 31, 4, 2013 (Proceedings of SIGGRAPH 2012) Direction fields, line fields and cross fields are used in a variety of computer graphics applications ranging from nonphotorealistic rendering to remeshing. In many cases, it is desirable that fields adhere to symmetry, which is predominant in natural as well as manmade shapes. We present an algorithm for designing smooth Nsymmetry fields on surfaces respecting generalized symmetries of the shape, while maintaining alignment with local features. Our formulation for constructing symmetry fields is based on global symmetries, which are given as input to the algorithm, with no isometry assumptions. We explore in detail the properties of generalized symmetries (reflections in particular), and we also develop an algorithm for the robust computation of such symmetry maps, based on a small number of correspondences, for surfaces of genus zero.
addendum
 
Global parametrization by incremental flattening Ashish Myles, Denis Zorin ACM Transactions on Graphics (TOG), vol. 31, 4, 2013 (Proceedings of SIGGRAPH 2012) Global parametrization of surfaces requires singularities (cones) to keep distortion minimal. We describe a method for finding cone locations and angles and an algorithm for global parametrization which aim to produce seamless parametrizations with low metric distortion. The idea of the method is to evolve the metric of the surface, starting with the original metric so that a growing fraction of the area of the surface is constrained to have zero Gaussian curvature; the curvature becomes gradually concentrated at a small set of vertices which become cones. We demonstrate that the resulting parametrizations have significantly lower metric distortion compared to previously proposed methods.
 
Computing extremal quasiconformal maps Ofir Weber, Ashish Myles, Denis Zorin Computer Graphics Forum vol. 31, 5, 2012, pp. 16791689 (Proceedings of SGP 2012) Conformal maps are widely used in geometry processing applications. They are smooth, preserve angles, and are locally injective by construction. However, conformal maps do not allow for boundary positions to be prescribed. A natural extension to the space of conformal maps is the richer space of quasiconformal maps of bounded conformal distortion. Extremal quasiconformal maps, that is, maps minimizing the maximal conformal distortion, have a number of appealing properties making them a suitable candidate for geometry processing tasks. Similarly to conformal maps, they are guaranteed to be locally bijective; unlike conformal maps however, extremal quasiconformal maps have sufficient flexibility to allow for solution of boundary value problems. Moreover, in practically relevant cases, these solutions are guaranteed to exist, are unique and have an explicit characterization.
We present an algorithm for computing piecewise linear approximations of extremal quasiconformal maps for genuszero surfaces with boundaries, based on Teichmueller's characterization of the dilatation of extremal maps using holomorphic quadratic differentials. We demonstrate that the algorithm closely approximates the maps when an explicit solution is available and exhibits good convergence properties for a variety of boundary conditions.
 
Global parametrization of range image sets N. Pietroni, M. Tarini, O. Sorkine, D. Zorin ACM Transactions on Graphics, 2011, vol. 30, 6 (Proceedings of SIGGRAPH Asia 2011) We present a method to globally parameterize a surface represented by height maps over a set of planes (range images). In contrast to other parametrization techniques, we do not start with a manifold mesh. The parametrization we compute defines a manifold structure, it is seamless and globally smooth, can be aligned to geometric features and shows good quality in terms of angle and area preservation, comparable to current parametrization techniques for meshes. Computing such global seamless parametrization makes it possible to perform quad remeshing, texture mapping and texture synthesis and many other types of geometry processing operations. Our approach is based on a formulation of the Poisson equation on a manifold structure defined for the surface by the range images. Construction of such global parametrization requires only a way to project surface data onto a set of planes, and can be applied directly to implicit surfaces, nonmanifold surfaces, very large meshes, and collections of range scans. We demonstrate application of our technique to all these geometry types.
 
InterferenceAware Geometric Modeling D. Harmon, D. Panozzo, O. Sorkine, D. Zorin ACM Transactions on Graphics, 2011, vol. 30, 6 (Proceedings of SIGGRAPH Asia 2011) While often a requirement for geometric models, there has been little research in resolving the interaction of deforming surfaces during realtime modeling sessions. To address this important topic, we introduce an interference algorithm specifically designed for the domain of geometric modeling. This algorithm is general, easily working within existing modeling paradigms to maintain their important properties. Our algorithm is fast, and is able to maintain interactive rates on complex deforming meshes of over 75K faces, while robustly removing intersections. Lastly, our method is controllable, allowing finetuning to meet the specific needs of the user. This includes support for minimum separation between surfaces and control over the relative rigidity of interacting objects.
video
 
Asynchronous integration with phantom meshes D. Harmon, Q. Zhou, D. Zorin 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2011, pp. 247–256 Asynchronous variational integration of layered contact models provides a framework for robust collision handling, correct physical behavior, and guaranteed eventual resolution of even the most dif?cult contact problems. Yet, even for lowcontact scenarios, this approach is signi?cantly slower compared to its less robust alternatives, often due to handling of stiff elastic forces in an explicit framework. We propose a method that retains the guarantees, but allows for variational implicit integration of some of the forces, while maintaining asynchronous integration needed for contact handling. Our method uses phantom meshes for calculations with stiff forces, which are then coupled to the original mesh through constraints. We use the augmented discrete Lagrangian of the constrained system to derive a variational integrator with the desired conservation properties.
 
Manifoldbased surfaces with boundary E. Tosun, D. Zorin Computer Aided Geometric Design, 2011, vol. 28 , 1, 2011, pp. 1–22 We present a manifoldbased surface construction extending the C1 construction of Ying and Zorin (2004a). Our surfaces allow for pircewisesmooth boundaries, have usercontrolled arbitrary degree of smoothness and improved derivative and visual behavior. 2flexibility of our surface construction is confirmed numerically for a range of local mesh configurations.
 
A fast algorithm for simulating vesicle flows in three dimensions S. Veerapaneni, A. Rahimian, G. Biros, D. Zorin Journal of Computational Physics, 2011, vol. 230, 14, pp. 5610–5634 Vesicles are locallyinextensible fluid membranes that can sustain bending. In this paper, we present a fast algorithm for simulating the dynamics of vesicles suspended in viscous fluids. Spatial quantities are discretized using spherical harmonics, and quadrature rules for singular surface integrals need to be adapted to this case; an algorithm for surface reparameterization is neeed to ensure suffcient of the time stepping scheme, and spectral filtering is introduced to maintain reasonable accuracy while minimizing computational costs. We obtain a timestepping scheme that, in our numerical experiments, is unconditionally stable. We present results to analyze the cost and convergence rates of the overall scheme. To illustrate the applicability of the new method, we consider a few vesicleflow interaction problems: a single vesicle in relaxation, sedimentation, shear flows, and manyvesicle flows.
video
 
A Freespace adaptive FMMBased PDE solver in three dimensions H. Langston, L. Greengard, D. Zorin Communications in Applied Mathematics and Computational Science, 2011, vol. 6, 79122 We present a kernelindependent, 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 righthand 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 righthand side and compute farfield expansions in the FMM from the coefficients of this approximation. Second, we precompute tables of quadratures to handle the nearfield 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.
 
Petascale Direct Numerical Simulation of Blood Flow on 200K Cores and Heterogeneous Architectures. A. Rahimian, I. Lashuk, S. K. Veerapaneni, A. Chandramowlishwaran, D. Malhotra, L. Moon, R. S. Sampath, A. Shringarpure, J. Vetter, R. W. Vuduc, D. Zorin, G. Biros Proceedings of SC10, p 1–11, (Gordon Bell Prize) We present a fast, petaflopscalable algorithm for Stokesian particulate flows. Our goal is the direct simulation of blood, which we model as a mixture of a Stokesian fluid (plasma) and red blood cells (RBCs). Directly simulating blood is a challenging multiscale, multiphysics problem. We report simulations with up to 200 million deformable RBCs. The largest simulation amounts to 90 billion unknowns in space. In terms of the number of cells, we improve the stateofthe art by several orders of magnitude: the previous largest simulation, at the same physical fidelity as ours, resolved the flow of O(1,00010,000) RBCs. Our approach has three distinct characteristics: (1) we faithfully represent the physics of RBCs by using nonlinear solid mechanics to capture the deformations of each cell; (2) we accurately resolve the longrange, Nbody, hydrodynamic interactions between RBCs (which are caused by the surrounding plasma); and (3) we allow for the highly nonuniform distribution of RBCs in space. The new method has been implemented in the software library MOBO (for Moving Boundaries). We designed MOBO to support parallelism at all levels, including internode distributed memory parallelism, intranode shared memory parallelism, data parallelism (vectorization), and finegrained multithreading for GPUs. We have implemented and optimized the majority of the computation kernels on both Intel/AMD x86 and NVidia's Tesla/Fermi platforms for single and double floating point precision. Overall, the code has scaled on 256 CPUGPUs on the Teragrid's Lincoln cluster and on 200,000 AMD cores of the Oak Ridge national Laboratory's Jaguar PF system. In our largest simulation, we have achieved 0.7 Petaflops/s of sustained performance on Jaguar.
 
Featurealigned Tmeshes A. Myles, N. Pietroni, D. Kovacs, D. Zorin ACM Transactions on Graphics, 2010, vol. 29, 4 (Proceedings of SIGGRAPH 2010) Highorder and regularly sampled surface representations are more efficient and compact than general meshes and considerably simplify many geometric modeling and processing algorithms. A number of recent algorithms for conversion of arbitrary meshes to regularly sampled form (typically quadrangulation) aim to align the resulting mesh with feature lines of the geometry. While resulting in a substantial improvement in mesh quality, feature alignment makes it difficult to obtain coarse regular patch partitions of the mesh.
In this paper, we propose an approach to constructing patch layouts consisting of small numbers of quadrilateral patches while maintaining good feature alignment. To achieve this, we use quadrilateral Tmeshes, for which the intersection of two faces may not be the whole edge or vertex, but a part of an edge. Tmeshes offer more flexibility for reduction of the number of patches and vertices in a base domain while maintaining alignment with geometric features. At the same time, Tmeshes retain many desirable features of quadrangulations, allowing construction of highorder representations, easy packing of regularly sampled geometric data into textures, as well as supporting different types of discretizations for physical simulation.
 
Mixed Finite Elements for Variational Surface Modeling A. Jacobson, E.Tosun, O. Sorkine, D. Zorin Computer Graphics Forum 2010, vol. 29, 5, pp. 1565–1574 (Proceedings of SGP 2010) Many problems in geometric modeling can be described using variational formulations that define the smoothness of the shape and its behavior w.r.t. the posed modeling constraints. For example, highquality C2 surfaces that obey boundary conditions on positions, tangents and curvatures can be conveniently defined as solutions of highorder geometric PDEs; the advantage of such a formulation is its conceptual representationindependence. In practice, solving highorder problems efficiently and accurately for surfaces approximated by meshes is notoriously difficult. For modeling applications, the preferred approach is to use discrete geometric schemes which are efficient and robust, but their convergence properties are less well understood compared to higherorder FEM. In this paper, we explore discretizations of common geometric PDEs on meshes using mixed finite elements, where additional variables for the derivatives in the problem are introduced. Such formulations use firstorder derivatives only, allowing a discretization with simple linear elements. Various boundary conditions can be naturally discretized in this setting. We formalize continuous region constraints commonly used in modeling applications, and show that these seamlessly fit into the mixed framework. We demonstrate that some of the commonly used discrete geometric discretizations can be regarded as a particular case of mixed finite elements. We study the convergence behavior of our discretizations, and how they can be applied to implement common modeling tasks.
 
Anisotropic quadrangulation D. Kovacs, A. Myles, D. Zorin Symposium on Solid and Physical Modeling 2010, pp 137–146 Quadrangulation algorithms approximate arbitrary meshes with meshes consisting of quads or mostly quads, and with only a small number of extraordinary vertices. To minimize the number of quads needed while maintaing a good approximation of shapes, one wants to use anisotropically scaled quads in areas with a high ratio of principal curvatures. Most existing techniques rely on global parametrization methods either producing uniform aspectratio quads, or anisotropic quads with sizes unrelated to the curvature magnitudes. We propose a simple technique that can be combined with a variety of parametrization and quadrangulation methods to produce anisotropic semiregular remeshing. Our approach is based on using a metric derived from the shape operator to adjust lengths and angles in surface parametrization equations in a way that equalizes normal error distribution over the surface.
 
A massively parallel adaptive fastmultipole method on heterogeneous architectures I. Lashuk, A. Chandramowlishwaran, H. Langston, T.A. Nguyen, R. S. Sampath, A. Shringarpure, R. W. Vuduc, L. Ying, D. Zorin, G. Biros Proceedings of SC09 We present new scalable algorithms and a new implementation of our kernelindependent fast multipole method (Ying et al. ACM/IEEE SC '03), in which we employ both distributed memory parallelism (via MPI) and shared memory/streaming parallelism (via GPU acceleration) to rapidly evaluate twobody nonoscillatory potentials. On traditional CPUonly systems, our implementation scales well up to 30 billion unknowns on 65K cores (AMD/CRAYbased Kraken system at NSF/NICS) for highly nonuniform point distributions. On GPUenabled systems, we achieve 30x speedup for problems of up to 256 million points on 256 GPUs (Lincoln at NSF/NCSA) over a comparable CPUonly based implementations.
We achieve scalability to such extreme core counts by adopting a new approach to scalable MPIbased tree construction and partitioning, and a new reduction algorithm for the evaluation phase. For the subcomponents of the evaluation phase (the direct and approximateinteractions, the target evaluation, and the sourcetomultipole translations), we use NVIDIA's CUDA framework for GPU acceleration to achieve excellent performance. To do so requires carefully constructed data structure transformations, which we describe in the paper and whose cost we show is minor. Taken together, these components show promise for ultrascalable FMM in the petascale era and beyond.
 
Highorder methods for simulating the dynamics of axissymmetric inextensible vesicles in viscous flow S. Veerapaneni, D. Gueyffier, G. Biros, D. Zorin Journal of Computational Physics, vol 228, 19, 2009, pp 7233–7249 We extend the efficient highorder 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 semiimplicit scheme needed to eliminate the CFLtype restriction in the toroidal case. We present an unconditionally stable scheme with low cost per time step, and spectrally accurate in space and thirdorder accurate in time. An important part of the algorithm is a novel numerical scheme for evaluation of the 3D Stokes singlelayer potential on an axisymmetric surface, needed to achieve optimal complexity. As an application, we explore the motion of axisymmetric vesicles under gravity
video
 
Realtime creased subdivision surfaces D. Kovacs, J. Mitchell, D. Zorin IEEE Transactions on Visualization and Computer Graphics, 2010, vol 16, 5, pp.742–751 We present an extension of recently developed Loop and Schaefer's approximation of CatmullClark 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
 
Applicationaware management of parallel simulation S.M. Yau, K. Damevski, V. Karamcheti, S. Parker, D. Zorin SIGPLAN Symposium on Principles and Practice of Parallel Programming 2009 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 UINTAHbased helium gas simulation code (ARCHES) and the SimX system for multiexperiment computational studies, this paper demonstrates that, by using applicationspecific 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 32processor cluster, and from almost 11 hours to just over 3.5 hours on a 64processor cluster.
 
Structured annotations for 2Dto3D modeling Y. Gingold, T. Igarashi, D. Zorin ACM Transactions on Computer Graphics, vol. 28, 5, 2009 We present a singleview 2D interface for 3D modeling based on the idea of placing 2D primitives and annotations on an existing, premade sketch or image. Our interface frees users to create 2D sketches from arbitrary angles using their preferred tool – including pencil and paper – which they then "describe" using our tool to create a 3D model. Our interface can be used to generate a 3D model from an illustration, such as those found in children's picture books. Our primitives are manipulated with persistent, dynamic handles, and our annotations take the form of markings commonly used in geometry textbooks. Our interface eliminates the constant rotation inherent to previous sketchbasedmodeling tools such as [Igarashi et al. 1999]. Our method is significantly different from computer vision approaches because many 2D drawings have no consistent 3D representation. Instead, we view 2D drawings as semantic, qualitative descriptions of 3D geometry, rather than as literal, quantitative descriptions. Our system solves this illposed problem with the help of human intervention. Our 3D models are generated entirely from the user's input; our algorithm does not consider the original 2D image. In this work, our focus is on rotund, freeform shapes and not manmade rectilinear/CAD models.
 
A boundary integral method for simulating the dynamics of inextensible vesicles suspended in a viscous fluid in 2D S. Veerapaneni, D. Gueyffier, G. Biros, D. Zorin Journal of Computational Physics, 2008 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 integrodifferential 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 timestepping schemes suffer from a severe stability constraint due to the stiffness related to highorder spatial derivatives and a milder constraint due to a transportlike 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 semiimplicit 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 thirdorder accurate scheme in time. We use the fast multipole method (FMM) to efficiently compute vesiclevesicle 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.
video
 
Shadingbased surface editing Y. Gingold, D. Zorin ACM Transactions on Computer Graphics,vol. 27, 3, SIGGRAPH 2008 We present a system for freeform surface modeling that allows a user to modify a shape by changing its rendered, shaded image using strokebased 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 freeform surface edits which may be difficult to cast in terms of standard deformation approaches can be easily performed using our system.
video
 
Realtime rendering of textures with feature curves E. Parilov, D. Zorin ACM Transactions on Computer Graphics, vol. 27, 1, 2008 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 highquality interactive rendering at arbitrary magnifications, one needs to interpolate the distance field preserving discontinuity curves exactly. We present a realtime, GPUbased 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 realtime rendering of complex feature patterns and blending normal maps with procedurally defined profiles near normal discontinuities.
video
 
Result reuse in design space exploration: a study in system support for interactive parallel computing S.M. Yau, K. Damevski, V. Karamcheti, S. Parker, D. Zorin IEEE International Parallel and Distributed Processing Symposium, 2008 This paper presents a system supporting reuse of simulation results in multiexperiment computational studies involving independent simulations and explores the benefits of such reuse. Using a SCIRunbased 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 moderatesized 128node processor cluster; a bruteforce 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.
 
Cubic shells A. Garg, E. Grinspun, M. Wardetzky, D. Zorin Symposium on Computer Animation 2007, pp. 91–98 Hingebased bending models are widely used in the physicallybased animation of cloth, thin plates and shells. We propose a hingebased 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.
 
Shape optimization using reflection lines E. Tosun, Y. I. Gingold, J. Reisman, D. Zorin Symposium on Geometry Processing 2007, pp. 193–202 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 screenspace surface parameterization, and we demonstrate how such discrete functionals can be used for several types of surface editing operations.
video
 
Controlledtopology filtering Y .I. Gingold, D. Zorin ComputerAided Design, vol. 39, 8, 2007, pp. 676–684 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 postprocessing 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.
 
Discrete quadratic bending energies M. Wardetzky, M. Bergou, D. Harmon, D. Zorin, E. Grinspun ComputerAided Geometric Design, Special Issue on Discrete Differential Geometry, vol. 24, 89, 2007, pp. 499518 We present a family of discrete isometric bending models (IBMs) for triangulated surfaces in 3space. 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 timeintegration of cloth dynamics with a two to threefold net speedup over existing nonlinear methods, and nearinteractive rates for Willmore smoothing of large meshes.
video
 
A note on the trianglecentered quadratic interpolation discretization of the shape operator J. Reisman, E. Grinspun, D. Zorin Technical report, 2001, NYU and Columbia  
SimX: Parallel system software for interactive multiexperiment computational studies S.M. Yau, E. Grinspun, V. Karamcheti, D. Zorin IEEE International Parallel and Distributed Processing Symposium, 2006 Advances in highperformance 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 highlevel 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 highlevel 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.
 
A Highorder 3D boundary integral equation solver for elliptic PDEs in smooth domains L. Ying, G. Biros, D. Zorin Journal of Computational Physics vol. 219, 1, 2006, pp. 247–275 We present a highorder 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(N3/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 kernelindependent fast summation algorithm is used to accelerate the evaluation of the discretized integral operators. We describe a highorder 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 regulargrid 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.
 
A quadratic bending model for inextensible surfaces M. Bergou, M. Wardetzky, D. Harmon, D. Zorin, E. Grinspun Symposium on Geometry Processing, 2006, pp. 227–230 Efficient computation of curvaturebased 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 curvaturebased 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.
video
 
Constructing curvaturecontinuous surfaces by blending D. Zorin Symposium on Geometry Processing, 2006, pp. 31–40 In this paper we describe an approach to the construction of curvaturecontinuous 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.
addendum
 
Computing discrete shape operators on general meshes E. Grinspun, Y. Gingold, J. Reisman, D. Zorin Computer Graphics Forum (Eurographics 2006) vol. 25,3, 2006, pp. 547–556, 3rd best paper award 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 twodimensional 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.
addendum
 
A Direct texture placement and editing interface Y. Gingold, P. Davidson, J. Han, D. Zorin Proceedings of he 19th ACM Symposium on User Interface Software and Technology (UIST06), pp. 23–32 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 UVcoordinate 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 multitouch 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 twohand input.
video
 
Subdivision on arbitrary meshes: algorithms and theory D. Zorin Institute of Mathematical Sciences (Singapore) Lecture Notes Series, 2006 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.
 
Curvaturebased energy for simulation D. Zorin Shape Modeling International Proceedings, 2005, pp. 198–206 Curvaturebased 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 springparticle 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 wellestablished 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 wellknown discrete geometry and finite element formulations and to derive new simple and efficient discretizations.
 
A survey of subdivisionbased tools for surface modeling I. BoierMartin, D. Zorin, F. Bernardini AMS/DIMACS Volume on ComputerAided Design and Manufacturing, vol. 67, 2005, pp. 1–28 Subdivision surfaces have emerged as a powerful representation for surface modeling and design. They address important limitations of traditional splinebased methods, such as the ability to handle arbitrary topologies and to support multiscale editing operations. In this paper we survey existing subdivisionbased modeling methods with emphasis on interactive tools for styling and decoration of 3D models.
 
Interactive modeling of topologically complex geometric detail J. Peng, D. Kristjansson, D. Zorin ACM Transactions on Graphics vol. 23, 3, (SIGGRAPH 2004), pp. 635–643 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 twodimensional 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 volumetextured surfaces. We demonstrate a number of interactive operations that these algorithms enable.
video
 
A simple manifoldbased construction of surfaces of arbitrary smoothness L. Ying, D. Zorin ACM Transactions on Graphics 23, 3, (SIGGRAPH 2004), pp. 271–275 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 Cinfinitycontinuous with explicit nonsingular Cinfinity parameterizations, highorder flexible at control vertices, depend linearly on control points, have fixedsize local support for basis functions, and have good visual quality.
 
Differentiable parametrization of CatmullClark subdivision surfaces I. Martin, D. Zorin Eurographics/SIGGRAPH Symposium on Geometry Processing, 2004, pp. 155–164 Subdivisionbased representations are recognized as important tools for the generation of highquality surfaces for Computer Graphics. In this paper we describe two parameterizations of CatmullClark subdivision surfaces that allow a variety of algorithms designed for other types of parametric surfaces (i.e., Bsplines) 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 ComputerAided Design (CAD) applications that seek to address the limitations of NURBSbased representations through the more flexible subdivision framework.
 
Lofting curve networks using subdivision surfaces S. Schaefer, J. Warren, D. Zorin Eurographics/SIGGRAPH Symposium on Geometry Processing, 2004, pp. 103–114 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 Bsplines 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 CatmullClark 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.
 
A kernelindependent adaptive fast multipole algorithm in two and three dimensions L. Ying, G. Biros, D. Zorin Journal of Computational Physiscs vol. 196, 2, 2004, pp. 591–626 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 Dirichlettype boundary value problems. The farfield 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.
code
 
A discrete model for inelastic deformation of thin shells A. J. Secord, E. Grinspun, D. Zorin Technical report (a poster presented at SCA 2004) 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, eggshells 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.
 
A new parallel kernelindependent fast multipole method L. Ying, G. Biros, H. Langston, D. Zorin Proceedings of SC03, 2003, The SCxy Conference series. (Best student paper award, Gordon Bell prize finalist) We present a new adaptive fast multipole algorithm and its parallel implementation. The algorithm is kernelindependent 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 MPIbased 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 fixedsize scalability for a variety of kernels on the Pittsburgh Supercomputing Center's TCS1 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.
 
A fast solver for the Stokes equations with distributed forces in complex geometries G. Biros, L. Ying, D. Zorin Journal of Computational Physics, vol. 193, 1, 2003, pp. 317–348 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 blackbox fashion; (2) it is secondorder 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) 285299. 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 velocitypressure formulation with equal order interpolation bilinear elements (Q1Q1). Stabilization is used to circumvent the infsup condition for the pressure space. For the integral equations, fast matrixvector 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 lowrank blocks. The regular grid solver is a Krylov method (conjugate residuals) combined with an optimal twolevel Schwartzpreconditioner. For the integral equation we use GMRES. We have tested our algorithm on several numerical examples and we have observed optimal convergence rates.
 
Sharp features on multiresolution subdivision surfaces H. Biermann, I. Martin, F. Bernardini, D. Zorin Graphical Models, vol. 64, 2002 (previously published in Proceedings of Pacific Graphics 2001) In this paper we describe a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of userdefined 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 CatmullClark surfaces that allows the creation of creases along diagonals of control mesh faces.
 
The embedded boundary integral method for the incompressible NavierStokes equations G. Biros, L. Ying, D. Zorin Proceedings of International Association for Boundary Element Methods 2002 Symposium We present a new method for the solution of the unsteady incompressible NavierStokes equations. Our goal is to achieve a robust and scalable methodology for two and three dimensional incompressible flows. The discretization of the NavierStokes operator is done using boundary integrals and structuredgrid finite elements. We use finitedifferences to advance the equations in time. The convective term is discretized via a semiLagrangian formulation which not only results in a spatial constantcoefficient (modified) Stokes operator, but in addition is unconditionally stable. The Stokes operator is inverted by a doublelayer boundary integral formulation. Domain integrals are computed via finite elements with appropriate forcing singularities to account for the irregular geometry. We use a velocitypressure formulation which we discretize with bilinear elements (Q1Q1), which give equal order interpolation for the velocities and pressures. Stabilization is used to circumvent the divstability 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.
 
Cutandpaste editing of multiresolution surfaces H. Biermann, I. Martin, F. Bernardini, D. Zorin SIGGRAPH 2002 Proceedings, pp. 312–321 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 cutandpaste too], especially during the initial stages of design when a large space of alternatives needs to be explored. Techniques to support cutandpaste 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 realtime interaction. In this paper, we describe a set of algorithms based on multiresolution subdivision surfaces that perform at interactive rates and enable intuitive cutandpaste operations.
video
 
Evaluation of piecewise smooth subdivision surfaces D. Zorin, D. Kristjansson Visual Computer, vol. 18, 6, 2002 In this paper we consider the constanttime 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.
 
Sharp features on multiresolution subdivision surfaces H. Biermann, I. Martin, F. Bernardini, D. Zorin Proceedings of Pacific Graphics, 2001 In this paper we describe a method for creating sharp features and trim regions on multiresolution subdivision surfaces along a set of userdefined 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 CatmullClark surfaces that allows the creation of creases along diagonals of control mesh faces.
 
Approximate boolean operations on freeform solids H. Biermann, D. Kristjansson, D. Zorin SIGGRAPH 2001 Proceedings, pp. 185–194 In this paper we describe a method for computing approximate results of boolcan operations (union, intersection, difference) applied to freeform 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, highaccuracy approximations are also possible at additional computational expense, if the topology of the intersection curve is resolved correctly.
 
Simple and efficient algorithm for surface denoising J. Peng, V. Strela, D. Zorin IEEE Visualization 2001 Proceedings, pp. 107–112 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.
video
 
Nonmanifold subdivision L. Ying, D. Zorin IEEE Visualization 2001 Proceedings, pp. 325–332 Commonlyused 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 wellknown Loop subdivision scheme, and uses techniques developed for piecewise smooth surfaces.
 
Texture and shape synthesis on surfaces L. Ying, A. Hertzman, H. Biermann, D. Zorin Prceedings of 12th Eurographics Workshop on Rendering 2001 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.
 
48 subdivision L. Velho, D. Zorin ComputerAided Geometric Design, vol. 18, 5, 2001, (Special Issue on Subdivision), pp. 397–427 In this paper we introduce 48 subdivision, a new scheme that generalizes the fourdirectional box spline of class C4 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 variableresolution 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 48 scheme are C4 continuous almost everywhere, except at extraordinary vertices where they are is C1continuous.
 
A Unified framework for primal/dual quadrilateral subdivision Schemes D. Zorin, P. Schröder ComputerAided Geometric Design, vol. 18, 5, 2001, (Special Issue on Subdivision), pp. 429–454 Quadrilateral subdivision schemes come in primal and dual varieties, splitting faces or respectively vertices. The scheme of CatmullClark is an example of the former, while the DooSabin 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 DooSabin and CatmullClark schemes followed by novel schemes generalizing Bsplines of bidegree up to nine. We prove the schemes to be C1 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 pversions of the Subdivision Element Method. Additionally we describe a simple algorithm for adaptive subdivision of dual schemes.
 
An embedded boundary integral solver for the unsteady incompressible NavierStokes equations G. Biros, L. Ying, D. Zorin Technical report, 2001  
Piecewise smooth subdivision surfaces with boundary and normal control H. Biermann, A. Levin, D. Zorin SIGGRAPH 2000 Proceedings, pp. 113–120 In this paper we introduce improved rules for CatmullClark 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.
code
 
Artistic multiprojection images M. Agrawala, D. Zorin, T. Munzner Rendering Techniques 2000: 11th Eurographics Workshop on Rendering, pp. 125–136 In composing handdrawn 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.
video
 
Illustrating smooth surfaces A. Hertzmann, D. Zorin SIGGRAPH 2000 Proceedings, pp. 517–526 We present a new set of algorithms for lineart 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.
code
 
A method for analysis of C^{1}continuity of subdivision surfaces D. Zorin SIAM Journal of Numerical Analysis, vol. 37, 5, 2000, pp. 1677–1708 A sufficient condition for C1continuity of subdivision surfaces was proposed by Reif [Comput. Aided Geom. Design, 12 (1995), pp. 153174.] and extended to a more general setting in [D. Zorin, Constr. Approx., accepted for publication]. In both cases, the analysis of C1continuity is reduced to establishing injectivity and regularity of a characteristic map. In all known proofs of C1continuity, 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 C1continuity 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 C1continuity 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.
 
Smoothness of subdivision on irregular meshes D. Zorin Constructive Approximation, vol. 16, no. 3, 2000, pp. 359–397 We derive necessary and sufficient conditions for tangent plane and Ckcontinuity 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.
 
Subdivision for modeling and animation D. Zorin, P. Schröder, A. DeRose, L. Kobbelt, A. Levin, W. Sweldens SIGGRAPH 2000 Course Notes, (earlier versions 1999,1999) 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.
 
Interactive multiresolution mesh editing D. Zorin, P. Schröder, W. Sweldens SIGGRAPH 1997 Proceedings, pp. 256–268 We describe a multiresolution representation for meshes based on subdivision,which is a natural extension of the existing patchbased 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.
video
 
Interpolation subdivision for meshes of arbitrary topology D. Zorin, W. Sweldens, P. Schröder SIGGRAPH 1996 Proceedings, pp. 189–192 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.
video
 
Correction of geometric perceptual distortion in pictures D. Zorin, A. H. Barr SIGGRAPH 1995 Proceedings, pp. 257–264 We suggest an approach for correcting several types of perceived geometric distortions in computergenerated 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 computergenerated and photographic perspective projection images. Our transformations can considerably reduce distortion in wideangle motion pictures and computergenerated animations.
video
 
Symmetric constraints in classification problems that admit replacement by functional constraints D. Zorin Cybernetics and Systems Anal. vol. 29, 4, 1993, pp. 531–537  
On a connection between homogeneity and independence constraints for classification algorithms D. Zorin Cybernetics vol. 27, 2, 1991, pp. 304–309 We describe a set of functional universal constraints for classification algorithms that correspond to particular systems of symmetric universal constraints.
