PinMesh—Fast and exact 3D point location queries using a uniform grid
| Autor: | Marcus V. A. Andrade, Wenli Li, Salles V. G. Magalhães, W. Randolph Franklin |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Computer science
Subroutine 020208 electrical & electronic engineering General Engineering Parallel algorithm 020207 software engineering 02 engineering and technology Grid Computer Graphics and Computer-Aided Design Human-Computer Interaction Exact algorithm Shared memory 0202 electrical engineering electronic engineering information engineering Preprocessor Point location Polygon mesh Algorithm |
| Zdroj: | Computers & Graphics. 58:1-11 |
| ISSN: | 0097-8493 |
| DOI: | 10.1016/j.cag.2016.05.017 |
| Popis: | This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multi-material 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µs. Graphical abstractDisplay Omitted HighlightsAn exact algorithm for point location in 3D triangulations or meshes is presented.Roundoff errors are completely avoided by computing with rational numbers.Special cases, or degeneracies, are handled correctly with Simulation of Simplicity.Preprocessing time is constant per input triangle and query time is almost constant.It parallelizes well and easily processes tens of millions of triangles. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect