Nehring-Wirxel, JuliusKern, PaulTrettner, PhilipKobbelt, LeifAttene, MarcoSellán, Silvia2025-06-202025-06-2020251467-8659https://doi.org/10.1111/cgf.70187https://diglib.eg.org/handle/10.1111/cgf70187The mesh kernel for a star-shaped mesh is a convex polyhedron given by the intersection of all half-spaces defined by the faces of the input mesh. For all non-star-shaped meshes, the kernel is empty. We present a method to robustly and efficiently compute the kernel of an input triangle mesh by using exact plane-based integer arithmetic to compute the mesh kernel. We make use of several ways to accelerate the computation time. Since many applications just require information if a non-empty mesh kernel exists, we also propose a method to efficiently determine whether a kernel exists by developing an exact plane-based linear program solver. We evaluate our method on a large dataset of triangle meshes and show that in contrast to previous methods, our approach is exact and robust while maintaining a high performance. It is on average two orders of magnitude faster than other exact state-of-the-art methods and often about one order of magnitude faster than non-exact methods.Attribution 4.0 International LicenseComputing methodologies → Mesh geometry models; Theory of computation → Linear programming; Applied computing → Computer-aided designComputing methodologies → Mesh geometry modelsTheory of computation → Linear programmingApplied computing → Computeraided designExact and Efficient Mesh-Kernel Generation10.1111/cgf.7018711 pages