SGP08: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection
[meta data] [files:
Attene, Marco
;
Mortara, Michela
;
Spagnuolo, Michela
;
Falcidieno, Bianca
Discrete Distortion in Triangulated 3-Manifolds
[meta data] [files:
Mesmoudi, Mohammed Mostefa
;
De Floriani, Leila
;
Port, Umberto
A smart stochastic approach for manifolds smoothing
[meta data] [files:
El Ouafdi, A.F.
;
Ziou, D.
;
Krim, H.
A Hierarchical Segmentation of Articulated Bodies
[meta data] [files:
De Goes, Fernando
;
Goldenstein, Siome
;
Velho, Luiz
Global Intrinsic Symmetries of Shapes
[meta data] [files:
Ovsjanikov, Maks
;
Sun, Jian
;
Guibas, Leonidas
G2 Tensor Product Splines over Extraordinary Vertices
[meta data] [files:
Loop, Charles
;
Schaefer, Scott
Fitting Sharp Features with Loop Subdivision Surfaces
[meta data] [files:
Ling, Ruotian
;
Wang, Wenping
;
Yan, Dongming
Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets
[meta data] [files:
Myles, A.
;
Ni, T.
;
Peters, J.
Streaming Surface Reconstruction Using Wavelets
[meta data] [files:
Manson, J.
;
Petrova, G.
;
Schaefer, S.
Provably Good 2D Shape Reconstruction from Unorganized Cross-Sections
[meta data] [files:
Memari, Pooran
;
Boissonnat, Jean-Daniel
Surface sampling and the intrinsic Voronoi diagram
[meta data] [files:
Dyer, Ramsay
;
Zhang, Hao
;
Moeller, Torsten
Global Correspondence Optimization for Non-Rigid Registration of Depth Scans
[meta data] [files:
Li, Hao
;
Sumner, Robert W.
;
Pauly, Mark
Deformation-Driven Shape Correspondence
[meta data] [files:
Zhang, H.
;
Sheffer, A.
;
Cohen-Or, D.
;
Zhou, Q.
;
Van Kaick, O.
;
Tagliasacchi, A.
Dental Inlay and Onlay Construction by Iterative Laplacian Surface Editing
[meta data] [files:
Steinbrecher, Tillmann
;
Gerth, Maik
Non-Rigid Registration Under Isometric Deformations
[meta data] [files:
Huang, Qi-Xing
;
Adams, Bart
;
Wicke, Martin
;
Guibas, Leonidas J.
Reconstructing Animated Meshes from Time-Varying Point Clouds
[meta data] [files:
Suessmuth, Jochen
;
Winter, Marco
;
Greiner, Guenther
Motorcycle Graphs: Canonical Quad Mesh Partitioning
[meta data] [files:
Eppstein, David
;
Goodrich, Michael T.
;
Kim, Ethan
;
Tamstorf, Rasmus
Spectral Conformal Parameterization
[meta data] [files:
Mullen, Patrick
;
Tong, Yiying
;
Alliez, Pierre
;
Desbrun, Mathieu
A Local/Global Approach to Mesh Parameterization
[meta data] [files:
Liu, Ligang
;
Zhang, Lei
;
Xu, Yin
;
Gotsman, Craig
;
Gortler, Steven J.
Pointwise radial minimization: Hermite interpolation on arbitrary domains
[meta data] [files:
Floater, M. S.
;
Schulz, C.
Polyhedral Finite Elements Using Harmonic Basis Functions
[meta data] [files:
Martin, Sebastian
;
Kaufmann, Peter
;
Botsch, Mario
;
Wicke, Martin
;
Gross, Markus
Browse
Recent Submissions
Item Preface, Table of Contents, Cover(The Eurographics Association and Blackwell Publishing, Inc, 2008)Item Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection(The Eurographics Association and Blackwell Publishing Ltd, 2008) Attene, Marco; Mortara, Michela; Spagnuolo, Michela; Falcidieno, BiancaGiven a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom-up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log2 n) operations are sufficient to compute the whole tree.Item Discrete Distortion in Triangulated 3-Manifolds(The Eurographics Association and Blackwell Publishing Ltd, 2008) Mesmoudi, Mohammed Mostefa; De Floriani, Leila; Port, UmbertoWe introduce a novel notion, that we call discrete distortion, for a triangulated 3-manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3-manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3-manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R4 defined by a scalar field on a 3D mesh. distance fields.Item A smart stochastic approach for manifolds smoothing(The Eurographics Association and Blackwell Publishing Ltd, 2008) El Ouafdi, A.F.; Ziou, D.; Krim, H.In this paper, we present a probabilistic approach for 3D object s smoothing. The core idea behind the proposed method is to relate the problem of smoothing objects to that of tracking the transition probability density functions of an underlying random process. We show that such an approach allows for additional insight and sufficient flexibility compared with existing standard smoothing techniques. In particular, we are able to propose a newer, faster, and simpler smoothing approach that retains and enhances important manifold features. Furthermore, it is demonstrated to improve performance over existing smoothing techniques.Item A Hierarchical Segmentation of Articulated Bodies(The Eurographics Association and Blackwell Publishing Ltd, 2008) De Goes, Fernando; Goldenstein, Siome; Velho, LuizThis paper presents a novel segmentation method to assist the rigging of articulated bodies. The method computes a coarse-to-fine hierarchy of segments ordered by the level of detail. The results are invariant to deformations, and numerically robust to noise, irregular tessellations, and topological short-circuits. The segmentation is based on two key ideas. First, it exploits the multiscale properties of the diffusion distance on surfaces, and then it introduces a new definition of medial structures, composing a bijection between medial structures and segments. Our method computes this bijection through a simple and fast iterative approach, and applies it to triangulated meshes.Item Global Intrinsic Symmetries of Shapes(The Eurographics Association and Blackwell Publishing Ltd, 2008) Ovsjanikov, Maks; Sun, Jian; Guibas, LeonidasAlthough considerable attention in recent years has been given to the problem of symmetry detection in general shapes, few methods have been developed that aim to detect and quantify the intrinsic symmetry of a shape rather than its extrinsic, or pose-dependent symmetry. In this paper, we present a novel approach for efficiently computing symmetries of a shape which are invariant up to isometry preserving transformations. We show that the intrinsic symmetries of a shape are transformed into the Euclidean symmetries in the signature space defined by the eigenfunctions of the Laplace-Beltrami operator. Based on this observation, we devise an algorithm which detects and computes the isometric mappings from the shape onto itself. We show that our approach is both computationally efficient and robust with respect to small non-isometric deformations, even if they include topological changes.Item G2 Tensor Product Splines over Extraordinary Vertices(The Eurographics Association and Blackwell Publishing Ltd, 2008) Loop, Charles; Schaefer, ScottWe present a second order smooth filling of an n-valent Catmull-Clark spline ring with n biseptic patches. While an underdetermined biseptic solution to this problem has appeared previously, we make several advances in this paper. Most notably, we cast the problem as a constrained minimization and introduce a novel quadratic energy functional whose absolute minimum of zero is achieved for bicubic polynomials. This means that for the regular 4-valent case, we reproduce the bicubic B-splines. In other cases, the resulting surfaces are aesthetically well behaved. We extend our constrained minimization framework to handle the case of input mesh with boundary.Item Fitting Sharp Features with Loop Subdivision Surfaces(The Eurographics Association and Blackwell Publishing Ltd, 2008) Ling, Ruotian; Wang, Wenping; Yan, DongmingVarious methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.Item Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets(The Eurographics Association and Blackwell Publishing Ltd, 2008) Myles, A.; Ni, T.; Peters, J.Item Streaming Surface Reconstruction Using Wavelets(The Eurographics Association and Blackwell Publishing Ltd, 2008) Manson, J.; Petrova, G.; Schaefer, S.We present a streaming method for reconstructing surfaces from large data sets generated by a laser range scanner using wavelets. Wavelets provide a localized, multiresolution representation of functions and this makes them ideal candidates for streaming surface reconstruction algorithms. We show how wavelets can be used to reconstruct the indicator function of a shape from a cloud of points with associated normals. Our method proceeds in several steps. We first compute a low-resolution approximation of the indicator function using an octree followed by a second pass that incrementally adds fine resolution details. The indicator function is then smoothed using a modified octree convolution step and contoured to produce the final surface. Due to the local, multiresolution nature of wavelets, our approach results in an algorithm over 10 times faster than previous methods and can process extremely large data sets in the order of several hundred million points in only an hour.Item Provably Good 2D Shape Reconstruction from Unorganized Cross-Sections(The Eurographics Association and Blackwell Publishing Ltd, 2008) Memari, Pooran; Boissonnat, Jean-DanielThis paper deals with the reconstruction of 2-dimensional geometric shapes from unorganized 1-dimensional cross-sections. We study the problem in its full generality following the approach of Boissonnat and Memari [BM07] for the analogous 3D problem. We propose a new variant of this method and provide sampling conditions to guarantee that the output of the algorithm has the same topology as the original object and is close to it (for the Hausdorff distance).Item Surface sampling and the intrinsic Voronoi diagram(The Eurographics Association and Blackwell Publishing Ltd, 2008) Dyer, Ramsay; Zhang, Hao; Moeller, TorstenWe develop adaptive sampling criteria which guarantee a topologically faithful mesh and demonstrate an improvement and simplification over earlier results, albeit restricted to 2D surfaces. These sampling criteria are based on functions defined by intrinsic properties of the surface: the strong convexity radius and the injectivity radius. We establish inequalities that relate these functions to the local feature size, thus enabling a comparison between the demands of the intrinsic sampling criteria and those based on Euclidean distances and the medial axis.Item Global Correspondence Optimization for Non-Rigid Registration of Depth Scans(The Eurographics Association and Blackwell Publishing Ltd, 2008) Li, Hao; Sumner, Robert W.; Pauly, MarkWe present a registration algorithm for pairs of deforming and partial range scans that addresses the challenges of non-rigid registration within a single non-linear optimization. Our algorithm simultaneously solves for correspondences between points on source and target scans, confidence weights that measure the reliability of each correspondence and identify non-overlapping areas, and a warping field that brings the source scan into alignment with the target geometry. The optimization maximizes the region of overlap and the spatial coherence of the deformation while minimizing registration error. All optimization parameters are chosen automatically; hand-tuning is not necessary. Our method is not restricted to part-in-whole matching, but addresses the general problem of partial matching, and requires no explicit prior correspondences or feature points. We evaluate the performance and robustness of our method using scan data acquired by a structured light scanner and compare our method with existing non-rigid registration algorithms.Item Deformation-Driven Shape Correspondence(The Eurographics Association and Blackwell Publishing Ltd, 2008) Zhang, H.; Sheffer, A.; Cohen-Or, D.; Zhou, Q.; Van Kaick, O.; Tagliasacchi, A.Non-rigid 3D shape correspondence is a fundamental and difficult problem. Most applications which require a correspondence rely on manually selected markers. Without user assistance, the performances of existing automatic correspondence methods depend strongly on a good initial shape alignment or shape prior, and they generally do not tolerate large shape variations. We present an automatic feature correspondence algorithm capable of handling large, non-rigid shape variations, as well as partial matching. This is made possible by leveraging the power of state-of-the-art mesh deformation techniques and relying on a combinatorial tree traversal for correspondence search. The search is deformation-driven, prioritized by a self-distortion energy measured on meshes deformed according to a given correspondence. We demonstrate the ability of our approach to naturally match shapes which differ in pose, local scale, part decomposition, and geometric detail through numerous examples.Item Automatic Registration for Articulated Shapes(The Eurographics Association and Blackwell Publishing Ltd, 2008) Chang, Will; Zwicker, MatthiasWe present an unsupervised algorithm for aligning a pair of shapes in the presence of significant articulated motion and missing data, while assuming no knowledge of a template, user-placed markers, segmentation, or the skeletal structure of the shape. We explicitly sample the motion, which gives a priori the set of possible rigid transformations between parts of the shapes. This transforms the problem into a discrete labeling problem, where the goal is to find an optimal assignment of transformations for aligning the shapes. We then apply graph cuts to optimize a novel cost function, which encodes a preference for a consistent motion assignment from both source to target and target to source. We demonstrate the robustness of our method by aligning several synthetic and real-world datasets.Item Dental Inlay and Onlay Construction by Iterative Laplacian Surface Editing(The Eurographics Association and Blackwell Publishing Ltd, 2008) Steinbrecher, Tillmann; Gerth, MaikWe propose a new method for automatic construction of inlays and onlays. Mesh models from a small tooth library are adapted to the remaining healthy surface of the patient s tooth. In the area above the cavity, the general morphology of the model tooth (fissures, cusp tips, etc) is preserved, but precisely adjusted to the intra-oral situation. Our approach uses iterative Laplacian Surface Editing to deform the model tooth. This allows the automatic generation of highly individual, functional and anatomically correct inlays/onlays, without having to resort to a large library of different tooth shapes.Item Non-Rigid Registration Under Isometric Deformations(The Eurographics Association and Blackwell Publishing Ltd, 2008) Huang, Qi-Xing; Adams, Bart; Wicke, Martin; Guibas, Leonidas J.We present a robust and efficient algorithm for the pairwise non-rigid registration of partially overlapping 3D surfaces. Our approach treats non-rigid registration as an optimization problem and solves it by alternating between correspondence and deformation optimization. Assuming approximately isometric deformations, robust correspondences are generated using a pruning mechanism based on geodesic consistency. We iteratively learn an appropriate deformation discretization from the current set of correspondences and use it to update the correspondences in the next iteration. Our algorithm is able to register partially similar point clouds that undergo large deformations, in just a few seconds. We demonstrate the potential of our algorithm in various applications such as example based articulated segmentation, and shape interpolation.Item Reconstructing Animated Meshes from Time-Varying Point Clouds(The Eurographics Association and Blackwell Publishing Ltd, 2008) Suessmuth, Jochen; Winter, Marco; Greiner, GuentherIn this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time-deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3-D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in R?4 that approximates the time-space surface of the time-varying point cloud. We then use the four-dimensional implicit function to reconstruct a polygonal model for the first time-step. By sliding this template mesh along the time-space surface in an as-rigid-as-possible manner, we obtain reconstructions for further time-steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly.The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real-time 3-D scanners.Item Motorcycle Graphs: Canonical Quad Mesh Partitioning(The Eurographics Association and Blackwell Publishing Ltd, 2008) Eppstein, David; Goodrich, Michael T.; Kim, Ethan; Tamstorf, RasmusWe describe algorithms for canonically partitioning semi-regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions-we prove that optimizing this number is NP-hard, but it can be efficiently approximated.Item Spectral Conformal Parameterization(The Eurographics Association and Blackwell Publishing Ltd, 2008) Mullen, Patrick; Tong, Yiying; Alliez, Pierre; Desbrun, MathieuWe present a spectral approach to automatically and efficiently obtain discrete free-boundary conformal parameterizations of triangle mesh patches, without the common artifacts due to positional constraints on vertices and without undue bias introduced by sampling irregularity. High-quality parameterizations are computed through a constrained minimization of a discrete weighted conformal energy by finding the largest eigenvalue/eigenvector of a generalized eigenvalue problem involving sparse, symmetric matrices. We demonstrate that this novel and robust approach improves on previous linear techniques both quantitatively and qualitatively.Item A Local/Global Approach to Mesh Parameterization(The Eurographics Association and Blackwell Publishing Ltd, 2008) Liu, Ligang; Zhang, Lei; Xu, Yin; Gotsman, Craig; Gortler, Steven J.We present a novel approach to parameterize a mesh with disk topology to the plane in a shape-preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global stitch operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as-similar-as-possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as-rigid-as-possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre-factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape-preserving results than other state-of-the-art approaches.We present also a more general hybrid parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.Item Maximum Entropy Coordinates for Arbitrary Polytopes(The Eurographics Association and Blackwell Publishing Ltd, 2008) Hormann, K.; Sukumar, N.Barycentric coordinates can be used to express any point inside a triangle as a unique convex combination of the triangle s vertices, and they provide a convenient way to linearly interpolate data that is given at the vertices of a triangle. In recent years, the ideas of barycentric coordinates and barycentric interpolation have been extended to arbitrary polygons in the plane and general polytopes in higher dimensions, which in turn has led to novel solutions in applications like mesh parameterization, image warping, and mesh deformation. In this paper we introduce a new generalization of barycentric coordinates that stems from the maximum entropy principle. The coordinates are guaranteed to be positive inside any planar polygon, can be evaluated efficiently by solving a convex optimization problem with Newton s method, and experimental evidence indicates that they are smooth inside the domain. Moreover, the construction of these coordinates can be extended to arbitrary polyhedra and higher-dimensional polytopes.Item Pointwise radial minimization: Hermite interpolation on arbitrary domains(The Eurographics Association and Blackwell Publishing Ltd, 2008) Floater, M. S.; Schulz, C.In this paper we propose a new kind of Hermite interpolation on arbitrary domains, matching derivative data of arbitrary order on the boundary. The basic idea stems from an interpretation of mean value interpolation as the pointwise minimization of a radial energy function involving first derivatives of linear polynomials. We generalize this and minimize over derivatives of polynomials of arbitrary odd degree. We analyze the cubic case, which assumes first derivative boundary data and show that the minimization has a unique, infinitely smooth solution with cubic precision. We have not been able to prove that the solution satisfies the Hermite interpolation conditions but numerical examples strongly indicate that it does for a wide variety of planar domains and that it behaves nicely.Item Polyhedral Finite Elements Using Harmonic Basis Functions(The Eurographics Association and Blackwell Publishing Ltd, 2008) Martin, Sebastian; Kaufmann, Peter; Botsch, Mario; Wicke, Martin; Gross, MarkusFinite element simulations in computer graphics are typically based on tetrahedral or hexahedral elements, which enables simple and efficient implementations, but in turn requires complicated remeshing in case of topological changes or adaptive refinement. We propose a flexible finite element method for arbitrary polyhedral elements, thereby effectively avoiding the need for remeshing. Our polyhedral finite elements are based on harmonic basis functions, which satisfy all necessary conditions for FEM simulations and seamlessly generalize both linear tetrahedral and trilinear hexahedral elements. We discretize harmonic basis functions using the method of fundamental solutions, which enables their flexible computation and efficient evaluation. The versatility of our approach is demonstrated on cutting and adaptive refinement within a simulation framework for corotated linear elasticity.