Delaunay refinement
میش جنریشن میں، ڈیلونے ریفائنمنٹس میش جنریشن کے لیے الگورتھم ہیں جو ایک ان پٹ کی جیومیٹری میں اسٹینر پوائنٹس کو جوڑنے کے اصول پر مبنی ہیں، اس طرح سے جو ڈیلونے مثلث کا سبب بنتا ہے یا میشنگ ایپلی کیشن کی معیار کی ضروریات کو پورا کرنے کے لیے آگمینٹڈ ان پٹ کے محدود ڈیلونے مثلث کا سبب بنتا ہے۔ ڈیلونی ریفائنمنٹ کے طریقوں میں چیؤ اور روپرٹ کے طریقے شامل ہیں۔ چیو کا دوسرا الگورتھم چیو کا دوسرا الگورتھم ایک پیس وائز لکیری سسٹم (پی ایل ایس) لیتا ہے اور صرف معیاری مثلثوں کا ایک محدود ڈیلونی مثلث واپس کرتا ہے جہاں مثلث میں کم سے کم زاویے سے معیار کی وضاحت کی جاتی ہے۔ تین جہتی جگہ میں سرایت شدہ میشنگ سطحوں کے لیے ایل پال چیو کے ذریعہ تیار کردہ، چیو کے دوسرے الگورتھم کو بعض صورتوں میں روپرٹ کے الگورتھم پر عملی فوائد کی وجہ سے دو جہتی میش جنریٹر کے طور پر اپنایا گیا ہے اور یہ آزادانہ طور پر دستیاب مثلث پیکیج میں نافذ کردہ ڈیفالٹ کوالٹی میش جنریٹر ہے۔ چیو کا دوسرا الگورتھم تقریبا 28.6 ڈگری تک کم سے کم زاویے کے ساتھ مقامی فیچر سائز کی درجہ بندی والے میش کو ختم کرنے اور تیار کرنے کی ضمانت دیتا ہے۔ الگورتھم ان پٹ عمودی کے محدود ڈیلونی مثلث سے شروع ہوتا ہے۔ ہر مرحلے پر، ناقص معیار کے مثلث کا دائرہ مرکز مثلث میں ایک رعایت کے ساتھ داخل کیا جاتا ہے: اگر دائرہ مرکز ناقص معیار کے مثلث کے طور پر کسی ان پٹ حصے کے مخالف سمت میں واقع ہے، تو حصے کا وسط نقطہ داخل کیا جاتا ہے۔ مزید برآں، اصل حصے کی ڈائمیٹرل گیند کے اندر (اس کے تقسیم ہونے سے پہلے) پہلے داخل کیے گئے سرکم سینٹرز کو مثلث سے ہٹا دیا جاتا ہے۔ سرکم سینٹر کا اندراج اس وقت تک دہرایا جاتا ہے جب تک کہ کوئی ناقص معیار کا مثلث موجود نہ ہو۔ رپرٹ کا الگورتھم رپرٹ کا الگورتھم ایک پلینر سیدھی لکیر کا گراف لیتا ہے (یا دو سے زیادہ طول و عرض میں ایک ٹکڑے ٹکڑے والا لکیری نظام) اور صرف معیاری مثلثوں کا مطابقت پذیر ڈیلونی مثلث واپس کرتا ہے۔ مثلث کو ناقص معیار سمجھا جاتا ہے اگر اس کا دائرہ اور مختصر ترین کنارے کا تناسب کسی مقررہ حد سے زیادہ ہو۔ 1990 کی دہائی کے اوائل میں جم روپرٹ نے دریافت کیا، "دو جہتی معیار کی میش نسل کے لیے روپرٹ کا الگورتھم شاید پہلا نظریاتی طور پر ضمانت شدہ میشنگ الگورتھم ہے جو عملی طور پر واقعی تسلی بخش ہے۔" محرک کمپیوٹر کے تخروپن جیسے کمپیوٹیشنل فلوئڈ ڈائنامکس کرتے وقت، ایک ماڈل جیسے ونگ سیکشن کے 2 ڈی آؤٹ لائن سے شروع ہوتا ہے۔ 2 ڈی محدود عنصر کے طریقہ کار کے لیے ان پٹ مثلث کی شکل میں ہونا چاہیے جو تمام جگہ کو بھرتا ہے، اور ہر مثلث کو ایک قسم کے مواد سے بھرا جانا چاہیے-اس مثال میں، یا تو "ہوا" یا "ونگ"۔ لمبے، پتلے مثلثوں کو درست طریقے سے نقل نہیں کیا جا سکتا۔ تخروپن کا وقت عام طور پر مثلثوں کی تعداد کے متناسب ہوتا ہے، اور اس لیے کوئی مثلثوں کی تعداد کو کم کرنا چاہتا ہے، جبکہ پھر بھی معقول حد تک درست نتائج دینے کے لیے کافی مثلثوں کا استعمال کرتا ہے-عام طور پر غیر ساختہ گرڈ کا استعمال کرتے ہوئے۔ کمپیوٹر روپرٹ کے الگورتھم (یا کچھ اسی طرح کے میشنگ الگورتھم) کا استعمال کرتا ہے تاکہ کثیر الاضحی ماڈل کو محدود عنصر کے طریقہ کار کے لیے موزوں مثلث میں تبدیل کیا جا سکے۔ الگورتھم الگورتھم ان پٹ عمودی کے ڈیلونی مثلث سے شروع ہوتا ہے اور پھر دو اہم کارروائیوں پر مشتمل ہوتا ہے۔ غیر خالی قطر کے حلقوں والے حصے کا درمیانی نقطہ مثلث میں داخل کیا جاتا ہے۔ ناقص معیار کے مثلث کا فریم سینٹر مثلث میں داخل کیا جاتا ہے، جب تک کہ یہ فریم سینٹر کسی حصے کے قطر کے دائرے میں نہ ہو۔ اس صورت میں، اس کے بجائے تجاوز شدہ حصے کو تقسیم کیا جاتا ہے۔ یہ کارروائیاں اس وقت تک دہرائی جاتی ہیں جب تک کہ کوئی ناقص معیار کا مثلث موجود نہ ہو اور تمام حصوں پر تجاوز نہ ہو۔ سیوڈو کوڈ فنکشن روپرٹ (پوائنٹس، سیگمنٹس، تھریشولڈ) T ہے: = ڈیلونی ٹرائینگولیشن (پوائنٹس) Q: = تجاوز شدہ حصوں اور ناقص معیار کے مثلثوں کا مجموعہ جبکہ Q خالی نہیں ہے:// مرکزی لوپ اگر Q میں ایک طبقہ s ہے: S کا وسط نقطہ T میں داخل کریں ورنہ Q میں ناقص معیار کا مثلث t ہے: اگر t کا دائرہ مرکز کسی حصے s پر تجاوز کرتا ہے: S کو Q میں شامل کریں ؛ بصورت دیگر: T کے دائرے کو T سرے میں داخل کریں اگر آخر میں Q سرے کو اپ ڈیٹ کرتا ہے جبکہ واپسی T سرے کو روپرٹ کرتا ہے۔ بغیر ترمیم کے عملی استعمال روپرٹ کا الگورتھم غیر تیز ان پٹ اور تقریبا 20.7 ڈگری سے کم کسی بھی ناقص معیار کی حد کے لیے ایک معیاری میش کو ختم کرنے اور پیدا کرنے کی ضمانت دیتا ہے۔ ان پابندیوں میں نرمی کے لیے مختلف چھوٹی چھوٹی اصلاحات کی گئی ہیں۔ چھوٹے ان پٹ زاویوں کے قریب معیار کی ضرورت کو کم کرکے، الگورتھم کو کسی بھی سیدھی لائن کے ان پٹ کو سنبھالنے کے لیے بڑھایا جا سکتا ہے۔ منحنی ان پٹ کو بھی اسی طرح کی تکنیکوں کا استعمال کرتے ہوئے جوڑ دیا جا سکتا ہے۔ رپرٹ کے الگورتھم کو قدرتی طور پر تین جہتوں تک بڑھایا جا سکتا ہے، تاہم سلور قسم کے ٹیٹراہیڈرون کی وجہ سے اس کی آؤٹ پٹ گارنٹیاں کچھ حد تک کمزور ہیں۔ دو جہتوں میں روپرٹ کے الگورتھم کی توسیع آزادانہ طور پر دستیاب مثلث پیکیج میں نافذ کی گئی ہے۔ اس پیکیج میں روپرٹ کے الگورتھم کی دو قسمیں تقریبا 26.5 ڈگری کی ناقص معیار کی حد تک ختم ہونے کی ضمانت دیتی ہیں۔ عملی طور پر یہ الگورتھم 30 ڈگری سے زیادہ ناقص معیار کی حد کے لیے کامیاب ہیں۔ تاہم، ایسی مثالیں معلوم ہیں جو الگورتھم کو 29.06 ڈگری سے زیادہ حد کے ساتھ ناکام ہونے کا سبب بنتی ہیں۔ مزید دیکھیں مقامی خصوصیت کا سائز پولیگن میش ٹیٹ جین ورونوئی خاکہ حوالہ جات مزید پڑھنے میش نسل مثلث (جیومیٹری) ویڈیو کلپس پر مشتمل مضامین