37-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 11 of 11

Effective Characterization of Relief Patterns
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Giachetti, Andrea; Ju, Tao and Vaxman, Amir
In this paper, we address the problem of characterizing relief patterns over surface meshes independently on the underlying shape. We propose to tackle the problem by estimating local invariant features and encoding them using the Improved Fisher Vector technique, testing both features estimated on 3D meshes and local descriptors estimated on raster images created by encoding local surface properties (e.g. mean curvature) over a surface parametrization. We compare the robustness of the obtained descriptors against noise and surface bending and evaluate retrieval performances on a specific benchmark proposed in a track of the Eurographics Shape REtrieval Contest 2017. Results show that, with the proposed framework, it is possible to obtain retrieval results largely improving the state of the art and that the image-based approach is still effective when the underlying surface is heavily deformed.
Efficient Path Generation with Reduced Coordinates
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Chen, Renjie; Gotsman, Craig; Hormann, Kai; Ju, Tao and Vaxman, Amir
Path generation is an important problem in many fields, especially robotics. One way to create a path between a source point z and a target point y inside a complex planar domain W is to define a non-negative distance function d(y; z), such that following the negative gradient of d (by z) traces out such a path. This presents two challenges: (1) The mathematical challenge of defining d, such that d(y; z) has a single minimum at z = y for any fixed y, because the gradient-descent path may otherwise terminate at a local minimum before reaching y; (2) The computational challenge of defining d, such that it can be computed efficiently. Using the concepts of harmonic measure and f -divergence, we show how to assign a set of reduced coordinates to each point in W and to define a family of distance functions based on these coordinates, such that both the mathematical and the computational challenge are met. Since in practice, especially in robotics applications, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites sampled from W, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm, which is the discrete equivalent of continuous gradient descent, based on our reduced coordinates is guaranteed to generate a path in the network between any two sites. In many cases, this network is close to a planar graph, especially if the set of sites is dense. Guaranteeing the existence of a greedy route between any two points in the graph is a significant advantage in practical applications, avoiding the complexity of other path-planning methods, such as the shortest-path and A* algorithms. While the paths generated by our algorithm are not the shortest possible, in practice we found that they are close to that.
An Explicit Structure-preserving Numerical Scheme for EPDiff
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Azencot, Omri; Vantzos, Orestis; Ben-Chen, Mirela; Ju, Tao and Vaxman, Amir
We present a new structure-preserving numerical scheme for solving the Euler-Poincaré Differential (EPDiff) equation on arbitrary triangle meshes. Unlike existing techniques, our method solves the difficult non-linear EPDiff equation by constructing energy preserving, yet fully explicit, update rules. Our approach uses standard differential operators on triangle meshes, allowing for a simple and efficient implementation. Key to the structure-preserving features that our method exhibits is a novel numerical splitting scheme. Namely, we break the integration into three steps which rely on linear solves with a fixed sparse matrix that is independent of the simulation and thus can be pre-factored. We test our method in the context of simulating concentrated reconnecting wavefronts on flat and curved domains. In particular, EPDiff is known to generate geometrical fronts which exhibit wave-like behavior when they interact with each other. In addition, we also show that at a small additional cost, we can produce globally-supported periodic waves by using our simulated fronts with wavefronts tracking techniques. We provide quantitative graphs showing that our method exactly preserves the energy in practice. In addition, we demonstrate various interesting results including annihilation and recreation of a circular front, a wave splitting and merging when hitting an obstacle and two separate fronts propagating and bending due to the curvature of the domain.
Hierarchical Quad Meshing of 3D Scanned Surfaces
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Bukenberger, Dennis R.; Lensch, Hendrik P. A.; Ju, Tao and Vaxman, Amir
In this paper we present a novel method to reconstruct watertight quad meshes on scanned 3D geometry. There exist many different approaches to acquire 3D information from real world objects and sceneries. Resulting point clouds depict scanned surfaces as sparse sets of positional information. A common downside is the lack of normals, connectivity or topological adjacency data which makes it difficult to actually recover a meaningful surface. The concept described in this paper is designed to reconstruct a surface mesh despite all this missing information. Even when facing varying sample density, our algorithm is still guaranteed to produce watertight manifold meshes featuring quad faces only. The topology can be set-up to follow superimposed regular structures or align naturally to the point cloud's shape. Our proposed approach is based on an initial divide and conquer subsampling procedure: Surface samples are clustered in meaningful neighborhoods as leafs of a kd-tree. A representative sample of the surface neighborhood is determined for each leaf using a spherical surface approximation. The hierarchical structure of the binary tree is utilized to construct a basic set of loose tiles and to interconnect them. As a final step, missing parts of the now coherent tile structure are filled up with an incremental algorithm for locally optimal gap closure. Disfigured or concave faces in the resulting mesh can be removed with a constrained smoothing operator.
Interactive Curve Constrained Functional Maps
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Gehre, Anne; Bronstein, Michael M.; Kobbelt, Leif; Solomon, Justin; Ju, Tao and Vaxman, Amir
Functional maps have gained popularity as a versatile framework for representing intrinsic correspondence between 3D shapes using algebraic machinery. A key ingredient for this framework is the ability to find pairs of corresponding functions (typically, feature descriptors) across the shapes. This is a challenging problem on its own, and when the shapes are strongly non-isometric, nearly impossible to solve automatically. In this paper, we use feature curve correspondences to provide flexible abstractions of semantically similar parts of non-isometric shapes. We design a user interface implementing an interactive process for constructing shape correspondence, allowing the user to update the functional map at interactive rates by introducing feature curve correspondences. We add feature curve preservation constraints to the functional map framework and propose an efficient numerical method to optimize the map with immediate feedback. Experimental results show that our approach establishes correspondences between geometrically diverse shapes with just a few clicks.
Kernel Functional Maps
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Wang, Larry; Gehre, Anne; Bronstein, Michael M.; Solomon, Justin; Ju, Tao and Vaxman, Amir
Functional maps provide a means of extracting correspondences between surfaces using linear-algebraic machinery. While the functional framework suggests efficient algorithms for map computation, the basic technique does not incorporate the intuition that pointwise modifications of a descriptor function (e.g. composition of a descriptor and a nonlinearity) should be preserved under the mapping; the end result is that the basic functional maps problem can be underdetermined without regularization or additional assumptions on the map. In this paper, we show how this problem can be addressed through kernelization, in which descriptors are lifted to higher-dimensional vectors or even infinite-length sequences of values. The key observation is that optimization problems for functional maps only depend on inner products between descriptors rather than descriptor values themselves. These inner products can be evaluated efficiently through use of kernel functions. In addition to deriving a kernelized version of functional maps including a recent extension in terms of pointwise multiplication operators, we provide an efficient conjugate gradient algorithm for optimizing our generalized problem as well as a strategy for low-rank estimation of kernel matrices through the Nyström approximation.
Möbius Registration
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Baden, Alex; Crane, Keenan; Kazhdan, Misha; Ju, Tao and Vaxman, Amir
Conformal parameterizations over the sphere provide high-quality maps between genus zero surfaces, and are essential for applications such as data transfer and comparative shape analysis. However, such maps are not unique: to define correspondence between two surfaces, one must find the Möbius transformation that best aligns two parameterizations-akin to picking a translation and rotation in rigid registration problems. We describe a simple procedure that canonically centers and rotationally aligns two spherical maps. Centering is implemented via elementary operations on triangle meshes in R3, and minimizes area distortion. Alignment is achieved using the FFT over the group of rotations. We examine this procedure in the context of spherical conformal parameterization, orbifold maps, non-rigid symmetry detection, and dense point-to-point surface correspondence.
Packing Irregular Objects in 3D Space via Hybrid Optimization
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Ma, Yuexin; Chen, Zhonggui; Hu, Wenchao; Wang, Wenping; Ju, Tao and Vaxman, Amir
Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non-overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.
Principal Geodesic Analysis in the Space of Discrete Shells
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Heeren, Behrend; Zhang, Chao; Rumpf, Martin; Smith, William; Ju, Tao and Vaxman, Amir
Important sources of shape variability, such as articulated motion of body models or soft tissue dynamics, are highly nonlinear and are usually superposed on top of rigid body motion which must be factored out. We propose a novel, nonlinear, rigid body motion invariant Principal Geodesic Analysis (PGA) that allows us to analyse this variability, compress large variations based on statistical shape analysis and fit a model to measurements. For given input shape data sets we show how to compute a low dimensional approximating submanifold on the space of discrete shells, making our approach a hybrid between a physical and statistical model. General discrete shells can be projected onto the submanifold and sparsely represented by a small set of coefficients. We demonstrate two specific applications: model-constrained mesh editing and reconstruction of a dense animated mesh from sparse motion capture markers using the statistical knowledge as a prior.
QuadriFlow: A Scalable and Robust Method for Quadrangulation
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Huang, Jingwei; Zhou, Yichao; Niessner, Matthias; Shewchuk, Jonathan Richard; Guibas, Leonidas J.; Ju, Tao and Vaxman, Amir
QuadriFlow is a scalable algorithm for generating quadrilateral surface meshes based on the Instant Field-Aligned Meshes of Jakob et al. (ACM Trans. Graph. 34(6):189, 2015). We modify the original algorithm such that it efficiently produces meshes with many fewer singularities. Singularities in quadrilateral meshes cause problems for many applications, including parametrization and rendering with Catmull-Clark subdivision surfaces. Singularities can rarely be entirely eliminated, but it is possible to keep their number small. Local optimization algorithms usually produce meshes with many singularities, whereas the best algorithms tend to require non-local optimization, and therefore are slow. We propose an efficient method to minimize singularities by combining the Instant Meshes objective with a system of linear and quadratic constraints. These constraints are enforced by solving a global minimum-cost network flow problem and local boolean satisfiability problems. We have verified the robustness and efficiency of our method on a subset of ShapeNet comprising 17,791 3D objects in the wild. Our evaluation shows that the quality of the quadrangulations generated by our method is as good as, if not better than, those from other methods, achieving about four times fewer singularities than Instant Meshes. Other algorithms that produce similarly few singularities are much slower; we take less than ten seconds to process each model. Our source code is publicly available.
A Unified Discrete Framework for Intrinsic and Extrinsic Dirac Operators for Geometry Processing
(The Eurographics Association and John Wiley & Sons Ltd., 2018) Ye, Zi; Diamanti, Olga; Tang, Chengcheng; Guibas, Leonidas J.; Hoffmann, Tim; Ju, Tao and Vaxman, Amir
Spectral mesh analysis and processing methods, namely ones that utilize eigenvalues and eigenfunctions of linear operators on meshes, have been applied to numerous geometric processing applications. The operator used predominantly in these methods is the Laplace-Beltrami operator, which has the often-cited property that it is intrinsic, namely invariant to isometric deformation of the underlying geometry, including rigid transformations. Depending on the application, this can be either an advantage or a drawback. Recent work has proposed the alternative of using the Dirac operator on surfaces for spectral processing. The available versions of the Dirac operator either only focus on the extrinsic version, or introduce a range of mixed operators on a spectrum between fully extrinsic Dirac operator and intrinsic Laplace operator. In this work, we introduce a unified discretization scheme that describes both an extrinsic and intrinsic Dirac operator on meshes, based on their continuous counterparts on smooth manifolds. In this discretization, both operators are very closely related, and preserve their key properties from the smooth case. We showcase various applications of our operators, with improved numerics over prior work.

Browse

Browsing 37-Issue 5 by Subject "Computational Geometry and Object Modeling"

Results Per Page

Sort Options