- Browse by Title

# SGP06: Eurographics Symposium on Geometry Processing

## Permanent URI for this collection

## Browse

### Browsing SGP06: Eurographics Symposium on Geometry Processing by Title

Now showing 1 - 20 of 26

###### Results Per Page

###### Sort Options

Item Automatic and Interactive Mesh to T-Spline Conversion(The Eurographics Association, 2006) Li, Wan-Chiu; Ray, Nicolas; LÃ©vy, Bruno; Alla Sheffer and Konrad PolthierShow more In Geometry Processing, and more specifically in surface approximation, one of the most important issues is the automatic generation of a quad-dominant control mesh from an arbitrary shape (e.g. a scanned mesh). One of the first fully automatic solutions was proposed by Eck and Hoppe in 1996. However, in the industry, designers still use manual tools (see e.g. cyslice). The main difference between a control mesh constructed by an automatic method and the one designed by a human user is that in the second case, the control mesh follows the features of the model. More precisely, it is well known from approximation theory that aligning the edges with the principal directions of curvature improves the smoothness of the reconstructed surface, and this is what designers intuitively do. In this paper, our goal is to automatically construct a control mesh driven by the anisotropy of the shape, mimicking the mesh that a designer would create manually. The control mesh generated by our method can be used by a wide variety of representations (splines, subdivision surfaces ...). We demonstrate our method applied to the automatic conversion from a mesh of arbitrary topology into a T-Spline surface. Our method first extracts an initial mesh from a PGP (Periodic Global Parameterization). To facilitate user-interaction, we extend the PGP method to take into account optional user-defined information. This makes it possible to locally tune the orientation and the density of the control mesh. The user can also interactively remove edges or sketch additional ones. Then, from this initial control mesh, our algorithm generates a valid T-Spline control mesh by enforcing some validity constraints. The valid T-Spline control mesh is finally fitted to the original surface, using a classic regularized optimization procedure. To reduce the L-infinite approximation error below a user-defined threshold, we iteratively use the T-Spline adaptive local refinement.Show more Item A C2 Polar Jet Subdivision(The Eurographics Association, 2006) Karciauskas, K.; Myles, A.; Peters, J.; Alla Sheffer and Konrad PolthierShow more We describe a subdivision scheme that acts on control nodes that each carry a vector of values. Each vector defines partial derivatives, referred to as jets in the following and subdivision computes new jets from old jets. By default, the jets are automatically initialized from a design mesh. While the approach applies more generally, we consider here only a restricted class of design meshes, consisting of extraordinary nodes surrounded by triangles and otherwise quadrilaterals with interior nodes of valence four. This polar mesh structure is appropriate for surfaces with the combinatorial structure of objects of revolution and for high valences. The resulting surfaces are curvature continuous with good curvature distribution near extraordinary points. Near extraordinary points the surfaces are piecewise polynomial of degree (6,5), away they are standard bicubic splines.Show more Item Constructing Curvature-continuous Surfaces by Blending(The Eurographics Association, 2006) Zorin, Denis; Alla Sheffer and Konrad PolthierShow more In this paper we describe an approach to the construction of curvature-continuous surfaces with arbitrary control meshes using subdivision. Using a simple modification of the widely used Loop subdivision algorithm we obtain perturbed surfaces which retain the overall shape and appearance of Loop subdivision surfaces but no longer have flat spots or curvature singularities at extraordinary vertices. Our method is computationally efficient and can be easily added to any existing subdivision code.Show more Item A Decomposition-based Representation for 3D Simplicial Complexes(The Eurographics Association, 2006) Hui, Annie; Vaczlavik, Lucas; Floriani, Leila De; Alla Sheffer and Konrad PolthierShow more We define a new representation for non-manifold 3D shapes described by three-dimensional simplicial complexes, that we call the Double-Level Decomposition (DLD) data structure. The DLD data structure is based on a unique decomposition of the simplicial complex into nearly manifold parts, and encodes the decomposition in an efficient and powerful two-level representation. It is compact, and it supports efficient topological navigation through adjacencies. It also provides a suitable basis for geometric reasoning on non-manifold shapes. We describe an algorithm to decompose a 3D simplicial complex into nearly manifold parts. We discuss how to build the DLD data structure from a description of a 3D complex as a collection of tetrahedra, dangling triangles and wire edges, and we present algorithms for topological navigation. We present a thorough comparison with existing representations for 3D simplicial complexes.Show more Item Defining and Computing Curve-skeletons with Medial Geodesic Function(The Eurographics Association, 2006) Dey, Tamal K.; Sun, Jian; Alla Sheffer and Konrad PolthierShow more Many applications in geometric modeling, computer graphics, visualization and computer vision benefit from a reduced representation called curve-skeletons of a shape. These are curves possibly with branches which compactly represent the shape geometry and topology. The lack of a proper mathematical definition has been a bottleneck in developing and applying the the curve-skeletons. A set of desirable properties of these skeletons has been identified and the existing algorithms try to satisfy these properties mainly through a procedural definition. We define a function called medial geodesic on the medial axis which leads to a methematical definition and an approximation algorithm for curve-skeletons. Empirical study shows that the algorithm is robust against noise, operates well with a single user parameter, and produces curve-skeletons with the desirable properties. Moreover, the curveskeletons can be associated with additional attributes that follow naturally from the definition. These attributes capture shape eccentricity, a local measure of how far a shape is away from a tubular one.Show more Item Designing Quadrangulations with Discrete Harmonic Forms(The Eurographics Association, 2006) Tong, Y.; Alliez, P.; Cohen-Steiner, D.; Desbrun, M.; Alla Sheffer and Konrad PolthierShow more We introduce a framework for quadrangle meshing of discrete manifolds. Based on discrete differential forms, our method hinges on extending the discrete Laplacian operator (used extensively in modeling and animation) to allow for line singularities and singularities with fractional indices. When assembled into a singularity graph, these line singularities are shown to considerably increase the design flexibility of quad meshing. In particular, control over edge alignments and mesh sizing are unique features of our novel approach. Another appeal of our method is its robustness and scalability from a numerical viewpoint: we simply solve a sparse linear system to generate a pair of piecewise-smooth scalar fields whose isocontours form a pure quadrangle tiling, with no T-junctions.Show more Item Error Bounds and Optimal Neighborhoods for MLS Approximation(The Eurographics Association, 2006) Lipman, Yaron; Cohen-Or, Daniel; Levin, David; Alla Sheffer and Konrad PolthierShow more In recent years, the moving least-square (MLS) method has been extensively studied for approximation and reconstruction of surfaces. The MLS method involves local weighted least-squares polynomial approximations, using a fast decaying weight function. The local approximating polynomial may be used for approximating the underlying function or its derivatives. In this paper we consider locally supported weight functions, and we address the problem of the optimal choice of the support size. We introduce an error formula for the MLS approximation process which leads us to developing two tools: One is a tight error bound independent of the data. The second is a data dependent approximation to the error function of the MLS approximation. Furthermore, we provide a generalization to the above in the presence of noise. Based on the above bounds, we develop an algorithm to select an optimal support size of the weight function for the MLS procedure. Several applications such as differential quantities estimation and up-sampling of point clouds are presented. We demonstrate by experiments that our approach outperforms the heuristic choice of support size in approximation quality and stabilitShow more Item Folding Meshes: Hierarchical Mesh Segmentation based on Planar Symmetry(The Eurographics Association, 2006) Simari, Patricio; Kalogerakis, Evangelos; Singh, Karan; Alla Sheffer and Konrad PolthierShow more Meshes representing real world objects, both artist-created and scanned, contain a high level of redundancy due to (possibly approximate) planar reflection symmetries, either global or localized to different subregions. An algorithm is presented for detecting such symmetries and segmenting the mesh into the symmetric and remaining regions. The method, inspired by techniques in Computer Vision, has foundations in robust statistics and is resilient to structured outliers which are present in the form of the non symmetric regions of the data. Also introduced is an application of the method: the folding tree data structure. The structure encodes the non redundant regions of the original mesh as well as the reflection planes and is created by the recursive application of the detection method. This structure can then be unfolded to recover the original shape. Applications include mesh compression, repair, skeletal extraction of objects of known symmetry as well as mesh processing acceleration by limiting computation to non redundant regions and propagation of results.Show more Item Hierarchical Error-Driven Approximation of Implicit Surfaces from Polygonal Meshes(The Eurographics Association, 2006) Kanai, Takashi; Ohtake, Yutaka; Kase, Kiwamu; Alla Sheffer and Konrad PolthierShow more This paper describes an efficient method for the hierarchical approximation of implicit surfaces from polygonal meshes. A novel error function between a polygonal mesh and an implicit surface is proposed. This error function is defined so as to be scale-independent from its global behavior as well as to be area-sensitive on local regions. An implicit surface tightly-fitted to polygons can be computed by the least-squares fitting method. Furthermore, this function can be represented as the quadric form, which realizes a compact representation of such an error metric. Our novel algorithm rapidly constructs a SLIM (Sparse Low-degree IMplicit) surface which is a recently developed non-conforming hierarchical implicit surface representation. Users can quickly obtain a set of implicit surfaces with arbitrary resolution according to errors from a SLIM surface.Show more Item Loop Subdivision with Curvature Control(The Eurographics Association, 2006) Ginkel, I.; Umlauf, G.; Alla Sheffer and Konrad PolthierShow more In this paper the problem of curvature behavior around extraordinary points of a Loop subdivision surface is addressed. A variant of Loop s algorithm with small stencils is used that generates surfaces with bounded curvature and prescribed elliptic or hyperbolic behavior. We present two different techniques that avoid the occurrence of hybrid configurations, so that an elliptic or hyperbolic shape can be guaranteed. The first technique uses a symmetric modification of the initial control-net to avoid hybrid shapes in the vicinity of an extraordinary point. To keep the difference between the original and the modified mesh as small as possible the changes are formulated as correction stencils and spread to a finite number of subdivision steps. The second technique is based on local optimization in the frequency domain. It provides more degrees of freedom and so more control over the global shape.Show more Item Nonobtuse Remeshing and Mesh Decimation(The Eurographics Association, 2006) Li, J. Y. S.; Zhang, H.; Alla Sheffer and Konrad PolthierShow more Quality meshing in 2D and 3D domains is an important problem in geometric modeling and scientific computing. We are concerned with triangle meshes having only nonobtuse angles. Specifically, we propose a solution for guaranteed nonobtuse remeshing and nonobtuse mesh decimation. Our strategy for the remeshing problem is to first convert an input mesh, using a modified Marching Cubes algorithm, into a rough approximate mesh that is guaranteed to be nonobtuse. We then apply iterative "deform-to-fit" via constrained optimization to obtain a high-quality approximation, where the search space is restricted to be the set of nonobtuse meshes having a fixed connectivity. With a detailed nonobtuse mesh in hand, we apply constrained optimization again, driven by a quadric-based error, to obtain a hierarchy of nonobtuse meshes via mesh decimation.Show more Item On Transfinite Barycentric Coordinates(The Eurographics Association, 2006) Belyaev, Alexander; Alla Sheffer and Konrad PolthierShow more A general construction of transfinite barycentric coordinates is obtained as a simple and natural generalization of Floater's mean value coordinates [Flo03, JSW05b]. The Gordon-Wixom interpolation scheme [GW74] and transfinite counterparts of discrete harmonic and Wachspress-Warren coordinates are studied as particular cases of that general construction. Motivated by finite element/volume applications, we study capabilities of transfinite barycentric interpolation schemes to approximate harmonic and quasi-harmonic functions. Finally we establish and analyze links between transfinite barycentric coordinates and certain inverse problems of differential and convex geometry.Show more Item Overfitting Control for Surface Reconstruction(The Eurographics Association, 2006) Lee, Yunjin; Lee, Seungyong; Ivrissimtzis, Ioannis; Seidel, Hans-Peter; Alla Sheffer and Konrad PolthierShow more This paper proposes a general framework for overfitting control in surface reconstruction from noisy point data. The problem we deal with is how to create a model that will capture as much detail as possible and simultaneously avoid reproducing the noise of the input points. The proposed framework is based on extra-sample validation. It is fully automatic and can work in conjunction with any surface reconstruction algorithm. We test the framework with a Radial Basis Function algorithm, Multi-level Partition of Unity implicits, and the Power Crust algorithm.Show more Item Partial Matching of 3D Shapes with Priority-Driven Search(The Eurographics Association, 2006) Funkhouser, T.; Shilane, P.; Alla Sheffer and Konrad PolthierShow more Priority-driven search is an algorithm for retrieving similar shapes from a large database of 3D objects. Given a query object and a database of target objects, all represented by sets of local 3D shape features, the algorithm produces a ranked list of the c best target objects sorted by how well any subset of k features on the query match features on the target object. To achieve this goal, the system maintains a priority queue of potential sets of feature correspondences (partial matches) sorted by a cost function accounting for both feature dissimilarity and the geometric deformation. Only partial matches that can possibly lead to the best full match are popped off the queue, and thus the system is able to find a provably optimal match while investigating only a small subset of potential matches. New methods based on feature distinction, feature correspondences at multiple scales, and feature difference ranking further improve search time and retrieval performance. In experiments with the Princeton Shape Benchmark, the algorithm provides significantly better classification rates than previously tested shape matching methods while returning the best matches in a few seconds per query.Show more Item Poisson Surface Reconstruction(The Eurographics Association, 2006) Kazhdan, Michael; Bolitho, Matthew; Hoppe, Hugues; Alla Sheffer and Konrad PolthierShow more We show that surface reconstruction from oriented points can be cast as a spatial Poisson problem. This Poisson formulation considers all the points at once, without resorting to heuristic spatial partitioning or blending, and is therefore highly resilient to data noise. Unlike radial basis function schemes, our Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution reduces to a well conditioned sparse linear system. We describe a spatially adaptive multiscale algorithm whose time and space complexities are proportional to the size of the reconstructed model. Experimenting with publicly available scan data, we demonstrate reconstruction of surfaces with greater detail than previously achievable.Show more Item PriMo: Coupled Prisms for Intuitive Surface Modeling(The Eurographics Association, 2006) Botsch, Mario; Pauly, Mark; Gross, Markus; Kobbelt, Leif; Alla Sheffer and Konrad PolthierShow more We present a new method for 3D shape modeling that achieves intuitive and robust deformations by emulating physically plausible surface behavior inspired by thin shells and plates. The surface mesh is embedded in a layer of volumetric prisms, which are coupled through non-linear, elastic forces. To deform the mesh, prisms are rigidly transformed to satisfy user constraints while minimizing the elastic energy. The rigidity of the prisms prevents degenerations even under extreme deformations, making the method numerically stable. For the underlying geometric optimization we employ both local and global shape matching techniques. Our modeling framework allows for the specification of various geometrically intuitive parameters that provide control over the physical surface behavior. While computationally more involved than previous methods, our approach significantly improves robustness and simplifies user interaction for large, complex deformations.Show more Item Probabilistic Fingerprints for Shapes(The Eurographics Association, 2006) Mitra, Niloy J.; Guibas, Leonidas; Giesen, Joachim; Pauly, Mark; Alla Sheffer and Konrad PolthierShow more We propose a new probabilistic framework for the efficient estimation of similarity between 3D shapes. Our framework is based on local shape signatures and is designed to allow for quick pruning of dissimilar shapes, while guaranteeing not to miss any shape with significant similarities to the query model in shape database retrieval applications. Since directly evaluating 3D similarity for large collections of signatures on shapes is expensive and impractical, we propose a suitable but compact approximation based on probabilistic fingerprints which are computed from the shape signatures using Rabin s hashing scheme and a small set of random permutations. We provide a probabilistic analysis that shows that while the preprocessing time depends on the complexity of the model, the fingerprint size and hence the query time depends only on the desired confidence in our estimated similarity. Our method is robust to noise, invariant to rigid transforms, handles articulated deformations, and effectively detects partial matches. In addition, it provides important hints about correspondences across shapes which can then significantly benefit other algorithms that explicitly align the models. We demonstrate the utility of our method on a wide variety of geometry processing applications.Show more Item A Quadratic Bending Model for Inextensible Surfaces(The Eurographics Association, 2006) Bergou, Miklos; Wardetzky, Max; Harmon, David; Zorin, Denis; Grinspun, Eitan; Alla Sheffer and Konrad PolthierShow more Relating the intrinsic Laplacian to the mean curvature normal, we arrive at a model for bending of inextensible surfaces. Due to its constant Hessian, our isometric bending model reduces cloth simulation times up to three-fold.Show more Item Reconstruction with Voronoi Centered Radial Basis Functions(The Eurographics Association, 2006) Samozino, M.; Alexa, M.; Alliez, P.; Yvinec, M.; Alla Sheffer and Konrad PolthierShow more We consider the problem of reconstructing a surface from scattered points sampled on a physical shape. The sampled shape is approximated as the zero level set of a function. This function is defined as a linear combination of compactly supported radial basis functions. We depart from previous work by using as centers of basis functions a set of points located on an estimate of the medial axis, instead of the input data points. Those centers are selected among the vertices of the Voronoi diagram of the sample data points. Being a Voronoi vertex, each center is associated with a maximal empty ball. We use the radius of this ball to adapt the support of each radial basis function. Our method can fit a user-defined budget of centers: The selected subset of Voronoi vertices is filtered using the notion of lambda medial axis, then clustered to fit the allocated budget.Show more Item Rectangular Multi-Chart Geometry Images(The Eurographics Association, 2006) Carr, Nathan A.; Hoberock, Jared; Crane, Keenan; Hart, John C.; Alla Sheffer and Konrad PolthierShow more Many mesh parameterization algorithms have focused on minimizing distortion and utilizing texture area, but few have addressed issues related to processing a signal on the mesh surface.We present an algorithm which partitions a mesh into rectangular charts while preserving a one-to-one texel correspondence across chart boundaries. This mapping permits any computation on the mesh surface which is typically carried out on a regular grid, and prevents seams by ensuring resolution continuity along the boundary. These features are also useful for traditional texture applications such as surface painting where continuity is important. Distortion is comparable to other parameterization schemes, and the rectangular charts yield efficient packing into a texture atlas. We apply this parameterization to texture synthesis, fluid simulation, mesh processing and storage, and locating geodesics.Show more