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

فرز المضلعات حسب العمق لكل مضلع p : لكل بكسل يغطيه p : ارسم لون p على البكسل

يعتمد التعقيد الزمني لخوارزمية الرسام على خوارزمية الفرز المستخدمة لترتيب المضلعات. بافتراض خوارزمية فرز مثالية، فإن خوارزمية الرسام لها تعقيد في أسوأ الحالات من رتبة O ( n log n + m*n )، حيث n هو عدد المضلعات و m هو عدد البكسلات المراد ملؤها.

إن التعقيد المكاني لخوارزمية الرسام في أسوأ الحالات هو O ( n+m )، حيث n هو عدد المضلعات و m هو عدد البكسلات المراد ملؤها.

خوارزمية الرسام ليست معقدة في بنيتها كغيرها من خوارزميات فرز العمق. ^{[ 9 ] [ 11 ]} تُعدّ مكونات مثل ترتيب العرض القائم على العمق، كما هو مُستخدم في خوارزمية الرسام، من أبسط الطرق لتحديد ترتيب إنتاج الرسومات. ^{[ 8 ]} هذه البساطة تجعلها مفيدة في سيناريوهات إخراج رسومات الحاسوب الأساسية حيث يلزم إجراء عرض بسيط دون عناء يُذكر. ^{[ 9 ]}

في أوائل السبعينيات، عندما طُوِّرت خوارزمية الرسام، كانت الذاكرة الفعلية صغيرة نسبيًا. ^{[ 12 ]} وقد استلزم ذلك من البرامج إدارة الذاكرة بأكبر قدر ممكن من الكفاءة لإنجاز المهام الكبيرة دون توقف. تُعطي خوارزمية الرسام الأولوية للاستخدام الأمثل للذاكرة، ولكن على حساب زيادة قوة المعالجة، نظرًا لضرورة معالجة جميع أجزاء جميع الصور. ^{[ 9 ]}

في حالة التداخل الدوري، كما هو موضح في الشكل على اليمين، تتداخل المضلعات أ، ب، وج مع بعضها البعض بطريقة تجعل من المستحيل تحديد أي مضلع يقع فوق الآخر. في هذه الحالة، يجب قص المضلعات المتداخلة للسماح بالفرز. ^{[ 4 ]}

تنشأ حالة المضلعات المتداخلة عندما يتقاطع مضلع مع آخر. ومثل التداخل الدوري، يمكن حل هذه المشكلة عن طريق قطع المضلعات المتداخلة. ^{[ 4 ]}

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

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

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

توفر خوارزمية نيويل ، المقترحة كخوارزمية موسعة لخوارزمية الرسام، طريقة لقطع المضلعات الدورية والمخترقة. ^{[ 4 ]}

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