SGP14: Eurographics Symposium on Geometry Processing (CGF 33-5)

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 29

Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2014) Thomas Funkhouser and Shi-Min Hu
Freeform Honeycomb Structures
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Jiang, Caigui; Wang, Jun; Wallner, Johannes; Pottmann, Helmut; Thomas Funkhouser and Shi-Min Hu
Motivated by requirements of freeform architecture, and inspired by the geometry of hexagonal combs in beehives, this paper addresses torsion-free structures aligned with hexagonal meshes. Since repetitive geometry is a very important contribution to the reduction of production costs, we study in detail ''honeycomb structures'', which are defined as torsion-free structures where the walls of cells meet at 120 degrees. Interestingly, the Gauss-Bonnet theorem is useful in deriving information on the global distribution of node axes in such honeycombs. This paper discusses the computation and modeling of honeycomb structures as well as applications, e.g. for shading systems, or for quad meshing. We consider this paper as a contribution to the wider topic of freeform patterns, polyhedral or otherwise. Such patterns require new approaches on the technical level, e.g. in the treatment of smoothness, but they also extend our view of what constitutes aesthetic freeform geometry.
Piecewise-Planar 3D Reconstruction with Edge and Corner Regularization
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Boulch, Alexandre; Gorce, Martin de La; Marlet, Renaud; Thomas Funkhouser and Shi-Min Hu
This paper presents a method for the 3D reconstruction of a piecewise-planar surface from range images, typically laser scans with millions of points. The reconstructed surface is a watertight polygonal mesh that conforms to observations at a given scale in the visible planar parts of the scene, and that is plausible in hidden parts. We formulate surface reconstruction as a discrete optimization problem based on detected and hypothesized planes. One of our major contributions, besides a treatment of data anisotropy and novel surface hypotheses, is a regularization of the reconstructed surface w.r.t. the length of edges and the number of corners. Compared to classical area-based regularization, it better captures surface complexity and is therefore better suited for man-made environments, such as buildings. To handle the underlying higher-order potentials, that are problematic for MRF optimizers, we formulate minimization as a sparse mixed-integer linear programming problem and obtain an approximate solution using a simple relaxation. Experiments show that it is fast and reaches near-optimal solutions.
Pseudo-Spline Subdivision Surfaces
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Deng, Chongyang; Hormann, Kai; Thomas Funkhouser and Shi-Min Hu
Pseudo-splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo-splines include uniform odd-degree B-splines and the interpolatory 2n-point subdivision schemes, and the other pseudo-splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo-spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo-spline surfaces can be arbitrarily smooth in regular mesh regions and C1 at extraordinary vertices as our numerical analysis reveals.
Functional Fluids on Surfaces
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Azencot, Omri; Weißmann, Steffen; Ovsjanikov, Maks; Wardetzky, Max; Ben-Chen, Mirela; Thomas Funkhouser and Shi-Min Hu
Fluid simulation plays a key role in various domains of science including computer graphics. While most existing work addresses fluids on bounded Euclidean domains, we consider the problem of simulating the behavior of an incompressible fluid on a curved surface represented as an unstructured triangle mesh. Unlike the commonly used Eulerian description of the fluid using its time-varying velocity field, we propose to model fluids using their vorticity, i.e., by a (time varying) scalar function on the surface. During each time step, we advance scalar vorticity along two consecutive, stationary velocity fields. This approach leads to a variational integrator in the space continuous setting. In addition, using this approach, the update rule amounts to manipulating functions on the surface using linear operators, which can be discretized efficiently using the recently introduced functional approach to vector fields. Combining these time and space discretizations leads to a conceptually and algorithmically simple approach, which is efficient, time-reversible and conserves vorticity by construction. We further demonstrate that our method exhibits no numerical dissipation and is able to reproduce intricate phenomena such as vortex shedding from boundaries.
Compressed Manifold Modes for Mesh Processing
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Neumann, Thomas; Varanasi, Kiran; Theobalt, Christian; Magnor, Marcus; Wacker, Markus; Thomas Funkhouser and Shi-Min Hu
This paper introduces compressed eigenfunctions of the Laplace-Beltrami operator on 3D manifold surfaces. They constitute a novel functional basis, called the compressed manifold basis, where each function has local support. We derive an algorithm, based on the alternating direction method of multipliers (ADMM), to compute this basis on a given triangulated mesh. We show that compressed manifold modes identify key shape features, yielding an intuitive understanding of the basis for a human observer, where a shape can be processed as a collection of parts. We evaluate compressed manifold modes for potential applications in shape matching and mesh abstraction. Our results show that this basis has distinct advantages over existing alternatives, indicating high potential for a wide range of use-cases in mesh processing.
Feature-Preserving Surface Completion Using Four Points
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Harary, Gur; Tal, Ayellet; Grinspun, Eitan; Thomas Funkhouser and Shi-Min Hu
We present a user-guided, semi-automatic approach to completing large holes in a mesh. The reconstruction of the missing features in such holes is usually ambiguous. Thus, unsupervised methods may produce unsatisfactory results. To overcome this problem, we let the user indicate constraints by providing merely four points per important feature curve on the mesh. Our algorithm regards this input as an indication of an important broken feature curve. Our completion is formulated as a global energy minimization problem, with user-defined spatialcoherence constraints, allows for completion that adheres to the existing features. We demonstrate the method on example problems that are not handled satisfactorily by fully automatic methods.
SUPER 4PCS: Fast Global Pointcloud Registration via Smart Indexing
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Mellado, Nicolas; Aiger, Dror; Mitra, Niloy J.; Thomas Funkhouser and Shi-Min Hu
Data acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state-of-the-art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present SUPER 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory-efficient, and fast. We demonstrate that SUPER 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.
Semi-sharp Creases on Subdivision Curves and Surfaces
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Kosinka, Jiri; Sabin, Malcolm A.; Dodgson, Neil A.; Thomas Funkhouser and Shi-Min Hu
We explore a method for generalising Pixar semi-sharp creases from the univariate cubic case to arbitrary degree subdivision curves. Our approach is based on solving simple matrix equations. The resulting schemes allow for greater flexibility over existing methods, via control vectors. We demonstrate our results on several high-degree univariate examples and explore analogous methods for subdivision surfaces.
Efficient Encoding of Texture Coordinates Guided by Mesh Geometry
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Vása, Libor; Brunnett, Guido; Thomas Funkhouser and Shi-Min Hu
In this paper, we investigate the possibilities of efficient encoding of UV coordinates associated with vertices of a triangle mesh. Since most parametrization schemes attempt to achieve at least some level of conformality, we exploit the similarity of the shapes of triangles in the mesh and in the parametrization. We propose two approaches building on this idea: first, applying a recently proposed generalization of the parallelogram predictor, using the inner angles of mesh triangles corresponding to the UV-space triangles. Second, we propose an encoding method based on discrete Laplace operator, which also allows exploiting the information contained in the mesh geometry to efficiently encode the parametrization. Our experiments show that the proposed approach leads to savings of up to 3 bits per UV vertex, without loss of precision.
An Efficient Approach to Correspondences between Multiple Non-Rigid Parts
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Tam, Gary K. L.; Martin, Ralph R.; Rosin, Paul L.; Lai, Yu-Kun; Thomas Funkhouser and Shi-Min Hu
Identifying multiple deformable parts on meshes and establishing dense correspondences between them are tasks of fundamental importance to computer graphics, with applications to e.g. geometric edit propagation and texture transfer. Much research has considered establishing correspondences between non-rigid surfaces, but little work can both identify similar multiple deformable parts and handle partial shape correspondences. This paper addresses two related problems, treating them as a whole: (i) identifying similar deformable parts on a mesh, related by a non-rigid transformation to a given query part, and (ii) establishing dense point correspondences automatically between such parts. We show that simple and efficient techniques can be developed if we make the assumption that these parts locally undergo isometric deformation. Our insight is that similar deformable parts are suggested by large clusters of point correspondences that are isometrically consistent. Once such parts are identified, dense point correspondences can be obtained by an iterative propagation process. Our techniques are applicable to models with arbitrary topology. Various examples demonstrate the effectiveness of our techniques.
Cross-Collection Map Inference by Intrinsic Alignment of Shape Spaces
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Shapira, Nitzan; Ben-Chen, Mirela; Thomas Funkhouser and Shi-Min Hu
Inferring maps between shapes is a long standing problem in geometry processing. The less similar the shapes are, the harder it is to compute a map, or even define criteria to evaluate it. In many cases, shapes appear as part of a collection, e.g. an animation or a series of faces or poses of the same character, where the shapes are similar enough, such that maps within the collection are easy to obtain. Our main observation is that given two collections of shapes whose ''shape space'' structure is similar, it is possible to find a correspondence between the collections, and then compute a cross-collection map. The cross-map is given as a functional correspondence, and thus it is more appropriate in cases where a bijective point-to-point map is not well defined. Our core idea is to treat each collection as a point-sampling from a low-dimensional shape-space manifold, and use dimensionality reduction techniques to find a low-dimensional Euclidean embedding of this sampling. To measure distances on the shape-space manifold, we use the recently introduced shape differences, which lead to a similar low-dimensional structure of the shape spaces, even if the shapes themselves are quite different. This allows us to use standard affine registration for point-clouds to align the shape-spaces, and then find a functional cross-map using a linear solve. We demonstrate the results of our algorithm on various shape collections and discuss its properties.
Clever Support: Efficient Support Structure Generation for Digital Fabrication
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Vanek, Juraj; Galicia, Jorge A. G.; Benes, Bedrich; Thomas Funkhouser and Shi-Min Hu
We introduce an optimization framework for the reduction of support structures required by 3D printers based on Fused Deposition Modeling (FDM) technology. The printers need to connect overhangs with the lower parts of the object or the ground in order to print them. Since the support material needs to be printed first and discarded later, optimizing its volume can lead to material and printing time savings.We present a novel, geometry-based approach that minimizes the support material while providing sufficient support. Using our approach, the input 3D model is first oriented into a position with minimal area that requires support. Then the points in this area that require support are detected. For these points the supporting structure is progressively built while attempting to minimize the overall length of the support structure. The resulting structure has a tree-like shape that effectively supports the overhangs. We have tested our algorithm on the MakerBot R ReplicatorTM 2 printer and we compared our solution to the embedded software solution in this printer and to Autodesk R MeshmixerTMsoftware. Our solution reduced printing time by an average of 29.4% (ranging from 13.9% to 49.5%) and the amount of material by 40.5% (ranging from 24.5% to 68.1%).
Discrete 2-Tensor Fields on Triangulations
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Goes, Fernando de; Liu, Beibei; Budninskiy, Max; Tong, Yiying; Desbrun, Mathieu; Thomas Funkhouser and Shi-Min Hu
Geometry processing has made ample use of discrete representations of tangent vector fields and antisymmetric tensors (i.e., forms) on triangulations. Symmetric 2-tensors, while crucial in the definition of inner products and elliptic operators, have received only limited attention. They are often discretized by first defining a coordinate system per vertex, edge or face, then storing their components in this frame field. In this paper, we introduce a representation of arbitrary 2-tensor fields on triangle meshes. We leverage a coordinate-free decomposition of continuous 2-tensors in the plane to construct a finite-dimensional encoding of tensor fields through scalar values on oriented simplices of a manifold triangulation. We also provide closed-form expressions of pairing, inner product, and trace for this discrete representation of tensor fields, and formulate a discrete covariant derivative and a discrete Lie bracket. Our approach extends discrete/finite-element exterior calculus, recovers familiar operators such as the weighted Laplacian operator, and defines discrete notions of divergence-free, curl-free, and traceless tensors-thus offering a numerical framework for discrete tensor calculus on triangulations. We finally demonstrate the robustness and accuracy of our operators on analytical examples, before applying them to the computation of anisotropic geodesic distances on discrete surfaces
A Variational Taxonomy for Surface Reconstruction from Oriented Points
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Schroers, Christopher; Setzer, Simon; Weickert, Joachim; Thomas Funkhouser and Shi-Min Hu
The problem of reconstructing a watertight surface from a finite set of oriented points has received much attention over the last decades. In this paper, we propose a general higher order framework for surface reconstruction. It is based on the idea that position and normal defined by each oriented point can be used to construct an implicit local description of the unknown surface. On the one hand, this allows us to systematically explain and relate several popular methods, for example implicit moving least squares, smooth signed distance surface reconstruction as well as (screened) Poisson surface reconstruction. On the other hand, it allows to derive and discuss a number of new approaches for reconstructing either the signed distance or the indicator function of the sought object. All of these approaches are able to achieve competitive results but one of them turns out to be especially promising. To improve reconstructions in difficult real world scenarios where point clouds have been estimated from colour images, we introduce a hull constraint that encourages the surface to stay within a given region. Our framework is implemented on the GPU using a recent cyclic scheme called Fast Jacobi, which combines low implementational effort with high efficiency.
Designing N-PolyVector Fields with Complex Polynomials
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Diamanti, Olga; Vaxman, Amir; Panozzo, Daniele; Sorkine-Hornung, Olga; Thomas Funkhouser and Shi-Min Hu
We introduce N-PolyVector fields, a generalization of N-RoSy fields for which the vectors are neither necessarily orthogonal nor rotationally symmetric. We formally define a novel representation for N-PolyVectors as the root sets of complex polynomials and analyze their topological and geometric properties. A smooth N-PolyVector field can be efficiently generated by solving a sparse linear system without integer variables. We exploit the flexibility of N-PolyVector fields to design conjugate vector fields, offering an intuitive tool to generate planar quadrilateral meshes.
Pattern-Based Quadrangulation for N-Sided Patches
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Takayama, Kenshi; Panozzo, Daniele; Sorkine-Hornung, Olga; Thomas Funkhouser and Shi-Min Hu
We propose an algorithm to quadrangulate an N-sided patch with prescribed numbers of edge subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We demonstrate the effectiveness of our algorithm by integrating it into a sketch-based quad remeshing system. A reference C++ implementation of our algorithm is provided as a supplementary material.
Remeshing-assisted Optimization for Locally Injective Mappings
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Jin, Yao; Huang, Jin; Tong, Ruofeng; Thomas Funkhouser and Shi-Min Hu
Constructing locally injective mappings for 2D triangular meshes is vital in applications such as deformations. In such a highly constrained optimization, the prescribed tessellation may impose strong restriction on the solution. As a consequence, the feasible region may be too small to contain an ideal solution, which leads to problems of slow convergence, poor solution, or even that no solution can be found. We propose to integrate adaptive remeshing into interior point method to solve this issue. We update the vertex positions via a parameter-free relaxation enhanced geometry optimization, and then use edge-flip operations to reduce the residual and keep a reasonable condition number for better convergence. For more robustness, when the iteration of interior point method terminates but leaves the positional constraints unsatisfied, we estimate the edges in the current tessellation that block vertices moving based on the convergence information of the optimization, and then split neighboring edges to break the restriction. The results show that our method has better performance than the solely geometric optimization approaches, especially for extreme deformations.
Transductive 3D Shape Segmentation using Sparse Reconstruction
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Xu, Weiwei; Shi, Zhouxu; Xu, Mingliang; Zhou, Kun; Wang, Jingdong; Zhou, Bin; Wang, Jinrong; Yuan, Zhenming; Thomas Funkhouser and Shi-Min Hu
We propose a transductive shape segmentation algorithm, which can transfer prior segmentation results in database to new shapes without explicitly specification of prior category information. Our method first partitions an input shape into a set of segmentations as a data preparation, and then a linear integer programming algorithm is used to select segments from them to form the final optimal segmentation. The key idea is to maximize the segment similarity between the segments in the input shape and the segments in database, where the segment similarity is computed through sparse reconstruction error. The segment-level similarity enables to handle a large amount of shapes with significant topology or shape variations with a small set of segmented example shapes. Experimental results show that our algorithm can generate high quality segmentation and semantic labeling results in the Princeton segmentation benchmark.
Supervised Learning of Bag-of-features Shape Descriptors Using Sparse Coding
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Litman, Roee; Bronstein, Alex; Bronstein, Michael; Castellani, Umberto; Thomas Funkhouser and Shi-Min Hu
We present a method for supervised learning of shape descriptors for shape retrieval applications. Many contentbased shape retrieval approaches follow the bag-of-features (BoF) paradigm commonly used in text and image retrieval by first computing local shape descriptors, and then representing them in a 'geometric dictionary' using vector quantization. A major drawback of such approaches is that the dictionary is constructed in an unsupervised manner using clustering, unaware of the last stage of the process (pooling of the local descriptors into a BoF, and comparison of the latter using some metric). In this paper, we replace the clustering with dictionary learning, where every atom acts as a feature, followed by sparse coding and pooling to get the final BoF descriptor. Both the dictionary and the sparse codes can be learned in the supervised regime via bi-level optimization using a taskspecific objective that promotes invariance desired in the specific application. We show significant performance improvement on several standard shape retrieval benchmarks.

Browse

Browsing SGP14: Eurographics Symposium on Geometry Processing (CGF 33-5) by Issue Date

Results Per Page

Sort Options