مكعبات متحركة

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
تم استخراج هياكل الرأس والدماغ (المخفية) من 150 شريحة من صور الرنين المغناطيسي باستخدام مكعبات متحركة (حوالي 150000 مثلث).

خوارزمية المكعبات المتحركة هي خوارزمية رسومات حاسوبية ، نُشرت في وقائع مؤتمر SIGGRAPH عام 1987 من قِبل لورنسن وكلاين، [ 1 ] لاستخراج شبكة مضلعية لسطح متساوي القيمة من حقل قياسي منفصل ثلاثي الأبعاد (تُسمى عناصره أحيانًا فوكسلات ). تُعنى تطبيقات هذه الخوارزمية بشكل أساسي بالتصوير الطبي ، مثل صور بيانات التصوير المقطعي المحوسب والتصوير بالرنين المغناطيسي ، والمؤثرات الخاصة أو النمذجة ثلاثية الأبعاد باستخدام ما يُسمى عادةً بالكرات الفائقة أو الأسطح الفائقة الأخرى. صُممت خوارزمية المكعبات المتحركة للاستخدام في البيئات ثلاثية الأبعاد؛ أما النسخة ثنائية الأبعاد منها فتُسمى خوارزمية المربعات المتحركة .

تاريخ

طُوِّرت هذه الخوارزمية بواسطة ويليام إي. لورنسن (1946-2019) وهارفي إي. كلاين نتيجةً لأبحاثهما لصالح شركة جنرال إلكتريك . وقد عملا في جنرال إلكتريك على إيجاد طريقة فعّالة لعرض البيانات من أجهزة التصوير المقطعي المحوسب والتصوير بالرنين المغناطيسي. [ 2 ]

تقوم خوارزمية البحث على تقسيم حجم الإدخال إلى مجموعة منفصلة من المكعبات. وبافتراض ترشيح إعادة البناء الخطي ، يمكن تحديد كل مكعب بسهولة، والذي يحتوي على جزء من سطح متساوي القيمة معين ، لأن قيم العينات عند رؤوس المكعب يجب أن تغطي قيمة السطح المتساوي القيمة المستهدف. لكل مكعب يحتوي على جزء من السطح المتساوي القيمة، يتم إنشاء شبكة مثلثية تقارب سلوك الاستيفاء ثلاثي الخطوط في المكعب الداخلي.

استغلت النسخة الأولى المنشورة من الخوارزمية التناظر الدوراني والانعكاسي، بالإضافة إلى تغيرات الإشارة، لبناء الجدول الذي يحتوي على 15 حالة فريدة. مع ذلك، ونظرًا لوجود غموض في سلوك الاستيفاء ثلاثي الخطوط في أوجه المكعب وداخله، فقد ظهرت في الشبكات المستخرجة بواسطة خوارزمية مكعبات المسير انقطاعات ومشاكل طوبولوجية. عند النظر إلى مكعب من الشبكة، يحدث غموض في الوجه عندما تكون إشارات رؤوسه متناوبة. أي أن رؤوس أحد الأقطار على هذا الوجه موجبة، بينما رؤوس القطر الآخر سالبة. لاحظ أنه في هذه الحالة، لا تكفي إشارات رؤوس الوجه لتحديد الطريقة الصحيحة لتثليث السطح المتساوي. وبالمثل، يحدث غموض داخلي عندما لا تكفي إشارات رؤوس المكعب لتحديد التثليث الصحيح للسطح ، أي عندما يكون من الممكن إجراء تثليثات متعددة لنفس تكوين المكعب.

أدى انتشار استخدام خوارزمية مكعبات المسير وانتشارها الواسع إلى إدخال العديد من التحسينات عليها لمعالجة حالات الغموض وتتبع سلوك الدالة المُستكمِلة بدقة. كان دورست [ 3 ] أول من لاحظ في عام 1988 أن جدول التثليث الذي اقترحه لورنسن وكلاين غير مكتمل، وأن بعض حالات مكعبات المسير تسمح بإجراء تثليثات متعددة. وقد أشار دورست في مرجعه الإضافي إلى خوارزمية سابقة وأكثر كفاءة (انظر دي أراوجو [ 4 ] ) لإنشاء مضلعات الأسطح المتساوية، والتي طورها ويفيل وويفيل وماكفيترز. [ 5 ] لاحقًا، لاحظ نيلسون وهامان [ 6 ] في عام 1991 وجود حالات غموض في سلوك الدالة المُستكمِلة على وجه المكعب. واقترحا اختبارًا يُسمى "المُقرر التقاربي" لتتبع الدالة المُستكمِلة بدقة على أوجه المكعب. في الواقع، وكما لاحظ ناتاراجان [ 7 ] عام 1994، تظهر مشكلة الغموض هذه أيضًا داخل المكعب. في بحثه، اقترح المؤلف اختبارًا لإزالة الغموض يعتمد على النقاط الحرجة المُستكمَلة، وأضاف أربع حالات جديدة إلى جدول تثليث مكعبات مارشينج (حالات فرعية من الحالات 3 و4 و6 و7). عند هذه النقطة، وحتى مع كل التحسينات المقترحة على الخوارزمية وجدول التثليث الخاص بها، ظلت الشبكات المُولَّدة بواسطة مكعبات مارشينج تعاني من عدم اتساق طوبولوجي.

تُعدّ خوارزمية مكعبات المسير 33، التي اقترحها تشيرنيايف [ 8 ] عام 1995، من أوائل خوارزميات استخراج الأسطح المتساوية المصممة للحفاظ على بنية المُستكمِل ثلاثي الخطوط. في عمله، وسّع تشيرنيايف عدد الحالات في جدول البحث الخاص بالتثليث إلى 33 حالة. ثم اقترح منهجًا مختلفًا لحلّ الغموض الداخلي، يعتمد على المُقرِّر التقاربي. لاحقًا، في عام 2003، أثبت نيلسون [ 9 ] أن جدول بحث تشيرنيايف كامل ويمكنه تمثيل جميع السلوكيات الممكنة للمُستكمِل ثلاثي الخطوط، واقترح ليوينر وآخرون [ 10 ] تطبيقًا للخوارزمية. أيضًا في عام 2003، وسّع لوبيز وبرودلي [ 11 ] الاختبارات التي اقترحها ناتاراجان. [ 7 ] في عام 2013، كوستوديو وآخرون. [ 12 ] لاحظ وصحح عدم الدقة الخوارزمية التي أثرت على صحة الطوبولوجيا للشبكة التي تم إنشاؤها بواسطة خوارزمية Marching Cubes 33 التي اقترحها تشيرنيايف. [ 8 ]

التكوينات المكعبة الخمسة عشر المنشورة أصلاً

الخوارزمية

تتابع الخوارزمية عملها عبر الحقل القياسي، حيث تأخذ ثمانية مواقع متجاورة في كل مرة (مكونةً بذلك مكعبًا وهميًا)، ثم تحدد المضلع (أو المضلعات) اللازمة لتمثيل جزء السطح المتساوي الذي يمر عبر هذا المكعب. بعد ذلك، تُدمج المضلعات الفردية لتكوين السطح المطلوب.

يتم ذلك بإنشاء فهرس لمصفوفة مُحسوبة مسبقًا تضم ​​256 تكوينًا مُحتملًا للمضلعات (2 ^8 = 256) داخل المكعب، وذلك بمعاملة كل قيمة من القيم العددية الثمانية كبت في عدد صحيح من 8 بتات. إذا كانت قيمة القيمة العددية أعلى من القيمة المتساوية (أي أنها داخل السطح)، يتم ضبط البت المناسب على واحد، بينما إذا كانت أقل (خارج السطح)، يتم ضبطه على صفر. القيمة النهائية، بعد فحص جميع القيم العددية الثمانية، هي الفهرس الفعلي لمصفوفة فهارس المضلعات.

وأخيراً، يتم وضع كل رأس من رؤوس المضلعات المولدة في الموضع المناسب على طول حافة المكعب عن طريق الاستيفاء الخطي للقيمتين القياسيتين المتصلتين بتلك الحافة.

يمثل تدرج الحقل القياسي عند كل نقطة من نقاط الشبكة متجهًا عموديًا على سطح متساوي افتراضي يمر من تلك النقطة. لذا، يمكن استيفاء هذه المتجهات العمودية على طول حواف كل مكعب لإيجاد المتجهات العمودية للرؤوس المتولدة، وهي ضرورية لتظليل الشبكة الناتجة باستخدام نموذج إضاءة معين .

قضايا براءات الاختراع

تم تسجيل براءة اختراع لتطبيق خوارزمية المكعبات المتحركة في الولايات المتحدة الأمريكية تحت رقم 4,710,876. [ 2 ] وتم تطوير خوارزمية مشابهة أخرى، تُسمى خوارزمية رباعيات الأوجه المتحركة ، للتحايل على براءة الاختراع وحل مشكلة غموض بسيطة تتعلق بخوارزمية المكعبات المتحركة مع بعض تكوينات المكعبات. انتهت صلاحية براءة الاختراع في عام 2005، وأصبح من القانوني الآن لمجتمع الرسومات استخدامها دون دفع أي رسوم، نظرًا لمرور أكثر من 20 عامًا على تاريخ إصدارها (1 ديسمبر 1987 [ 2 ] ).

مصادر

  1. ↑ لورنسن، ويليام إي.؛ كلاين، هارفي إي. (1 أغسطس 1987). "مكعبات متحركة: خوارزمية بناء أسطح ثلاثية الأبعاد عالية الدقة". مجلة ACM SIGGRAPH لرسومات الحاسوب . 21 (4): 163-169 . CiteSeerX 10.1.1.545.613 . doi : 10.1145/37402.37422 . 
  2. 1 2 3 منحت الولايات المتحدة الأمريكية براءة الاختراع رقم US4710876A ، كلاين، هارفي ولورنسن ، ويليام، "نظام وطريقة لعرض الهياكل السطحية الموجودة داخل المنطقة الداخلية لجسم صلب"، صدرت في 1987-12-01 
  3. ↑ دورست، مارتن ج. (1988-10-01). "ردًا على: إشارة إضافية إلى "المكعبات المتحركة"" . ACM SIGGRAPH Computer Graphics . 22 (5): 243. doi : 10.1145/378267.378271 . ISSN 0097-8930 . S2CID 36741734 .  
  4. ↑ دي أراوجو، برونو؛ لوبيز، دانيال؛ جيب، بولين؛ خورخي، جواكيم؛ ويفيل، برايان (2015). "دراسة استقصائية حول مضلعات السطح الضمنية". مجلة ACM Computing Surveys . 47 (4): 60:1–60:39. doi : 10.1145/2732197 . S2CID 14395359 . 
  5. ↑ وايفيل، جيف؛ وايفيل، برايان؛ مكفيترز، كريج (1986). "هياكل البيانات للكائنات المرنة". الحاسوب المرئي . 2 (4): 227-234 . doi : 10.1007/BF01900346 . S2CID 18993002 . 
  6. ↑ نيلسون، جي إم؛ هامان، ب. (1991). "المُحَدِّد التقاربي: حل الغموض في مكعبات المسير". وقائع مؤتمر التصور '91 . الصفحات 83-91 . doi : 10.1109/visual.1991.175782 . ISBN  978-0818622458. S2CID 35739150 . 
  7. 1 2 ناتاراجان، ب.ك. (يناير 1994). "حول توليد أسطح متساوية متسقة طوبولوجيًا من عينات منتظمة". الحاسوب المرئي . 11 (1): 52-62 . doi : 10.1007/bf01900699 . ISSN 0178-2789 . S2CID 526698 .  
  8. 1 2 V.، تشيرنيايف، إي. (1995). مكعبات المسير 33 : بناء أسطح متساوية صحيحة طوبولوجيًا : عُرضت في مؤتمر GRAPHICON '95، سانت بطرسبرغ، روسيا، 03-07.07.1995 . سيرن. قسم الحوسبة والشبكات. OCLC 897851506 .   {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  9. ↑ نيلسون، جي إم (2003). "حول مكعبات الحركة". معاملات IEEE في التصور ورسومات الحاسوب . 9 (3): 283-297 . doi : 10.1109/TVCG.2003.1207437 .
  10. ^ لوينر، توماس. لوبيز، هيليو؛ فييرا، أنطونيو ويلسون؛ تافاريس ، جيوفان (يناير 2003). “التنفيذ الفعال لحالات المكعبات المسيرة مع الضمانات الطوبولوجية”. مجلة أدوات الرسومات . 8 (2): 1– 15. دوى : 10.1080/10867651.2003.10487582 . ردمك 1086-7651 . S2CID 6195034 .  
  11. ↑ لوبيز، أ.؛ برودلي، ك. (2003). "تحسين متانة ودقة خوارزمية المكعبات المتحركة لتحديد الأسطح المتساوية" (ملف PDF) . معاملات IEEE في التصور ورسومات الحاسوب . 9 : 16-29 . doi : 10.1109/tvcg.2003.1175094 . hdl : 10316/12925 .
  12. ↑ كوستوديو، ليس؛ إتيان، تياغو؛ بيسكو، سينيسيو؛ سيلفا، كلاوديو (نوفمبر 2013). "اعتبارات عملية حول صحة خوارزمية مكعبات المسير من الناحية الطوبولوجية". الحوسبة والرسومات . 37 (7): 840-850 . CiteSeerX 10.1.1.361.3074 . doi : 10.1016/j.cag.2013.04.004 . ISSN 0097-8493 . S2CID 1930192 .   

انظر أيضاً

  • لورنسن، دبليو إي؛ كلاين، هارفي إي. (1987). "مكعبات متحركة: خوارزمية بناء أسطح ثلاثية الأبعاد عالية الدقة". مجلة ACM SIGGRAPH لرسومات الحاسوب . 21 (4): 163-169 . CiteSeerX 10.1.1.545.613 . doi : 10.1145/37402.37422 . 
  • نيلسون، جي إم؛ هامان، ب. (1991). "المُحَدِّد التقاربي: حل الغموض في مكعبات المسير". وقائع مؤتمر التصور 91. الصفحات 83-91 . doi : 10.1109/VISUAL.1991.175782 . ISBN  9780818622458. S2CID 35739150 . 
  • مونتاني، كلاوديو؛ سكاتيني، ريكاردو؛ سكوبينيو، روبرتو (1994). "جدول بحث مُعدَّل لإزالة الغموض الضمني لمكعبات المسير". الحاسوب المرئي . 10 (6): 353-355 . doi : 10.1007/BF01900830 . S2CID 31316542 . 
  • نيلسون، جي إم؛ جون وون سونغ (1997). "تقسيم الحجم الفاصل إلى رباعيات الأوجه". وقائع مؤتمر التصور 97 (رقم التصنيف 97CB36155) . الصفحات 221-228 . doi : 10.1109/VISUAL.1997.663886 . ISBN  978-0-8186-8262-9. S2CID 5575097 . 
  • بول بورك. "نظرة عامة وشفرة المصدر" .
  • ماثيو وارد. "نظرة عامة على تطوير الألعاب" .
  • "وصف تمهيدي مع رسومات إضافية" .
  • "مكعبات متحركة" .بعض من التاريخ المبكر لفرقة Marching Cubes.
  • نيومان، تيموثي س.؛ يي، هونغ (2006). "دراسة استقصائية لخوارزمية المكعبات المتحركة". الحوسبة والرسومات . 30 (5): 854-879 . CiteSeerX 10.1.1.413.7458 . doi : 10.1016/j.cag.2006.07.021 . 
  • ستيفان ديل. "تخصيص خوارزميات التصور" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 24 أكتوبر 2017. تم الاطلاع عليه بتاريخ 6 فبراير 2013 .