SGP04: Eurographics Symposium on Geometry Processing
https://diglib.eg.org:443/handle/10.2312/443
2019-06-20T15:24:43ZTopology Preserving Surface Extraction Using Adaptive Subdivision
https://diglib.eg.org:443/handle/10.2312/SGP.SGP04.241-250
Topology Preserving Surface Extraction Using Adaptive Subdivision
Varadhan, Gokul; Krishnan, Shankar; Sriram, TVN; Manocha, Dinesh
Roberto Scopigno and Denis Zorin
We 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.
2004-01-01T00:00:00ZIsotopic Approximation of Implicit Curves and Surfaces
https://diglib.eg.org:443/handle/10.2312/SGP.SGP04.251-260
Isotopic Approximation of Implicit Curves and Surfaces
Plantinga, Simon; Vegter, Gert
Roberto Scopigno and Denis Zorin
Implicit 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.
2004-01-01T00:00:00ZTwo Algorithms for Fast Reclustering of Dynamic Meshed Surfaces
https://diglib.eg.org:443/handle/10.2312/SGP.SGP04.229-240
Two Algorithms for Fast Reclustering of Dynamic Meshed Surfaces
Carr, Nathan A.; Hart, John C.
Roberto Scopigno and Denis Zorin
Numerous 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.
2004-01-01T00:00:00ZShape Segmentation Using Local Slippage Analysis
https://diglib.eg.org:443/handle/10.2312/SGP.SGP04.219-228
Shape Segmentation Using Local Slippage Analysis
Gelfand, Natasha; Guibas, Leonidas J.
Roberto Scopigno and Denis Zorin
We 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.
2004-01-01T00:00:00Z