31-Issue 5

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 23

Fast and Robust Normal Estimation for Point Clouds with Sharp Features
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Boulch, Alexandre; Marlet, Renaud; Eitan Grinspun and Niloy Mitra
This paper presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed-size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise-resistant as state-of-the-art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.
Finding Surface Correspondences Using Symmetry Axis Curves
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Liu, Tianqiang; Kim, Vladimir G.; Funkhouser, Thomas; Eitan Grinspun and Niloy Mitra
In this paper, we propose an automatic algorithm for finding a correspondence map between two 3D surfaces. The key insight is that global reflective symmetry axes are stable, recognizable, semantic features of most real-world surfaces. Thus, it is possible to find a useful map between two surfaces by first extracting symmetry axis curves, aligning the extracted curves, and then extrapolating correspondences found on the curves to both surfaces. The main advantages of this approach are efficiency and robustness: the difficult problem of finding a surface map is reduced to three significantly easier problems: symmetry detection, curve alignment, and correspondence extrapolation, each of which has a robust, polynomial-time solution (e.g., optimal alignment of 1D curves is possible with dynamic programming). We investigate of this approach on a wide range of examples, including both intrinsically symmetric surfaces and polygon soups, and find that it is superior to previous methods in cases where two surfaces have different overall shapes but similar reflective symmetry axes, a common case in computer graphics.
Shape-Up: Shaping Discrete Geometry with Projections
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Bouaziz, Sofien; Deuss, Mario; Schwartzburg, Yuliy; Weise, Thibaut; Pauly, Mark; Eitan Grinspun and Niloy Mitra
We introduce a unified optimization framework for geometry processing based on shape constraints. These constraints preserve or prescribe the shape of subsets of the points of a geometric data set, such as polygons, one-ring cells, volume elements, or feature curves. Our method is based on two key concepts: a shape proximity function and shape projection operators. The proximity function encodes the distance of a desired least-squares fitted elementary target shape to the corresponding vertices of the 3D model. Projection operators are employed to minimize the proximity function by relocating vertices in a minimal way to match the imposed shape constraints. We demonstrate that this approach leads to a simple, robust, and efficient algorithm that allows implementing a variety of geometry processing applications, simply by combining suitable projection operators. We show examples for computing planar and circular meshes, shape space exploration, mesh quality improvement, shape-preserving deformation, and conformal parametrization. Our optimization framework provides a systematic way of building new solvers for geometry processing and produces similar or better results than state-of-the-art methods.
From A Medial Surface To A Mesh
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Delamé, Thomas; Roudet, Céline; Faudot, Dominique; Eitan Grinspun and Niloy Mitra
Medial surfaces are well-known and interesting surface skeletons. As such, they can describe the topology and the geometry of a 3D closed object. The link between an object and its medial surface is also intuitively understood by people. We want to exploit such skeletons to use them in applications like shape creation and shape deformation. For this purpose, we need to define medial surfaces as Shape Representation Models (SRMs). One of the very first task of a SRM is to offer a visualization of the shape it describes. However, achieving this with a medial surface remains a challenging problem. In this paper, we propose a method to build a mesh that approximates an object only described by a medial surface. To do so, we use a volumetric approach based on the construction of an octree. Then, we mesh the boundary of that octree to get a coarse approximation of the object. Finally, we refine this mesh using an original migration algorithm. Quantitative and qualitative studies, on objects coming from digital modeling and laser scans, shows the efficiency of our method in providing high quality surfaces with a reasonable computational complexity.
Dihedral Angle Mesh Error: a Fast Perception Correlated Distortion Measure for Fixed Connectivity Triangle Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Vása, Libor; Rus, Jan; Eitan Grinspun and Niloy Mitra
In computer graphics, triangle meshes are ubiquitous as a representation of surface models. Processing of this kind of data, such as compression or watermarking, often involves an unwanted distortion of the surface geometry. Advanced processing algorithms are continuously being proposed, aiming at improving performance (compression ratio, watermark robustness and capacity), while minimizing the introduced distortion. In most cases, the final resulting mesh is intended to be viewed by a human observer, and it is therefore necessary to minimise the amount of distortion perceived by the human visual system. However, only recently there have been studies published on subjective experiments in this field, showing that previously used objective error measures exhibit rather poor correlation with the results of subjective experiments. In this paper, we present results of our own large subjective testing aimed at human perception of triangle mesh distortion. We provide an independent confirmation of the previous result by Lavoué et al. that most current metrics perform poorly, with the exception of the MSDM/MSDM2 metrics. We propose a novel metric based on measuring the distortion of dihedral angles, which provides even higher correlation with the results of our experiments and experiments performed by other researchers. Our metric is about two orders of magnitude faster than MSDM/MSDM2, which makes it much more suitable for usage in iterative optimisation algorithms.
Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Eitan Grinspun and Niloy Mitra
Smooth Shape-Aware Functions with Controlled Extrema
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Jacobson, Alec; Weinkauf, Tino; Sorkine, Olga; Eitan Grinspun and Niloy Mitra
Functions that optimize Laplacian-based energies have become popular in geometry processing, e.g. for shape deformation, smoothing, multiscale kernel construction and interpolation. Minimizers of Dirichlet energies, or solutions of Laplace equations, are harmonic functions that enjoy the maximum principle, ensuring no spurious local extrema in the interior of the solved domain occur. However, these functions are only C0 at the constrained points, which often causes smoothness problems. For this reason, many applications optimize higher-order Laplacian energies such as biharmonic or triharmonic. Their minimizers exhibit increasing orders of continuity but lose the maximum principle and show oscillations. In this work, we identify characteristic artifacts caused by spurious local extrema, and provide a framework for minimizing quadratic energies on manifolds while constraining the solution to obey the maximum principle in the solved region. Our framework allows the user to specify locations and values of desired local maxima and minima, while preventing any other local extrema. We demonstrate our method on the smoothness energies corresponding to popular polyharmonic functions and show its usefulness for fast handle-based shape deformation, controllable color diffusion, and topologically-constrained data smoothing.
Feature-Preserving Reconstruction of Singular Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Dey, Tamal K.; Ge, Xiaoyin; Que, Qichao; Safa, Issam; Wang, Lei; Wang, Yusu; Eitan Grinspun and Niloy Mitra
Reconstructing a surface mesh from a set of discrete point samples is a fundamental problem in geometric modeling. It becomes challenging in presence of 'singularities' such as boundaries, sharp features, and non-manifolds. A few of the current research in reconstruction have addressed handling some of these singularities, but a unified approach to handle them all is missing. In this paper we allow the presence of various singularities by requiring that the sampled object is a collection of smooth surface patches with boundaries that can meet or intersect. Our algorithm first identifies and reconstructs the features where singularities occur. Next, it reconstructs the surface patches containing these feature curves. The identification and reconstruction of feature curves are achieved by a novel combination of the Gaussian weighted graph Laplacian and the Reeb graphs. The global reconstruction is achieved by a method akin to the well known Cocone reconstruction, but with weighted Delaunay triangulation that allows protecting the feature samples with balls. We provide various experimental results to demonstrate the effectiveness of our feature-preserving singular surface reconstruction algorithm.
Computing Extremal Quasiconformal Maps
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Weber, Ofir; Myles, Ashish; Zorin, Denis; Eitan Grinspun and Niloy Mitra
Conformal maps are widely used in geometry processing applications. They are smooth, preserve angles, and are locally injective by construction. However, conformal maps do not allow for boundary positions to be prescribed. A natural extension to the space of conformal maps is the richer space of quasiconformal maps of bounded conformal distortion. Extremal quasiconformal maps, that is, maps minimizing the maximal conformal distortion, have a number of appealing properties making them a suitable candidate for geometry processing tasks. Similarly to conformal maps, they are guaranteed to be locally bijective; unlike conformal maps however, extremal quasiconformal maps have sufficient flexibility to allow for solution of boundary value problems. Moreover, in practically relevant cases, these solutions are guaranteed to exist, are unique and have an explicit characterization. We present an algorithm for computing piecewise linear approximations of extremal quasiconformal maps for genus-zero surfaces with boundaries, based on Teichmüller's characterization of the dilatation of extremal maps using holomorphic quadratic differentials.We demonstrate that the algorithm closely approximates the maps when an explicit solution is available and exhibits good convergence properties for a variety of boundary conditions.
Stream Surface Parametrization by Flow-Orthogonal Front Lines
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Schulze, Maik; Germer, Tobias; Rössl, Christian; Theisel, Holger; Eitan Grinspun and Niloy Mitra
The generation of discrete stream surfaces is an important and challenging task in scientific visualization, which can be considered a particular instance of geometric modeling. The quality of numerically integrated stream surfaces depends on a number of parameters that can be controlled locally, such as time step or distance of adjacent vertices on the front line. In addition there is a parameter that cannot be controlled locally: stream surface meshes tend to show high quality, well-shaped elements only if the current front line is "globally" approximately perpendicular to the flow direction. We analyze the impact of this geometric property and present a novel solution a stream surface integrator that forces the front line to be perpendicular to the flow and that generates quaddominant meshes with well-shaped and well-aligned elements. It is based on the integration of a scaled version of the flow field, and requires repeated minimization of an error functional along the current front line. We show that this leads to computing the 1-dimensional kernel of a bidiagonal matrix: a linear problem that can be solved efficiently. We compare our method with existing stream surface integrators and apply it to a number of synthetic and real world data sets.
New Bounds on the Size of Optimal Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Sheehy, Donald R.; Eitan Grinspun and Niloy Mitra
The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing Φ, then the number of vertices in an optimal mesh will be O(Φ<sup>d</sup>n), where d is the input dimension. We give a new analysis of this integral showing that the output size is only<br> θ(n+nlogΦ). The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size O(n).
Soft Maps Between Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Solomon, Justin; Nguyen, Andy; Butscher, Adrian; Ben-Chen, Mirela; Guibas, Leonidas; Eitan Grinspun and Niloy Mitra
The problem of mapping between two non-isometric surfaces admits ambiguities on both local and global scales. For instance, symmetries can make it possible for multiple maps to be equally acceptable, and stretching, slippage, and compression introduce difficulties deciding exactly where each point should go. Since most algorithms for point-to-point or even sparse mapping struggle to resolve these ambiguities, in this paper we introduce soft maps, a probabilistic relaxation of point-to-point correspondence that explicitly incorporates ambiguities in the mapping process. In addition to explaining a continuous theory of soft maps, we show how they can be represented using probability matrices and computed for given pairs of surfaces through a convex optimization explicitly trading off between continuity, conformity to geometric descriptors, and spread. Given that our correspondences are encoded in matrix form, we also illustrate how low-rank approximation and other linear algebraic tools can be used to analyze, simplify, and represent both individual and collections of soft maps.
Time-Discrete Geodesics in the Space of Shells
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Heeren, Behrend; Rumpf, Martin; Wardetzky, Max; Wirth, Benedikt; Eitan Grinspun and Niloy Mitra
Building on concepts from continuum mechanics, we offer a computational model for geodesics in the space of thin shells, with a metric that reflects viscous dissipation required to physically deform a thin shell. Different from previous work, we incorporate bending contributions into our deformation energy on top of membrane distortion terms in order to obtain a physically sound notion of distance between shells, which does not require additional smoothing. Our bending energy formulation depends on the so-called relative Weingarten map, for which we provide a discrete analogue based on principles of discrete differential geometry. Our computational results emphasize the strong impact of physical parameters on the evolution of a shell shape along a geodesic path.
Flexible Developable Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Solomon, Justin; Vouga, Etienne; Wardetzky, Max; Grinspun, Eitan; Eitan Grinspun and Niloy Mitra
We introduce a discrete paradigm for developable surface modeling. Unlike previous attempts at interactive developable surface modeling, our system is able to enforce exact developability at every step, ensuring that users do not inadvertently suggest configurations that leave the manifold of admissible folds of a flat two-dimensional sheet. With methods for navigation of this highly nonlinear constraint space in place, we show how to formulate a discrete mean curvature bending energy measuring how far a given discrete developable surface is from being flat. This energy enables relaxation of user-generated configurations and suggests a straightforward subdivision scheme that produces admissible smoothed versions of bent regions of our discrete developable surfaces.
Growing Least Squares for the Analysis of Manifolds in Scale-Space
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Mellado, Nicolas; Guennebaud, Gaël; Barla, Pascal; Reuter, Patrick; Schlick, Christophe; Eitan Grinspun and Niloy Mitra
We present a novel approach to the multi-scale analysis of point-sampled manifolds of co-dimension 1. It is based on a variant of Moving Least Squares, whereby the evolution of a geometric descriptor at increasing scales is used to locate pertinent locations in scale-space, hence the name "Growing Least Squares". Compared to existing scale-space analysis methods, our approach is the first to provide a continuous solution in space and scale dimensions, without requiring any parametrization, connectivity or uniform sampling. An important implication is that we identify multiple pertinent scales for any point on a manifold, a property that had not yet been demonstrated in the literature. In practice, our approach exhibits an improved robustness to change of input, and is easily implemented in a parallel fashion on the GPU. We compare our method to state-of-the-art scale-space analysis techniques and illustrate its practical relevance in a few application scenarios.
Can Mean-Curvature Flow be Modified to be Non-singular?
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Kazhdan, Michael; Solomon, Jake; Ben-Chen, Mirela; Eitan Grinspun and Niloy Mitra
This work considers the question of whether mean-curvature flow can be modified to avoid the formation of singularities. We analyze the finite-elements discretization and demonstrate why the original flow can result in numerical instability due to division by zero. We propose a variation on the flow that removes the numerical instability in the discretization and show that this modification results in a simpler expression for both the discretized and continuous formulations. We discuss the properties of the modified flow and present empirical evidence that not only does it define a stable surface evolution for genus-zero surfaces, but that the evolution converges to a conformal parameterization of the surface onto the sphere.
Radial Symmetry Detection and Shape Characterization with the Multiscale Area Projection Transform
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Giachetti, Andrea; Lovato, Christian; Eitan Grinspun and Niloy Mitra
We present a novel method to characterize 3D surfaces through the computation of a function called (multiscale) area projection transform, measuring the likelihood of points in the 3D space to be center of radial symmetry at selected scales (radii). The function is derived through a simple geometric framework based on parallel surfaces and can be easily computed on triangulated meshes. It measures locally the area of the surface well approximated by a sphere of radius R centered in the point and can be normalized in order to obtain a scale invariant radial symmetry enhancement transform. This transform can therefore be used to detect and characterize salient regions like approximately spherical and approximately cylindrical surface parts and, being robust against holes and missing parts, it is suitable for real world applications e.g. anatomical features detection. Furthermore, its histograms can be effectively used to build a global shape descriptor that provides very good results in shape retrieval experiments.
Parallel Blue-noise Sampling by Constrained Farthest Point Optimization
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Chen, Renjie; Gotsman, Craig; Eitan Grinspun and Niloy Mitra
We describe a fast sampling algorithm for generating uniformly-distributed point patterns with good blue noise characteristics. The method, based on constrained farthest point optimization, is provably optimal and may be easily parallelized, resulting in an algorithm whose performance/quality tradeoff is superior to other state-of-theart approaches.
Co-Segmentation of 3D Shapes via Subspace Clustering
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Hu, Ruizhen; Fan, Lubin; Liu, Ligang; Eitan Grinspun and Niloy Mitra
We present a novel algorithm for automatically co-segmenting a set of shapes from a common family into consistent parts. Starting from over-segmentations of shapes, our approach generates the segmentations by grouping the primitive patches of the shapes directly and obtains their correspondences simultaneously. The core of the algorithm is to compute an affinity matrix where each entry encodes the similarity between two patches, which is measured based on the geometric features of patches. Instead of concatenating the different features into one feature descriptor, we formulate co-segmentation into a subspace clustering problem in multiple feature spaces. Specifically, to fuse multiple features, we propose a new formulation of optimization with a consistent penalty, which facilitates both the identification of most similar patches and selection of master features for two similar patches. Therefore the affinity matrices for various features are sparsity-consistent and the similarity between a pair of patches may be determined by part of (instead of all) features. Experimental results have shown how our algorithm jointly extracts consistent parts across the collection in a good manner.
Nonrigid Matching of Undersampled Shapes via Medial Diffusion
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Berger, Matthew; Silva, Claudio T.; Eitan Grinspun and Niloy Mitra
We introduce medial diffusion for the matching of undersampled shapes undergoing a nonrigid deformation. We construct a diffusion process with respect to the medial axis of a shape, and use the quantity of heat diffusion as a measure which is both tolerant of missing data and approximately invariant to nonrigid deformations. A notable aspect of our approach is that we do not define the diffusion on the shape's medial axis, or similar medial representation. Instead, we construct the diffusion process directly on the shape. This permits the diffusion process to better capture surface features, such as varying spherical and cylindrical parts, as well as combine with other surface-based diffusion processes. We show how to use medial diffusion to detect intrinsic symmetries, and for computing correspondences between pairs of shapes, wherein shapes contain substantial missing data.

Browse

Browsing 31-Issue 5 by Issue Date

Results Per Page

Sort Options