.png){kind=icon}
.png){kind=icon}
Return
Exact and Efficient Mesh-Kernel Generation
.png){kind=icon}
PRE
AI
DOI：10.1111/cgf.70187.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
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
Journal
IF:
2.9
Papers:
496
Citations:
1.1W