خوارزمية المكعبات السيارة

خوارزمية المكعبات السيارة (بالإنجليزية: Marching cubes)‏ هي خوارزمية في الرسوميات الحاسوبية نشرت للمرة الأولى في مؤتمر سيغراف 1987 من قبل لورنسن وكلاين، وتهدف إلى استخراج المضلع الشبكي عند سطح القيم المتساوية (Isosurface) من حقل سلمي ثلاثي الأبعاد (يسمى في بعض الأحيان فوكسل). لهذه الخوارزمية طريقة مماثلة في الفضاء ثنائي الأبعاد يطلق عليها اسم خوارزمية خوارزمية المربعات السيارة.

شبكة مضلعية تحوي حوالي 150 ألف مثلث لرأس بشري مستخرجة بطريقة المكعبات السيارة من صورة تصوير بالرنين المغناطيسي ثلاثية الأبعاد ذات 150 شريحة.

شرح الخوارزمية

الاحتمالات الـ15 لتوضع المضلعات التي تم نشرها في المرة الأولى.

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

يتم ذلك من خلال إنشاء فهرس لمجموعة الاحتمالات الواردة لتكوينات المضلعات الممكنة والتي عددها 256 ($2^{8}=256$) داخل المكعب الواحد، وذلك باعتبار كل من القيم العددية الثمانية على أنها عدد صحيح ذو حجم 8 بت. إذا كانت القيمة العددية أعلى من القيمة الحدية (iso-value) (أي، داخل السطح) يتم تعيين قيمة للبت المناسب إلى قيمة (1)، بينما إذا كانت القيمة أقل (خارج السطح)، فإنه يتم تعيين القيمة إلى (0). وتكون القيمة النهائية بعد أن يتم فحص جميع القيم الثمانية، هي فهرس مجموعة المضلعات المحددة.

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

تطبيقات هذه الخوارزمية تهتم أساسا بالتعامل مع التصوير الطبي مثل صور الأشعة المقطعية والتصوير بالرنين المغناطيسي، وغيرها من التأثيرات الثلاثية الأبعاد الخاصة.