Abstract
Abstract
The geometric kernel defines points inside and on the boundary of a shape, ensuring shape visibility. In this work, two different approaches are given to compute the 3D kernel. First, we introduce a novel approach to approximate the geometric kernel of a 3D-embedded polygon mesh. Our algorithm uses scattered rays to identify sample points on the kernel surface, leveraging them to locate surface vertices. Computing the convex hull of these points yields an approximate kernel representation. Importantly, the output of our method 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, excluding finer boundary details. Adjusting algorithmic settings allows reaching the entire kernel with a proportional speed trade-off. 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 enables incremental addition of kernel vertices and edges in a simple and fast manner. The output is a polyhedron or a polygon mesh representing the kernel itself, not an approximation. Extensive comparisons again with CGAL and Polyhedron Kernel demonstrate the promising performance of our method for computing the kernel polyhedron 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 interpolation, spherical parametrization, and shape decomposition.