Efficient Parallel Thinning of 3d Objects on the Body-centered Cubic Lattice. (October 2022)

• Record Type: Journal Article
• Authors: Brunner, David; Brunnett, Guido; Kronfeld, Thomas; Strand, Robin
• Is Part Of: Computer aided design. Volume 151(2022)
• Publication Date: 2022-10
• Subjects: Body-centered cubic grid -- Parallel thinning -- Skeletonization; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103328
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We consider thinning methods to extract one dimensional skeletons from discrete objects defined on the body-centered cubic (bcc) lattice. In Strand (2004), a condition has been given that guarantees the preservation of the object's topology in such a thinning process. In this paper, we present stronger conditions that even allow the topological invariant point removal in a parallelized process. These conditions for p -simplicity can be efficiently evaluated which leads to a very fast thinning process. We show that p -simplicity is a new concept that cannot be obtained by adapting the checking plane conditions of Tsao and Fu to the bcc lattice. Furthermore, we introduce distance information and an optional pruning mechanism into the thinning process to improve the quality of the resulting skeletons. The presented results show that our method generates high quality skeletons that reproduce the symmetries of the models even under the condition of added noise and contain only very few spurious branches. The presented running times demonstrate the linear run-time behavior of our algorithm and the speedup that is achieved by the parallelization. Graphical abstract: Highlights: Curve-like skeletons of closed 3D objects are used for many different purposes in computer graphics. Thinning is a method to extract the skeleton which requires the object to be discretized on a lattice. Only for thinning on the cubic grid parallel algorithms are available. We present the first parallel thinning algorithm on the bcc lattice. Our method generates high quality skeletons that contain only very few spurious branches. The skeletons reproduce the symmetries of the models even under the condition of added noise.