KerGen: A Kernel Computation Algorithm for 3D Polygon Meshes


ASİLER M., SAHİLLİOĞLU Y.

Computer Graphics Forum, vol.43, no.5, 2024 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 43 Issue: 5
  • Publication Date: 2024
  • Doi Number: 10.1111/cgf.15137
  • Journal Name: Computer Graphics Forum
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Art Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, DIALNET, Civil Engineering Abstracts
  • Keywords: CCS Concepts, • Computing methodologies → Mesh geometry models
  • Middle East Technical University Affiliated: Yes

Abstract

We compute the kernel of a shape embedded in 3D as a polygon mesh, which is defined as the set of all points that have a clear line of sight to every point of the mesh. The KerGen algorithm, short for Kernel Generation, employs efficient plane-plane and line-plane intersections, alongside point classifications based on their positions relative to planes. This approach allows for the incremental addition of kernel vertices and edges to the resulting set in a simple and systematic way. The output is a polygon mesh that represents the surface of the kernel. Extensive comparisons with the existing methods, CGAL and Polyhedron Kernel, demonstrate the remarkable timing performance of our novel additive kernel computation method. Yet another advantage of our additive process is the availability of the partial kernel at any stage, making it useful for specific geometry processing applications such as star decomposition and castable shape reconstruction.