Abstract
Abstract
The geometric kernel defines points inside or on the boundary of a shape, ensuring shape visibility. In this work, two different approaches are given to compute the kernel in 3D. First, we introduce a novel approach to approximate the kernel of a polygon mesh. Our algorithm uses scattered rays to identify sample points on the kernel surface, leveraging them to identify surface vertices. Computing the convex hull of these points yields an approximate kernel representation. Importantly, the output remains inside or on the kernel surface. Comparative evaluations against CGAL and Polyhedron Kernel demonstrate the superior computational speed and high accuracy of our method. Unlike the others, 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. Additionally, adjusting the algorithmic settings also enables the computation of the kernel itself with a trade-off in computational speed. Second, we give another novel approach, the KerGen algorithm (Kernel Generation), to compute the kernel. KerGen employs efficient plane-plane and line-plane intersections, alongside point classifications based on positions relative to planes. This approach allows for the incremental addition of kernel vertices and edges to the resulting set in a simple and systematic way. The output is a polygon mesh that represents the surface of the kernel, not an approximation. Extensive comparisons again with CGAL and Polyhedron Kernel demonstrate the remarkable performance of our method for computing the kernel faster and more practically. Both approaches promptly and accurately identify an empty kernel for non-star-shaped configurations. In summary, these approaches may open up avenues for the solution of many geometry processing problems, such as shape deformation, shape simplification, spherical parametrization, star decomposition and castable shape reconstruction.