期刊
COMPUTERS & GRAPHICS-UK
卷 80, 期 -, 页码 29-36出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cag.2019.03.011
关键词
Power diagram; GPU accelerate; Centroidal; Capacity
资金
- National Key Research and Development Plan [2016YFC0800100]
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. (C) 2019 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据