3D geometric kernel computation in polygon mesh structures☆

This paper introduces a novel approach to compute the geometric kernel of a polygon mesh embedded in 3D. The geometric kernel defines the set of points inside or on the shape's boundary, ensuring visibility of the entire shape. The proposed method utilizes scattered rays to identify a sufficient number of sample points on the kernel surface and subsequently leverages these points to locate as many surface vertices as possible. By computing the convex hull of these identified points, we derive an approximation of the kernel. Notably, the output of our method consists exclusively of interior or boundary points of the actual kernel. Comparative evaluations against established CGAL and Polyhedron Kernel algorithms highlight our method's superior computational speed and high approximation accuracy. The parametric structure of our solution allows for different levels of accuracy to be obtained, enabling the user to tailor the approximation to their specific needs. This property sets our algorithm apart from others and provides greater flexibility in its use. Additionally, adjusting the algorithmic settings also enables the computation of the kernel itself with a tradeoff in computational speed. Furthermore, our algorithm swiftly and accurately identifies an empty kernel for non-star-shaped configurations.