27-Issue 5

Permanent URI for this collection

Geometry Processing Proceedings

BibTeX (27-Issue 5)
                
@article{
-,
journal = {Computer Graphics Forum}, title = {{
Preface, Table of Contents, Cover}},
author = {}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing, Inc},
ISSN = {1467-8659},
DOI = {
-}
}
                
@article{
10.1111:j.1467-8659.2008.01271.x,
journal = {Computer Graphics Forum}, title = {{
Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection}},
author = {
Attene, Marco
and
Mortara, Michela
and
Spagnuolo, Michela
and
Falcidieno, Bianca
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01271.x}
}
                
@article{
10.1111:j.1467-8659.2008.01272.x,
journal = {Computer Graphics Forum}, title = {{
Discrete Distortion in Triangulated 3-Manifolds}},
author = {
Mesmoudi, Mohammed Mostefa
and
De Floriani, Leila
and
Port, Umberto
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01272.x}
}
                
@article{
10.1111:j.1467-8659.2008.01274.x,
journal = {Computer Graphics Forum}, title = {{
A Hierarchical Segmentation of Articulated Bodies}},
author = {
De Goes, Fernando
and
Goldenstein, Siome
and
Velho, Luiz
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01274.x}
}
                
@article{
10.1111:j.1467-8659.2008.01273.x,
journal = {Computer Graphics Forum}, title = {{
Global Intrinsic Symmetries of Shapes}},
author = {
Ovsjanikov, Maks
and
Sun, Jian
and
Guibas, Leonidas
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01273.x}
}
                
@article{
10.1111:j.1467-8659.2008.01275.x,
journal = {Computer Graphics Forum}, title = {{
A smart stochastic approach for manifolds smoothing}},
author = {
El Ouafdi, A.F.
and
Ziou, D.
and
Krim, H.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01275.x}
}
                
@article{
10.1111:j.1467-8659.2008.01278.x,
journal = {Computer Graphics Forum}, title = {{
Fitting Sharp Features with Loop Subdivision Surfaces}},
author = {
Ling, Ruotian
and
Wang, Wenping
and
Yan, Dongming
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01278.x}
}
                
@article{
10.1111:j.1467-8659.2008.01277.x,
journal = {Computer Graphics Forum}, title = {{
G2 Tensor Product Splines over Extraordinary Vertices}},
author = {
Loop, Charles
and
Schaefer, Scott
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01277.x}
}
                
@article{
10.1111:j.1467-8659.2008.01276.x,
journal = {Computer Graphics Forum}, title = {{
Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets}},
author = {
Myles, A.
and
Ni, T.
and
Peters, J.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01276.x}
}
                
@article{
10.1111:j.1467-8659.2008.01281.x,
journal = {Computer Graphics Forum}, title = {{
Streaming Surface Reconstruction Using Wavelets}},
author = {
Manson, J.
and
Petrova, G.
and
Schaefer, S.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01281.x}
}
                
@article{
10.1111:j.1467-8659.2008.01280.x,
journal = {Computer Graphics Forum}, title = {{
Provably Good 2D Shape Reconstruction from Unorganized Cross-Sections}},
author = {
Memari, Pooran
and
Boissonnat, Jean-Daniel
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01280.x}
}
                
@article{
10.1111:j.1467-8659.2008.01279.x,
journal = {Computer Graphics Forum}, title = {{
Surface sampling and the intrinsic Voronoi diagram}},
author = {
Dyer, Ramsay
and
Zhang, Hao
and
Moeller, Torsten
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01279.x}
}
                
@article{
10.1111:j.1467-8659.2008.01282.x,
journal = {Computer Graphics Forum}, title = {{
Global Correspondence Optimization for Non-Rigid Registration of Depth Scans}},
author = {
Li, Hao
and
Sumner, Robert W.
and
Pauly, Mark
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01282.x}
}
                
@article{
10.1111:j.1467-8659.2008.01283.x,
journal = {Computer Graphics Forum}, title = {{
Deformation-Driven Shape Correspondence}},
author = {
Zhang, H.
and
Sheffer, A.
and
Cohen-Or, D.
and
Zhou, Q.
and
Van Kaick, O.
and
Tagliasacchi, A.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01283.x}
}
                
@article{
10.1111:j.1467-8659.2008.01286.x,
journal = {Computer Graphics Forum}, title = {{
Automatic Registration for Articulated Shapes}},
author = {
Chang, Will
and
Zwicker, Matthias
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01286.x}
}
                
@article{
10.1111:j.1467-8659.2008.01284.x,
journal = {Computer Graphics Forum}, title = {{
Dental Inlay and Onlay Construction by Iterative Laplacian Surface Editing}},
author = {
Steinbrecher, Tillmann
and
Gerth, Maik
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01284.x}
}
                
@article{
10.1111:j.1467-8659.2008.01285.x,
journal = {Computer Graphics Forum}, title = {{
Non-Rigid Registration Under Isometric Deformations}},
author = {
Huang, Qi-Xing
and
Adams, Bart
and
Wicke, Martin
and
Guibas, Leonidas J.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01285.x}
}
                
@article{
10.1111:j.1467-8659.2008.01287.x,
journal = {Computer Graphics Forum}, title = {{
Reconstructing Animated Meshes from Time-Varying Point Clouds}},
author = {
Suessmuth, Jochen
and
Winter, Marco
and
Greiner, Guenther
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01287.x}
}
                
@article{
10.1111:j.1467-8659.2008.01288.x,
journal = {Computer Graphics Forum}, title = {{
Motorcycle Graphs: Canonical Quad Mesh Partitioning}},
author = {
Eppstein, David
and
Goodrich, Michael T.
and
Kim, Ethan
and
Tamstorf, Rasmus
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01288.x}
}
                
@article{
10.1111:j.1467-8659.2008.01289.x,
journal = {Computer Graphics Forum}, title = {{
Spectral Conformal Parameterization}},
author = {
Mullen, Patrick
and
Tong, Yiying
and
Alliez, Pierre
and
Desbrun, Mathieu
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01289.x}
}
                
@article{
10.1111:j.1467-8659.2008.01290.x,
journal = {Computer Graphics Forum}, title = {{
A Local/Global Approach to Mesh Parameterization}},
author = {
Liu, Ligang
and
Zhang, Lei
and
Xu, Yin
and
Gotsman, Craig
and
Gortler, Steven J.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01290.x}
}
                
@article{
10.1111:j.1467-8659.2008.01292.x,
journal = {Computer Graphics Forum}, title = {{
Maximum Entropy Coordinates for Arbitrary Polytopes}},
author = {
Hormann, K.
and
Sukumar, N.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01292.x}
}
                
@article{
10.1111:j.1467-8659.2008.01291.x,
journal = {Computer Graphics Forum}, title = {{
Pointwise radial minimization: Hermite interpolation on arbitrary domains}},
author = {
Floater, M. S.
and
Schulz, C.
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01291.x}
}
                
@article{
10.1111:j.1467-8659.2008.01293.x,
journal = {Computer Graphics Forum}, title = {{
Polyhedral Finite Elements Using Harmonic Basis Functions}},
author = {
Martin, Sebastian
and
Kaufmann, Peter
and
Botsch, Mario
and
Wicke, Martin
and
Gross, Markus
}, year = {
2008},
publisher = {
The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {
10.1111/j.1467-8659.2008.01293.x}
}

Browse

Recent Submissions

Now showing 1 - 24 of 24
  • 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, Bianca
    Given 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, Umberto
    We 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 Hierarchical Segmentation of Articulated Bodies
    (The Eurographics Association and Blackwell Publishing Ltd, 2008) De Goes, Fernando; Goldenstein, Siome; Velho, Luiz
    This 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, Leonidas
    Although 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
    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
    Fitting Sharp Features with Loop Subdivision Surfaces
    (The Eurographics Association and Blackwell Publishing Ltd, 2008) Ling, Ruotian; Wang, Wenping; Yan, Dongming
    Various 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
    G2 Tensor Product Splines over Extraordinary Vertices
    (The Eurographics Association and Blackwell Publishing Ltd, 2008) Loop, Charles; Schaefer, Scott
    We 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
    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-Daniel
    This 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, Torsten
    We 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, Mark
    We 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, Matthias
    We 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, Maik
    We 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, Guenther
    In 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, Rasmus
    We 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, Mathieu
    We 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, Markus
    Finite 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.