30-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/165
Geometry Processing Proceedings

BibTeX (30-Issue 5)
                
@article{
https::/diglib.eg.org/handle/10.1111/000_frontmatter_sgp2011,
-,

journal = {Computer Graphics Forum},
title = {{
Preface and Table of Contents}},

author = {},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
https://diglib.eg.org/handle/10.1111/000_frontmatter_sgp2011}
-}

}
                
@article{
10.1111:j.1467-8659.2011.02011.x,

journal = {Computer Graphics Forum},
title = {{
Functional Webs for Freeform Architecture}},

author = {
Deng, B.
 and 
Pottmann, Helmut
 and 
Wallner, Johannes
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02011.x}

}
                
@article{
10.1111:j.1467-8659.2011.02012.x,

journal = {Computer Graphics Forum},
title = {{
Surface Patches from Unorganized Space Curves}},

author = {
Abbasinejad, Fatemeh
 and 
Joshi, Pushkar
 and 
Amenta, Nina
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02012.x}

}
                
@article{
10.1111:j.1467-8659.2011.02013.x,

journal = {Computer Graphics Forum},
title = {{
Rational Bi-cubic G2 Splines for Design with Basic Shapes}},

author = {
Karciauskas, Kestutis
 and 
Peters, Jörg
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02013.x}

}
                
@article{
10.1111:j.1467-8659.2011.02014.x,

journal = {Computer Graphics Forum},
title = {{
CubeCover - Parameterization of 3D Volumes}},

author = {
Nieser, Matthias
 and 
Reitebuch, Ulrich
 and 
Polthier, Konrad
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02014.x}

}
                
@article{
10.1111:j.1467-8659.2011.02015.x,

journal = {Computer Graphics Forum},
title = {{
All-Hex Mesh Generation via Volumetric PolyCube Deformation}},

author = {
Gregson, James
 and 
Sheffer, Alla
 and 
Zhang, Eugene
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02015.x}

}
                
@article{
10.1111:j.1467-8659.2011.02016.x,

journal = {Computer Graphics Forum},
title = {{
Localized Delaunay Refinement for Volumes}},

author = {
Dey, Tamal K.
 and 
Slatton, Andrew G.
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02016.x}

}
                
@article{
10.1111:j.1467-8659.2011.02018.x,

journal = {Computer Graphics Forum},
title = {{
Optimising Perceived Distortion in Lossy Encoding of Dynamic Meshes}},

author = {
Vá a, L.
 and 
Petrík, O.
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02018.x}

}
                
@article{
10.1111:j.1467-8659.2011.02017.x,

journal = {Computer Graphics Forum},
title = {{
A Multiscale Metric for 3D Mesh Visual Quality Assessment}},

author = {
Lavoué, Guillaume
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02017.x}

}
                
@article{
10.1111:j.1467-8659.2011.02020.x,

journal = {Computer Graphics Forum},
title = {{
Coarse-to-Fine Combinatorial Matching for Dense Isometric Shape Correspondence}},

author = {
Sahillioglu, Yusuf
 and 
Yemez, Yucel
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02020.x}

}
                
@article{
10.1111:j.1467-8659.2011.02019.x,

journal = {Computer Graphics Forum},
title = {{
A Hierarchical Grid Based Framework for Fast Collision Detection}},

author = {
Fan, Wenshan
 and 
Wang, Bin
 and 
Paul, Jean-Claude
 and 
Sun, Jiaguang
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02019.x}

}
                
@article{
10.1111:j.1467-8659.2011.02024.x,

journal = {Computer Graphics Forum},
title = {{
A Condition Number for Non-Rigid Shape Matching}},

author = {
Ovsjanikov, Maks
 and 
Huang, Qi-Xing
 and 
Guibas, Leonidas
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02024.x}

}
                
@article{
10.1111:j.1467-8659.2011.02022.x,

journal = {Computer Graphics Forum},
title = {{
An Optimization Approach to Improving Collections of Shape Maps}},

author = {
Nguyen, Andy
 and 
Ben-Chen, Mirela
 and 
Welnicka, Katarzyna
 and 
Ye, Yinyu
 and 
Guibas, Leonidas
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02022.x}

}
                
@article{
10.1111:j.1467-8659.2011.02023.x,

journal = {Computer Graphics Forum},
title = {{
Deformable 3D Shape Registration Based on Local Similarity Transforms}},

author = {
Papazov, Chavdar
 and 
Burschka, Darius
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02023.x}

}
                
@article{
10.1111:j.1467-8659.2011.02021.x,

journal = {Computer Graphics Forum},
title = {{
Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching}},

author = {
Windheuser, Thomas
 and 
Schlickewei, Ulrich
 and 
Schmidt, Frank R.
 and 
Cremers, Daniel
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02021.x}

}
                
@article{
10.1111:j.1467-8659.2011.02026.x,

journal = {Computer Graphics Forum},
title = {{
Multiscale Biharmonic Kernels}},

author = {
Rustamov, Raif M.
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02026.x}

}
                
@article{
10.1111:j.1467-8659.2011.02027.x,

journal = {Computer Graphics Forum},
title = {{
A Complex View of Barycentric Mappings}},

author = {
Weber, Ofir
 and 
Ben-Chen, Mirela
 and 
Gotsman, Craig
 and 
Hormann, Kai
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02027.x}

}
                
@article{
10.1111:j.1467-8659.2011.02025.x,

journal = {Computer Graphics Forum},
title = {{
On Approximation of the Laplace-Beltrami Operator and the Willmore Energy of Surfaces}},

author = {
Hildebrandt, Klaus
 and 
Polthier, Konrad
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02025.x}

}
                
@article{
10.1111:j.1467-8659.2011.02028.x,

journal = {Computer Graphics Forum},
title = {{
As-Killing-As-Possible Vector Fields for Planar Deformation}},

author = {
Solomon, Justin
 and 
Ben-Chen, Mirela
 and 
Butscher, Adrian
 and 
Guibas, Leonidas
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02028.x}

}
                
@article{
10.1111:j.1467-8659.2011.02029.x,

journal = {Computer Graphics Forum},
title = {{
On the Shape of a Set of Points and Lines in the Plane}},

author = {
Kreveld, Marc van
 and 
Lankveld, Thijs van
 and 
Veltkamp, Remco C.
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02029.x}

}
                
@article{
10.1111:j.1467-8659.2011.02030.x,

journal = {Computer Graphics Forum},
title = {{
VASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point Clouds}},

author = {
Tagliasacchi, Andrea
 and 
Olson, Matt
 and 
Zhang, Hao
 and 
Hamarneh, Ghassan
 and 
Cohen-Or, Daniel
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02030.x}

}
                
@article{
10.1111:j.1467-8659.2011.02032.x,

journal = {Computer Graphics Forum},
title = {{
A Multiscale Approach to Optimal Transport}},

author = {
Mérigot, Quentin
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02032.x}

}
                
@article{
10.1111:j.1467-8659.2011.02033.x,

journal = {Computer Graphics Forum},
title = {{
An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes}},

author = {
Goes, Fernando de
 and 
Cohen-Steiner, David
 and 
Alliez, Pierre
 and 
Desbrun, Mathieu
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02033.x}

}
                
@article{
10.1111:j.1467-8659.2011.02031.x,

journal = {Computer Graphics Forum},
title = {{
Skeleton Computation of Orthogonal Polyhedra}},

author = {
Martinez, Jonas
 and 
Vigo, Marc
 and 
Pla-Garcia, Nuria
},
year = {
2011},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd.},


ISSN = {1467-8659},

DOI = {
10.1111/j.1467-8659.2011.02031.x}

}

Browse

Recent Submissions

Now showing 1 - 24 of 24
  • Thumbnail Image
    Item
    Preface and Table of Contents
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Mario Botsch and Scott Schaefer
  • Thumbnail Image
    Item
    Functional Webs for Freeform Architecture
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Deng, B.; Pottmann, Helmut; Wallner, Johannes; Mario Botsch and Scott Schaefer
    Rationalization and construction-aware design dominate the issue of realizability of freeform architecture. The former means the decomposition of an intended shape into parts which are sufficiently simple and efficient to manufacture; the latter refers to a design procedure which already incorporates rationalization. Recent contributions to this topic have been concerned mostly with small-scale parts, for instance with planar faces of meshes. The present paper deals with another important aspect, namely long-range parts and supporting structures. It turns out that from the pure geometry viewpoint this means studying families of curves which cover surfaces in certain well-defined ways. Depending on the application one has in mind, different combinatorial arrangements of curves are required. We here restrict ourselves to so-called hexagonal webs which correspond to a triangular or tri-hex decomposition of a surface. The individual curve may have certain special properties, like being planar, being a geodesic, or being part of a circle. Each of these properties is motivated by manufacturability considerations and imposes constraints on the shape of the surface. We investigate the available degrees of freedom, show numerical methods of optimization, and demonstrate the effectivity of our approach and the variability of construction solutions derived from webs by means of actual architectural designs.
  • Thumbnail Image
    Item
    Surface Patches from Unorganized Space Curves
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Abbasinejad, Fatemeh; Joshi, Pushkar; Amenta, Nina; Mario Botsch and Scott Schaefer
    Recent 3D sketch tools produce networks of three-space curves that suggest the contours of shapes. The shapes may be non-manifold, closed three-dimensional, open two-dimensional, or mixed. We describe a system that automatically generates intuitively appealing piecewise-smooth surfaces from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both the automatic and the semi-automatic parts of the system use a linear algebra representation of the set of surface patches to track the topology. On complicated inputs from ILoveSketch [BBS08], our system allows the user to build the desired surface with just a few mouse-clicks.
  • Thumbnail Image
    Item
    Rational Bi-cubic G2 Splines for Design with Basic Shapes
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Karciauskas, Kestutis; Peters, Jörg; Mario Botsch and Scott Schaefer
    The paper develops a rational bi-cubic G<sup>2</sup> (curvature continuous) analogue of the non-uniform polynomial C<sup>2</sup> cubic B-spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly-connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes.
  • Thumbnail Image
    Item
    CubeCover - Parameterization of 3D Volumes
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Nieser, Matthias; Reitebuch, Ulrich; Polthier, Konrad; Mario Botsch and Scott Schaefer
    Despite the success of quad-based 2D surface parameterization methods, effective parameterization algorithms for 3D volumes with cubes, i.e. hexahedral elements, are still missing. CUBECOVER is a first approach for generating a hexahedral tessellation of a given volume with boundary aligned cubes which are guided by a frame field. The input of CUBECOVER is a tetrahedral volume mesh. First, a frame field is designed with manual input from the designer. It guides the interior and boundary layout of the parameterization. Then, the parameterization and the hexahedral mesh are computed so as to align with the given frame field. CUBECOVER has similarities to the QUADCOVER algorithm and extends it from 2D surfaces to 3D volumes. The paper also provides theoretical results for 3D hexahedral parameterizations and analyses topological properties of the appropriate function space.
  • Thumbnail Image
    Item
    All-Hex Mesh Generation via Volumetric PolyCube Deformation
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Gregson, James; Sheffer, Alla; Zhang, Eugene; Mario Botsch and Scott Schaefer
    While hexahedral mesh elements are preferred by a variety of simulation techniques, constructing quality all-hex meshes of general shapes remains a challenge. An attractive hex-meshing approach, often referred to as submapping, uses a low distortion mapping between the input model and a PolyCube (a solid formed from a union of cubes), to transfer a regular hex grid from the PolyCube to the input model. Unfortunately, the construction of suitable PolyCubes and corresponding volumetric maps for arbitrary shapes remains an open problem. Our work introduces a new method for computing low-distortion volumetric PolyCube deformations of general shapes and for subsequent all-hex remeshing. For a given input model, our method simultaneously generates an appropriate PolyCube structure and mapping between the input model and the PolyCube. From these we automatically generate good quality all-hex meshes of complex natural and man-made shapes.
  • Thumbnail Image
    Item
    Localized Delaunay Refinement for Volumes
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Dey, Tamal K.; Slatton, Andrew G.; Mario Botsch and Scott Schaefer
    Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state-of-the-art meshing tool provided by CGAL.
  • Thumbnail Image
    Item
    Optimising Perceived Distortion in Lossy Encoding of Dynamic Meshes
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Vá a, L.; Petrík, O.; Mario Botsch and Scott Schaefer
    Development of geometry data compression techniques in the past years has been limited by the lack of a metric with proven correlation with human perception of mesh distortion. Many algorithms have been proposed, but usually the aim has been to minimise mean squared error, or some of its derivatives. In the field of dynamic mesh compression, the situation has changed with the recent proposal of the STED metric, which has been shown to capture the human perception of mesh distortion much better than previous metrics. In this paper we show how existing algorithms can be steered to provide optimal results with respect to this metric, and we propose a novel dynamic mesh compression algorithm, based on trajectory space PCA and Laplacian coordinates, specifically designed to minimise the newly proposed STED error. Our experiments show that using the proposed algorithm, we were able to reduce the required data rate by up to 50% while preserving the introduced STED error.
  • Thumbnail Image
    Item
    A Multiscale Metric for 3D Mesh Visual Quality Assessment
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Lavoué, Guillaume; Mario Botsch and Scott Schaefer
    Many processing operations are nowadays applied on 3D meshes like compression, watermarking, remeshing and so forth; these processes are mostly driven and/or evaluated using simple distortion measures like the Hausdorff distance and the root mean square error, however these measures do not correlate with the human visual perception while the visual quality of the processed meshes is a crucial issue. In that context we introduce a full-reference 3D mesh quality metric; this metric can compare two meshes with arbitrary connectivity or sampling density and produces a score that predicts the distortion visibility between them; a visual distortion map is also created. Our metric outperforms its counterparts from the state of the art, in term of correlation with mean opinion scores coming from subjective experiments on three existing databases. Additionally, we present an application of this new metric to the improvement of rate-distortion evaluation of recent progressive compression algorithms.
  • Thumbnail Image
    Item
    Coarse-to-Fine Combinatorial Matching for Dense Isometric Shape Correspondence
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Sahillioglu, Yusuf; Yemez, Yucel; Mario Botsch and Scott Schaefer
    We present a dense correspondence method for isometric shapes, which is accurate yet computationally efficient. We minimize the isometric distortion directly in the 3D Euclidean space, i.e., in the domain where isometry is originally defined, by using a coarse-to-fine sampling and combinatorial matching algorithm. Our method does not require any initialization and aims to find an accurate solution in the minimum-distortion sense for perfectly isometric shapes. We demonstrate the performance of our method on various isometric (or nearly isometric) pairs of shapes.
  • Thumbnail Image
    Item
    A Hierarchical Grid Based Framework for Fast Collision Detection
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Fan, Wenshan; Wang, Bin; Paul, Jean-Claude; Sun, Jiaguang; Mario Botsch and Scott Schaefer
    We present a novel hierarchical grid based method for fast collision detection (CD) for deformable models on GPU architecture. A two-level grid is employed to accommodate the non-uniform distribution of practical scene geometry. A bottom-to-top method is implemented to assign the triangles into the hierarchical grid without any iteration while a deferred scheme is introduced to efficiently update the data structure. To address the issue of load balancing, which greatly influences the performance in SIMD parallelism, a propagation scheme which utilizes a parallel scan and a segmented scan is presented, distributing workloads evenly across all concurrent threads. The proposed method supports both discrete collision detection (DCD) and continuous collision detection (CCD) with self-collision. Some typical benchmarks are tested to verify the effectiveness of our method. The results highlight our speedups over prior algorithms on different commodity GPUs.
  • Thumbnail Image
    Item
    A Condition Number for Non-Rigid Shape Matching
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Ovsjanikov, Maks; Huang, Qi-Xing; Guibas, Leonidas; Mario Botsch and Scott Schaefer
    Despite the large amount of work devoted in recent years to the problem of non-rigid shape matching, practical methods that can successfully be used for arbitrary pairs of shapes remain elusive. In this paper, we study the hardness of the problem of shape matching, and introduce the notion of the shape condition number, which captures the intuition that some shapes are inherently more difficult to match against than others. In particular, we make a connection between the symmetry of a given shape and the stability of any method used to match it while optimizing a given distortion measure. We analyze two commonly used classes of methods in deformable shape matching, and show that the stability of both types of techniques can be captured by the appropriate notion of a condition number. We also provide a practical way to estimate the shape condition number and show how it can be used to guide the selection of landmark correspondences between shapes. Thus we shed some light on the reasons why general shape matching remains difficult and provide a way to detect and mitigate such difficulties in practice.
  • Thumbnail Image
    Item
    An Optimization Approach to Improving Collections of Shape Maps
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Nguyen, Andy; Ben-Chen, Mirela; Welnicka, Katarzyna; Ye, Yinyu; Guibas, Leonidas; Mario Botsch and Scott Schaefer
    Finding an informative, structure-preserving map between two shapes has been a long-standing problem in geometry processing, involving a variety of solution approaches and applications. However, in many cases, we are given not only two related shapes, but a collection of them, and considering each pairwise map independently does not take full advantage of all existing information. For example, a notorious problem with computing shape maps is the ambiguity introduced by the symmetry problem - for two similar shapes which have reflectional symmetry there exist two maps which are equally favorable, and no intrinsic mapping algorithm can distinguish between them based on these two shapes alone. Another prominent issue with shape mapping algorithms is their relative sensitivity to how similar two shapes are - good maps are much easier to obtain when shapes are very similar. Given the context of additional shape maps connecting our collection, we propose to add the constraint of global map consistency, requiring that any composition of maps between two shapes should be independent of the path chosen in the network. This requirement can help us choose among the equally good symmetric alternatives, or help us replace a bad pairwise map with the composition of a few good maps between shapes that in some sense interpolate the original ones. We show how, given a collection of pairwise shape maps, to define an optimization problem whose output is a set of alternative maps, compositions of those given, which are consistent, and individually at times much better than the original. Our method is general, and can work on any collection of shapes, as long as a seed set of good pairwise maps is provided. We demonstrate the effectiveness of our method for improving maps generated by state-of-the-art mapping methods on various shape databases.
  • Thumbnail Image
    Item
    Deformable 3D Shape Registration Based on Local Similarity Transforms
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Papazov, Chavdar; Burschka, Darius; Mario Botsch and Scott Schaefer
    In this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as-rigid-as-possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre-aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closestpoint search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general-purpose non-linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state-of-the-art approaches.
  • Thumbnail Image
    Item
    Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Windheuser, Thomas; Schlickewei, Ulrich; Schmidt, Frank R.; Cremers, Daniel; Mario Botsch and Scott Schaefer
    We study an algorithmic framework for computing an elastic orientation-preserving matching of non-rigid 3D shapes. We outline an Integer Linear Programming formulation whose relaxed version can be minimized globally in polynomial time. Because of the high number of optimization variables, the key algorithmic challenge lies in efficiently solving the linear program. We present a performance analysis of several Linear Programming algorithms on our problem. Furthermore, we introduce a multiresolution strategy which allows the matching of higher resolution models.
  • Thumbnail Image
    Item
    Multiscale Biharmonic Kernels
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Rustamov, Raif M.; Mario Botsch and Scott Schaefer
    This paper introduces a general principle for constructing multiscale kernels on surface meshes, and presents a construction of the multiscale pre-biharmonic and multiscale biharmonic kernels. Our construction is based on an optimization problem that seeks to minimize a smoothness criterion, the Laplacian energy, subject to a sparsity inducing constraint. Namely, we use the lasso constraint, which sets an upper bound on the l1-norm of the solution, to obtain a family of solutions parametrized by this upper-bound parameter. The interplay between sparsity and smoothness results in smooth kernels that vanish away from the diagonal. We prove that the resulting kernels have gradually changing supports, consistent behavior over partial and complete meshes, and interesting limiting behaviors (e.g. in the limit of large scales, the multiscale biharmonic kernel converges to the Green's function of the biharmonic equation); in addition, these kernels are based on intrinsic quantities and so are insensitive to isometric deformations. We show empirically that our kernels are shape-aware, are robust to noise, tessellation, and partial object, and are fast to compute. Finally, we demonstrate that the new kernels can be useful for function interpolation and shape correspondence.
  • Thumbnail Image
    Item
    A Complex View of Barycentric Mappings
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Weber, Ofir; Ben-Chen, Mirela; Gotsman, Craig; Hormann, Kai; Mario Botsch and Scott Schaefer
    Barycentric coordinates are very popular for interpolating data values on polyhedral domains. It has been recently shown that expressing them as complex functions has various advantages when interpolating two-dimensional data in the plane, and in particular for holomorphic maps. We extend and generalize these results by investigating the complex representation of real-valued barycentric coordinates, when applied to planar domains. We show how the construction for generating real-valued barycentric coordinates from a given weight function can be applied to generating complex-valued coordinates, thus deriving complex expressions for the classical barycentric coordinates: Wachspress, mean value, and discrete harmonic. Furthermore, we show that a complex barycentric map admits the intuitive interpretation as a complex-weighted combination of edge-to-edge similarity transformations, allowing the design of home-made barycentric maps with desirable properties. Thus, using the tools of complex analysis, we provide a methodology for analyzing existing barycentric mappings, as well as designing new ones.
  • Thumbnail Image
    Item
    On Approximation of the Laplace-Beltrami Operator and the Willmore Energy of Surfaces
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Hildebrandt, Klaus; Polthier, Konrad; Mario Botsch and Scott Schaefer
    Discrete Laplace Beltrami operators on polyhedral surfaces play an important role for various applications in geometry processing and related areas like physical simulation or computer graphics. While discretizations of the weak Laplace Beltrami operator are well-studied, less is known about the strong form. We present a principle for constructing strongly consistent discrete Laplace Beltrami operators based on the cotan weights. The consistency order we obtain, improves previous results reported for the mesh Laplacian. Furthermore, we prove consistency of the discrete Willmore energies corresponding to the discrete Laplace Beltrami operators.
  • Thumbnail Image
    Item
    As-Killing-As-Possible Vector Fields for Planar Deformation
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Solomon, Justin; Ben-Chen, Mirela; Butscher, Adrian; Guibas, Leonidas; Mario Botsch and Scott Schaefer
    Cartoon animation, image warping, and several other tasks in two-dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near-isometric deformations, which can be motivated as direction fields minimizing an as-rigid-as-possible (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories - the set of logarithmic spirals - is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state-of-the-art deformation methods.
  • Thumbnail Image
    Item
    On the Shape of a Set of Points and Lines in the Plane
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Kreveld, Marc van; Lankveld, Thijs van; Veltkamp, Remco C.; Mario Botsch and Scott Schaefer
    Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free-form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided a-shape: an extension of the well known a-shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided a-shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided a-shape can be constructed in O((n+m) log(n+m)) time, from an input of n points and m guides. We apply guided a-shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided a-shapes of both synthetic and real data and show they are consistently better than a-shapes for this application.
  • Thumbnail Image
    Item
    VASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point Clouds
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Tagliasacchi, Andrea; Olson, Matt; Zhang, Hao; Hamarneh, Ghassan; Cohen-Or, Daniel; Mario Botsch and Scott Schaefer
    Objects with many concavities are difficult to acquire using laser scanners. The highly concave areas are hard to access by a scanner due to occlusions by other components of the object. The resulting point scan typically suffers from large amounts of missing data. Methods that use surface-based priors rely on local surface estimates and perform well only when filling small holes. When the holes become large, the reconstruction problem becomes severely under-constrained, which necessitates the use of additional reconstruction priors. In this paper, we introduce weak volumetric priors which assume that the volume of a shape varies smoothly and that each point cloud sample is visible from outside the shape. Specifically, the union of view-rays given by the scanner implicitly carves the exterior volume, while volumetric smoothness regularizes the internal volume. We incorporate these priors into a surface evolution framework where a new energy term defined by volumetric smoothness is introduced to handle large amount of missing data. We demonstrate the effectiveness of our method on objects exhibiting deep concavities, and show its general applicability over a broader spectrum of geometric scenario.
  • Thumbnail Image
    Item
    A Multiscale Approach to Optimal Transport
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Mérigot, Quentin; Mario Botsch and Scott Schaefer
    In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth-mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart.
  • Thumbnail Image
    Item
    An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Goes, Fernando de; Cohen-Steiner, David; Alliez, Pierre; Desbrun, Mathieu; Mario Botsch and Scott Schaefer
    We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect-laden point set with noise and outliers. We introduce an optimal-transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0- and 1-simplices. A fine-to-coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.
  • Thumbnail Image
    Item
    Skeleton Computation of Orthogonal Polyhedra
    (The Eurographics Association and Blackwell Publishing Ltd., 2011) Martinez, Jonas; Vigo, Marc; Pla-Garcia, Nuria; Mario Botsch and Scott Schaefer
    Skeletons are powerful geometric abstractions that provide useful representations for a number of geometric operations. The straight skeleton has a lower combinatorial complexity compared with the medial axis. Moreover, while the medial axis of a polyhedron is composed of quadric surfaces the straight skeleton just consist of planar faces. Although there exist several methods to compute the straight skeleton of a polygon, the straight skeleton of polyhedra has been paid much less attention. We require to compute the skeleton of very large datasets storing orthogonal polyhedra. Furthermore, we need to treat geometric degeneracies that usually arise when dealing with orthogonal polyhedra. We present a new approach so as to robustly compute the straight skeleton of orthogonal polyhedra. We follow a geometric technique that works directly with the boundary of an orthogonal polyhedron. Our approach is output sensitive with respect to the number of vertices of the skeleton and solves geometric degeneracies. Unlike the existing straight skeleton algorithms that shrink the object boundary to obtain the skeleton, our algorithm relies on the plane sweep paradigm. The resulting skeleton is only composed of axis-aligned and 45 rotated planar faces and edges.