Iterative Mesh Segmentation Using Approximated Voronoi Diagram

Mesh segmentation and partitioning of 3D models have always been significant as one of the most structural tools used in many applications of CAD and computer graphics. One of the most versatile of these algorithms, which is capable of optimum segmentation of model, is the iterative algorithm. It segments the model in an optimized way based on Lloyd algorithm, and by forming Voronoi diagram through points cloud data. The most remarkable disadvantage of iterative algorithms is their long solving time which is caused by iteration of algorithm in order to yield the best segmentation or, in other words, the best Voronoi diagram on the model. In this paper, using an approximation of Voronoi diagram, a method has been presented to obtain the optimum segmentation in a shorter time relative to other iterative algorithms.