Volume 31 (2012)

Permanent URI for this community

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

Browse

Now showing 1 - 8 of 8

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.
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.
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.
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.
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.
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.
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.
Tessellation-Independent Smooth Shadow Boundaries
(The Eurographics Association and Blackwell Publishing Ltd., 2012) Mattausch, Oliver; Scherzer, Daniel; Wimmer, Michael; Igarashi, Takeo; Fredo Durand and Diego Gutierrez
We propose an efficient and light-weight solution for rendering smooth shadow boundaries that do not reveal the tessellation of the shadow-casting geometry. Our algorithm reconstructs the smooth contours of the underlying mesh and then extrudes shadow volumes from the smooth silhouettes to render the shadows. For this purpose we propose an improved silhouette reconstruction using the vertex normals of the underlying smooth mesh. Then our method subdivides the silhouette loops until the contours are sufficiently smooth and project to smooth shadow boundaries. This approach decouples the shadow smoothness from the tessellation of the geometry and can be used to maintain equally high shadow quality for multiple LOD levels. It causes only a minimal change to the fill rate, which is the well-known bottleneck of shadow volumes, and hence has only small overhead.

Browse

Browsing Volume 31 (2012) by Subject "Computational Geometry and Object Modeling"

Results Per Page

Sort Options