ناحيه بندي مدل هندسي با استفاده از تقريب دياگرام ورونوي و تشكيل نواحي فازي

Geometric Model Segmentation using Approximate Voronoi Diagram and Fuzzy Regions Construction

مسيله ي ناحيه بندي و افراز مدل هاي سه بعدي همواره به عنوان يكي از كليدي ترين ابزارهاي مورد استفاده در بسياري از كاربردهاي طراحي به كمك كامپيوتر و گرافيك كامپيوتري مطرح بوده است. يكي از پركاربردترين روش هاي ناحيه بندي كه امكان افراز مدل به صورت بهينه ي سراسري را فراهم مي كند، الگوريتم تكرارپذير است. الگوريتم تكرارپذير، روشي پارامتريك است كه براساس الگوريتم لويد و تشكيل دياگرام ورونوي بر روي داده هاي ابر نقاط، مدل را به صورت بهينه ناحيه بندي مي كند. مهمترين عيب اين روش كه كاربرد آن را محدود مي كند، زمان بر بودن آن است. در اين مقاله، با بهره گيري از مفهوم ناحيه بندي فازي، راه كاري جهت تعيين تعداد نواحي مورد نياز براي افراز مدل و در نتيجه ناحيه بندي به صورت غيرپارامتريك و بدون نياز به تنظيمات اوليه ي كاربر پيشنهاد شده است. همچنين با استفاده از تقريب دياگرام ورونوي و تشكيل زيرناحيه هاي فازي بر روي مدل روشي جديد براي بدست آوردن ناحيه بندي بهينه در زماني كوتاه تر نسبت به ساير الگوريتم هاي تكرارپذير ارايه مي شود. روش پيشنهادي جهت اعتبار سنجي بر روي مدلي استاندارد پياده سازي شده است. مشـاهده مي گردد كه نتايج بدست آمده نسبت به نتايج حاصل از الگوريتم تكرارپذير بهبود قابل ملاحظه اي دارد كه نشان دهنده ي كارآيي اين روش در ناحيه-بندي مدل هاي سه بعدي است.

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 is a parametric method based on Lloyd algorithm, which segments the model in an optimized way by plotting the Voronoi diagram through the points cloud data. The main disadvantage of this method is the time-consuming problem which limits its application. In this paper, by employing the nature of fuzzy segmentation a solution has been proposed to specify the number of regions required for model’s partitioning and to carry out the nonparametric segmentation without the need for user’s initial settings. Additionally, utilizing the approximate Voronoi diagram and fuzzy regions construction, a novel method for obtaining the optimized segmentation in a shorter time interval in comparison with other iterative algorithms has been presented. The proposed method has been implemented in a standard model for validation. It has been observed that the obtained results have remarkable improvements relative to the results from the iterative algorithm, which demonstrates the efficiency of this method in segmentation of 3D models.