SGP04: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/443

Browse

Now showing 1 - 20 of 25

Comparing Point Clouds
(The Eurographics Association, 2004) Mémoli, Facundo; Sapiro, Guillermo; Roberto Scopigno and Denis Zorin
Point 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.
Connectivity Transformation for Mesh Metamorphosis
(The Eurographics Association, 2004) Ahn, Minsu; Lee, Seungyong; Seidel, Hans-Peter; Roberto Scopigno and Denis Zorin
In 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.
A data structure for non-manifold simplicial d-complexes
(The Eurographics Association, 2004) Floriani, Leila De; Greenfieldboyce, David; Hui, Annie; Roberto Scopigno and Denis Zorin
We 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.
Differentiable Parameterization of Catmull-Clark Subdivision Surfaces
(The Eurographics Association, 2004) Boier-Martin, Ioana; Zorin, Denis; Roberto Scopigno and Denis Zorin
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.
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 Zorin
We 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.
Geometric Texture Synthesis by Example
(The Eurographics Association, 2004) Bhat, Pravin; Ingram, Stephen; Turk, Greg; Roberto Scopigno and Denis Zorin
Patterns 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.
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 Zorin
We 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.
Isotopic Approximation of Implicit Curves and Surfaces
(The Eurographics Association, 2004) 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.
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 Zorin
Surface 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.
Lofting Curve Networks using Subdivision Surfaces
(The Eurographics Association, 2004) Schaefer, S.; Warren, J.; Zorin, D.; Roberto Scopigno and Denis Zorin
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.
Parameterization of Triangle Meshes over Quadrilateral Domains
(The Eurographics Association, 2004) Boier-Martin, Ioana; Rushmeier, Holly; Jin, Jingyi; Roberto Scopigno and Denis Zorin
We 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.
Persistence Barcodes for Shapes
(The Eurographics Association, 2004) Carlssony, Gunnar; Zomorodian, Afra; Collins, Anne; Guibas, Leonidas; Roberto Scopigno and Denis Zorin
In 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.
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 Zorin
We 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.
A Remeshing Approach to Multiresolution Modeling
(The Eurographics Association, 2004) Botsch, Mario; Kobbelt, Leif; Roberto Scopigno and Denis Zorin
Providing 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.
Seamless Texture Atlases
(The Eurographics Association, 2004) Purnomo, Budirijanto; Cohen, Jonathan D.; Kumar, Subodh; Roberto Scopigno and Denis Zorin
Texture 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.
Second Order Smoothness over Extraordinary Vertices
(The Eurographics Association, 2004) Loop, Charles; Roberto Scopigno and Denis Zorin
Catmull & 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.
Shape Segmentation Using Local Slippage Analysis
(The Eurographics Association, 2004) 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.
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 Zorin
We 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.
Similarity-Based Surface Modelling Using Geodesic Fans
(The Eurographics Association, 2004) Zelinka, Steve; Garland, Michael; Roberto Scopigno and Denis Zorin
We 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.
Simplification and Improvement of Tetrahedral Models for Simulation
(The Eurographics Association, 2004) Cutler, B.; Dorsey, J.; McMillan, L.; Roberto Scopigno and Denis Zorin
Most 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.

Browse

Browsing SGP04: Eurographics Symposium on Geometry Processing by Title

Results Per Page

Sort Options