Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

High-Performance Delaunay Triangulation for Many-Core Computers

: Fütterling, V.; Lojewski, C.; Pfreundt, F.-J.


Wald, I. ; European Association for Computer Graphics -EUROGRAPHICS-; Association for Computing Machinery -ACM-, Special Interest Group on Computer Graphics and Interactive Techniques -SIGGRAPH-:
High Performance Graphics 2014 : Lyon, France, 2014. Proceedings
Aire-la-Ville: Eurographics Association, 2014
ISBN: 978-3-905674-60-6
Symposium on High Performance Graphics <2014, Lyon>
Conference Paper
Fraunhofer ITWM ()

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.