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.
We present novel parallel algorithms for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many‐core GPUs. Our ...approach uses thread and data parallelism to perform fast hierarchy construction, updating, and traversal using tight‐fitting bounding volumes such as oriented bounding boxes (OBB) and rectangular swept spheres (RSS). We also describe efficient algorithms to compute a linear bounding volume hierarchy (LBVH) and update them using refitting methods. Moreover, we show that tight‐fitting bounding volume hierarchies offer improved performance on GPU‐like throughput architectures. We use our algorithms to perform discrete and continuous collision detection including self‐collisions, as well as separation distance computation between non‐overlapping models. In practice, our approach (gProximity) can perform these queries in a few milliseconds on a PC with NVIDIA GTX 285 card on models composed of tens or hundreds of thousands of triangles used in cloth simulation, surgical simulation, virtual prototyping and N‐body simulation. Moreover, we observe more than an order of magnitude performance improvement over prior GPU‐based algorithms.
Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the ...same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrisation and remeshing.
Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrization, and remeshing.
Non-Rigid Puzzles Litany, O.; Rodolà, E.; Bronstein, A. M. ...
Computer graphics forum,
August 2016, Letnik:
35, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology ...and many more. In settings where the shapes are allowed to undergo non‐rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non‐rigid multi‐part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non‐rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.
Sparse Iterative Closest Point Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark
Computer graphics forum,
August 2013, Letnik:
32, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative ...Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.
This paper presents a novel method to detect free‐surfaces on particle‐based volume representation. In contrast to most particle‐based free‐surface detection methods, which perform the surface ...identification based on physical and geometrical properties derived from the underlying fluid flow simulation, the proposed approach only demands the spatial location of the particles to properly recognize surface particles, avoiding even the use of kernels. Boundary particles are identified through a Hidden Point Removal (HPR) operator used for visibility test. Our method is very simple, fast, easy to implement and robust to changes in the distribution of particles, even when facing large deformation of the free‐surface. A set of comparisons against state‐of‐the‐art boundary detection methods show the effectiveness of our approach. The good performance of our method is also attested in the context of fluid flow simulation involving free‐surface, mainly when using level‐sets for rendering purposes.
The greedy spanner in a low-dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades, as it possesses the two most basic properties of ...a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh 28 showed that the greedy spanner in \(\mathbb {R}^2\) admits a sublinear separator in a strong sense: Any subgraph of k vertices of the greedy spanner in \(\mathbb {R}^2\) has a separator of size \(O(\sqrt {k})\) . Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in \(\mathbb {R}^d\) for any constant d ≥ 3 as an open problem. In this article, we resolve the problem of Eppstein and Khodabandeh 28 by showing that any subgraph of k vertices of the greedy spanner in \(\mathbb {R}^d\) has a separator of size \(O(k^{1-1/d})\) . We introduce a new technique that gives a simple criterion for any geometric graph to have a sublinear separator that we dub τ-lanky: A geometric graph is τ-lanky if any ball of radius r cuts at most τ edges of length at least r in the graph. We show that any τ-lanky geometric graph of n vertices in \(\mathbb {R}^d\) has a separator of size \(O(\tau n^{1-1/d})\) . We then derive our main result by showing that the greedy spanner is O(1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in \(\mathbb {R}^d\) . Our technique naturally extends to doubling metrics. We use the τ-lanky criterion to show that there exists a (1+ε)-spanner for doubling metrics of dimension d with a constant maximum degree and a separator of size \(O(n^{1-\frac{1}{d}})\) ; this result resolves an open problem posed by Abam and Har-Peled 1 a decade ago. We then introduce another simple criterion for a graph in doubling metrics of dimension d to have a sublinear separator. We use the new criterion to show that the greedy spanner of an n-point metric space of doubling dimension d has a separator of size \(O((n^{1-\frac{1}{d}}) + \log \Delta)\) where Δ is the spread of the metric; the factor log (Δ) is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has unbounded maximum degree. Finally, we discuss algorithmic implications of our results.
Voro++ is a software library written in C++ for computing the Voronoi tessellation, a technique in computational geometry that is widely used for analyzing systems of particles. Voro++ was released ...in 2009 and is based on computing the Voronoi cell for each particle individually. Here, we take advantage of modern computer hardware, and extend the original serial version to allow for multithreaded computation of Voronoi cells via the OpenMP application programming interface. We test the performance of the code, and demonstrate that it can achieve parallel efficiencies greater than 95% in many cases. The multithreaded extension follows standard OpenMP programming paradigms, allowing it to be incorporated into other programs. We provide an example of this using the VoroTop software library, performing a multithreaded Voronoi cell topology analysis of up to 102.4 million particles.
Program title:Voro++
CPC Library link to program files:https://doi.org/10.17632/tddc4w4zkk.1
Developer's repository link:https://github.com/chr1shr/voro
Licensing provisions: BSD 3-clause (with LBNL modification)
Programming language: C++
External routines/libraries: OpenMP
Nature of problem: Multithreaded computation of the Voronoi tessellation in two and three dimensions
Solution method: The Voro++ library is built around several C++ classes that can be incorporated into other programs. The two largest components are the container... classes that spatially sort input particles into a grid-based data structure, allowing for efficient searches of nearby particles, and the voronoicell... classes that represent a single Voronoi cell as an arbitrary convex polygon or polyhedron. The Voronoi cell for each particle is built by considering a sequence of plane cuts based on neighboring particles, after which many different statistics (e.g. volume, centroid, number of vertices) can be computed. Since each Voronoi cell is calculated individually, the Voronoi cells can be computed using multithreading via OpenMP.
Partial Functional Correspondence Rodolà, E.; Cosmo, L.; Bronstein, M. M. ...
Computer graphics forum,
January 2017, Letnik:
36, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In this paper, we propose a method for computing partial functional correspondence between non‐rigid shapes. We use perturbation analysis to show how removal of shape parts changes the ...Laplace–Beltrami eigenfunctions, and exploit it as a prior on the spectral representation of the correspondence. Corresponding parts are optimization variables in our problem and are used to weight the functional correspondence; we are looking for the largest and most regular (in the Mumford–Shah sense) parts that minimize correspondence distortion. We show that our approach can cope with very challenging correspondence settings.
In this paper, we propose a method for computing partial functional correspondence between non‐rigid shapes. We use perturbation analysis to show how removal of shape parts changes the Laplace‐Beltrami eigenfunctions, and exploit it as a prior on the spectral representation of the correspondence. Corresponding parts are optimization variables in our problem and are used to weight the functional correspondence; we are looking for the largest and most regular (in the Mumford‐Shah sense) parts that minimize correspondence distortion. We show that our approach can cope with very challenging correspondence settings.
We introduce a family of signatures for finite metric spaces, possibly endowed with real valued functions, based on the persistence diagrams of suitable filtrations built on top of these spaces. We ...prove the stability of our signatures under Gromov‐Hausdorff perturbations of the spaces. We also extend these results to metric spaces equipped with measures. Our signatures are well‐suited for the study of unstructured point cloud data, which we illustrate through an application in shape classification.
PDF
