High-Performance Delaunay Triangulation for Many-Core Computers
Loading...
Date
2014
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
We present an efficient implementation of a Dwyer-style Delaunay triangulation algorithm that runs in O(N) expected time. An implicit quad-tree is constructed directly from the floating point bit patterns of the input points by sorting the corresponding Morton codes with a radix sorting procedure. This unique structure adapts elegantly to any (non-)uniform distribution of input points and increases the accuracy of the merging calculations by grouping floating point values with similar bit patterns. Our implementation allows for easy parallelization and we demonstrate a record construction speed of one Billion Delaunay triangles in just 8s on a many-core SMP machine.
Description
@inproceedings{10.2312:hpg.20141098https::/diglib.eg.org:443/handle/10.2312/hpg.20141098,
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics},
editor = {Ingo Wald and Jonathan Ragan-Kelley},
title = {{High-Performance Delaunay Triangulation for Many-Core Computers}},
author = {Fuetterling, Valentin and Lojewski, Carsten and Pfreundt, Franz-Josef},
year = {2014},
publisher = {The Eurographics Association},
ISSN = {2079-8679},
ISBN = {978-3-905674-60-6},
DOI = {10.2312/hpg.20141098https://diglib.eg.org:443/handle/10.2312/hpg.20141098}
}