Beberapa penarik mempesona dengan keindahannya bahkan dalam gambar statis. Kami ingin membuat aplikasi yang dapat memvisualisasikan sebagian besar penarik dalam dinamika, dalam 3D, dan tanpa jeda.
Tentang kami
Kami adalah Roman Venediktov, Vladislav Nosivskoy dan Kirill Karnaukhov - mahasiswa tahun kedua dari program Sarjana "Matematika Terapan dan Ilmu Komputer" di Sekolah Tinggi Ekonomi - St. Petersburg. Kami telah menyukai pemrograman sejak masa sekolah. Mereka bertiga terlibat dalam pemrograman Olimpiade dan lulus pada tahun yang berbeda ke tahap akhir Olimpiade Semua-Rusia untuk anak sekolah dalam ilmu komputer, tetapi mereka tidak memiliki pengalaman dalam pemrograman industri sebelumnya, dan bagi kami ini adalah proyek tim besar pertama. Kami mempertahankannya sebagai makalah tentang C ++.
Pemodelan
Ada banyak cara untuk mendefinisikan sistem dinamika dengan penarik aneh, tetapi yang paling umum adalah sistem tiga persamaan diferensial orde pertama. Kami mulai dengannya.
Sebelum memvisualisasikan sesuatu, Anda perlu mensimulasikan proses itu sendiri dan menemukan lintasan titik-titiknya. Metode pemodelan yang akurat cukup melelahkan, dan kami ingin melakukannya secepat mungkin.
Saat mengimplementasikan pemodelan, kami memutuskan untuk menggunakan metaprogramming, mengabaikan std :: function dan mekanisme serupa lainnya. Mereka bisa saja menyederhanakan arsitektur dan pengkodean, tetapi mereka akan sangat mengurangi kinerja, yang tidak kita inginkan.
Awalnya, metode Runge - Kutta yang paling sederhana dari akurasi urutan ke-4 dengan langkah konstan digunakan untuk pemodelan. Sejauh ini kami belum kembali ke menambah jumlah metode dan komponen matematis lainnya dari model, dan sekarang ini adalah satu-satunya metode yang disajikan. Pada kebanyakan sistem yang ditemukan, cukup akurat untuk menghasilkan gambar yang mirip dengan gambar dari sumber lain.
Model menerima sebagai masukan:
- fungsi 'turunan' untuk mendapatkan turunan dengan koordinat titik;
- Functor 'pengamat', yang dipanggil dari titik segera setelah diterima;
- parameter simulasi (titik awal, ukuran langkah, jumlah titik).
Di masa mendatang, Anda dapat menambahkan tanda centang untuk melihat bagaimana gambar yang disajikan cocok dengan gambar asli, beberapa metode yang lebih kuat untuk pemodelan (misalnya, dengan menghubungkan pustaka Boost.Numeric.Odeint) dan beberapa metode analisis lain yang pengetahuan matematika kita masih belum cukup.
Sistem
Kami menemukan sistem penarik aneh paling populer untuk mendapatkan kinerja terbaik darinya. Di sini kami ingin mengucapkan terima kasih kepada situs chaoticatmospheres.com, yang membuat pencarian ini sangat mudah bagi kami.
Semua sistem harus dibungkus sehingga, terlepas dari kenyataan bahwa semuanya adalah "template kami", mereka dapat diletakkan di wadah dan bekerja secara normal dengan mereka di pengontrol. Kami sampai pada solusi berikut:
- DynamicSystem ‘observer’, (, ...) std::function ‘compute’. ‘Compute’ , , ‘derivatives’ .
- std::function , DynamicSystemInternal compute .
- DynamicSystemInternal ‘observer’, ‘derivatives’. ‘derivatives’, .
Kami mulai bekerja untuk menambahkan DynamicSystemWrapper, yang akan memiliki DynamicSystem dan dapat melakukan praproses yang diperlukan untuk visualisasi (pemilihan konstanta untuk normalisasi, kesalahan yang dapat diterima untuk metode dengan kontrol panjang langkah ...), tetapi tidak punya waktu untuk menyelesaikan.
Visualisasi
Kami memilih OpenGL sebagai pustaka rendering karena kinerja dan kemampuannya, serta Qt5, yang memiliki pembungkus yang nyaman dibandingkan OpenGL.
Untuk memulainya, kami ingin belajar cara menggambar setidaknya sesuatu, dan setelah beberapa saat kami dapat membuat kubus pertama kami. Tak lama kemudian, versi sederhana dari model matematika muncul, dan inilah visualisasi pertama dari penarik:
Dengan visualisasi versi pertama, versi kamera yang sangat sederhana juga sudah siap. Dia tahu bagaimana berputar di sekitar satu titik dan mendekati / menjauh. Kami menginginkan lebih banyak kebebasan di luar angkasa: penarik berbeda, dan mereka perlu dieksplorasi dengan cara yang berbeda. Kemudian kamera versi kedua muncul, yang dapat dengan bebas berputar dan bergerak ke segala arah (kami dipandu oleh kamera di Minecraft). Pada saat itu, aljabar linier baru saja dimulai, dan oleh karena itu pengetahuannya belum cukup: kami harus mencari banyak informasi di Internet.
Selama ini fotonya putih, statis dan tidak menarik. Saya ingin menambahkan warna dan dinamika. Untuk memulainya, kami belajar bagaimana melukis seluruh gambar dalam satu warna, tetapi itu juga ternyata tidak menarik. Kemudian kami menemukan solusi berikut:
- Ambil banyak (100–500, Anda dapat memilih lebih banyak dalam pengaturan, yang utama adalah performa yang cukup) dari titik awal yang berdekatan satu sama lain.
- Simulasikan lintasan dari masing-masingnya.
- Merender jalur pada saat yang sama, sambil mewarnai jalur tersebut dengan warna berbeda, dan hanya menampilkan segmen jalur.
Ternyata sebagai berikut:
Kira-kira skema seperti itu tetap ada sampai akhir.
Kami tersadar bahwa garisnya terlalu "bersudut", dan kami memutuskan untuk belajar cara menghaluskannya. Tentu saja, kami mencoba mengurangi langkah simulasi, tetapi, sayangnya, prosesor modern pun tidak dapat menghitung jumlah poin seperti itu. Itu perlu untuk mencari opsi lain.
Awalnya kami berpikir bahwa OpenGL harus memiliki alat anti-aliasing, tetapi setelah banyak pencarian, kami menemukan bahwa ini bukanlah masalahnya. Kemudian muncul ide untuk menginterpolasi kurva dan menambahkan beberapa lagi di antara setiap pasangan titik yang berdekatan yang jaraknya cukup jauh. Untuk melakukan ini, perlu memilih metode untuk kurva interpolasi, dan ada banyak metode seperti itu. Sayangnya, kebanyakan dari mereka (misalnya, kurva Bezier) membutuhkan beberapa poin lagi untuk ditentukan, yang jelas tidak cocok untuk tugas kami: kami ingin hasilnya hanya bergantung pada apa yang model matematika berikan kepada kami. Setelah beberapa saat, kami menemukan interpolasi yang cocok: kurva Catmull - Roma. Ternyata seperti ini:
Setelah itu, kami memutuskan bahwa akan menyenangkan untuk merekam video di dalam aplikasi. Kami ingin mempertahankannya lintas platform, jadi kami memilih perpustakaan libav (hampir tidak ada pilihan di antara perpustakaan). Sayangnya, seluruh pustaka ditulis dalam C dan memiliki antarmuka yang sangat tidak nyaman, jadi kami butuh waktu lama untuk mempelajari cara menulis sesuatu. Semua gif berikutnya dibuat menggunakan rekaman bawaan.
Sampai saat ini, semua warna kurva telah ditentukan secara eksplisit saat pembuatan. Kami memutuskan bahwa untuk gambar yang indah, kami perlu mengatur warna secara berbeda. Untuk melakukan ini, hanya warna kontrol yang mulai ditunjukkan, dan sisanya dihitung menggunakan gradien linier. Bagian ini telah dipindahkan ke shader (sebelumnya standar).
Kami merasa menarik untuk mewarnai lintasan sedemikian rupa sehingga masing-masing lintasan berubah warna dari kepala ke ekor. Hal ini memungkinkan Anda untuk mengamati efek kecepatan:
Kemudian kami berpikir bahwa ada baiknya mencoba mengurangi waktu praproses untuk lintasan: menyisipkan kurva adalah operasi yang "mahal". Diputuskan untuk mentransfer bagian ini ke shader sehingga GPU menghitung interpolasi setiap kali diminta untuk menggambar bagian dari lintasan. Untuk ini, kami menggunakan Geometry Shader. Solusi ini memberikan banyak keuntungan: tidak ada penundaan pada sisi rendering sebelum menggambar, kemampuan untuk memperhalus kurva bahkan lebih (kalkulasi semacam itu dilakukan pada GPU lebih cepat daripada pada CPU), penggunaan RAM yang lebih sedikit (sebelumnya, semua titik yang diinterpolasi harus disimpan, sekarang - tidak ).
Pengontrol dan antarmuka pengguna
Setelah memilih Qt5 sebagai kerangka kerja dasar, pertanyaan tentang memilih teknologi untuk antarmuka segera menghilang. Qt Creator bawaan cukup memenuhi semua kebutuhan aplikasi kecil.
Untuk menanggapi permintaan pengguna, Anda harus menulis pengontrol. Untungnya, Qt memiliki cara mudah untuk menangani penekanan tombol dan memasukkan nilai ke dalam bidang. Ini menggunakan ide utama Qt - sinyal dan mekanisme slot. Misalnya, jika dalam aplikasi kita kita menekan tombol yang bertanggung jawab untuk membangun kembali model, sebuah sinyal akan dihasilkan yang akan diterima oleh slot penangan. Ini akan memulai pembangunan kembali itu sendiri.
Saat mengembangkan hampir semua aplikasi dengan antarmuka, cepat atau lambat ide membuat aplikasi multi-threaded muncul. Tampaknya perlu bagi kami: membangun model bawaan membutuhkan waktu beberapa detik, dan membuat model khusus membutuhkan waktu 10 detik. Pada saat yang sama, tentu saja, antarmuka macet, karena semua perhitungan dilakukan dalam satu utas. Untuk waktu yang lama kami membahas opsi yang berbeda dan memikirkan asynchrony menggunakan std :: async, tetapi pada akhirnya kami menyadari bahwa kami ingin dapat mengganggu kalkulasi di thread lain. Untuk melakukan ini, saya harus menulis pembungkus di atas std :: thread. Semuanya sesederhana mungkin: bendera atom untuk diperiksa dan interupsi rapi jika pemeriksaan gagal.
Ini tidak hanya memberikan hasil yang diinginkan - antarmuka berhenti menggantung - tetapi juga menambahkan beberapa fitur: karena kekhasan arsitektur dan interaksi antara data model dan visualisasi, menjadi mungkin untuk menggambar semuanya secara online, tepat saat penghitungan. Sebelumnya, Anda harus menunggu semua data.
Sistem kustom
Ada banyak penarik yang telah disediakan dalam aplikasi, tetapi kami juga ingin mengizinkan pengguna untuk memasukkan sendiri persamaannya. Untuk ini, kami menulis parser yang mendukung variabel (x, y, z), operasi matematika standar (+ - * / ^), konstanta, banyak fungsi matematika (sin, cos, log, atan, sinh, exp, dll.) dan tanda kurung. Begini Cara kerjanya:
- String kueri asli diberi token. Selanjutnya, token diurai dari kiri ke kanan dan pohon ekspresi dibangun.
- Operasi yang memungkinkan dibagi menjadi beberapa kelompok. Setiap grup memiliki Node-nya sendiri. Grup: plus-minus, perkalian-divisi, eksponen, minus unary, yang disebut sheet (ini termasuk konstanta, variabel, pemanggilan fungsi).
- Setiap kelompok memiliki tingkat penghitungannya sendiri. Setiap level menyebabkan penghitungan rekursif di level berikutnya. Anda dapat melihat bahwa urutan panggilan memengaruhi distribusi prioritas operasi. Kami memilikinya dalam urutan yang dijelaskan di atas.
Cari detail lebih lanjut di kode sumber parser .
Setiap level mengembalikan beberapa jenis pewaris Node. Ada empat di antaranya:
- operator biner - menyimpan pointer ke dua turunan dan jenis operasinya sendiri;
- operator unary - menyimpan pointer ke anak dan jenis operasinya sendiri. Ini termasuk fungsi, karena ini adalah kasus khusus dari operasi unary;
- konstan - menyimpan nilainya;
- variabel - menyimpan pointer ke tempat di memori di mana nilainya berada.
Struktur Node hanya memiliki fungsi kalk virtual yang mengembalikan nilai subpohonnya.
Keluaran yang dihasilkan sangat sesuai dengan arsitektur sistem yang dijelaskan sebelumnya. Lambda hanya diteruskan ke DynamicSystemInternal, yang menyimpan pointer ke node root dari tiga pohon yang diperoleh dan posisi memori xyz dari nilai tersebut. Ketika dipanggil, itu mengubah nilai di sana ke yang disediakan dan memanggil calc dari simpul akar.
Hasil
Hasilnya, kami mendapat program yang dapat memvisualisasikan sistem yang ditentukan pengguna dan memiliki basis sejumlah besar penarik. Dia melakukannya dengan cukup baik dan dioptimalkan, yang merupakan kabar baik.
Tapi masih banyak pekerjaan:
- tambahkan metode yang lebih tepat;
- tambahkan satu lapisan pemrosesan sistem (normalisasi dan pemilihan kesalahan otomatis dalam metode yang lebih kompleks);
- meningkatkan pekerjaan dengan sistem pengguna (dukungan untuk variabel, penghematan);
- mengoptimalkan pekerjaan mereka (kompilasi JIT atau utilitas yang mengubah sistem yang disimpan menjadi kode c ++ dan hanya memulai kompilasi ulang sehingga mereka mencapai kinerja sistem tertanam);
- menambah kemampuan untuk analisis hasil atau visualisasi yang sangat dibutuhkan oleh orang-orang yang bekerja dengan sistem semacam itu;
- ...
Repositori kami .
Dan beberapa video lagi dengan pemikat: