32-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 24

An Algorithm for Triangulating Multiple 3D Polygons
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Zou, Ming; Ju, Tao; Carr, Nathan; Yaron Lipman and Hao Zhang
We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
Animation-Aware Quadrangulation
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Marcias, Giorgio; Pietroni, Nico; Panozzo, Daniele; Puppo, Enrico; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point-to-point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field-aligned quadrangulation with an off-the-shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state-of-the-art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.
Approximating Functions on a Mesh with Restricted Voronoï Diagrams
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Nivoliers, Vincent; Lévy, Bruno; Yaron Lipman and Hao Zhang
We propose a method that computes a piecewise constant approximation of a function defined on a mesh. The approximation is associated with the cells of a restricted Voronoï diagram. Our method optimizes an objective function measuring the quality of the approximation. This objective function depends on the placement of the samples that define the restricted Voronoï diagram and their associated function values. We study the continuity of the objective function, derive the closed-form expression of its derivatives and use them to design a numerical solution mechanism. The method can be applied to a function that has discontinuities, and the result aligns the boundaries of the Voronoï cells with the discontinuities. Some examples are shown, suggesting potential applications in image vectorization and compact representation of lighting.
Bijective Composite Mean Value Mappings
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Schneider, Teseo; Hormann, Kai; Floater, Michael S.; Yaron Lipman and Hao Zhang
We introduce the novel concept of composite barycentric mappings and give theoretical conditions under which they are guaranteed to be bijective. We then focus on mean value mappings and derive a simple procedure for computing their Jacobians, leading to an efficient GPU-assisted implementation for interactively designing composite mean value mappings which are bijective up to pixel resolution. We provide a number of examples of 2D image deformation and an example of 3D shape deformation based on a natural extension of the concept to spatial mappings.
Connectivity Editing for Quad-Dominant Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Peng, Chi-Han; Wonka, Peter; Yaron Lipman and Hao Zhang
We propose a connectivity editing framework for quad-dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non-quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad-dominant mesh design.
Consistent Shape Maps via Semidefinite Programming
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Huang, Qi-Xing; Guibas, Leonidas; Yaron Lipman and Hao Zhang
Recent advances in shape matching have shown that jointly optimizing the maps among the shapes in a collection can lead to significant improvements when compared to estimating maps between pairs of shapes in isolation. These methods typically invoke a cycle-consistency criterion - the fact that compositions of maps along a cycle of shapes should approximate the identity map. This condition regularizes the network and allows for the correction of errors and imperfections in individual maps. In particular, it encourages the estimation of maps between dissimilar shapes by compositions of maps along a path of more similar shapes. In this paper, we introduce a novel approach for obtaining consistent shape maps in a collection that formulates the cycle-consistency constraint as the solution to a semidefinite program (SDP). The proposed approach is based on the observation that, if the ground truth maps between the shapes are cycle-consistent, then the matrix that stores all pair-wise maps in blocks is low-rank and positive semidefinite. Motivated by recent advances in techniques for low-rank matrix recovery via semidefinite programming, we formulate the problem of estimating cycle-consistent maps as finding the closest positive semidefinite matrix to an input matrix that stores all the initial maps. By analyzing the Karush-Kuhn-Tucker (KKT) optimality condition of this program, we derive theoretical guarantees for the proposed algorithm, ensuring the correctness of the recovery when the errors in the inputs maps do not exceed certain thresholds. Besides this theoretical guarantee, experimental results on benchmark datasets show that the proposed approach outperforms state-of-the-art multiple shape matching methods.
Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Sacht, Leonardo; Jacobson, Alec; Panozzo, Daniele; Schüller, Christian; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self-intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet-meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self-intersections in the input surface. This enables volumetric processing on self-intersecting models. We leverage conformalized mean-curvature flow, which removes self-intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.
Consolidation of Low-quality Point Clouds from Outdoor Scenes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Jun; Xu, Kai; Liu, Ligang; Cao, Junjie; Liu, Shengjun; Yu, Zeyun; Gu, Xianfeng David; Yaron Lipman and Hao Zhang
The emergence of laser/LiDAR sensors, reliable multi-view stereo techniques and more recently consumer depth cameras have brought point clouds to the forefront as a data format useful for a number of applications. Unfortunately, the point data from those channels often incur imperfection, frequently contaminated with severe outliers and noise. This paper presents a robust consolidation algorithm for low-quality point data from outdoor scenes, which essentially consists of two steps: 1) outliers filtering and 2) noise smoothing. We first design a connectivitybased scheme to evaluate outlierness and thereby detect sparse outliers. Meanwhile, a clustering method is used to further remove small dense outliers. Both outlier removal methods are insensitive to the choice of the neighborhood size and the levels of outliers. Subsequently, we propose a novel approach to estimate normals for noisy points based on robust partial rankings, which is the basis of noise smoothing. Accordingly, a fast approach is exploited to smooth noise, while preserving sharp features. We evaluate the effectiveness of the proposed method on the point clouds from a variety of outdoor scenes.
Dirichlet Energy for Analysis and Synthesis of Soft Maps
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Solomon, Justin; Guibas, Leonidas; Butscher, Adrian; Yaron Lipman and Hao Zhang
Soft maps taking points on one surface to probability distributions on another are attractive for representing surface mappings in the presence of symmetry, ambiguity, and combinatorial complexity. Few techniques, however, are available to measure their continuity and other properties. To this end, we introduce a novel Dirichlet energy for soft maps generalizing the classical map Dirichlet energy, which measures distortion by computing how soft maps transport probabilistic mass from one distribution to another. We formulate the computation of the Dirichlet energy in terms of a differential equation and provide a finite elements discretization that enables all of the quantities introduced to be computed. We demonstrate the effectiveness of our framework for understanding soft maps arising from various sources. Furthermore, we suggest how these energies can be applied to generate continuous soft or point-to-point maps.
Discrete Line Congruences for Shading and Lighting
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Jun; Jiang, Caigui; Bompas, Philippe; Wallner, Johannes; Pottmann, Hellmut; Yaron Lipman and Hao Zhang
Two-parameter families of straight lines (line congruences) are implicitly present in graphics and geometry processing in several important ways including lighting and shape analysis. In this paper we make them accessible to optimization and geometric computing, by introducing a general discrete version of congruences based on piecewise-linear correspondences between triangle meshes. Our applications of congruences are based on the extraction of a so-called torsion-free support structure, which is a procedure analogous to remeshing a surface along its principal curvature lines. A particular application of such structures are freeform shading and lighting systems for architecture. We combine interactive design of such systems with global optimization in order to satisfy geometric constraints. In this way we explore a new area where architecture can greatly benefit from graphics.
Dynamic Maps for Exploring and Browsing Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Kleiman, Yanir; Fish, Noa; Lanir, Joel; Cohen-Or, Daniel; Yaron Lipman and Hao Zhang
Large datasets of 3D objects require an intuitive way to browse and quickly explore shapes from the collection. We present a dynamic map of shapes where similar shapes are placed next to each other. Similarity between 3D models exists in a high dimensional space which cannot be accurately expressed in a two dimensional map. We solve this discrepancy by providing a local map with pan capabilities and a user interface that resembles an online experience of navigating through geographical maps. As the user navigates through the map, new shapes appear which correspond to the specific navigation tendencies and interests of the user, while maintaining a continuous browsing experience. In contrast with state of the art methods which typically reduce the search space by selecting constraints or employing relevance feedback, our method enables exploration of large sets without constraining the search space, allowing the user greater creativity and serendipity. A user study evaluation showed a strong preference of users for our method over a standard relevance feedback method.
Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Larsson, Thomas; Källberg, Linus; Yaron Lipman and Hao Zhang
In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1:001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.
Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Paillé, Gilles-Philippe; Poulin, Pierre; Lévy, Bruno; Yaron Lipman and Hao Zhang
We propose a method for mapping polynomial volumes. Given a closed surface and an initial template volume grid, our method deforms the template grid by fitting its boundary to the input surface while minimizing a volume distortion criterion. The result is a point-to-point map distorting linear cells into curved ones. Our method is based on several extensions of Voronoi Squared Distance Minimization (VSDM) combined with a higher-order finite element formulation of the deformation energy. This allows us to globally optimize the mapping without prior parameterization. The anisotropic VSDM formulation allows for sharp and semi-sharp features to be implicitly preserved without tagging. We use a hierarchical finite element function basis that selectively adapts to the geometric details. This makes both the method more efficient and the representation more compact. We apply our method to geometric modeling applications in computer-aided design and computer graphics, including mixed-element meshing, mesh optimization, subdivision volume fitting, and shell meshing.
Locally Injective Mappings
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Schüller, Christian; Kavan, Ladislav; Panozzo, Daniele; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
Mappings and deformations are ubiquitous in geometry processing, shape modeling, and animation. Numerous deformation energies have been proposed to tackle problems like mesh parameterization and volumetric deformations. We present an algorithm that modifies any deformation energy to guarantee a locally injective mapping, i.e., without inverted elements. Our formulation can be used to compute continuous planar or volumetric piecewise-linear maps and it uses a barrier term to prevent inverted elements. Differently from previous methods, we carefully design both the barrier term and the associated numerical techniques to be able to provide immediate feedback to the user, enabling interactive manipulation of inversion-free mappings. Stress tests show that our method robustly handles extreme deformations where previous techniques converge very slowly or even fail. We demonstrate that enforcing local injectivity increases fidelity of the results in applications such as shape deformation and parameterization.
Noise-Adaptive Shape Reconstruction from Raw Point Sets
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Giraudot, Simon; Cohen-Steiner, David; Alliez, Pierre; Yaron Lipman and Hao Zhang
We propose a noise-adaptive shape reconstruction method specialized to smooth, closed shapes. Our algorithm takes as input a defect-laden point set with variable noise and outliers, and comprises three main steps. First, we compute a novel noise-adaptive distance function to the inferred shape, which relies on the assumption that the inferred shape is a smooth submanifold of known dimension. Second, we estimate the sign and confidence of the function at a set of seed points, through minimizing a quadratic energy expressed on the edges of a uniform random graph. Third, we compute a signed implicit function through a random walker approach with soft constraints chosen as the most confident seed points computed in previous step.
An Operator Approach to Tangent Vector Field Processing
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Azencot, Omri; Ben-Chen, Mirela; Chazal, Frédéric; Ovsjanikov, Maks; Yaron Lipman and Hao Zhang
In this paper, we introduce a novel coordinate-free method for manipulating and analyzing vector fields on discrete surfaces. Unlike the commonly used representations of a vector field as an assignment of vectors to the faces of the mesh, or as real values on edges, we argue that vector fields can also be naturally viewed as operators whose domain and range are functions defined on the mesh. Although this point of view is common in differential geometry it has so far not been adopted in geometry processing applications. We recall the theoretical properties of vector fields represented as operators, and show that composition of vector fields with other functional operators is natural in this setup. This leads to the characterization of vector field properties through commutativity with other operators such as the Laplace-Beltrami and symmetry operators, as well as to a straight-forward definition of differential properties such as the Lie derivative. Finally, we demonstrate a range of applications, such as Killing vector field design, symmetric vector field estimation and joint design on multiple surfaces.
PHOG: Photometric and Geometric Functions for Textured Shape Retrieval
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Biasotti, Silvia; Cerri, Andrea; Giorgi, Daniela; Spagnuolo, Michaela; Yaron Lipman and Hao Zhang
In this paper we target the problem of textured 3D object retrieval. As a first contribution, we show how to include photometric information in the persistence homology setting, also proposing a novel theoretical result about multidimensional persistence spaces. As a second contribution, we introduce a generalization of the integral geodesic distance which fuses shape and color properties. Finally, we adopt a purely geometric description based on the selection of geometric functions that are mutually independent. The photometric, hybrid and geometric descriptions are combined into a signature, whose performance is tested on a benchmark dataset.
Practical Anisotropic Geodesy
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Campen, Marcel; Heistermann, Martin; Kobbelt, Leif; Yaron Lipman and Hao Zhang
The computation of intrinsic, geodesic distances and geodesic paths on surfaces is a fundamental low-level building block in countless Computer Graphics and Geometry Processing applications. This demand led to the development of numerous algorithms - some for the exact, others for the approximative computation, some focussing on speed, others providing strict guarantees. Most of these methods are designed for computing distances according to the standard Riemannian metric induced by the surface's embedding in Euclidean space. Generalization to other, especially anisotropic, metrics - which more recently gained interest in several application areas - is not rarely hampered by fundamental problems. We explore and discuss possibilities for the generalization and extension of well-known methods to the anisotropic case, evaluate their relative performance in terms of accuracy and speed, and propose a novel algorithm, the Short-Term Vector Dijkstra. This algorithm is strikingly simple to implement and proves to provide practical accuracy at a higher speed than generalized previous methods.
Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Yaron Lipman and Hao Zhang
Semantizing Complex 3D Scenes using Constrained Attribute Grammars
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Boulch, Alexandre; Houllier, Simon; Marlet, Renaud; Tournaire, Olivier; Yaron Lipman and Hao Zhang
We propose a new approach to automatically semantize complex objects in a 3D scene. For this, we define an expressive formalism combining the power of both attribute grammars and constraint. It offers a practical conceptual interface, which is crucial to write large maintainable specifications. As recursion is inadequate to express large collections of items, we introduce maximal operators, that are essential to reduce the parsing search space. Given a grammar in this formalism and a 3D scene, we show how to automatically compute a shared parse forest of all interpretations - in practice, only a few, thanks to relevant constraints. We evaluate this technique for building model semantization using CAD model examples as well as photogrammetric and simulated LiDAR data.

Browse

Browsing 32-Issue 5 by Title

Results Per Page

Sort Options