Exact and Efficient Mesh-Kernel Generation

Julius Nehring-Wirxel

doi:10.1111/cgf.70187

Return

Exact and Efficient Mesh-Kernel Generation

2025-08-28

PRE

Julius Nehring-Wirxel

P. Kern

Philip Trettner

Leif Kobbelt

DOI：10.1111/cgf.70187

Original

Original request for help

Save

Abstract

En 中文

The 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.

Keywords:

CCS Concepts

• Computing methodologies → Mesh geometry models

• Theory of computation → Linear programming

• Applied computing → Computer-aided design