Parallel Post-processing of Restricted Voronoi Diagram on Thin Sheet Models. (June 2023)

• Record Type: Journal Article
• Authors: Zong, Chen; Wang, Pengfei; Yan, Dong-Ming; Chen, Shuangmin; Xin, Shiqing; Tu, Changhe; Hu, Qiang
• Is Part Of: Computer aided design. Volume 159(2023)
• Publication Date: 2023-06
• Subjects: Restricted Voronoi Diagram -- Thin sheet model -- Parallelization; 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.2023.103511
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Given a thin-sheet surface S in 3D, as well as a collection of sites located on S, it is a fundamental operation in digital geometry processing to partition S into a set of constituent surface patches in terms of proximity. Geodesic Voronoi diagram (GVD) provides a theoretically sound solution to this problem, but has limited use due to its high computational cost. Restricted Voronoi Diagram (RVD) considers the partitioning of S based on the straight-line distance. Under general conditions, RVD can yield a practicable solution with much less running time. However, when the input model contains thin sheets but the sites are sparse, RVD may present some issues due to the significant difference between the straight-line distance and the geodesic distance. The resulting flawed RVD cells limit the use of RVDs on further geometry processing occasions. In this paper, we address two kinds of commonly encountered issues: (1) a site dominates multiple disconnected regions, and (2) a site dominates one single region but the region is kidney-shaped. Both of the issues occur frequently, on a thin-sheet model with a relatively small number of sites. The first kind of flawed RVD cells occurs when the dominance of a site penetrates the other side of the surface. For such flawed RVD cells, it is easy to separate the remote parts from the principal region, based on connectivity. The second kind of flawed RVD cells occurs when a site is nearby a geometry edge and its dominating area crosses the geometry edge, leading to a kidney-shaped region. We observe that for a roughly flat RVD cell, the sum of its turning angles is close to 2 π . For a kidney-shaped region, however, the total angle becomes much larger than 2 π, which inspires us to develop an angle-based checking rule. We further propose a concept of "virtual site" to cut the region at the narrowest part and re-partition the ownerless region by the surrounding sites (may be virtual). All of the above-mentioned operations can be parallelized and generally only require lightweight computational relative to the RVD. After post-processing, the improved RVD has inconspicuous difference from the GVD, and is of much higher quality than LRVD (Yan et al., 2014) and EDBVD (Xin et al., 2022). We present its usage in intrinsic Delaunay triangulation (IDT) and centroidal Voronoi tessellation (CVT) based meshing. Highlights: Propose a parallel post-processing algorithm to fix the issues of the RVD. We classify flawed RVD cells into two types T1 and T2. For T1, isolate one or more ownerless regions from the principal region. For T2, cut the kidney-shaped region into two parts and introduce a virtual site. We further give a set of strategies for re-partitioning ownerless regions locally.