Di Dalam Gempa: Selalu Pertimbangkan Alternatif

Programmer Michael Abrash, yang diundang oleh John Carmack untuk bekerja pada mesin Gempa pertama pada pertengahan 90-an, menulis serangkaian artikel selama proses pengembangan. Ini adalah kolom kedua dalam seri ini. Terjemahan yang pertama ada di sini .

Saya harus mengakui: Saya bosan dengan rock klasik. Terakhir kali saya senang mendengarkan sesuatu dari Cars atau Boston untuk waktu yang lama, sekitar 20 tahun yang lalu. Selain itu, saya tidak pernah secara khusus tertarik pada Bob Seager dan Queen, belum lagi Elvis, jadi sedikit yang berubah. Tetapi saya menyadari bahwa ada sesuatu yang berubah ketika saya ingin mengganti radio ketika saya mendengar Allman Brothers, atau Steely Dan, atau Pink Floyd, atau, Tuhan, maafkan saya, The Beatles (tetapi hanya pada hal-hal seperti "Halo Selamat Tinggal" dan "Saya akan Sebaliknya, Menangis, Bukan Tiket untuk Naik atau Sehari dalam Kehidupan; Aku belum pergi sejauh itu). Tidak butuh waktu lama untuk menemukan alasannya; Saya mendengarkan lagu yang sama selama seperempat abad, dan hanya bosan dengan lagu-lagu itu.

Saya mengatakannya sejauh ini karena ketika putri saya dan saya pergi keluar dari kafe suatu malam, stasiun radio "Tidak ada alternatif" dinyalakan untuk pertama kalinya di dalam mobil.

Kita berbicara tentang seorang gadis berusia sepuluh tahun yang dibesarkan dengan diet lamanya. Dia suka melodi, lagu-lagu menarik dan penyanyi yang bagus. Anda tidak akan menemukan ini ketika mendengarkan stasiun rock alternatif. Karena itu, tidak mengherankan bahwa ketika saya menyalakan radio, dia pertama kali berkata, "Fu!"

Tapi inilah yang mengejutkan saya: setelah mendengarkan sebentar, dia berkata: "Anda tahu, ayah, tapi itu sangat menarik."

Ini tidak hanya mengisyaratkan kepada saya tentang jenis musik apa yang akan bergemuruh di seluruh rumah ketika ia menjadi remaja. Adopsi rock alternatifnya yang cepat (dibandingkan dengan ketertarikan saya dengan musik masa muda saya selama sepuluh tahun) mengingatkan saya pada sesuatu yang mudah dilupakan ketika Anda beranjak tua dan gaya hidup menjadi mapan. Ini mengingatkan saya bahwa perlu untuk menjaga pikiran terbuka dan bersiap - apalagi, berusaha - untuk mencoba hal-hal baru. Programmer cenderung melekat pada pendekatan yang sudah dikenal, dan cenderung menggunakannya jika mereka cukup menangani tugas-tugas. Tetapi selalu ada alternatif untuk pemrograman, dan saya menemukan bahwa mereka sering perlu ditelusuri.

Tetapi mengingat sifat Quake yang selalu berubah, saya benar-benar tidak perlu membutuhkan pengingat seperti itu.

Aliran materi iklan

Pada bulan Januari, saya mendeskripsikan aliran kreatif yang mengarahkan John Carmack untuk memutuskan untuk menggunakan polygon set potensial yang dapat dihitung yang dihitung sebelumnya untuk setiap sudut pandang yang mungkin dalam Quake (permainan yang kami kembangkan bersama dalam id Software). Perhitungan awal PVS berarti bahwa alih-alih menghabiskan banyak waktu mencari basis data poligon yang terlihat dari sudut pandang saat ini dalam basis data dunia, kita dapat dengan mudah menarik semua poligon dalam PVS kembali ke depan (mengambil urutan dari pohon BSP dunia; pembahasan BSP- lihat pohon di kolom kami untuk Mei, Juli, dan November 1995), dan dapatkan adegan dirender dengan benar tanpa mencari, memungkinkan rendering mundur untuk menyelesaikan langkah terakhir penghapusan permukaan-tersembunyi (HSR). Itu adalah ide yang luar biasa, tetapi untuk arsitektur Quake jalannya belum selesai.

Menggambar objek bergerak

Misalnya, masih ada pertanyaan tentang cara menyortir dan menggambar objek bergerak dengan benar; sebenarnya, pertanyaan setelah kolom Januari ini adalah yang paling banyak ditanyakan, jadi saya akan memberikan waktu. Masalah utama adalah bahwa model yang bergerak dapat jatuh ke beberapa daun BSP, dan ketika model bergerak, daun-daun ini berubah; bersama dengan kemungkinan menemukan beberapa model dalam satu lembar, ini berarti bahwa tidak ada cara mudah untuk menggunakan urutan BSP untuk menggambar model dalam urutan yang diurutkan dengan benar. Ketika saya menulis kolom Januari, kami menggambar sprite (seperti ledakan), model BSP bergerak (seperti pintu) dan model poligon (seperti monster), memotong masing-masing dengan daun yang mereka sentuh, dan kemudian menggambar bagian yang sesuai ketika setiap lembar BSP mencapai giliran Anda saat berputar dari belakang ke depan. Namun, ini tidak memecahkan masalah memilah beberapa model bergerak dalam satu lembar relatif satu sama lain, dan juga meninggalkan masalah yang tidak menyenangkan dengan model poligon yang kompleks.

John memecahkan masalah penyortiran untuk sprite dan model poligon dengan cara yang sangat rendah teknologi: sekarang kita menuliskannya ke buffer-z. (Yaitu, sebelum menggambar setiap piksel, kami membandingkan jaraknya, atau z, dengan nilai z dari piksel yang sudah ada di layar. Sebuah piksel baru diambil hanya jika lebih dekat dari yang sudah ada.) Pertama, kami menggambar dunia utama - dinding, langit-langit, dan sebagainya. seperti itu. Pada tahap ini, tidak ada pengujian buffer-z yang digunakan (seperti yang akan segera kita lihat, definisi permukaan yang terlihat di dunia dilakukan dengan cara lain); namun, kami mengisi buffer - z dengan nilai z (sebenarnya nilai 1 / z, seperti dijelaskan di bawah) untuk semua piksel di dunia. Mengisi buffer-Z adalah proses yang jauh lebih cepat daripada buffer-z seluruh dunia, karena tidak ada pembacaan, tidak ada perbandingan, hanya menulis nilai-z. Setelah menyelesaikan gambar dan mengisi buffer-z dunia, kita cukup menggambar sprite dan model poligonal menggunakan buffer-z dan mendapatkan sort yang sempurna.

Saat menggunakan z-buffer, pertanyaan yang tak terhindarkan muncul: bagaimana ini mempengaruhi memori dan kinerja yang diduduki? Pada resolusi 320x200, ini membutuhkan memori 128 KB, yang tidak sepele, tetapi tidak begitu banyak untuk game yang membutuhkan 8 MB untuk bekerja. Dampak pada kinerja: sekitar 10% saat mengisi z-buffer dunia, dan sekitar 20% (indikator sangat bervariasi) saat merender sprite dan model poligon. Sebagai imbalannya, kita mendapatkan dunia yang diurutkan dengan sempurna, serta kemampuan untuk membuat efek tambahan, misalnya, ledakan dan asap dari partikel, karena z-buffer memungkinkan Anda untuk dengan mudah mengurutkan efek ini di dunia. Secara umum, penggunaan z-buffer secara signifikan meningkatkan kualitas visual dan fleksibilitas mesin Quake, serta menyederhanakan kode secara signifikan, dengan biaya biaya dan kinerja memori yang cukup masuk akal.

Meratakan dan meningkatkan produktivitas

Seperti yang saya katakan di atas, arsitektur Quake pertama kali menggambar dunia itu sendiri, tanpa membaca atau membandingkan buffer-z, hanya mengisi buffer-z dengan nilai-nilai poligon dunia dalam z. Setelah itu, objek yang bergerak digambar di atas dunia menggunakan buffer-z penuh. Sejauh ini saya hanya berbicara tentang cara menggambar objek bergerak. Di bagian lain kolom, saya akan berbicara tentang bagian lain dari persamaan rendering - menggambar dunia itu sendiri, ketika seluruh dunia disimpan sebagai satu pohon BSP dan tidak pernah bergerak.

Seperti yang dapat Anda ingat dari kolom Januari, kami khawatir tentang kinerja mentah dan rata-rata. Yaitu, kami ingin agar kode rendering dieksekusi secepat mungkin, tetapi pada saat yang sama, sehingga perbedaan antara kecepatan rendering adegan tengah dan paling lambat dalam rendering adegan sekecil mungkin. Tidak ada yang baik dalam rata-rata 30 frame per detik jika 10% dari adegan diambil pada 5 fps, karena menyentak dalam adegan seperti itu akan sangat terlihat dibandingkan dengan adegan rata-rata. Lebih baik rata-rata frekuensinya dengan 15 frame per detik dalam 100% kasus, meskipun kecepatan rendering rata-rata akan separuh.

PVS yang dihitung di muka adalah langkah penting menuju kinerja yang lebih tinggi dan lebih seimbang, karena menghilangkan kebutuhan untuk menentukan poligon yang terlihat - tahap yang agak lambat, yang memanifestasikan diri terburuk dalam adegan paling kompleks. Namun demikian, di beberapa tempat tingkat permainan nyata, PVS pra-komputasi mengandung lima kali lebih banyak poligon daripada yang terlihat; bersamaan dengan pelepasan permukaan bersembunyi ke belakang (HSR), ini menciptakan "zona panas" di mana laju bingkai berkurang secara nyata. Ratusan poligon ditarik kembali ke depan, dan kebanyakan dari mereka segera digambar ulang oleh poligon yang lebih dekat. Kinerja mentah secara keseluruhan juga menurun rata-rata 50% dari redraw yang disebabkan oleh rendering semua yang ada di PVS. Oleh karena itu, meskipun merender set PVS mundur bekerja sebagai tahap terakhir dari HSR dan merupakan perbaikan dari arsitektur sebelumnya, itu tidak ideal. John berpikir mungkin ada cara yang lebih baik untuk menggunakan PVS daripada menggambar dari depan ke belakang.

Dan dia sebenarnya ditemukan.

Interval Diurutkan

Tahap akhir HSR yang ideal untuk Quake adalah membuang semua poligon dalam PVS yang ternyata ternyata tidak terlihat, dan hanya menggambar piksel yang terlihat dari poligon yang tersisa tanpa menggambar ulang. Artinya, setiap piksel akan ditarik tepat satu kali dan tanpa kehilangan kinerja, tentu saja. Salah satu solusi (membutuhkan, bagaimanapun, biaya) adalah menggambar dari depan ke belakang, menyimpan area yang menggambarkan bagian layar yang saat ini tumpang tindih, dan memotong setiap poligon dengan batas-batas area ini sebelum rendering. Kedengarannya menjanjikan, tetapi sebenarnya kira-kira mengingatkan pada solusi bundle tree yang saya jelaskan di kolom Januari. Seperti yang kami ketahui, pendekatan ini membutuhkan pemborosan sumber daya tambahan dan memiliki masalah serius dengan penyeimbangan muatan.

Anda dapat melakukan jauh lebih baik jika Anda memindahkan langkah HSR terakhir dari level poligon ke level interval dan menggunakan solusi dengan interval yang diurutkan. Pada dasarnya, pendekatan ini terdiri dari mengubah setiap poligon menjadi seperangkat interval, seperti yang ditunjukkan pada Gambar 1, diikuti dengan menyortir dan memotong interval relatif satu sama lain sampai hanya bagian yang terlihat dari interval yang terlihat tetap untuk dirender, seperti yang ditunjukkan pada Gambar 2. Ini mungkin tampak sangat mirip dengan z-buffering (yang, seperti yang saya katakan di atas, terlalu lambat untuk digunakan dalam rendering dunia, meskipun cocok untuk objek bergerak yang lebih kecil), tetapi ada perbedaan penting. Tidak seperti z-buffering, hanya bagian yang terlihat dari interval yang terlihat yang dipindai piksel demi piksel (walaupun semua tepi poligon masih perlu dirasterisasi). Lebih baik lagi, penyortiran yang dilakukan oleh buffering z untuk setiap piksel menjadi operasi interval dengan interval yang diurutkan, dan karena properti integral dari daftar interval adalah keterhubungan, setiap sisi diurutkan hanya relatif terhadap beberapa interval di baris yang sama, dan hanya terpotong oleh beberapa interval ketika hamparan horizontal. Meskipun adegan kompleks masih membutuhkan waktu lebih lama untuk diproses daripada yang sederhana, kasus terburuk tidak seburuk ketika menggunakan pohon balok atau ketika menyortir dari belakang ke depan, karena tidak ada redrawing dan pemindaian untuk piksel tersembunyi, kompleksitas dibatasi oleh resolusi piksel, dan konektivitas interval membatasi pengurutan yang terburuk kasing di setiap area layar. Sebagai bonus, output dari interval yang diurutkan adalah dalam bentuk yang dibutuhkan rasterizer tingkat rendah: dalam format sekumpulan deskriptor interval, yang masing-masing terdiri dari koordinat awal dan panjang.



Generasi Interval

Singkatnya, solusi dengan interval yang diurutkan cukup dekat dengan kriteria asli kami; Meskipun tidak menghemat biaya, mereka masih tidak sepenuhnya mengerikan. Ini sepenuhnya menghilangkan redrawing dan pemindaian piksel bagian tumpang tindih poligon, dan cenderung untuk menyamakan kinerja dalam kasus terburuk. Kami tidak akan hanya bergantung pada interval yang diurutkan sebagai mekanisme untuk menghilangkan permukaan yang tersembunyi, tetapi PVS pra-komputasi mengurangi jumlah poligon ke tingkat yang ditangani dengan interval yang cukup baik.

Jadi, kami telah menemukan pendekatan yang kami butuhkan; tetap hanya untuk menulis kode dan ini selesai, kan? Ya dan tidak Pendekatan konseptual dengan interval yang diurutkan sederhana, tetapi sangat sulit diimplementasikan: Anda perlu membuat beberapa keputusan desain yang penting, butuh sedikit matematika dan ada perangkap yang licik. Mari kita lihat solusi desain terlebih dahulu.

Iga vs Interval

Keputusan pertama adalah memilih apa yang akan disortir: interval atau tepi (kedua konsep ini termasuk kategori umum "interval disortir"). Meskipun hasil dalam kedua kasus akan sama (daftar interval yang perlu ditarik tanpa menggambar ulang), implementasi dan implikasi kinerja sangat berbeda, karena penyortiran dan pemotongan dilakukan oleh struktur data yang sangat berbeda.

Saat menyortir interval, interval ini disimpan dalam segmen memori yang diurutkan berdasarkan daftar tertaut x, biasanya satu segmen per baris raster. Setiap poligon, pada gilirannya, dirasterisasi ke dalam interval, seperti yang ditunjukkan pada Gambar 1. Setiap interval diurutkan dan dipotong ke dalam segmen memori dari garis raster di mana interval berada, seperti yang ditunjukkan pada Gambar 2, sehingga pada setiap titik waktu setiap segmen berisi interval yang ditemui terdekat , selalu tanpa overlay. Dengan pendekatan ini, maka perlu untuk menghasilkan semua interval untuk setiap poligon secara bergantian, dan setiap interval segera diurutkan, dipotong dan ditambahkan ke segmen memori yang sesuai.



Gambar 2: interval dari poligon A dari Gambar 1 diurutkan dan dipotong pada interval dari poligon B, sedangkan poligon A berada pada jarak konstan 100 sepanjang sumbu Z, dan poligon B berada pada jarak konstan 50 sepanjang sumbu Z (poligon B lebih dekat ke kamera )

Saat menyortir tepi, tepi ini disimpan dalam segmen memori yang diurutkan berdasarkan daftar x tertaut menurut garis raster awal. Setiap poligon, pada gilirannya, dibagi menjadi beberapa sisi, bersama-sama membuat daftar semua sisi dalam adegan. Ketika semua tepi semua poligon di piramida visibilitas ditambahkan ke daftar tepi, seluruh daftar dipindai dalam satu lintasan dari atas ke bawah, dari kiri ke kanan. Daftar daftar tepi aktif (AEL) disimpan. Pada setiap langkah ke garis raster baru, tepi yang muncul pada garis raster ini dihapus dari AEL, tepi aktif pergi ke koordinat x baru, tepi mulai dari garis raster baru ditambahkan ke AEL, dan tepi diurutkan berdasarkan koordinat x saat ini.

Untuk setiap baris raster, daftar poligon aktif (APL) yang diurutkan berdasarkan z disimpan. Ini berjalan agar diurutkan berdasarkan x AEL. Ketika bertemu dengan masing-masing tepi baru (yaitu, ketika setiap poligon mulai atau berakhir ketika bergerak dari kiri ke kanan), poligon yang terkait dengannya diaktifkan dan disortir menjadi APL (dalam kasus tepi awal), seperti yang ditunjukkan pada Gambar 3, atau dinonaktifkan dan dihapus dari APL ( dalam kasus trailing edge), seperti yang ditunjukkan pada Gambar 4. Jika poligon terdekat telah berubah (yaitu, yang terdekat adalah poligon baru atau poligon terdekat telah berakhir), untuk poligon yang baru saja berhenti menjadi yang terdekat, interval dibuat mulai dari titik di mana poligon tidak vym karena adalah yang paling dekat dan berakhir x koordinat tepi saat ini dan saat ini x-koordinat dicatat dalam TPA, yang sekarang paling dekat. Koordinat tersimpan ini kemudian digunakan sebagai awal interval yang dibuat ketika poligon terdekat yang baru berhenti berada di depan.



Gambar 3: aktivasi poligon ketika tepi awal terdeteksi di AEL.



Gambar 4: penonaktifan poligon ketika sebuah trailing edge terdeteksi di AEL.

Jangan khawatir jika Anda tidak sepenuhnya memahami hal di atas; ini hanya gambaran singkat tentang penyortiran tepi sehingga bagian kolom lainnya lebih jelas. Penjelasan terperinci akan ada di kolom berikutnya.

Interval yang dihasilkan dengan menyortir tepi menjadi interval yang persis sama dengan yang akan dihasilkan dari penyortiran interval; perbedaannya adalah pada struktur data menengah yang digunakan untuk mengurutkan interval dalam adegan. Ketika menyortir tepi, interval disimpan di dalam tepi sampai set akhir interval terlihat dihasilkan, jadi penyortiran, pemangkasan dan membuat interval dilakukan ketika setiap tepi menambah atau menghilangkan poligon, berdasarkan pada keadaan interval yang ditentukan oleh tepi dan set poligon aktif. Ketika menyortir interval, interval langsung menjadi jelas ketika setiap poligon diraster, dan interval menengah ini kemudian disortir dan dipotong relatif terhadap interval di garis raster untuk membuat interval akhir; oleh karena itu, keadaan interval secara konstan ditetapkan secara eksplisit, dan semua pekerjaan dilakukan secara langsung pada interval.

Kedua penyortiran interval dan penyortiran tepi bekerja dengan baik, mereka telah berhasil digunakan dalam proyek komersial. Untuk Quake, kami memilih penyortiran tepi, sebagian karena tampaknya lebih efisien dan memiliki konektivitas horizontal yang sangat baik yang menyediakan waktu penyortiran minimum, berbeda dengan penyortiran yang berpotensi mahal ke dalam daftar tertaut, yang mungkin diperlukan saat menyortir interval.Namun, alasan yang lebih penting adalah bahwa ketika menyortir tepi, kita dapat membagi tepi antara poligon yang berdekatan, dan ini mengurangi penyortiran, pemangkasan dan rasterisasi tepi sekitar setengah, dan juga secara signifikan mengurangi basis data dunia karena fakta bahwa tepi menjadi umum.

Dan keuntungan terakhir dari menyortir tepi adalah tidak membedakan antara cembung dan poligon cekung. Untuk sebagian besar mesin grafis, ini bukan aspek yang sangat penting, tetapi dalam Quake, pemangkasan, pengubahan, proyeksi dan pemilahan tepi telah menjadi hambatan utama, jadi kami melakukan segala yang mungkin untuk mengurangi jumlah poligon dan sisi, dan poligon cekung sangat membantu dalam hal ini. Meskipun poligon cekung juga dapat diproses dengan menyortir interval, ini memerlukan penurunan kinerja yang signifikan.

Namun, tidak ada jawaban pasti tentang pendekatan terbaik. Pada akhirnya, interval pemilahan dan tepi pemilahan melakukan satu fungsional, dan memilih di antara keduanya adalah masalah kegunaan. Di kolom berikutnya, saya akan berbicara lebih banyak tentang mengurutkan tepi dengan implementasi penuh. Di sisa kolom ini, saya akan meletakkan dasar untuk selanjutnya dengan berbicara tentang tombol sortir dan perhitungan 1 / z. Dalam prosesnya, saya akan membuat beberapa referensi untuk aspek-aspek dari sorting edge, yang belum dibahas secara rinci; Saya minta maaf, tetapi ini tidak bisa dihindari, dan semuanya akan menjadi jelas hanya pada akhir kolom berikutnya.

Rib Sort Keys

Sekarang kita tahu bahwa kita akan memilih penyortiran tepi, dan menggunakannya untuk membuat interval poligon terdekat dengan pemirsa, pertanyaan muncul: bagaimana Anda tahu jika poligon ini adalah yang terdekat? Idealnya, kita hanya akan menyimpan kunci pengurutan setiap poligon, dan ketika tepi baru muncul, kita akan membandingkan kunci permukaannya dengan kunci-kunci poligon aktif lain saat ini untuk dengan mudah menentukan poligon mana yang paling dekat.

Kedengarannya terlalu bagus, tapi itu mungkin. Jika, misalnya, basis data dunia Anda disimpan sebagai pohon BSP, dan semua poligon dipotong ke daun BSP, maka urutan traversal BSP akan menjadi urutan rendering yang benar. Karena itu, misalnya, jika Anda memutar BSP dari depan ke belakang, menugaskan setiap poligon nilai kunci yang semakin besar ketika mencapai itu, maka poligon dengan nilai kunci yang lebih tinggi akan dijamin berada di depan poligon dengan kunci yang lebih kecil. Pendekatan ini telah digunakan di Quake selama beberapa waktu, tetapi sekarang solusi yang berbeda sedang diterapkan untuk alasan yang akan saya jelaskan segera.

Jika Anda tidak memiliki BSP atau struktur data yang serupa, atau jika Anda memiliki banyak poligon bergerak (BSP tidak memproses poligon bergerak dengan sangat efisien), maka cara lain untuk mencapai tujuan adalah dengan menyortir semua poligon relatif satu sama lain sebelum membuat adegan dan menetapkan kunci yang sesuai sesuai dengan spasial mereka hubungan di viewport. Sayangnya, dalam kasus umum ini adalah tugas yang sangat lambat, karena setiap poligon harus dibandingkan satu sama lain. Ada teknik untuk meningkatkan kinerja penyortiran poligon, tetapi saya tidak tahu siapa pun yang akan melakukan penyortiran umum poligon pada PC secara real time.

Alternatifnya adalah mengurutkan berdasarkan jarak z dari pemirsa di ruang layar; solusi ini sangat cocok dengan konektivitas spasial yang unggul dari penyortiran tepi. Saat bertemu dengan setiap sisi baru pada garis raster, Anda dapat menghitung jarak z poligon yang sesuai dan membandingkan dengan jarak poligon lain, setelah itu poligon dapat disimpan dalam APL.

Namun, mendapatkan jarak sepanjang z bisa menjadi tugas yang sulit. Jangan lupa bahwa kita harus dapat menghitung z pada titik sembarang pada poligon, karena suatu sisi dapat terjadi dan menyebabkan poligon mengurutkan APL di mana saja pada layar. Kita dapat menghitung z langsung dari koordinat layar x dan y dan persamaan bidang poligon, tetapi, sayangnya, ini tidak dapat dilakukan dengan sangat cepat, karena z untuk pesawat tidak berubah secara linear dalam ruang layar; Namun, 1 / z bervariasi secara linear, jadi kami menggunakan nilai ini. (Untuk pembahasan linearitas dalam ruang layar dan gradien untuk 1 / z, lihat seri Chris Hecker tentang pemetaan tekstur di majalah Game Developer tahun lalu).) Keuntungan lain menggunakan 1 / z adalah resolusi meningkat dengan jarak yang menurun, yaitu, dengan 1 / z kita akan selalu memiliki resolusi kedalaman terbaik untuk objek dekat yang paling penting.

Cara yang jelas untuk mendapatkan nilai 1 / z pada titik sembarang dalam poligon adalah dengan menghitung 1 / z pada titik, interpolasi mereka di kedua sisi poligon, dan interpolasi antara tepi untuk mendapatkan nilai pada titik yang diinginkan. Sayangnya, ini membutuhkan banyak pekerjaan yang harus dilakukan di sepanjang tulang rusuk masing-masing; lebih buruk lagi, ini membutuhkan pembagian untuk menghitung langkah 1 / z per piksel di setiap interval.

Akan lebih baik untuk menghitung 1 / z langsung dari persamaan bidang dan layar x dan y dari piksel yang menarik bagi kami. Persamaannya memiliki bentuk sebagai berikut:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

di mana z adalah koordinat dalam ruang-z titik pada bidang yang diproyeksikan ke dalam koordinat layar (x ', y') (asal koordinat untuk perhitungan ini adalah pusat proyeksi, titik pada layar tepat di depan sudut pandang), [abc] adalah normal ke pesawat di viewport, dan d adalah jarak dari asal viewport ke pesawat sepanjang normal. Pembagian dilakukan hanya sekali untuk setiap pesawat, karena a, b, c dan d adalah konstanta untuk pesawat.

Perhitungan 1 / z penuh membutuhkan dua perkalian dan dua tambahan, dan setiap operasi harus dilakukan dengan titik mengambang untuk menghindari kesalahan rentang. Volume perhitungan floating point seperti itu tampaknya mahal, tetapi kenyataannya tidak, terutama pada prosesor Pentium, di mana nilai 1 / z pesawat pada titik mana pun dapat dihitung dalam bahasa assembly hanya dalam enam siklus.

Jika Anda tertarik, inilah derivasi cepat dari persamaan 1 / z. Persamaan bidang untuk bidang memiliki bentuk berikut:

$$

$$ax + by + cz - d = 0$$

di mana x dan y adalah koordinat ruang tampilan, a, b, c, d, dan z didefinisikan di atas. Jika kita melakukan substitusi$$$x=x'z$ dan $$$y=-y'z$(dari definisi proyeksi perspektif; y mengubah tanda karena ia naik di viewport, tetapi turun di ruang layar). Melakukan permutasi, kami memperoleh:

$$

$$z = d / (ax' - by' + c)$$

Melawan dan memperluas persamaan, kita memperoleh:

$$

$$1/z = ax'/d - by'/d + c/d$$

Nanti saya akan menunjukkan 1 / z sorting beraksi.

Gempa dan urutkan berdasarkan z

Saya sebutkan di atas bahwa Quake tidak lagi menggunakan urutan BSP sebagai kunci pengurutan; pada kenyataannya, 1 / z sekarang diterapkan sebagai kunci. Terlepas dari keanggunan gradien, menghitung 1 / z darinya jelas lebih lambat daripada hanya membandingkan dengan kunci urutan BSP, jadi mengapa kita beralih menggunakan 1 / z di Quake?

Alasan utamanya adalah penurunan jumlah poligon. Untuk rendering dalam urutan BSP, perlu untuk mengikuti aturan-aturan tertentu, termasuk poligon ketika berpotongan dengan pesawat-BSP harus dibagi. Pemisahan ini secara signifikan meningkatkan jumlah poligon dan pinggirannya. Berkat pengurutan dengan 1 / z, kita dapat membiarkan poligon tidak terbagi, tetapi masih mendapatkan urutan gambar yang benar, jadi kita perlu memproses lebih sedikit bagian tepi; sementara rendering umumnya dipercepat, meskipun ada tambahan biaya penyortiran sebesar 1 / z.

Keuntungan lain dari penyortiran 1 / z adalah bahwa ia memecahkan masalah penyortiran yang disebutkan di awal artikel ini: model yang bergerak, yang sendiri adalah pohon BSP kecil. Penyortiran dalam tatanan dunia BSP tidak akan berfungsi di sini karena model ini merupakan BSP yang terpisah, dan tidak ada cara mudah untuk menanamkannya dalam urutan berurutan dari dunia BSP. Kami tidak ingin menggunakan z-buffering untuk model-model ini karena mereka sering merupakan objek besar (misalnya, pintu), dan kami tidak ingin kehilangan manfaat dari pengurangan gambar ulang yang disediakan pintu tertutup ketika merender melalui daftar tepi. Saat menggunakan interval yang disortir, tepi model BSP yang bergerak hanya ditempatkan pada daftar tepi (pertama memotong poligon sehingga tidak bersinggungan dengan permukaan padat dunia untuk menghindari kompleksitas,terkait dengan penetrasi timbal balik) alih-alih semua ujung dunia, dan sisanya diurutkan berdasarkan 1 / z.

Pindah

Artikel itu, tanpa ragu, menetapkan sejumlah besar informasi, dan banyak yang belum dimasukkan ke dalam kepala Anda. Kode dan penjelasan dari artikel selanjutnya akan membantu; jika Anda ingin melihat terlebih dahulu, pada saat Anda membaca artikel ini, kode tersebut harus tersedia di ftp.idsoftware.com/mikeab/ddjsort.zip. Ada baiknya juga melihat Grafik Komputer Foley dan Van Dam atau Elemen Prosedural untuk Grafik Komputer Rogers.

Tidak jelas pada saat ini bagaimana hasil dari Gempaharus mengurutkan tepi - dalam urutan BSP atau 1 / z. Bahkan, tidak ada jaminan bahwa interval yang diurutkan dalam bentuk apa pun akan menjadi solusi terakhir. Kadang-kadang tampaknya kita mengganti mesin grafis sesering ketika mereka menempatkan Elvis di stasiun radio yang didedikasikan untuk hit tahun 50-an (tapi, mudah-mudahan, dengan hasil yang jauh lebih estetis!), Dan kita tidak akan ragu mempertimbangkan alternatif hingga tanggal rilis permainan.