34-Issue 5

Permanent URI for this collection

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

Browse

Browsing 34-Issue 5 by Subject "Geometric algorithms"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Fast and Exact (Poisson) Solvers on Symmetric Geometries
    (The Eurographics Association and John Wiley & Sons Ltd., 2015) Kazhdan, Misha; Mirela Ben-Chen and Ligang Liu
    In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation-theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.
  • Thumbnail Image
    Item
    Hierarchical Multiview Rigid Registration
    (The Eurographics Association and John Wiley & Sons Ltd., 2015) Tang, Yizhi; Feng, Jieqing; Mirela Ben-Chen and Ligang Liu
    Registration is a key step in the 3D reconstruction of real-world objects. In this paper, we propose a hierarchical method for the rigid registration of multiple views. The multiview registration problem is solved via hierarchical optimization defined on an undirected graph. Each node or edge in this graph represents a single view or a connection between two overlapped views, respectively. The optimizations are performed hierarchically on the edges, the loops, and the entire graph. First, each overlapped pair of views is locally aligned. Then, a loop-based incremental registration algorithm is introduced to refine the initial pairwise alignments. After a loop is registered, the views in the loop are merged into a metaview in the graph. Finally, global error diffusion is applied to the entire graph to evenly distribute the accumulated errors to all views. In addition, a new objective function is defined to describe the loop closure problem; it improves the accuracy and robustness of registration by simultaneously considering transformation and registration errors. The experimental results show that the proposed hierarchical approach is accurate, efficient and robust for initial view states that are not well posed.
  • Thumbnail Image
    Item
    Stable Topological Signatures for Points on 3D Shapes
    (The Eurographics Association and John Wiley & Sons Ltd., 2015) Carrière, Mathieu; Oudot, Steve Y.; Ovsjanikov, Maks; Mirela Ben-Chen and Ligang Liu
    Comparing points on 3D shapes is among the fundamental operations in shape analysis. To facilitate this task, a great number of local point signatures or descriptors have been proposed in the past decades. However, the vast majority of these descriptors concentrate on the local geometry of the shape around the point, and thus are insensitive to its connectivity structure. By contrast, several global signatures have been proposed that successfully capture the overall topology of the shape and thus characterize the shape as a whole. In this paper, we propose the first point descriptor that captures the topology structure of the shape as 'seen' from a single point, in a multiscale and provably stable way. We also demonstrate how a large class of topological signatures, including ours, can be mapped to vectors, opening the door to many classical analysis and learning methods. We illustrate the performance of this approach on the problems of supervised shape labeling and shape matching. We show that our signatures provide complementary information to existing ones and allow to achieve better performance with less training data in both applications.