Exact and Efficient Mesh-Kernel Generation
| dc.contributor.author | Nehring-Wirxel, Julius | en_US |
| dc.contributor.author | Kern, Paul | en_US |
| dc.contributor.author | Trettner, Philip | en_US |
| dc.contributor.author | Kobbelt, Leif | en_US |
| dc.contributor.editor | Attene, Marco | en_US |
| dc.contributor.editor | Sellán, Silvia | en_US |
| dc.date.accessioned | 2025-06-20T07:39:21Z | |
| dc.date.available | 2025-06-20T07:39:21Z | |
| dc.date.issued | 2025 | |
| dc.description.abstract | 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. | en_US |
| dc.description.number | 5 | |
| dc.description.sectionheaders | Mesh Processing | |
| dc.description.seriesinformation | Computer Graphics Forum | |
| dc.description.volume | 44 | |
| dc.identifier.doi | 10.1111/cgf.70187 | |
| dc.identifier.issn | 1467-8659 | |
| dc.identifier.pages | 11 pages | |
| dc.identifier.uri | https://doi.org/10.1111/cgf.70187 | |
| dc.identifier.uri | https://diglib.eg.org/handle/10.1111/cgf70187 | |
| dc.publisher | The Eurographics Association and John Wiley & Sons Ltd. | en_US |
| dc.rights | Attribution 4.0 International License | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | Computing methodologies → Mesh geometry models; Theory of computation → Linear programming; Applied computing → Computer-aided design | |
| dc.subject | Computing methodologies → Mesh geometry models | |
| dc.subject | Theory of computation → Linear programming | |
| dc.subject | Applied computing → Computer | |
| dc.subject | aided design | |
| dc.title | Exact and Efficient Mesh-Kernel Generation | en_US |
Files
Original bundle
1 - 1 of 1