Relaxed Parallel Priority Queue with Filter Levels for Parallel Mesh Decimation

Abstract

We propose a novel implementation of a parallel priority queue in the context of multithreaded mesh decimation. Previous parallel priority queues either have a major bottleneck when extracting nodes, cannot guarantee reasonable node quality for the extracted nodes, or cannot be used for mesh decimation. Our data structure allows the extraction of multiple high-priority elements at the same time. For this, we relax the requirement of returning the highest priority element to returning an element that belongs to the top k elements. We demonstrate its use in the context of parallel mesh decimation and show that our decimated mesh is almost indistinguishable from an optimally decimated mesh while being 2 to 2.6 times faster than a naive parallel priority queue implementation.