Biharmonic Distance Driven Voronoi Diagrams Restricted on Curved Surfaces

Abstract

Computing surface-based Voronoi diagrams is a fundamental operation in geometry processing, typically relying on either geodesic or straight-line distances as solvers. However, when the input is a 3D model containing thin-plate structures, geodesic distances incur significant computational overhead,whereas straight-line distances can result in ownerless regions. To address this issue, we propose integrating biharmonic embedding distances into the SurfaceVoronoi framework. Specifically, mesh vertices can be embedded into a high-dimensional spectral space, ensuring that the embedding distance closely approximates the straight-line distance between sufficiently close points. In contrast, when points reside on opposite sides of a thin plate, the embedding distance significantly exceeds the straight-line distance, effectively preventing dominance from penetrating through to the opposite side. Our proposed framework offers several advantages: 1) It operates efficiently, as the embedding distance can be rapidly evaluated as a straight-line distance in high-dimensional space. 2) It guarantees the “one site, one region” property, even for models consisting of thinplate structures. 3) It enables high-quality triangulation through iterative repositioning of each site to the centroid of its dominant region. Extensive experiments conducted on benchmark meshes demonstrate these benefits.