Perfect Spatial Hashing for Point-cloud-to-mesh Registration
View/ Open
Date
2019Author
Mejia-Parra, Daniel
Lalinde-Pulido, Juan
Sánchez, Jairo R.
Ruiz-Salguero, Oscar
Posada, Jorge
Metadata
Show full item recordAbstract
Point-cloud-to-mesh registration estimates a rigid transformation that minimizes the distance between a point sample of a surface and a reference mesh of such a surface, both lying in different coordinate systems. Point-cloud-to-mesh-registration is an ubiquitous problem in medical imaging, CAD CAM CAE, reverse engineering, virtual reality and many other disciplines. Common registration methods include Iterative Closest Point (ICP), RANdom SAmple Consensus (RANSAC) and Normal Distribution Transform (NDT). These methods require to repeatedly estimate the distance between a point cloud and a mesh, which becomes computationally expensive as the point set sizes increase. To overcome this problem, this article presents the implementation of a Perfect Spatial Hashing for point-cloud-to-mesh registration. The complexity of the registration algorithm using Perfect Spatial Hashing is O(NYxn) (NY : point cloud size, n: number of max. ICP iterations), compared to standard octrees and kd-trees (time complexity O(NY log(NT)xn), NT : reference mesh size). The cost of pre-processing is O(NT +(N3H )2) (N3H : Hash table size). The test results show convergence of the algorithm (error below 7e-05) for massive point clouds / reference meshes (NY = 50k and NT = 28055k, respectively). Future work includes GPU implementation of the algorithm for fast registration of massive point clouds.
BibTeX
@inproceedings {10.2312:ceig.20191202,
booktitle = {Spanish Computer Graphics Conference (CEIG)},
editor = {Casas, Dan and Jarabo, Adrián},
title = {{Perfect Spatial Hashing for Point-cloud-to-mesh Registration}},
author = {Mejia-Parra, Daniel and Lalinde-Pulido, Juan and Sánchez, Jairo R. and Ruiz-Salguero, Oscar and Posada, Jorge},
year = {2019},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-093-2},
DOI = {10.2312/ceig.20191202}
}
booktitle = {Spanish Computer Graphics Conference (CEIG)},
editor = {Casas, Dan and Jarabo, Adrián},
title = {{Perfect Spatial Hashing for Point-cloud-to-mesh Registration}},
author = {Mejia-Parra, Daniel and Lalinde-Pulido, Juan and Sánchez, Jairo R. and Ruiz-Salguero, Oscar and Posada, Jorge},
year = {2019},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-093-2},
DOI = {10.2312/ceig.20191202}
}
Collections
Related items
Showing items related by title, author, creator and subject.
-
Rational Bézier Guarding
Khanteimouri, Payam; Mandad, Manish; Campen, Marcel (The Eurographics Association and John Wiley & Sons Ltd., 2022)We present a reliable method to generate planar meshes of nonlinear rational triangular elements. The elements are guaranteed to be valid, i.e. defined by injective rational functions. The mesh is guaranteed to conform ... -
VA + Embeddings STAR: A State-of-the-Art Report on the Use of Embeddings in Visual Analytics
Huang, Zeyang; Witschard, Daniel; Kucher, Kostiantyn; Kerren, Andreas (The Eurographics Association and John Wiley & Sons Ltd., 2023)Over the past years, an increasing number of publications in information visualization, especially within the field of visual analytics, have mentioned the term ''embedding'' when describing the computational approach. ... -
Teaching Game Programming in an Upper-level Computing Course Through the Development of a C++ Framework and Middleware
Hooper, Steffan; Wünsche, Burkhard C.; Denny, Paul; Luxton-Reilly, Andrew (The Eurographics Association, 2024)The game development industry has a programming skills shortage, with industry surveys often ranking game programming as the top skill-in-demand across small, mid-sized, and large triple-A (AAA) game studios. C++ programming ...