34 results
Search Results
Now showing 1 - 10 of 34
Item Robust Filtering of Noisy Scattered Point Data(The Eurographics Association, 2005) Schall, Oliver; Belyaev, Alexander; Seidel, Hans-Peter; Marc Alexa and Szymon Rusinkiewicz and Mark Pauly and Matthias ZwickerIn this paper, we develop a method for robust filtering of a noisy set of points sampled from a smooth surface. The main idea of the method consists of using a kernel density estimation technique for point clustering. Specifically, we use a mean-shift based clustering procedure. With every point of the input data we associate a local likelihood measure capturing the probability that a 3D point is located on the sampled surface. The likelihood measure takes into account the normal directions estimated at the scattered points. Our filtering procedure suppresses noise of different amplitudes and allows for an easy detection of outliers which are then automatically removed by simple thresholding. The remaining set of maximum likelihood points delivers an accurate point-based approximation of the surface. We also show that while some established meshing techniques often fail to reconstruct the surface from original noisy point scattered data, they work well in conjunction with our filtering method.Item Topology Preserving Surface Extraction Using Adaptive Subdivision(The Eurographics Association, 2004) Varadhan, Gokul; Krishnan, Shankar; Sriram, TVN; Manocha, Dinesh; Roberto Scopigno and Denis ZorinWe address the problem of computing a topology preserving isosurface from a volumetric grid using Marching Cubes for geometry processing applications. We present a novel topology preserving subdivision algorithm to generate an adaptive volumetric grid. Our algorithm ensures that every grid cell satisfies two local geometric criteria: a complex cell criterion and a star-shaped criterion. We show that these two criteria are sufficient to ensure that the surface extracted from the grid using Marching Cubes has the same genus and connectedness as that of the exact isosurface. We use our subdivision algorithm for accurate boundary evaluation of CSG combinations of polyhedra and low degree algebraic primitives, translational motion planning, model simplification and remeshing. The running time of our algorithm varies between a few seconds for simple models composed of a few thousand triangles to tens of seconds for complex polyhedral models represented using hundreds of thousands of triangles.Item Spherical Barycentric Coordinates(The Eurographics Association, 2006) Langer, Torsten; Belyaev, Alexander; Seidel, Hans-Peter; Alla Sheffer and Konrad PolthierWe 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.Item An Edge-based Approach to Adaptively Refining a Mesh for Cloth Deformation(The Eurographics Association, 2009) Simnett, Timothy J. R.; Laycock, Stephen D.; Day, Andy M.; Wen Tang and John CollomosseSimulating cloth in real-time is a challenging endeavour due to the number of triangles necessary to depict the potentially frequent changes in curvature, in combination with the physics calculations which model the deformations. To alleviate the costs, adaptive methods are often employed to refine the mesh in areas of high curvature, however, they do not often consider a decimation or coarsening of areas which were refined previously. In addition to this, the triangulation and consistency checks required to maintain a continuous mesh can be prohibitively time consuming when attempting to simulate larger pieces of cloth. In this paper we present an efficient edge-based approach to adaptively refine and coarsen a dynamic mesh, with the aim to exploit the varied nature of cloth by trading the level of detail in flat parts for increased detail in the curved regions of the cloth. An edge-based approach enables fast incremental refinement and coarsening, whereby only two triangles need updating on each split or join of an edge. The criteria for refinement includes curvature, edge length and edge collisions. Simple collision detection is performed allowing interactions between the cloth and the other objects in the environment.Item Meshing Point Clouds Using Spherical Parameterization(The Eurographics Association, 2004) Zwicker, M.; Gotsman, C.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a simple method for meshing a 3D point cloud to a manifold genus-0 mesh. Our approach is based on recent methods for spherical embedding of planar graphs, where we use instead a k-nearest neighborhood graph of the point cloud. Our approach proceeds in two steps: We first embed the neighborhood graph on a sphere using an iterative procedure, minimizing the tangential Laplacian. Then we triangulate the embedded points and apply the resulting mesh connectivity to the input points. Besides meshing, spherical embedding of point clouds may also be used for other applications such as texture mapping or morphing.Item Elastic Secondary Deformations by Vector Field Integration(The Eurographics Association, 2007) Funck, Wolfram von; Theisel, Holger; Seidel, Hans-Peter; Alexander Belyaev and Michael GarlandWe present an approach for elastic secondary deformations of shapes described as triangular meshes. The deformations are steered by the simulation of a low number of simple mass-spring sets. The result of this simulation is used to define time-dependent divergence-free vector fields whose numerical path line integration gives the new location of each vertex. This way the deformation is guaranteed to be volume-preserving and without self-intersections, giving plausible elastic deformations. Due to a GPU implementation, the deformation can be obtained in real-time for fairly complex shapes. The approach also avoids unwanted intersections in the case of collisions in the primary animation. We demonstrate its accuracy, stableness and usefulness for different kinds of primary animations/deformations.Item A Benchmarking Framework for Static Collision Detection(The Eurographics Association, 2008) Diktas, Engin Deniz; Sahiner, Ali Vahit; Ik Soo Lim and Wen TangPerformanceof static collision detection queries depends on the type of the hierarchy chosen as well as the relative positioning of the colliding objects. In order to evaluate the performance of bounding volume hierarchies, relevant criteria that affect the query performance need to be determined and the sample space should be generated accordingly. In this paper we present a benchmarking framework for evaluating the performance of various static collision detection algorithms. In this framework, instances of a moving rigid object are placed on the surface of another instance of the same object fixed at a certain position, where the contact occurs for the first time. Then by offsetting the surface inwards (outwards) we generate new surfaces that are at a certain fixed negative (positive) distance to the original surface. Placing the moving object on these offset surfaces makes the object penetrate (approach) the fixed object at a fixed distance. For offset surface generation we create a signed distance field and run marching cubes algorithm on it.Item A Streaming Algorithm for Surface Reconstruction(The Eurographics Association, 2007) Allegre, Remi; Chaine, Raphaelle; Akkouche, Samir; Alexander Belyaev and Michael GarlandWe present a streaming algorithm for reconstructing closed surfaces from large non-uniform point sets based on a geometric convection technique. Assuming that the sample points are organized into slices stacked along one coordinate axis, a triangle mesh can be efficiently reconstructed in a streamable layout with a controlled memory footprint. Our algorithm associates a streaming 3D Delaunay triangulation data-structure with a multilayer version of the geometric convection algorithm. Our method can process millions of sample points at the rate of 50k points per minute with 350 MB of main memory.Item Robust Reconstruction of Watertight 3D Models from Non-uniformly Sampled Point Clouds Without Normal Information(The Eurographics Association, 2006) Hornung, Alexander; Kobbelt, Leif; Alla Sheffer and Konrad PolthierWe present a new volumetric method for reconstructing watertight triangle meshes from arbitrary, unoriented point clouds. While previous techniques usually reconstruct surfaces as the zero level-set of a signed distance function, our method uses an unsigned distance function and hence does not require any information about the local surface orientation. Our algorithm estimates local surface confidence values within a dilated crust around the input samples. The surface which maximizes the global confidence is then extracted by computing the minimum cut of a weighted spatial graph structure. We present an algorithm, which efficiently converts this cut into a closed, manifold triangle mesh with a minimal number of vertices. The use of an unsigned distance function avoids the topological noise artifacts caused by misalignment of 3D scans, which are common to most volumetric reconstruction techniques. Due to a hierarchical approach our method efficiently produces solid models of low genus even for noisy and highly irregular data containing large holes, without loosing fine details in densely sampled regions. We show several examples for different application settings such as model generation from raw laser-scanned data, image-based 3D reconstruction, and mesh repair.Item A Dynamic Surface Reconstruction Framework for Large Unstructured Point Sets(The Eurographics Association, 2006) Allègre, Rémi; Chaine, Raphaëlle; Akkouche, Samir; Mario Botsch and Baoquan Chen and Mark Pauly and Matthias ZwickerWe present a method to reconstruct simplified mesh surfaces from large unstructured point sets, extending recent work on dynamic surface reconstruction. The method consists of two core components: an efficient selective reconstruction algorithm, based on geometric convection, that simplifies the input point set while reconstructing a surface, and a local update algorithm that dynamically refines or coarsens the reconstructed surface according to specific local sampling constraints. We introduce a new data-structure that significantly accelerates the original selective reconstruction algorithm and makes it possible to handle point set models with millions of sample points. Our data-structure mixes a kd-tree with the Delaunay triangulation of the selected points enriched with a sparse subset of landmark sample points. This design efficiently responds to the specific spatial location issues of the geometric convection algorithm. We also develop an out-of-core implementation of the method, that permits to seamlessly reconstruct and interactively update simplified mesh surfaces from point sets that do not fit into main memory.