Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
PinMesh – Fast and exact 3D point location queries using a uniform grid.
Computer & Graphics Journal, special issue on Shape Modeling International 2016, 58:1–11, August 2016.
(online 17 May). Awarded a reproducibility stamp, \url http://www.reproducibilitystamp.com/.
URL: http://www.sciencedirect.com/science/article/pii/S0097849316300607, doi:10.1016/j.cag.2016.05.017.
[full text] [slides] [BibTeX▼]
This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multimaterial mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently handle the largest available meshes. Because of a 2-level uniform grid, the expected preprocessing time is linear in the input size, and the code parallelizes well on a shared memory machine. Querying time is almost independent of the dataset size. PinMesh uses exact arithmetic with rational numbers to prevent roundoff errors, and symbolic perturbation with Simulation of Simplicity (SoS) to handle geometric degeneracies or special cases. PinMesh is intended to be a subroutine in more complex algorithms. It can preprocess a dataset and perform 1 million queries up to 27 times faster than RCT (Relative Closest Triangle), the current fastest algorithm. Preprocessing a sample dataset with 50 million triangles took only 14 elapsed seconds on a 16-core Xeon processor. The mean query time was 0.6 microseconds.