خوارزمية نيولز

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

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

في هذه الحالة، تختبر خوارزمية نيويل ما يلي:

1. اختبار تداخل Z؛ وهو أمر مضمن في اختيار الوجه Q من قائمة الفرز
2. لا تتداخل قيم الإحداثيات القصوى في X للوجهين ( اختبار minimax في X)
3. لا تتداخل قيم الإحداثيات القصوى في المحور Y للوجهين (اختبار الحد الأدنى الأقصى في المحور Y)
4. جميع رؤوس النقطة P تقع أعمق من مستوى النقطة Q
5. تقع جميع رؤوس النقطة Q أقرب إلى نقطة الرؤية من مستوى النقطة P
6. لا تتداخل عملية تحويل P و Q إلى صورة نقطية

تُجرى الاختبارات بترتيب تصاعدي حسب صعوبة الحساب. يجب أن تكون المضلعات مستوية . إذا كانت جميع الاختبارات خاطئة، يُبدَّل ترتيب المضلعين P و Q في عملية الفرز، ويُسجَّل التغيير، ثم تُعاد المحاولة. في حال محاولة تبديل ترتيب مضلع للمرة الثانية، تحدث دورة رؤية، ويجب تقسيم المضلعات. يتم التقسيم باختيار أحد المضلعات وقصه على طول خط التقاطع مع المضلع الآخر. تُجرى الاختبارات المذكورة أعلاه مرة أخرى، وتستمر الخوارزمية حتى تجتاز جميع المضلعات الاختبارات المذكورة.

• ساذرلاند، إيفان إي .؛ سبرول، روبرت إف.؛ شوماكر، روبرت أ. (1974)، "توصيف لعشر خوارزميات للأسطح المخفية"، مجلة Computing Surveys ، 6 (1): 1-55 ، CiteSeerX 10.1.1.132.8222 ، doi : 10.1145/356625.356626 ، S2CID 14222390  .
• نيويل، إم إي ؛ نيويل، آر جي ؛ سانشا، تي إل ( 1972)، "نهج جديد لمشكلة الصورة المظللة"، وقائع المؤتمر الوطني لجمعية آلات الحوسبة ، الصفحات 443-450 .

• خوارزمية الرسام
• العمليات المنطقية على المضلعات