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

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 29

As-Conformal-As-Possible Surface Registration
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Yoshiyasu, Yusuke; Ma, Wan-Chun; Yoshida, Eiichi; Kanehiro, Fumio; Thomas Funkhouser and Shi-Min Hu
We present a non-rigid surface registration technique that can align surfaces with sizes and shapes that are different from each other, while avoiding mesh distortions during deformation. The registration is constrained locally as conformal as possible such that the angles of triangle meshes are preserved, yet local scales are allowed to change. Based on our conformal registration technique, we devise an automatic registration and interactive registration technique, which can reduce user interventions during template fitting. We demonstrate the versatility of our technique on a wide range of surfaces.
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.
3D Motion Completion in Crowded Scenes
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Gafni, Niv; Sharf, Andrei; Thomas Funkhouser and Shi-Min Hu
Crowded motions refer to multiple objects moving around and interacting such as crowds, pedestrians and etc. We capture crowded scenes using a depth scanner at video frame rates. Thus, our input is a set of depth frames which sample the scene over time. Processing such data is challenging as it is highly unorganized, with large spatiotemporal holes due to many occlusions. As no correspondence is given, locally tracking 3D points across frames is hard due to noise and missing regions. Furthermore global segmentation and motion completion in presence of large occlusions is ambiguous and hard to predict. Our algorithm utilizes Gestalt principles of common fate and good continuity to compute motion tracking and completion respectively. Our technique does not assume any pregiven markers or motion template priors. Our key-idea is to reduce the motion completion problem to a 1D curve fitting and matching problem which can be solved efficiently using a global optimization scheme. We demonstrate our segmentation and completion method on a variety of synthetic and real world crowded scanned scenes.
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.
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.
Blue-Noise Remeshing with Farthest Point Optimization
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Yan, Dong-Ming; Guo, Jianwei; Jia, Xiaohong; Zhang, Xiaopeng; Wonka, Peter; Thomas Funkhouser and Shi-Min Hu
In this paper, we present a novel method for surface sampling and remeshing with good blue-noise properties. Our approach is based on the farthest point optimization (FPO), a relaxation technique that generates high quality blue-noise point sets in 2D. We propose two important generalizations of the original FPO framework: adaptive sampling and sampling on surfaces. A simple and efficient algorithm for accelerating the FPO framework is also proposed. Experimental results show that the generalized FPO generates point sets with excellent blue-noise properties for adaptive and surface sampling. Furthermore, we demonstrate that our remeshing quality is superior to the current state-of-the-art approaches.
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
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%).
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.
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/.
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.
Exploring the Geometry of the Space of Shells
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Heeren, Behrend; Rumpf, Martin; Schröder, Peter; Wardetzky, Max; Wirth, Benedikt; Thomas Funkhouser and Shi-Min Hu
We prove both in the smooth and discrete setting that the Hessian of an elastic deformation energy results in a proper Riemannian metric on the space of shells (modulo rigid body motions). Based on this foundation we develop a time- and space-discrete geodesic calculus. In particular we show how to shoot geodesics with prescribed initial data, and we give a construction for parallel transport in shell space. This enables, for example, natural extrapolation of paths in shell space and transfer of large nonlinear deformations from one shell to another with applications in animation, geometric, and physical modeling. Finally, we examine some aspects of curvature on shell space.
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.
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.
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.
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.
Real-time Bas-Relief Generation from Depth-and-Normal Maps on GPU
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Ji, Zhongping; Sun, Xianfang; Li, Shi; Wang, Yigang; Thomas Funkhouser and Shi-Min Hu
To design a bas-relief from a 3D scene is an inherently interactive task in many scenarios. The user normally needs to get instant feedback to select a proper viewpoint. However, current methods are too slow to facilitate this interaction. This paper proposes a two-scale bas-relief modeling method, which is computationally efficient and easy to produce different styles of bas-reliefs. The input 3D scene is first rendered into two textures, one recording the depth information and the other recording the normal information. The depth map is then compressed to produce a base surface with level-of-depth, and the normal map is used to extract local details with two different schemes. One scheme provides certain freedom to design bas-reliefs with different visual appearances, and the other provides a control over the level of detail. Finally, the local feature details are added into the base surface to produce the final result. Our approach allows for real-time computation due to its implementation on graphics hardware. Experiments with a wide range of 3D models and scenes show that our approach can effectively generate digital bas-reliefs in real time.
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.
Robust Region Detection via Consensus Segmentation of Deformable Shapes
(The Eurographics Association and John Wiley and Sons Ltd., 2014) Rodolà, Emanuele; Bulò, Samuel Rota; Cremers, Daniel; Thomas Funkhouser and Shi-Min Hu
We consider the problem of stable region detection and segmentation of deformable shapes. We pursue this goal by determining a consensus segmentation from a heterogeneous ensemble of putative segmentations, which are generated by a clustering process on an intrinsic embedding of the shape. The intuition is that the consensus segmentation, which relies on aggregate statistics gathered from the segmentations in the ensemble, can reveal components in the shape that are more stable to deformations than the single baseline segmentations. Compared to the existing approaches, our solution exhibits higher robustness and repeatability throughout a wide spectrum of non-rigid transformations. It is computationally efficient, naturally extendible to point clouds, and remains semantically stable even across different object classes. A quantitative evaluation on standard datasets confirms the potentiality of our method as a valid tool for deformable shape analysis.
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.

Browse

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

Results Per Page

Sort Options