博文
CudaPre3D: An Alternative Preprocessing Algorithm
|||
CudaPre3D: An Alternative Preprocessing Algorithm for Accelerating 3D Convex Hull Computation on the GPU
https://m.sciencenet.cn/blog-617277-899268.html
上一篇：论文：A Generic Paradigm for Accelerating Laplacian-Based
下一篇：祝贺屠呦呦老师获得诺贝尔奖！
Abstract
In the calculating of convex hulls for point sets, a preprocessing procedure that is to filter the input points by discarding non-extreme points is commonly used to improve the computational efficiency. We previously proposed a quite straightforward preprocessing approach for accelerating 2D convex hull computation on the GPU. In this paper, we extend that algorithm to being used in 3D cases. The basic ideas behind these two preprocessing algorithms are similar: first, several groups of extreme points are found according to the original set of input points and several rotated versions of the input set; then, a convex polyhedron / hull is created using the found extreme points; and finally those interior points that locate inside the formed convex polyhedron / hull are discarded. Experimental results show that: when employing the proposed preprocessing algorithm, it achieves the speedups of about 4x on average and 5x ~ 6x in the best cases over the cases where the proposed approach is not used. In addition, more than 95% input points can be discarded in most experimental tests.
https://m.sciencenet.cn/blog-617277-899268.html
上一篇：论文：A Generic Paradigm for Accelerating Laplacian-Based
下一篇：祝贺屠呦呦老师获得诺贝尔奖！
扫一扫，分享此博文