1,721,046 research outputs found
Nonobtuse Remeshing and Mesh Decimation
No full textQuality 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.Symposium on Geometry Processin
A Decomposition-based Representation for 3D Simplicial Complexes
No full textWe 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.Symposium on Geometry Processin
Error Bounds and Optimal Neighborhoods for MLS Approximation
No full textIn 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 stabilitSymposium on Geometry Processin
Poisson Surface Reconstruction
No full textWe 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.Symposium on Geometry Processin
Constructing Curvature-continuous Surfaces by Blending
No full textIn 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.Symposium on Geometry Processin
Partial Matching of 3D Shapes with Priority-Driven Search
No full textPriority-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.Symposium on Geometry Processin
A Quadratic Bending Model for Inextensible Surfaces
No full textRelating 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.Symposium on Geometry Processin
Rectangular Multi-Chart Geometry Images
No full textMany 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.Symposium on Geometry Processin
Spherical Barycentric Coordinates
No full textWe develop spherical barycentric coordinates. Analogous to classical, planar barycentric coordinates that describe the positions of points in a plane with respect to the vertices of a given planar polygon, spherical barycentric coordinates describe the positions of points on a sphere with respect to the vertices of a given spherical polygon. In particular, we introduce spherical mean value coordinates that inherit many good properties of their planar counterparts. Furthermore, we present a construction that gives a simple and intuitive geometric interpretation for classical barycentric coordinates, like Wachspress coordinates, mean value coordinates, and discrete harmonic coordinates. One of the most interesting consequences is the possibility to construct mean value coordinates for arbitrary polygonal meshes. So far, this was only possible for triangular meshes. Furthermore, spherical barycentric coordinates can be used for all applications where only planar barycentric coordinates were available up to now. They include Bézier surfaces, parameterization, free-form deformations, and interpolation of rotations.Symposium on Geometry Processin
On Transfinite Barycentric Coordinates
No full textA 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.Symposium on Geometry Processin
- …
