Pada satu titik, selama pengembangan game, saya dihadapkan dengan masalah kinerja pada PC modern. Pemodel kami memiliki komputer rakitan merah modern yang cukup kuat. Tapi proyek kami sangat lambat, memuat satu inti prosesor.
Alasannya sederhana - prosesor baru memiliki banyak inti, tetapi sebenarnya mereka kurang efisien dalam aplikasi single-threaded. Pada saat itu, saya mendapat render dalam satu aliran. Tetapi faktanya, alasannya tidak begitu banyak dalam hal ini. Dan dalam proses menemukan masalah, saya memutuskan untuk menghitung berapa banyak poligon hadir di tempat kejadian:
Pada peta permainan rata-rata, dengan jarak maksimum dan dengan sekelompok besar pohon palem -
15 824 756 segitiga! Hampir 16 juta! Sejumlah besar.
Setelah bermain sedikit dengan generator peta, saya berhasil menemukan tempat dengan 16,75 juta:
Meskipun, di sini, tempat yang mirip dengan pohon Natal hanya memberi 8,5 juta segitiga:
Adegan rata-rata terdiri dari ~ 4 juta:
Secara umum, saya senang bahwa render saya mengatasi sejumlah besar segitiga, tetapi jumlah mereka terlalu banyak. Solusinya ada di permukaan:
- Optimalkan jumlah poligon dalam model.
- Optimalkan mesh poligonal dari lanskap.
- Implementasi multi-threaded rendering.
Bagi mereka yang mungkin tidak tertarik dengan paragraf pertama dari program optimasi kami, misalnya, spesialis yang tidak berpengalaman, saya sarankan dengan aman pergi ke bagian kedua.
1. Optimalisasi jumlah poligon dalam model
Di mesin kami, vegetasi digambar dalam "paket", seluruh lanskap dibagi menjadi ubin dan sub-ubin, paket minimum adalah satu sub-ubin.
Satu paket adalah satu mesh, karena mengurangi jumlah jerat secara signifikan mengurangi jumlah panggilan CPU-> GPU.
Awalnya, pohon kami terdiri dari kerucut terpotong, bergerak ke kerucut penuh, kami berhasil menghilangkan beberapa segitiga tambahan:
Ceri pada kue adalah keputusan untuk menghapus batang dari pohon, karena dengan sudut kamera kami mereka tidak terlihat.
Sebagai hasilnya, kami berhasil mengurangi jumlah poligon, pada satu bungkus pohon Natal, dengan rata-rata 40%. Perbedaannya hampir tidak terlihat:
Dengan pohon palem itu lebih sulit, tetapi paket 5000 - 6000 poligon perlu diperbaiki. Bagaimana cara mencapai kepadatan dan kepadatan hutan? Kepadatan hutan yang tinggi dicapai karena banyaknya pohon palem:
Kami memutuskan untuk menyederhanakan telapak tangan dan memperkenalkan vegetasi tingkat kedua, yang memungkinkan kami mempertahankan kerapatan yang nyata dan mencapai 600 - 700 poligon yang diinginkan per bungkus.
Mengurangi jumlah poligon sebanyak 10 kali adalah hasil yang sangat baik.
2. Optimalisasi lanskap jala poligonal
Awalnya, kotak lanskap adalah:
Tangkapan layar memperlihatkan bagian lanskap yang polos, ini adalah ubin padang rumput, dataran, meskipun permukaan halus lainnya. Saya memutuskan untuk menghilangkan penyimpangan kecil di lanskap. Dengan demikian, ia meningkatkan luas ubin yang sama tingginya. Tidak dengan mengecek semua simpul ubin dan sub-ubin untuk kesetaraan ketinggian, saya dapat mencapai hasil ini:
Masih ada tempat datar yang bisa dioptimalkan, dan saya mulai membuat poligon dari segitiga yang tingginya sama. Ubin diambil dan semua segitiga disortir ke dalam array segitiga tinggi tidak sama dan daftar array yang terdiri dari tinggi sama dan segitiga yang berdekatan.
Dalam contoh yang diberikan, ternyata: 1 array segitiga yang tidak dapat diubah, karena mereka semua berbeda ketinggian (segitiga merah) dan daftar yang terdiri dari dua array segitiga dengan ketinggian yang sama (array diisi dengan warna).
Sekarang tugasnya adalah menemukan dari array segitiga kontur cembungnya (Concave Hull), dan banyak segitiga bisa berlubang. Sebelumnya, saya menemukan Convex Hull dalam pekerjaan saya, tidak ada masalah dengan mereka, saya sudah menggunakan algoritma Graham. Tetapi ada masalah dengan pembangunan Concave Hull ... Ternyata cukup sulit untuk menemukan informasi tentang topik ini di Internet. Saya harus menulis implementasi algoritma dari awal. Saya tidak akan berbohong jika saya mengatakan bahwa saya telah membaca sekitar sepuluh disertasi berbeda mengenai hal ini. Tetapi semua algoritma yang diusulkan memberikan hasil perkiraan dengan beberapa kesalahan. Setelah seminggu siksaan dan rasa sakit, saya muncul dengan gagasan algoritma saya.
Saya mencoba membangun kontur dari himpunan simpul segitiga, mis. Saya menerjemahkan array segitiga menjadi array simpul dan sudah membuat shell pada mereka. Tetapi untuk tugas saya ini tidak diperlukan. Menurut kesimpulan saya, membuat cangkang langsung dari segitiga lebih mudah, dan akurasi lambung cekung adalah 100%.
Awalnya, saya ingin meletakkan tambalan kode sumber dari algoritma di sini, tetapi tampaknya lebih mudah untuk menggambarkannya secara singkat: Dasar adalah aturan: jika simpul segitiga termasuk dalam empat atau kurang segitiga, maka salah satu ujung yang membentuk simpul terletak di perbatasan. Selanjutnya, daftar tepi tersebut dibentuk dengan mempertimbangkan penghapusan tepi identik. Kami menemukan tepi dengan X dan Y terkecil dan dari sana kita mulai bagian / penyortiran tepi dengan penambahan simpul unik ke daftar. Daftar ini akan menjadi cangkang banyak segitiga. Satu-satunya hal di final adalah menghapus titik collinear dari daftar.
Sebagai hasil dari ini, saya dapat membangun Concave Hull dari hampir semua kompleksitas. Algoritma ini tidak masuk ke dalam set lubang, tapi saya berkeliling dengan hanya membagi set ini menjadi dua bagian dalam lubang. Lalu saya mendapatkan sirkuit dan melakukan triangulasi:
Semuanya ternyata baik-baik saja:
Tetapi pada akhirnya, saya kecewa dengan hasilnya. Algoritme yang saya kembangkan memberikan peningkatan kinerja yang nyata saat merender adegan, karena jumlah poligon rata-rata berkurang 60 - 70%. Tetapi pada saat yang sama, pembuatan kartu mulai terjadi 10 kali lebih lambat. Algoritma ternyata sangat memakan waktu.
Butuh tiga hari untuk mempertimbangkan versi ringan dari algoritma untuk mengoptimalkan mesh poligonal lanskap, yang memberikan hasil ini:
Sekarang perhitungan data untuk optimasi telah menjadi tidak terlihat dengan latar belakang pembuatan peta, dan jumlah poligon telah menurun rata-rata sebesar 40-50%.
Artikel ini adalah uji coba dan dangkal. Jika ada orang yang tertarik dengan topik pengembangan game, saya siap untuk melanjutkan dan memperluas artikel dengan hantu langkah spesifik, solusi dan rencana masa depan. Juga, saya pikir Anda akan tertarik pada topik membangun aplikasi Open GL multi-threaded yang dikembangkan di Jawa, yang akan saya coba bicarakan pada artikel berikutnya.