>

Denis ZorinDenis Zorin

Vision, Learning and Graphics Group
Computer Science Department
Mathematics Department
Courant Institute of Mathematical Sciences
New York University
719 Broadway, 12th floor
New York, NY 10003
phone: (212)998-3405
fax: (212)995-4122
e-mail: dzorin@cs.nyu.edu

Research Interests

Geometric modeling: subdivision surfaces, variational modeling, manifold constructions, interactive and appearance based modeling, discretization of geometric quantities.

Scientific computing: Fast multipole methods, numerical solution of integral equations, fluid and deformable membrane simulation, parallel algorithms and software tools.

Publications

Quad-Mesh 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. 51-76
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 semi-regular 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, Per-Gunnar 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 off-diagonal 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 Semi-Separable" (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 reduced-space 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 full-coordinate simulations, striking a desirable balance between runtime speeds and expressive ability.
video
Controlled-distortion 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 cross-fields 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 variation-minimizing cross-fields and related 1-forms and conformal maps, and demonstrate how it leads to a constrained optimization problem formulation. We show for boundary-aligned parametrizations metric distortion may be reduced by cone chains, sometimes to an arbitrarily small value, and the trade-off 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 state-of-the art field-based method, yet maintain feature and boundary alignment. In the most extreme cases, parametrization collapse due to alignment constraints is eliminated.
Worst-case 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. Trial-and-error, the most common approach, is time-consuming 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. 101-109
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 two-body 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/CRAY-based Jaguar system at ORNL. On a GPU-enabled 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 non-photorealistic rendering to remeshing. In many cases, it is desirable that fields adhere to symmetry, which is predominant in natural as well as man-made shapes. We present an algorithm for designing smooth N-symmetry 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. 1679-1689 (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 genus-zero 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.
Interference-Aware 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 real-time 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 fine-tuning 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 low-contact 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.
Manifold-based surfaces with boundary
E. Tosun, D. Zorin
Computer Aided Geometric Design, 2011, vol. 28 , 1, 2011, pp. 1–22
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.
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 locally-inextensible 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 time-stepping 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 vesicle-flow interaction problems: a single vesicle in relaxation, sedimentation, shear flows, and many-vesicle flows.
video
A Free-space adaptive FMM-Based PDE solver in three dimensions
H. Langston, L. Greengard, D. Zorin
Communications in Applied Mathematics and Computational Science, 2011, vol. 6, 79-122
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.
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, petaflop-scalable 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 state-of-the art by several orders of magnitude: the previous largest simulation, at the same physical fidelity as ours, resolved the flow of O(1,000-10,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 long-range, N-body, hydrodynamic interactions between RBCs (which are caused by the surrounding plasma); and (3) we allow for the highly non-uniform 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 inter-node distributed memory parallelism, intra-node shared memory parallelism, data parallelism (vectorization), and fine-grained 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 CPU-GPUs 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.
Feature-aligned T-meshes
A. Myles, N. Pietroni, D. Kovacs, D. Zorin
ACM Transactions on Graphics, 2010, vol. 29, 4 (Proceedings of SIGGRAPH 2010)
High-order 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 T-meshes, for which the intersection of two faces may not be the whole edge or vertex, but a part of an edge. T-meshes 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, T-meshes retain many desirable features of quadrangulations, allowing construction of high-order 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, high-quality C2 surfaces that obey boundary conditions on positions, tangents and curvatures can be conveniently defined as solutions of high-order geometric PDEs; the advantage of such a formulation is its conceptual representation-independence. In practice, solving high-order 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 higher-order 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 first-order 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 aspect-ratio 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 fast-multipole 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 kernel-independent 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 two-body non-oscillatory potentials. On traditional CPU-only systems, our implementation scales well up to 30 billion unknowns on 65K cores (AMD/CRAY-based Kraken system at NSF/NICS) for highly non-uniform point distributions. On GPU-enabled systems, we achieve 30x speedup for problems of up to 256 million points on 256 GPUs (Lincoln at NSF/NCSA) over a comparable CPU-only based implementations. We achieve scalability to such extreme core counts by adopting a new approach to scalable MPI-based tree construction and partitioning, and a new reduction algorithm for the evaluation phase. For the sub-components of the evaluation phase (the direct- and approximate-interactions, the target evaluation, and the source-to-multipole 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.
High-order methods for simulating the dynamics of axis-symmetric 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 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
video
Real-time 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 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
Application-aware 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 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.
Structured annotations for 2D-to-3D modeling
Y. Gingold, T. Igarashi, D. Zorin
ACM Transactions on Computer Graphics, vol. 28, 5, 2009
We present a single-view 2D interface for 3D modeling based on the idea of placing 2D primitives and annotations on an existing, pre-made 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 sketch-based-modeling 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 ill-posed 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, free-form shapes and not man-made 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 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.
video
Shading-based surface editing
Y. Gingold, D. Zorin
ACM Transactions on Computer Graphics,vol. 27, 3, SIGGRAPH 2008
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.
video
Real-time 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 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.
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 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.
Cubic shells
A. Garg, E. Grinspun, M. Wardetzky, D. Zorin
Symposium on Computer Animation 2007, pp. 91–98
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.
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 screen-space surface parameterization, and we demonstrate how such discrete functionals can be used for several types of surface editing operations.
video
Controlled-topology filtering
Y .I. Gingold, D. Zorin
Computer-Aided 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 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.
Discrete quadratic bending energies
M. Wardetzky, M. Bergou, D. Harmon, D. Zorin, E. Grinspun
Computer-Aided Geometric Design, Special Issue on Discrete Differential Geometry, vol. 24, 8-9, 2007, pp. 499-518
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.
video
A note on the triangle-centered quadratic interpolation discretization of the shape operator
J. Reisman, E. Grinspun, D. Zorin
Technical report, 2001, NYU and Columbia
Sim-X: Parallel system software for interactive multi-experiment computational studies
S.-M. Yau, E. Grinspun, V. Karamcheti, D. Zorin
IEEE International Parallel and Distributed Processing Symposium, 2006
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.
A High-order 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 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.
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 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.
video
Constructing curvature-continuous surfaces by blending
D. Zorin
Symposium on Geometry Processing, 2006, pp. 31–40
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.
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 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.
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 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.
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.
Curvature-based energy for simulation
D. Zorin
Shape Modeling International Proceedings, 2005, pp. 198–206
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.
A survey of subdivision-based tools for surface modeling
I. Boier-Martin, D. Zorin, F. Bernardini
AMS/DIMACS Volume on Computer-Aided 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 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.
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 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.
video
A simple manifold-based 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 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.
Differentiable parametrization of Catmull-Clark subdivision surfaces
I. Martin, D. Zorin
Eurographics/SIGGRAPH Symposium on Geometry Processing, 2004, pp. 155–164
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 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 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.
A kernel-independent 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 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.
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, 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.
A new parallel kernel-independent 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 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.
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 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.
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 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.
The embedded boundary integral method for the incompressible Navier-Stokes 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 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.
Cut-and-paste 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 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.
video
Evaluation of piecewise smooth subdivision surfaces
D. Zorin, D. Kristjansson
Visual Computer, vol. 18, 6, 2002
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.
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 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.
Approximate boolean operations on free-form 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 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.
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
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.
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.
4-8 subdivision
L. Velho, D. Zorin
Computer-Aided Geometric Design, vol. 18, 5, 2001, (Special Issue on Subdivision), pp. 397–427
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.
A Unified framework for primal/dual quadrilateral subdivision Schemes
D. Zorin, P. Schröder
Computer-Aided 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 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.
An embedded boundary integral solver for the unsteady incompressible Navier-Stokes 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 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.
code
Artistic multi-projection images
M. Agrawala, D. Zorin, T. Munzner
Rendering Techniques 2000: 11th Eurographics Workshop on Rendering, pp. 125–136
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.
video
Illustrating smooth surfaces
A. Hertzmann, D. Zorin
SIGGRAPH 2000 Proceedings, pp. 517–526
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.
code
A method for analysis of C1-continuity of subdivision surfaces
D. Zorin
SIAM Journal of Numerical Analysis, vol. 37, 5, 2000, pp. 1677–1708
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.
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 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.
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 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.
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 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.
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.