مؤمن محمد عبد الستار الجمعة، 10 يونيو 2022

 

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

إذا: في هذا المقال سأصطحبك في مغامرة حاسوبية، سنكتب فهيا معا ما يسميه المبرمجون متتبع أشعة Ray tracer. هل أنت جاهز؟

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

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

هذا المشهد اسمه Cornell box ويستخدم لاختبار متتبعات الأشعة

إذا لنكتب خوارزمية بدائية لبرنامج يحل مشكلتنا

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

تتبع الأشعة بداية من مصدر الضوء ووصولا للكاميرا، لاحظ كيف نضيع وقت الحاسوب في تتبع الكثير من الأشعة التي لا تصل للكاميرا

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

لاحظ كيف أن تتبع الأشعة بداية من الكاميرا ووصولا لمصدر الضوء يجعل الحاسوب يركز على الأشعة التي ستصل للكاميرا

إذا خوارزميتنا كالآتي:

    لكل بكسل في الصورة:
        أخرج شعاعا من الكاميرا يمر بالبكسل
        لكل غرض في المشهد: اختبر تقاطع الشعاع مع الغرض
        هات أقرب تقاطع من الكاميرا
        إذا كان الغرض المتقاطع معه مضيئا: لون البكسل بلون الضوء
        في غير ذلك: لون البكسل بالأسود

إذا لننظر للنتيجة:

لدينا مشكلة الآن: خوارزميتنا هذه تمكنت من تلونين البكاسل التي تصور مصدر الضوء باللون الأبيض، لكن لا شيء آخر في المشهد مضيء! ويكأن مصدر الضوء هذا لا يضيء أي شيء حوله، كيف نصلح هذه المشكلة؟
لنضف هذه الخطوة لخوارزميتنا: بدلا من تلوين البكسل بالأسود عندما نتقاطع بجسم معتم، سنختبر ما آذا كان مصدر الضوء يضيء هذه النقطة المعتمة أم لا. إذا كان يضيئها فسنلون البكسل بلون الغرض، وإن كان لا يضيئها نلون البكسل بالأسود

[صورة]
إذا خوارزميتنا بعد التعديل كالآتي:

    لكل بكسل في الصورة:
        أخرج شعاعا من الكاميرا يمر بالبكسل
        لكل غرض في المشهد: اختبر تقاطع الشعاع مع الغرض
        هات أقرب تقاطع من الكاميرا
        إذا كان الغرض المتقاطع معه مضيئا: لون البكسل بلون الضوء
        في غير ذلك:
            أخرج شعاعا يبدأ من نقطة التقاطع وينتهي بمضدر الضوء
             لكل غرض في المشهد: اختبر تقاطع الشعاع مع الغرض
             إذا كان الشعاع لا يتقاطع مع أي غرض بالمنتصف: فهذا يعني أنه لا يوجد ظل، لون البكسل بلون الضوء وهو يضيء نقطة التطاطع
             أما إذا كان الشعاع يتقاطع مع أي غرض في المنتصف: فهذا يعني أن شعاع الضوء لم يصل لنقطة التقاطع لوجود ظل: لون البكسل بالأسود

 إذا لنر النتيجة بعد تحديث خوارزميتنا

نعم أفضل بكثير الآن! ولكن لا يزال ينقصها شيء ما... نعم، الخطوط خشنة! انظر مثلا للحد الفاصل بين الجدار الأحمر والجدار الأبيض، أو الخط الفاصل بين الوجه المضيء والوجه المظلم للمكعب، كيف أنها خشنة وليست كما كنا نتخيلها في بداية المقال، كيف نحل هذه المشكلة؟ الحل هو إزالة الخشونة أو Anti-aliasing
المشكلة في هذا الخط هو أن كل بكسل إما أبيض أو أحمر، أما ما يتوقعه المشاهد هو أن يكون كل بكسل متراوحا بين الأبيض والأحمر حسب مكانه، فتكون الحدود بين الألوان ناعمة.

المشاهد يتوقع البكاسل أن تكون مختلطة بين الأحمر والأبيض بنسب متفاوتة حسب مكانها، فمثلا أن يكون البكسل 1 أكثر حمرة وأن يكون البكسل 2 أكثر بياضا، لا أن يكون أحدهما أحمر تماما والآخر أبيض تماما.

صورة أخرى توضح إزالة الخشونة

يمكن أن نحل هذه المشكلة كالآتي: بدلا من أخذ شعاع واحد من كل بكسل، سنأخذ 16 شعاعا (16 عينة) في اتجاهات مختلفة تمر بالبكسل. سأخذ متوسط النتائج التي تعطيها إلينا الأشعة الستة عشر (سنجمع النتائج ونقسمها على 16). بهذا ستصبح البكاسل الحدودية متفاوتة في اللون حسب كمية الأحمر والأبيض التي تستقبلها، وسيكون المشهد مريحا أكثر للعين.

وها هي النتيجة بعد أن أخذنا 16 عينة بدلا من عينة واحدة (بنفس الخوارزمية السابقة)

جميل! لقد تقدمنا كثيرا! ولكن لا زال هناك شيء ناقص ... ما هو يا ترى؟

الصورة التي كنا نريد رؤيتها

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

صورة توضح الفرق بين الخوارزمية الأولى والثانية

إذا خوارزميتنا في تتبع الأشعة ستكون كالآتي:

    لكل بكسل في الصورة:
        الضوء_المحصل يساوي صفر // تذكر كلمة الضوء_المحصل جيدا لأنك ستراها لاحقا في الخوارزمية
        أخرج شعاعا من الكاميرا يمر بالبكسل
        لكل غرض في المشهد: اختبر تقاطع الشعاع مع الغرض
        هات أقرب تقاطع من الكاميرا
        إذا كان الغرض المتقاطع معه مضيئا: أضف لون الضوء لـ الضوء_المحصل
        في غير ذلك:
            أخرج شعاعا يبدأ من نقطة التقاطع وينتهي بمضدر الضوء
                 لكل غرض في المشهد: اختبر تقاطع الشعاع مع الغرض
                 إذا كان الشعاع لا يتقاطع مع أي غرض بالمنتصف: فهذا يعني أنه لا يوجد ظل، أضف هذا الضوء لـ الضوء_المحصل
                 أما إذا كان الشعاع يتقاطع مع أي غرض في المنتصف: فهذا يعني أن شعاع الضوء لم يصل لنقطة التقاطع لوجود ظل: لا تضف شيئا الضوء_المحصل
             أخرج شعاعا آخر من نقطة التقاطع في اتجاه عشوائي، كرر هذه العملية عند نقطة التقاطع الثانية وأضف الضوء الآتي منها لـ الضوء_المحصل
     في النهاية: لون البكسل بلون الضوء_المحصل

     
 الآن سنأخذ 16 عينة بهذه الخوارزمية الجديدة، ولنر النتيجة:

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

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

صورة توضح لم لا يتمكن متتبع الأشعة الذي لنا من إيصال ضوء الشمس لأي شيء تحت سطح الماء

هذا نفس المشهد بمتتبع أشعة RenderMan، وهو يحل المشكلة بطريقة بسيطة جدا: إذا كان السطح الذي يسد مجرى الضوء شفافا، تجاهله ووصل مسار الضوء! (طبعا توجد المزيد من الخطوات ولكن هذا اختصار) هذا يجعل الماء عديم الظل ويحل مشكلة القاع المعتم فيعطي نتيجة مسرة للعين وأفضل من PBRT، لكنه أيضا يجعل الماء عديم كسر الضوء (ويكأن الماء لا يكسر ضوء الشمس)،فيكون Hyperion المتفوق في رندرة مشهد "جزيرة موانا"

ذلك لأن Hyperion له خوارزمية أخرى (اسمها Adaptive progressive photon mapping) يتمكن بها من تتبع الضوء المنكسر عبر سطح الماء ليصل لكل ما في البحر حتى قاعه، فتضيء الشمس قاع البحر كما نتوقعها.
لن أتطرق لهذه الخوارزمية في هذا المقال، ولكن ما أريد قوله هو أن خوارزميتنا بدائية جدا وبها مئات المشاكل التي تحتاج لحلول لكن هذه المشاكل لا تظهر في مشهد المكعبات البسيط هذا.
وأريد أيضا أن أوضح أن الكثير من التفاصيل لم أوضحها لجعل المقال مبسطا (ولا زلت أراه معقدا قليلا). مثلا: هل فكرت كيف نجد التقاطع بين مثلث وشعاع؟ رغم وجود خوارزمية كاملة لفعل ذلك- تخطيتها في هذا المقال للتركيز على خوارزمية تتبع الأشعة فحسب، وكذلك الأمر بالنسبة للكثير من التفاصيل.
آه وبالمناسبة، الخوارزمية التي طورناها معا في هذا المقال اسمها Unidirectional path tracer.

وتذكر دائما أن خير طرق تعلم البرمجة هو قراءة وكتابة البرامج

كان هذا كل شيء لهذا المقال، فكر كمبرمج! شكرا على القراءة!

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