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

خوارزمية وارنوك هي خوارزمية سطح مخفي ابتكرها جون وارنوك، وتُستخدم عادةً في مجال رسومات الحاسوب . ^{[ 1 ]} تحل هذه الخوارزمية مشكلة عرض صورة معقدة من خلال تقسيم المشهد بشكل متكرر حتى يتم الحصول على مناطق يسهل حسابها. بعبارة أخرى، إذا كان المشهد بسيطًا بما يكفي لحسابه بكفاءة، يتم عرضه؛ وإلا يتم تقسيمه إلى أجزاء أصغر يتم اختبارها بدورها للتأكد من بساطتها. ^{[ 2 ]}

هذه خوارزمية فرق تسد، ووقت تشغيلها هو${\displaystyle O(np)}$، حيث n هو عدد المضلعات و p هو عدد البكسلات في منفذ العرض.

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

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

• ملخص خوارزمية وارنوك