جميل؟ للغاية! كيف كتبنا تطبيقًا لتصور الجذابين

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



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

معلومات عنا

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

النمذجة

هناك طرق عديدة لتعريف نظام ديناميكي بجاذب غريب ، ولكن الأكثر شيوعًا هو نظام من ثلاث معادلات تفاضلية من الدرجة الأولى. بدأنا معها.

$$

$$\begin{cases} x' = f(x,y,z) \\ y' = f(x,y,z) \\ z' = f(x,y,z) \\ \end{cases}$$

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



عند تنفيذ النمذجة ، قررنا استخدام البرمجة الوصفية ، والتخلي عن std :: function والميكانيكا المماثلة الأخرى. كان من الممكن أن يكون لديهم هندسة معمارية وترميز مبسطون ، لكنهم كانوا سيقللون بشكل كبير من الأداء ، وهو ما لم نكن نريده.



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



يقبل النموذج كمدخلات:

• مشتقات "المشتقات" للحصول على المشتقات بإحداثيات نقطة ؛
• الممتلئ "المراقب" ، والذي يتم استدعاؤه من النقطة بمجرد استلامه ؛
• معلمات المحاكاة (نقطة البداية ، حجم الخطوة ، عدد النقاط).

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

الأنظمة

لقد وجدنا أكثر أنظمة الجذب الغريبة شيوعًا للحصول على أفضل أداء منها. هنا نريد أن نشكرك على موقع chaoticatmospheres.com الذي جعل هذا البحث سهلاً للغاية بالنسبة لنا.



كان لابد من تغليف جميع الأنظمة بحيث يمكن وضعها في حاوية والعمل معها بشكل طبيعي في وحدة التحكم ، على الرغم من أنها جميعًا "قوالبنا". توصلنا إلى الحل التالي:

• DynamicSystem ‘observer’, (, ...) std::function ‘compute’. ‘Compute’ , , ‘derivatives’ .
• std::function , DynamicSystemInternal compute .
• DynamicSystemInternal ‘observer’, ‘derivatives’. ‘derivatives’, .

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

التصور

لقد اخترنا OpenGL كمكتبة عرض نظرًا لأدائها وإمكانياتها ، بالإضافة إلى Qt5 ، الذي يحتوي على غلاف مناسب عبر OpenGL.



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







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







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

• خذ الكثير (100-500 ، يمكنك اختيار المزيد في الإعدادات ، الشيء الرئيسي هو وجود أداء كافٍ) لنقاط البداية القريبة من بعضها البعض.
• محاكاة المسار من كل منهم.
• قم برسم المسارات في نفس الوقت ، مع تلوينها بألوان مختلفة ، وإظهار جزء المسار فقط.

اتضح ما يلي:







بقي مثل هذا المخطط تقريبًا حتى النهاية.



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



في البداية اعتقدنا أن OpenGL يجب أن يحتوي على أداة تنعيم الخطوط ، ولكن بعد الكثير من البحث ، وجدنا أن هذا ليس هو الحال. ثم جاءت الفكرة لاستيفاء المنحنيات وإضافة المزيد بين كل زوج من النقاط المتجاورة البعيدة بدرجة كافية. للقيام بذلك ، كان من الضروري اختيار طريقة لاستيفاء المنحنيات ، وهناك العديد من هذه الطرق. للأسف ، تطلب معظمهم (على سبيل المثال ، منحنى بيزيير) تحديد بضع نقاط أخرى ، والتي لم تكن مناسبة بشكل واضح لمهمتنا: أردنا أن تعتمد النتيجة فقط على ما قدمه لنا النموذج الرياضي. بعد فترة ، وجدنا الاستيفاء المناسب: منحنى Catmull - Roma. اتضح مثل هذا:







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







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



وجدنا أنه من المثير للاهتمام تلوين المسارات بطريقة يتغير لون كل منها من رأس إلى آخر. هذا يسمح لنا بمراقبة تأثير السرعة:







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

وحدة تحكم وواجهة مستخدم

بعد اختيار Qt5 كإطار أساسي ، اختفت على الفور مسألة اختيار تقنيات الواجهة. يلبي برنامج Qt Creator المدمج بشكل كافٍ جميع احتياجات التطبيقات الصغيرة.





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







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



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

أنظمة مخصصة

هناك العديد من عوامل الجذب المتوفرة بالفعل في التطبيق ، لكننا أردنا أيضًا السماح للمستخدم بإدخال المعادلات بنفسه. للقيام بذلك ، كتبنا محللًا يدعم المتغيرات (x ، y ، z) ، العمليات الرياضية القياسية (+ - * / ^) ، الثوابت ، العديد من الدوال الرياضية (sin ، cos ، log ، atan ، sinh ، exp ، إلخ.) والأقواس. هذه هي الطريقة التي يعمل بها:

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

ابحث عن مزيد من التفاصيل في كود المصدر المحلل .



يقوم كل مستوى بإرجاع نوع من وراثة العقدة. هناك أربعة منهم:

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

تحتوي بنية العقدة فقط على وظيفة حساب افتراضية تُرجع قيمة شجرتها الفرعية.



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

النتيجة

نتيجة لذلك ، حصلنا على برنامج يمكنه تصور الأنظمة التي يحددها المستخدم ولديه قاعدة من عدد كبير من عوامل الجذب. إنها تفعل ذلك بشكل جيد ومحسّن ، وهذا خبر سار.



لكن لا يزال هناك الكثير من العمل:

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

لدينا مستودع .



وعدد قليل من مقاطع الفيديو مع الجذابين: