SGP04: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Spectral Surface Reconstruction From Noisy Point Clouds
[meta data] [files:
Kolluri, Ravikrishna
;
Shewchuk, Jonathan Richard
;
O'Brien, James F.
Registration of Point Cloud Data from a Geometric Optimization Perspective
[meta data] [files:
Mitra, Niloy J.
;
Gelfand, Natasha
;
Pottmann, Helmut
;
Guibas, Leonidas
Iso-charts: Stretch-driven Mesh Parameterization using Spectral Analysis
[meta data] [files:
Zhou, Kun
;
Synder, John
;
Guo, Baining
;
Shum, Heung-Yeung
Geometric Texture Synthesis by Example
[meta data] [files:
Bhat, Pravin
;
Ingram, Stephen
;
Turk, Greg
Seamless Texture Atlases
[meta data] [files:
Purnomo, Budirijanto
;
Cohen, Jonathan D.
;
Kumar, Subodh
Signal-Specialized Parameterization for Piecewise Linear Reconstruction
[meta data] [files:
Tewari, Geetika
;
Snyder, John
;
Sander, Pedro V.
;
Gortler, Steven J.
;
Hoppe, Hugues
Connectivity Transformation for Mesh Metamorphosis
[meta data] [files:
Ahn, Minsu
;
Lee, Seungyong
;
Seidel, Hans-Peter
A data structure for non-manifold simplicial d-complexes
[meta data] [files:
Floriani, Leila De
;
Greenfieldboyce, David
;
Hui, Annie
Simplification and Improvement of Tetrahedral Models for Simulation
[meta data] [files:
Cutler, B.
;
Dorsey, J.
;
McMillan, L.
Symmetry Descriptors and 3D Shape Matching
[meta data] [files:
Kazhdan, Michael
;
Funkhouser, Thomas
;
Rusinkiewicz, Szymon
Lofting Curve Networks using Subdivision Surfaces
[meta data] [files:
Schaefer, S.
;
Warren, J.
;
Zorin, D.
Fast Collision Detection between Massive Models using Dynamic Simplification
[meta data] [files:
Yoon, Sung-Eui
;
Salomon, Brian
;
Lin, Ming
;
Manocha, Dinesh
Persistence Barcodes for Shapes
[meta data] [files:
Carlssony, Gunnar
;
Zomorodian, Afra
;
Collins, Anne
;
Guibas, Leonidas
Smooth Subdivision of Tetrahedral Meshes
[meta data] [files:
Schaefer, S.
;
Hakenberg, J.
;
Warren, J.
Differentiable Parameterization of Catmull-Clark Subdivision Surfaces
[meta data] [files:
Boier-Martin, Ioana
;
Zorin, Denis
Laplacian Surface Editing
[meta data] [files:
Sorkine, O.
;
Cohen-Or, D.
;
Lipman, Y.
;
Alexa, M.
;
Rössl, C.
;
Seidel, H.-P.
Parameterization of Triangle Meshes over Quadrilateral Domains
[meta data] [files:
Boier-Martin, Ioana
;
Rushmeier, Holly
;
Jin, Jingyi
A Remeshing Approach to Multiresolution Modeling
[meta data] [files:
Botsch, Mario
;
Kobbelt, Leif
Similarity-Based Surface Modelling Using Geodesic Fans
[meta data] [files:
Zelinka, Steve
;
Garland, Michael
Shape Segmentation Using Local Slippage Analysis
[meta data] [files:
Gelfand, Natasha
;
Guibas, Leonidas J.
Topology Preserving Surface Extraction Using Adaptive Subdivision
[meta data] [files:
Varadhan, Gokul
;
Krishnan, Shankar
;
Sriram, TVN
;
Manocha, Dinesh
Two Algorithms for Fast Reclustering of Dynamic Meshed Surfaces
[meta data] [files:
Carr, Nathan A.
;
Hart, John C.
Isotopic Approximation of Implicit Curves and Surfaces
[meta data] [files:
Plantinga, Simon
;
Vegter, Gert
Browse
Recent Submissions
Item Spectral Surface Reconstruction From Noisy Point Clouds(The Eurographics Association, 2004) Kolluri, Ravikrishna; Shewchuk, Jonathan Richard; O'Brien, James F.; Roberto Scopigno and Denis ZorinWe introduce a noise-resistant algorithm for reconstructing a watertight surface from point cloud data. It forms a Delaunay tetrahedralization, then uses a variant of spectral graph partitioning to decide whether each tetrahedron is inside or outside the original object. The reconstructed surface triangulation is the set of triangular faces where inside and outside tetrahedra meet. Because the spectral partitioner makes local decisions based on a global view of the model, it can ignore outliers, patch holes and undersampled regions, and surmount ambiguity due to measurement errors. Our algorithm can optionally produce a manifold surface. We present empirical evidence that our implementation is substantially more robust than several closely related surface reconstruction programs.Item Registration of Point Cloud Data from a Geometric Optimization Perspective(The Eurographics Association, 2004) Mitra, Niloy J.; Gelfand, Natasha; Pottmann, Helmut; Guibas, Leonidas; Roberto Scopigno and Denis ZorinWe propose a framework for pairwise registration of shapes represented by point cloud data (PCD). We assume that the points are sampled from a surface and formulate the problem of aligning two PCDs as a minimization of the squared distance between the underlying surfaces. Local quadratic approximants of the squared distance function are used to develop a linear system whose solution gives the best aligning rigid transform for the given pair of point clouds. The rigid transform is applied and the linear system corresponding to the new orientation is build. This process is iterated until it converges. The point-to-point and the point-to-plane Iterated Closest Point (ICP) algorithms can be treated as special cases in this framework. Our algorithm can align PCDs even when they are placed far apart, and is experimentally found to be more stable than point-to-plane ICP. We analyze the convergence behavior of our algorithm and of point-to-point and point-to-plane ICP under our proposed framework, and derive bounds on their rate of convergence. We compare the stability and convergence properties of our algorithm with other registration algorithms on a variety of scanned data.Item Comparing Point Clouds(The Eurographics Association, 2004) Mémoli, Facundo; Sapiro, Guillermo; Roberto Scopigno and Denis ZorinPoint clouds are one of the most primitive and fundamental surface representations. A popular source of point clouds are three dimensional shape acquisition devices such as laser range scanners. Another important field where point clouds are found is in the representation of high-dimensional manifolds by samples. With the increasing popularity and very broad applications of this source of data, it is natural and important to work directly with this representation, without having to go to the intermediate and sometimes impossible and distorting steps of surface reconstruction. A geometric framework for comparing manifolds given by point clouds is presented in this paper. The underlying theory is based on Gromov-Hausdorff distances, leading to isometry invariant and completely geometric comparisons. This theory is embedded in a probabilistic setting as derived from random sampling of manifolds, and then combined with results on matrices of pairwise geodesic distances to lead to a computational implementation of the framework. The theoretical and computational results here presented are complemented with experiments for real three dimensional shapes.Item Iso-charts: Stretch-driven Mesh Parameterization using Spectral Analysis(The Eurographics Association, 2004) Zhou, Kun; Synder, John; Guo, Baining; Shum, Heung-Yeung; Roberto Scopigno and Denis ZorinWe describe a fully automatic method, called iso-charts, to create texture atlases on arbitrary meshes. It is the first to consider stretch not only when parameterizing charts, but also when forming charts. The output atlas bounds stretch by a user-specified constant, allowing the user to balance the number of charts against their stretch. Our approach combines two seemingly incompatible techniques: stretch-minimizing parameterization, based on the surface integral of the trace of the local metric tensor, and the "isomap" or MDS (multi-dimensional scaling) parameterization, based on an eigen-analysis of the matrix of squared geodesic distances between pairs of mesh vertices. We show that only a few iterations of nonlinear stretch optimization need be applied to the MDS parameterization to obtain low-stretch atlases. The close relationship we discover between these two parameterizations also allows us to apply spectral clustering based on MDS to partition the mesh into charts having low stretch. We also novelly apply the graph cut algorithm in optimizing chart boundaries to further minimize stretch, follow sharp features, and avoid meandering. Overall, our algorithm creates texture atlases quickly, with fewer charts and lower stretch than previous methods, providing improvement in applications like geometric remeshing. We also describe an extension, signal-specialized atlas creation, to efficiently sample surface signals, and show for the first time that considering signal stretch in chart formation produces better texture maps.Item Geometric Texture Synthesis by Example(The Eurographics Association, 2004) Bhat, Pravin; Ingram, Stephen; Turk, Greg; Roberto Scopigno and Denis ZorinPatterns on real-world objects are often due to variations in geometry across the surface. Height fields and other common parametric methods cannot synthesize many forms of geometric surface texture such as thorns, scales, and bark. We present an example-based technique for synthesizing a variety of geometric textures on a model s surface. The applied textures can be from models specifically created for this purpose, or may be drawn from user-specified regions of an example model. We extend existing neighborhood-based texture synthesis algorithms to operate on volumetric models. Similar to image analogies [11], given a training pair of unfiltered and filtered source models and an unfiltered destination model (all volumetric grids), we synthesize a filtered fourth model that exhibits the desired geometric texture. The user defines vector fields to specify the direction of texture anisotropy on the source and destination models. The vector field defines a coordinate frame on the destination object s surface that is used to sample the voxel density values in the neighborhood near a given voxel, which then gives a feature vector that is matched to the neighborhoods in the source model. Destination voxels are visited in an order that is dictated by the vector field. We show geometric synthesis results on a variety of models using textures such as pits, grooves, thru-holes and thorns.Item Seamless Texture Atlases(The Eurographics Association, 2004) Purnomo, Budirijanto; Cohen, Jonathan D.; Kumar, Subodh; Roberto Scopigno and Denis ZorinTexture atlas parameterization provides an effective way to map a variety of color and data attributes from 2D texture domains onto polygonal surface meshes. However, the individual charts of such atlases are typically plagued by noticeable seams. We describe a new type of atlas which is seamless by construction. Our seamless atlas comprises all quadrilateral charts, and permits seamless texturing, as well as per-fragment down-sampling on rendering hardware and polygon simplification. We demonstrate the use of this atlas for capturing appearance attributes and producing seamless renderings.Item Signal-Specialized Parameterization for Piecewise Linear Reconstruction(The Eurographics Association, 2004) Tewari, Geetika; Snyder, John; Sander, Pedro V.; Gortler, Steven J.; Hoppe, Hugues; Roberto Scopigno and Denis ZorinWe propose a metric for surface parameterization specialized to its signal that can be used to create more efficient, high-quality texture maps. Derived from Taylor expansion of signal error, our metric predicts the signal approximation error - the difference between the original surface signal and its reconstruction from the sampled texture. Unlike previous methods, our metric assumes piecewise-linear reconstruction, and thus makes a good approximation to bilinear reconstruction employed in graphics hardware. We achieve significant savings in texture area for a desired signal accuracy compared to the signal-specialized parameterization metric proposed by Sander et al. in the 2002 Eurographics Workshop on Rendering.Item Connectivity Transformation for Mesh Metamorphosis(The Eurographics Association, 2004) Ahn, Minsu; Lee, Seungyong; Seidel, Hans-Peter; Roberto Scopigno and Denis ZorinIn previous mesh morphing techniques, the vertex set and connectivity of an in-between mesh are fixed and only the vertex positions are interpolated between input meshes. With this restriction, to accurately represent both source and target shapes, an in-between mesh should contain a much larger number of vertices than input meshes. This paper proposes a novel approach for mesh morphing, which includes connectivity changes in a metamorphosis. With the approach, an in-between mesh contains only the vertices from the input meshes and so the in-between vertex count does not exceed the sum of source and target vertex counts. The connectivity changes are realized by a sequence of edge swap operations, determined by considering the geometric errors from the input meshes. Experimental results demonstrate that the proposed approach generates almost same in-between shapes as the metamesh-based approach with a much smaller number of vertices.Item A data structure for non-manifold simplicial d-complexes(The Eurographics Association, 2004) Floriani, Leila De; Greenfieldboyce, David; Hui, Annie; Roberto Scopigno and Denis ZorinWe propose a data structure for d-dimensional simplicial complexes, that we call the Simplified Incidence Graph (SIG). The simplified incidence graph encodes all simplices of a simplicial complex together with a set of boundary and partial co-boundary topological relations. It is a dimension-independent data structure in the sense that it can represent objects of arbitrary dimensions. It scales well to the manifold case, i.e. it exhibits a small overhead when applied to simplicial complexes with a manifold domain. Here, we present efficient navigation algorithms for retrieving all topological relations from a SIG, and an algorithm for generating a SIG from a representation of the complex as an incidence graph. Finally, we compare the simplified incidence graph with the incidence graph, with a widely-used data structure for d-dimensional pseudo-manifold simplicial complexes, and with two data structures specific for two- and three-dimensional simplicial complexes.Item Simplification and Improvement of Tetrahedral Models for Simulation(The Eurographics Association, 2004) Cutler, B.; Dorsey, J.; McMillan, L.; Roberto Scopigno and Denis ZorinMost 3D mesh generation techniques require simplification and mesh improvement stages to prepare a tetrahedral model for efficient simulation. We have developed an algorithm that both reduces the number of tetrahedra in the model to permit interactive manipulation and removes the most poorly shaped tetrahedra to allow for stable physical simulations such as the finite element method. The initial tetrahedral model may be composed of several different materials representing internal structures. Our approach targets the elimination of poorly-shaped elements while simplifying the model using edge collapses and other mesh operations, such as vertex smoothing, tetrahedral swaps, and vertex addition. We present the results of our algorithm on a variety of inputs, including models with more than a million tetrahedra. In practice, our algorithm reliably reduces meshes to contain only tetrahedra that meet specified shape requirements, such as the minimum solid angle.Item Symmetry Descriptors and 3D Shape Matching(The Eurographics Association, 2004) Kazhdan, Michael; Funkhouser, Thomas; Rusinkiewicz, Szymon; Roberto Scopigno and Denis ZorinIn this paper, we present the Symmetry Descriptors of a 3D model. This is a collection of spherical functions that describes the measure of a model's rotational and reflective symmetry with respect to every axis passing through the center of mass. We show that Symmetry Descriptors can be computed efficiently using fast signal processing techniques, and demonstrate the empirical value of Symmetry Descriptors by showing that they improve matching performance in a variety of shape retrieval experiments.Item Lofting Curve Networks using Subdivision Surfaces(The Eurographics Association, 2004) Schaefer, S.; Warren, J.; Zorin, D.; Roberto Scopigno and Denis ZorinLofting 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.Item Fast Collision Detection between Massive Models using Dynamic Simplification(The Eurographics Association, 2004) Yoon, Sung-Eui; Salomon, Brian; Lin, Ming; Manocha, Dinesh; Roberto Scopigno and Denis ZorinWe present a novel approach for collision detection between large models composed of tens of millions of polygons. Each model is represented as a clustered hierarchy of progressive meshes (CHPM). The CHPM is a dual hierarchy of the original model; it serves both as a multiresolution representation of the original model, as well as a bounding volume hierarchy. We use the cluster hierarchy of a CHPM to perform coarse-grained selective refinement and the progressive meshes for fine-grained local refinement. We present a novel conservative error metric to perform collision queries based on the multiresolution representation. We use this error metric to perform dynamic simplification for collision detection. Our approach is conservative in that it may overestimate the set of colliding regions, but never misses any collisions. Furthermore, we are able to generate these hierarchies and perform collision queries using out-of-core techniques on all triangulated models. We have applied our algorithm to perform conservative collision detection between massive CAD and scanned models, consisting of millions of triangles at interactive rates on a commodity PC.Item Persistence Barcodes for Shapes(The Eurographics Association, 2004) Carlssony, Gunnar; Zomorodian, Afra; Collins, Anne; Guibas, Leonidas; Roberto Scopigno and Denis ZorinIn this paper, we initiate a study of shape description and classification via the application of persistent homology to two tangential constructions on geometric objects. Our techniques combine the differentiating power of geometry with the classifying power of topology. The homology of our first construction, the tangent complex, can distinguish between topologically identical shapes with different "sharp" features, such as corners. To capture "soft" curvature-dependent features, we define a second complex, the filtered tangent complex, obtained by parametrizing a family of increasing subcomplexes of the tangent complex. Applying persistent homology, we obtain a shape descriptor, called a barcode, that is a finite union of intervals. We define a metric over the space of such intervals, arriving at a continuous invariant that reflects the geometric properties of shapes. We illustrate the power of our methods through a number of detailed studies of parametrized families of mathematical shapes.Item Smooth Subdivision of Tetrahedral Meshes(The Eurographics Association, 2004) Schaefer, S.; Hakenberg, J.; Warren, J.; Roberto Scopigno and Denis ZorinWe describe a new subdivision scheme for unstructured tetrahedral meshes. Previous tetrahedral schemes based on generalizations of box splines have encoded arbitrary directional preferences in their associated subdivision rules that were not reflected in tetrahedral base mesh. Our method avoids this choice of preferred directions resulting a scheme that is simple to implement via repeated smoothing. In an extended appendix, we analyze this tetrahedral scheme and prove that the scheme generates C2 deformations everywhere except along edges of the tetrahedral base mesh. Along edges shared by four or more tetrahedra in the base mesh, we present strong evidence that the scheme generates C1 deformations.Item Second Order Smoothness over Extraordinary Vertices(The Eurographics Association, 2004) Loop, Charles; Roberto Scopigno and Denis ZorinCatmull & Clark subdivision is now a standard for smooth free-form surface modeling. These surfaces are everywhere curvature continuous except at points corresponding to vertices not incident on four edges. While the surface has a continuous tangent plane at such a point, the lack of curvature continuity presents a severe problem for many applications. Topologically, each n-valent extraordinary vertex of a Catmull & Clark limit surface corresponds to an n-sided hole in the underlying 2-manifold represented by the control mesh. The problem we address here is: How to fill such a hole in a Catmull & Clark surface with exactly n tensor product patches that meet the surrounding bicubic patch network and each other with second order continuity. We convert the problem of filling the hole with n tensor product patches in the spatial domain into the problem of filling the hole in the n frequency modes with a single bidegree 7 tensor product patch.Item Differentiable Parameterization of Catmull-Clark Subdivision Surfaces(The Eurographics Association, 2004) Boier-Martin, Ioana; Zorin, Denis; Roberto Scopigno and Denis ZorinSubdivision-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.Item Laplacian Surface Editing(The Eurographics Association, 2004) Sorkine, O.; Cohen-Or, D.; Lipman, Y.; Alexa, M.; Rössl, C.; Seidel, H.-P.; Roberto Scopigno and Denis ZorinSurface editing operations commonly require geometric details of the surface to be preserved as much as possible. We argue that geometric detail is an intrinsic property of a surface and that, consequently, surface editing is best performed by operating over an intrinsic surface representation. We provide such a representation of a surface, based on the Laplacian of the mesh, by encoding each vertex relative to its neighborhood. The Laplacian of the mesh is enhanced to be invariant to locally linearized rigid transformations and scaling. Based on this Laplacian representation, we develop useful editing operations: interactive free-form deformation in a region of interest based on the transformation of a handle, transfer and mixing of geometric details between two surfaces, and transplanting of a partial surface mesh onto another surface. The main computation involved in all operations is the solution of a sparse linear system, which can be done at interactive rates. We demonstrate the effectiveness of our approach in several examples, showing that the editing operations change the shape while respecting the structural geometric detail.Item Parameterization of Triangle Meshes over Quadrilateral Domains(The Eurographics Association, 2004) Boier-Martin, Ioana; Rushmeier, Holly; Jin, Jingyi; Roberto Scopigno and Denis ZorinWe present a method for parameterizing irregularly triangulated input models over polyhedral domains with quadrilateral faces. A combination of center-based clustering techniques is used to generate a partition of the model into regions suitable for remeshing. Several issues are addressed: the size and shape of the regions, their positioning with respect to features of the input geometry, and the amount of distortion introduced by approximating each region with a coarse polygon. Region boundaries are used to define a coarse polygonal mesh which is quadrangulated to obtain a parameterization domain. Constraints can be optionally imposed to enforce a strict correspondence between input and output features. We use the parameterization for multiresolution Catmull-Clark remeshing and we illustrate two applications that take advantage of the resulting representation: interactive model editing and texture mapping.Item A Remeshing Approach to Multiresolution Modeling(The Eurographics Association, 2004) Botsch, Mario; Kobbelt, Leif; Roberto Scopigno and Denis ZorinProviding a thorough mathematical foundation, multiresolution modeling is the standard approach for global surface deformations that preserve fine surface details in an intuitive and plausible manner. A given shape is decomposed into a smooth low-frequency base surface and high-frequency detail information. Adding these details back onto a deformed version of the base surface results in the desired modification. Using a suitable detail encoding, the connectivity of the base surface is not restricted to be the same as that of the original surface. We propose to exploit this degree of freedom to improve both robustness and efficiency of multiresolution shape editing. In several approaches the modified base surface is computed by solving a linear system of discretized Laplacians. By remeshing the base surface such that the Voronoi areas of its vertices are equalized, we turn the unsymmetric surface-related linear system into a symmetric one, such that simpler, more robust, and more efficient solvers can be applied. The high regularity of the remeshed base surface further removes numerical problems caused by mesh degeneracies and results in a better discretization of the Laplacian operator. The remeshing is performed on the low-frequency base surface only, while the connectivity of the original surface is kept fixed. Hence, this functionality can be encapsulated inside a multiresolution kernel and is thus completely hidden from the user.Item Similarity-Based Surface Modelling Using Geodesic Fans(The Eurographics Association, 2004) Zelinka, Steve; Garland, Michael; Roberto Scopigno and Denis ZorinWe present several powerful new techniques for similarity-based modelling of surfaces using geodesic fans, a new framework for local surface comparison. Similarity-based surface modelling provides intelligent surface manipulation by simultaneously applying a modification to all similar areas of the surface. We demonstrate similaritybased painting, deformation, and filtering of surfaces, and show how to vary our similarity measure to encompass geometry, textures, or other arbitrary signals. Geodesic fans are neighbourhoods uniformly sampled in the geodesic polar coordinates of a point on a surface. We show how geodesic fans offer fast approximate alignment and comparison of surface neighbourhoods using simple spoke reordering. As geodesic fans offer a a structurally equivalent definition of neighbourhoods everywhere on a surface, they are amenable to standard acceleration techniques and are well-suited to extending image domain methods for modelling by example to surfaces.Item Shape Segmentation Using Local Slippage Analysis(The Eurographics Association, 2004) Gelfand, Natasha; Guibas, Leonidas J.; Roberto Scopigno and Denis ZorinWe propose a method for segmentation of 3D scanned shapes into simple geometric parts. Given an input point cloud, our method computes a set of components which possess one or more slippable motions: rigid motions which, when applied to a shape, slide the transformed version against the stationary version without forming any gaps. Slippable shapes include rotationally and translationally symmetrical shapes such as planes, spheres, and cylinders, which are often found as components of scanned mechanical parts. We show how to determine the slippable motions of a given shape by computing eigenvalues of a certain symmetric matrix derived from the points and normals of the shape. Our algorithm then discovers slippable components in the input data by computing local slippage signatures at a set of points of the input and iteratively aggregating regions with matching slippable motions. We demonstrate the performance of our algorithm for reverse engineering surfaces of mechanical parts.Item Topology Preserving Surface Extraction Using Adaptive Subdivision(The Eurographics Association, 2004) Varadhan, Gokul; Krishnan, Shankar; Sriram, TVN; Manocha, Dinesh; Roberto Scopigno and Denis ZorinWe address the problem of computing a topology preserving isosurface from a volumetric grid using Marching Cubes for geometry processing applications. We present a novel topology preserving subdivision algorithm to generate an adaptive volumetric grid. Our algorithm ensures that every grid cell satisfies two local geometric criteria: a complex cell criterion and a star-shaped criterion. We show that these two criteria are sufficient to ensure that the surface extracted from the grid using Marching Cubes has the same genus and connectedness as that of the exact isosurface. We use our subdivision algorithm for accurate boundary evaluation of CSG combinations of polyhedra and low degree algebraic primitives, translational motion planning, model simplification and remeshing. The running time of our algorithm varies between a few seconds for simple models composed of a few thousand triangles to tens of seconds for complex polyhedral models represented using hundreds of thousands of triangles.Item Two Algorithms for Fast Reclustering of Dynamic Meshed Surfaces(The Eurographics Association, 2004) Carr, Nathan A.; Hart, John C.; Roberto Scopigno and Denis ZorinNumerous mesh algorithms such as parametrization, radiosity, and collision detection require the decomposition of meshes into a series of clusters. In this paper we present two novel approaches for maintaining mesh clusterings on dynamically deforming meshes. The first approach maintains a complete face cluster tree hierarchy using a randomized data structure. The second algorithm maintains a mesh decomposition for a fixed set of clusters. With both algorithms we are able to maintain clusterings on dynamically deforming surfaces of over 100K faces in fractions of a second.Item Isotopic Approximation of Implicit Curves and Surfaces(The Eurographics Association, 2004) Plantinga, Simon; Vegter, Gert; Roberto Scopigno and Denis ZorinImplicit surfaces are defined as the zero set of a function F : R<sup>3</sup>-> R. Although several algorithms exist for generating piecewise linear approximations, most of them are based on a user-defined stepsize or bounds to indicate the precision, and therefore cannot guarantee topological correctness. Interval arithmetic provides a mechanism to determine global properties of the implicit function. In this paper we present an algorithm that uses these properties to generate a piecewise linear approximation of implicit curves and surfaces, that is isotopic to the curve or surface itself. The algorithm is simple and fast, and is among the first to guarantee isotopy for implicit surface meshing.