GPU-based efficient computation of power diagram
| Autor: | Benzhu Xu, Gui Zhiqiang, Liping Zheng, Fei Yue, Gaofeng Zhang, Ruiwen Cai |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Coupling
Parallel rendering Computer science Flooding algorithm Computation General Engineering 020207 software engineering 02 engineering and technology Computer Graphics and Computer-Aided Design Bottleneck Computational science Power (physics) Human-Computer Interaction 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Power diagram Graphics ComputingMethodologies_COMPUTERGRAPHICS |
| Zdroj: | Computers & Graphics. 80:29-36 |
| ISSN: | 0097-8493 |
| DOI: | 10.1016/j.cag.2019.03.011 |
| Popis: | Power diagrams are widely used in graphics and engineering. One of the most complex operations defined on the centroidal capacity-constrained power diagrams is the geometrical construction, which takes more than 50% of the total computing time. In order to overcome this performance bottleneck, we propose a novel GPU-based power diagram construction algorithm. To this end, we first introduce the jump flooding algorithm for parallel rendering of the power diagram, and present an approach for extracting the geometrical vertices and edges. Next, we introduce two novel GPU-based algorithms to improve the computational performance. The first algorithm allows a hybrid GPU-CPU implementation by coupling the existing CPU-based algorithm while the second algorithm is a pure GPU implementation for the platforms where GPU hardware is capable of significant speedups. In our implementation, we utilize the discrete Lloyd’s algorithm for centroidal constraints and a GPU-based analytical algorithm for weights and capacities. Experiment results show that our approach improves the effciency of the power diagram construction up to several orders of magnitude. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect