SGP12: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Flexible Developable Surfaces
[meta data] [files:
Solomon, Justin
;
Vouga, Etienne
;
Wardetzky, Max
;
Grinspun, Eitan
Smooth Shape-Aware Functions with Controlled Extrema
[meta data] [files:
Jacobson, Alec
;
Weinkauf, Tino
;
Sorkine, Olga
Nonrigid Matching of Undersampled Shapes via Medial Diffusion
[meta data] [files:
Berger, Matthew
;
Silva, Claudio T.
Microtiles: Extracting Building Blocks from Correspondences
[meta data] [files:
Kalojanov, Javor
;
Bokeloh, Martin
;
Wand, Michael
;
Guibas, Leonidas
;
Seidel, Hans-Peter
;
Slusallek, Philipp
Finding Surface Correspondences Using Symmetry Axis Curves
[meta data] [files:
Liu, Tianqiang
;
Kim, Vladimir G.
;
Funkhouser, Thomas
From A Medial Surface To A Mesh
[meta data] [files:
Delamé, Thomas
;
Roudet, Céline
;
Faudot, Dominique
Soft Maps Between Surfaces
[meta data] [files:
Solomon, Justin
;
Nguyen, Andy
;
Butscher, Adrian
;
Ben-Chen, Mirela
;
Guibas, Leonidas
Shape-Up: Shaping Discrete Geometry with Projections
[meta data] [files:
Bouaziz, Sofien
;
Deuss, Mario
;
Schwartzburg, Yuliy
;
Weise, Thibaut
;
Pauly, Mark
Radial Symmetry Detection and Shape Characterization with the Multiscale Area Projection Transform
[meta data] [files:
Giachetti, Andrea
;
Lovato, Christian
Computing Extremal Quasiconformal Maps
[meta data] [files:
Weber, Ofir
;
Myles, Ashish
;
Zorin, Denis
Growing Least Squares for the Analysis of Manifolds in Scale-Space
[meta data] [files:
Mellado, Nicolas
;
Guennebaud, Gaël
;
Barla, Pascal
;
Reuter, Patrick
;
Schlick, Christophe
Co-Segmentation of 3D Shapes via Subspace Clustering
[meta data] [files:
Hu, Ruizhen
;
Fan, Lubin
;
Liu, Ligang
Dihedral Angle Mesh Error: a Fast Perception Correlated Distortion Measure for Fixed Connectivity Triangle Meshes
[meta data] [files:
Vása, Libor
;
Rus, Jan
Stream Surface Parametrization by Flow-Orthogonal Front Lines
[meta data] [files:
Schulze, Maik
;
Germer, Tobias
;
Rössl, Christian
;
Theisel, Holger
Mean Curvature Skeletons
[meta data] [files:
Tagliasacchi, Andrea
;
Alhashim, Ibraheem
;
Olson, Matt
;
Zhang, Hao
Time-Discrete Geodesics in the Space of Shells
[meta data] [files:
Heeren, Behrend
;
Rumpf, Martin
;
Wardetzky, Max
;
Wirth, Benedikt
Can Mean-Curvature Flow be Modified to be Non-singular?
[meta data] [files:
Kazhdan, Michael
;
Solomon, Jake
;
Ben-Chen, Mirela
Fast and Robust Normal Estimation for Point Clouds with Sharp Features
[meta data] [files:
Boulch, Alexandre
;
Marlet, Renaud
Parallel Blue-noise Sampling by Constrained Farthest Point Optimization
[meta data] [files:
Chen, Renjie
;
Gotsman, Craig
Feature-Preserving Reconstruction of Singular Surfaces
[meta data] [files:
Dey, Tamal K.
;
Ge, Xiaoyin
;
Que, Qichao
;
Safa, Issam
;
Wang, Lei
;
Wang, Yusu
Browse
Recent Submissions
Item Preface and Table of Contents(The Eurographics Association and Blackwell Publishing Ltd., 2012) Eitan Grinspun and Niloy MitraItem Flexible Developable Surfaces(The Eurographics Association and Blackwell Publishing Ltd., 2012) Solomon, Justin; Vouga, Etienne; Wardetzky, Max; Grinspun, Eitan; Eitan Grinspun and Niloy MitraWe 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.Item 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 MitraFunctions 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.Item 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 MitraWe 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.Item Microtiles: Extracting Building Blocks from Correspondences(The Eurographics Association and Blackwell Publishing Ltd., 2012) Kalojanov, Javor; Bokeloh, Martin; Wand, Michael; Guibas, Leonidas; Seidel, Hans-Peter; Slusallek, Philipp; Eitan Grinspun and Niloy MitraIn this paper, we develop a theoretical framework for characterizing shapes by building blocks. We address two questions: First, how do shape correspondences induce building blocks? For this, we introduce a new representation for structuring partial symmetries (partial self-correspondences), which we call "microtiles". Starting from input correspondences that form point-wise equivalence relations, microtiles are obtained by grouping connected components of points that share the same set of symmetry transformations. The decomposition is unique, requires no parameters beyond the input correspondences, and encodes the partial symmetries of all subsets of the input. The second question is: What is the class of shapes that can be assembled from these building blocks? Here, we specifically consider r-similarity as correspondence model, i.e., matching of local r-neighborhoods. Our main result is that the microtiles of the partial r-symmetries of an object S can build all objects that are (r+e)-similar to S for any e>0. Again, the construction is unique. Furthermore, we give necessary conditions for a set of assembly rules for the pairwise connection of tiles. We describe a practical algorithm for computing microtile decompositions under rigid motions, a corresponding prototype implementation, and conduct a number of experiments to visualize the structural properties in practice.Item 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 MitraIn 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.Item 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 MitraMedial 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.Item New Bounds on the Size of Optimal Meshes(The Eurographics Association and Blackwell Publishing Ltd., 2012) Sheehy, Donald R.; Eitan Grinspun and Niloy MitraThe 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).Item 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 MitraThe 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.Item Modeling Polyhedral Meshes with Affine Maps(The Eurographics Association and Blackwell Publishing Ltd., 2012) Vaxman, Amir; Eitan Grinspun and Niloy MitraWe offer a framework for editing and modeling of planar meshes, focusing on planar quad, and hexagonaldominant meshes, which are held in high demand in the field of architectural design. Our framework manipulates these meshes by affine maps that are assigned per-face, and which naturally ensure the planarity of these faces throughout the process, resulting in a linear subspace of compatible planar deformations for any given mesh. Our modeling metaphors include classical handle-based editing, mesh interpolation, and shape-space exploration, all of which allow for an intuitive way to produce new polyhedral and near-polyhedral meshes by editing.Item 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 MitraWe 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.Item 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 MitraWe 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.Item Computing Extremal Quasiconformal Maps(The Eurographics Association and Blackwell Publishing Ltd., 2012) Weber, Ofir; Myles, Ashish; Zorin, Denis; Eitan Grinspun and Niloy MitraConformal 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.Item 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 MitraWe 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.Item 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 MitraWe 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.Item 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 MitraIn 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.Item 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 MitraThe 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.Item Mean Curvature Skeletons(The Eurographics Association and Blackwell Publishing Ltd., 2012) Tagliasacchi, Andrea; Alhashim, Ibraheem; Olson, Matt; Zhang, Hao; Eitan Grinspun and Niloy MitraInspired by recent developments in contraction-based curve skeleton extraction, we formulate the skeletonization problem via mean curvature flow (MCF). While the classical application of MCF is surface fairing, we take advantage of its area-minimizing characteristic to drive the curvature flow towards the extreme so as to collapse the input mesh geometry and obtain a skeletal structure. By analyzing the differential characteristics of the flow, we reveal that MCF locally increases shape anisotropy. This justifies the use of curvature motion for skeleton computation, and leads to the generation of what we call "mean curvature skeletons". To obtain a stable and efficient discretization, we regularize the surface mesh by performing local remeshing via edge splits and collapses. Simplifying mesh connectivity throughout the motion leads to more efficient computation and avoids numerical instability arising from degeneracies in the triangulation. In addition, the detection of collapsed geometry is facilitated by working with simplified mesh connectivity and monitoring potential non-manifold edge collapses. With topology simplified throughout the flow, minimal post-processing is required to convert the collapsed geometry to a curve. Formulating skeletonization via MCF allows us to incorporate external energy terms easily, resulting in a constrained flow. We define one such energy term using the Voronoi medial skeleton and obtain a medially centred curve skeleton. We call the intermediate results of our skeletonization motion meso-skeletons; these consist of a mixture of curves and surface sheets as appropriate to the local 3D geometry they capture.Item 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 MitraBuilding 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.Item 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 MitraThis 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.Item 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 MitraThis 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.Item 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 MitraWe 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.Item 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 MitraReconstructing 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.