عرض خطوط المسح

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

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

يمكن دمج هذا النوع من الخوارزميات بسهولة مع العديد من تقنيات الرسومات الأخرى، مثل نموذج انعكاس فونغ أو خوارزمية المخزن المؤقت Z.

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

إن الجمع بين هذا و Z-buffering يتخلص من فرز جدول الحواف النشط، وبدلاً من ذلك يقوم بتحويل خط مسح واحد في كل مرة إلى Z-buffer، مع الحفاظ على امتدادات المضلع النشطة من خط مسح إلى آخر.

في صيغة أخرى، يتم تحويل مخزن المعرف إلى صورة نقطية في خطوة وسيطة، مما يسمح بتأجيل تظليل وحدات البكسل المرئية الناتجة.

ربما كان أول منشور لتقنية عرض خطوط المسح هو من قبل وايلي، رومني، إيفانز، وإردال في عام 1967. ^{[ 1 ]}

ومن التطورات المبكرة الأخرى لطريقة عرض خطوط المسح الضوئي ما قام به بوكنايت في عام 1969، ^{[ 2 ]} ونيويل ونيويل وسانشا في عام 1972. ^{[ 3 ]} وقد تم إنجاز الكثير من العمل المبكر على هذه الأساليب في مجموعة الرسومات الخاصة بإيفان ساذرلاند في جامعة يوتا ، وفي شركة إيفانز وساذرلاند في مدينة سولت ليك .

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

يُعد جهاز Nintendo DS أحدث الأجهزة التي تقوم بعرض المشاهد ثلاثية الأبعاد بهذه الطريقة، مع إمكانية تخزين الصور النقطية مؤقتًا في ذاكرة الوصول العشوائي للفيديو (VRAM).

يمكن اعتبار أجهزة معالجة الصور النقطية الشائعة في أجهزة ألعاب الثمانينيات شكلاً بسيطاً ثنائي الأبعاد من تقنية عرض الخطوط المسحية .

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

قامت شركة سوني بتجربة برامج عرض الخطوط المسحية على معالج Cell ثانٍ أثناء تطوير جهاز PlayStation 3 ، قبل أن تستقر على ترتيب وحدة المعالجة المركزية/وحدة معالجة الرسومات التقليدي.

يُستخدم مبدأ مشابه في تقنية العرض المُجزأ (وأشهرها شريحة PowerVR ثلاثية الأبعاد)؛ حيث تُرتّب العناصر الأولية في مساحة الشاشة، ثم تُعرض في ذاكرة الشريحة السريعة، عنصرًا تلو الآخر. وقد وفّر جهاز Dreamcast وضعًا لتحويل صف واحد من العناصر إلى صورة نقطية في كل مرة للمسح النقطي المباشر، مما يُغني عن الحاجة إلى مخزن إطارات كامل، وهو ما يُشبه إلى حد ما تقنية العرض الخطي للأجهزة.

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

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

في أنظمة Z-buffer الحديثة، يمكن الحصول على فوائد مماثلة من خلال الفرز الأولي من الأمام إلى الخلف (الاقتراب من "خوارزمية الرسامين العكسية")، ورفض Z المبكر (بالاقتران مع Z الهرمي)، وتقنيات العرض المؤجل الأقل شيوعًا الممكنة على وحدات معالجة الرسومات القابلة للبرمجة.

تتميز تقنيات المسح الخطي التي تعمل على الصور النقطية بعيب يتمثل في عدم التعامل مع التحميل الزائد بشكل سلس.

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

ونتيجةً لذلك، أصبح مخزن العمق (Z-buffer) شائع الاستخدام في تطبيقات الرسومات التفاعلية المعاصرة. يسمح مخزن العمق بمعالجة كميات أكبر من العناصر الرسومية بشكل خطي ومتوازٍ، بطريقة تتوافق مع الأجهزة الحديثة. لا تحتاج الإحداثيات المُحوّلة وتدرجات السمات وغيرها إلى مغادرة شريحة الرسومات؛ إذ يتم تخزين وحدات البكسل المرئية وقيم العمق فقط.

• مسح نقطي
• تتبع الأشعة
• التخزين المؤقت Z
• محول واجهة التلفزيون ، شريحة أتاري 2600، التي كانت تتعامل مع الرسومات سطرًا بسطر دون استخدام مخزن الإطارات

• تاريخ مجموعة الرسومات بجامعة يوتا