Recently, Katz et al. have shown how visibility information for a point cloud may be estimated by the so-called HPR operator. In a nutshell, the operator consists of a simple transformation of the cloud followed by a convex hull computation. Since convex hulls take $O(n log n)$ time to compute in the worst case, this method has been considered impractical for real-time rendering of medium to large point clouds. In this paper, we describe a GPU implementation of an approximate convex-hull algorithm that runs in $O(n+k)$ time, where $k$ is a parameter of the method. Experiments show that the method is suitable for real-time rendering and partial reconstruction of point clouds with millions of points.
展开▼
机译：最近，Katz等人。已经显示了所谓的HPR运营商如何估算点云的可见性信息。简而言之，运算符包括对云的简单转换，然后进行凸包计算。由于在最坏的情况下凸包需要$ O（n log n）$的时间进行计算，因此该方法被认为不适合实时渲染中到大型点云。在本文中，我们描述了在$ O（n + k）$时间内运行的近似凸包算法的GPU实现，其中$ k $是该方法的参数。实验表明，该方法适用于具有数百万个点的点云的实时渲染和局部重建。
展开▼
