77 results
Search Results
Now showing 1 - 10 of 77
Item Sparse Iterative Closest Point(The Eurographics Association and Blackwell Publishing Ltd., 2013) Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark; Yaron Lipman and Hao ZhangRigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.Item Non-rigid 3D Shape Retrieval via Sparse Representation(The Eurographics Association, 2013) Wan, Lili; Li, Shuai; Miao, Zhenjiang J.; Cen, Yigang G.; Bruno Levy and Xin Tong and KangKang YinShape descriptor design is an important but challenging problem for non-rigid 3D shape retrieval. Recently, bagof- words based methods are widely used to integrate a model's local shape descriptors into a global histogram. In this paper, we present a new method to pool the local shape descriptors into a global shape descriptor by means of sparse representation. Firstly, we employ heat kernel signature (HKS) to depict the multi-scale local shape. Then, for each model in the training dataset, we take the HKSs corresponding to its mesh vertices to serve as training signals, and thus an over-complete dictionary can be learned from them. Finally, the HKSs of each 3D model are sparsely coded based on the learned dictionary, and such sparse representations can be further integrated to form an object-level shape descriptor. Moreover, we conduct extensive experiments on the state-of-the-art benchmarks, wherein comprehensive evaluations state our method can achieve better performance than other bag-of-words based approaches.Item Watertight Scenes from Urban LiDAR and Planar Surfaces(The Eurographics Association and Blackwell Publishing Ltd., 2013) Kreveld, Marc van; Lankveld, Thijs van; Veltkamp, Remco C.; Yaron Lipman and Hao ZhangThe demand for large geometric models is increasing, especially of urban environments. This has resulted in production of massive point cloud data from images or LiDAR. Visualization and further processing generally require a detailed, yet concise representation of the scene's surfaces. Related work generally either approximates the data with the risk of over-smoothing, or interpolates the data with excessive detail. Many surfaces in urban scenes can be modeled more concisely by planar approximations. We present a method that combines these polygons into a watertight model. The polygon-based shape is closed with free-form meshes based on visibility information. To achieve this, we divide 3-space into inside and outside volumes by combining a constrained Delaunay tetrahedralization with a graph-cut. We compare our method with related work on several large urban LiDAR data sets. We construct similar shapes with a third fewer triangles to model the scenes. Additionally, our results are more visually pleasing and closer to a human modeler's description of urban scenes using simple boxes.Item A Tracking Approach for the Skeletonization of Tubular Parts of 3D Shapes(The Eurographics Association, 2013) Garro, Valeria; Giachetti, Andrea; Michael Bronstein and Jean Favre and Kai HormannIn this paper we propose a new simple and efficient method to characterize shapes by segmenting their elongated parts and characterizing them with their centerlines. We call it Tubular Section Tracking, because it consists of slicing the interested volume along different directions, tracking centroids of the extracted sections with approximately constant centroid position, area and eccentricity and refining the extracted lines with a post processing step removing bad branches and centering, joining and extending the relevant ones. We show that, even using just a few slicing directions (in some cases even just three perpendicular directions), the method is able to obtain good results, approximately pose independent and that the extracted lines can be more informative on the relevant feature of the objects than the classical skeletal lines extracted as subsets of the medial axis. Estimated lines can be used to segment shapes into meaningful parts and compute useful parameters (e.g. length, diameters).Item Consistent Surface Model for SPH-based Fluid Transport(ACM SIGGRAPH / Eurographics Association, 2013) Orthmann, Jens; Hochstetter, Hendrik; Bader, Julian; Bayraktar, Serkan; Kolb, Andreas; Theodore Kim and Robert SumnerSurface effects play an essential role in fluid simulations. A vast number of dynamics including wetting of surfaces, cleansing, and foam dynamics are based on surface-surface and surface-bulk interactions, which in turn rely on a robust surface computation. In this paper we introduce a conservative Lagrangian formulation of surface effects based upon incompressible smoothed particle hydrodynamics (SPH). The key concept of our approach is to realize an implicit definition of the fluid's (free) surface by assigning each particle a value estimating its surface area. Based on this consistent surface representation, a conservative coupling of bulk and surface is achieved. We demonstrate the applicability and robustness of our approach for several types of surface-relevant effects including adsorption, diffusion and reaction kinetics.Item Ray-Traced Collision Detection: Interpenetration Control and Multi-GPU Performance(The Eurographics Association, 2013) Lehericey, Francois; Gouranton, Valérie; Arnaldi, Bruno; Betty Mohler and Bruno Raffin and Hideo Saito and Oliver StaadtWe proposed in [LGA13] an iterative ray-traced collision detection algorithm (IRTCD) that exploits spatial and temporal coherency and proved to be computationally efficient but at the price of some geometrical approximations that allow more interpenetration than needed. In this paper, we present two methods to efficiently control and reduce the interpenetration without noticeable computation overhead. The first method predicts the next potentially colliding vertices. These predictions are used to make our IRTCD algorithm more robust to the above-mentioned approximations, therefore reducing the errors up to 91%. We also present a ray re-projection algorithm that improves the physical response of ray-traced collision detection algorithm. This algorithm also reduces, up to 52%, the interpenetration between objects in a virtual environment. Our last contribution shows that our algorithm, when implemented on multi-GPUs architectures, is far faster.Item Fabrication-aware Design with Intersecting Planar Pieces(The Eurographics Association and Blackwell Publishing Ltd., 2013) Schwartzburg, Yuliy; Pauly, Mark; I. Navazo, P. PoulinWe propose a computational design approach to generate 3D models composed of interlocking planar pieces. We show how intricate 3D forms can be created by sliding the pieces into each other along straight slits, leading to a simple construction that does not require glue, screws, or other means of support. To facilitate the design process, we present an abstraction model that formalizes the main geometric constraints imposed by fabrication and assembly, and incorporates conditions on the rigidity of the resulting structure.We show that the tight coupling of constraints makes manual design highly nontrivial and introduce an optimization method to automate constraint satisfaction based on an analysis of the constraint relation graph. This algorithm ensures that the planar parts can be fabricated and assembled. We demonstrate the versatility of our approach by creating 3D toy models, an architectural design study, and several examples of functional furniture.Item SymPan: 3D Model Pose Normalization via Panoramic Views and Reflective Symmetry(The Eurographics Association, 2013) Sfikas, Konstantinos; Pratikakis, Ioannis; Theoharis, Theoharis; Umberto Castellani and Tobias Schreck and Silvia Biasotti and Ioannis Pratikakis and Afzal Godil and Remco VeltkampA novel pose normalization method, based on panoramic views and reflective symmetry, is presented. Initially, the surface of a 3D model is projected onto the lateral surface of a circumscribed cylinder, aligned with the primary principal axis of space. Based on this cylindrical projection, a normals' deviation map is extracted and using an octree-based search strategy, the rotation which optimally aligns the primary principal axis of the 3D model and the cylinder's axis is computed. The 3D model's secondary principal axis is then aligned with the secondary principal axis of space in a similar manner. The proposed method is incorporated in a hybrid scheme, that serves as the pose normalization method in a state-of-the-art 3D model retrieval system. The effectiveness of this system, using the hybrid pose normalization scheme, is evaluated in terms of retrieval accuracy and the results clearly show improved performance against current approaches.Item Initial Steps for the Coupling of JavaScript Physics Engines with X3DOM(The Eurographics Association, 2013) Huber, Linda; Jan Bender and Jeremie Dequidt and Christian Duriez and Gabriel ZachmannDuring the past years, first physics engines based on JavaScript have been developed for web applications. These are capable of displaying virtual scenes much more realistically. Thus, new application areas can be opened up, particularly with regard to the coupling of X3DOM-based 3D models. The advantage is that web-based applications are easily accessible to all users. Furthermore, such engines allow popularizing and presenting simulation results without having to compile large simulation software. This paper provides an overview and a comparison of existing JavaScript physics engines. It also introduces a guideline for the derivation of a physical model based on a 3D model in X3DOM. The aim of using JavaScript physics engines is not only to virtually visualize designed products but to simulate them as well. The user is able to check and test an individual product virtually and interactively in a browser according to physically correct behavior regarding gravity, friction or collision. It can be used for verification in the design phase or web-based training purposes.Item Level of Detail for Real-Time Volumetric Terrain Rendering(The Eurographics Association, 2013) Scholz, Manuel; Bender, Jan; Dachsbacher, Carsten; Michael Bronstein and Jean Favre and Kai HormannTerrain rendering is an important component of many GIS applications and simulators. Most methods rely on heightmap-based terrain which is simple to acquire and handle, but has limited capabilities for modeling features like caves, steep cliffs, or overhangs. In contrast, volumetric terrain models, e.g. based on isosurfaces can represent arbitrary topology. In this paper, we present a fast, practical and GPU-friendly level of detail algorithm for large scale volumetric terrain that is specifically designed for real-time rendering applications. Our algorithm is based on a longest edge bisection (LEB) scheme. The resulting tetrahedral cells are subdivided into four hexahedra, which form the domain for a subsequent isosurface extraction step. The algorithm can be used with arbitrary volumetric models such as signed distance fields, which can be generated from triangle meshes or discrete volume data sets. In contrast to previous methods our algorithm does not require any stitching between detail levels. It generates crack free surfaces with a good triangle quality. Furthermore, we efficiently extract the geometry at runtime and require no preprocessing, which allows us to render infinite procedural content with low memory consumption.