Inside Quake: Mendefinisikan Permukaan Terlihat

Veteran pemrograman grafis tiga dimensi Michael Abrash, menggunakan contoh pengembangan Gempa pertama, berbicara tentang perlunya pemikiran kreatif dalam pemrograman.

Bertahun-tahun yang lalu, saya bekerja untuk perusahaan video adapter Video Seven yang sekarang sudah tidak aktif. Di sana saya membantu mengembangkan klon VGA. Rekan saya Tom Wilson, yang bekerja selama berbulan-bulan untuk mengembangkan chip Video Seven VGA, mencoba membuat VGA secepat mungkin, dan yakin bahwa kinerjanya dioptimalkan hampir secara maksimal. Namun, ketika Tom sudah memperkenalkan sentuhan akhir pada desain chip, kami mendengar desas-desus bahwa pesaing kami Paradise telah mencapai kinerja yang lebih besar di klon pengembangannya dengan menambahkan FIFO ke dalamnya.

Ini adalah akhir dari rumor - kami tidak tahu apa itu FIFO, atau seberapa besar ia membantu, tidak ada yang lain. Namun, Tom, biasanya orang yang ramah dan santai, berubah menjadi fanatik yang aktif dan terobsesi dengan terlalu banyak kafein dalam darahnya. Berdasarkan bit-bit informasi ini, ia mencoba mencari tahu apa yang bisa dilakukan Paradise. Pada akhirnya, ia sampai pada kesimpulan bahwa Paradise mungkin memasukkan buffer tulis FIFO antara bus sistem dan VGA, sehingga ketika CPU merekam ke memori video, data yang sedang ditulis akan langsung masuk ke FIFO, dan ini akan memungkinkan CPU untuk terus memproses daripada berdiri diam setiap kali ketika dia sedang menulis ke tampilan memori.

Tom tidak memiliki elemen logika, atau waktu yang cukup untuk mengimplementasikan FIFO penuh, tetapi ia berhasil mengimplementasikan FIFO dengan kedalaman operasi tunggal, yang memungkinkan prosesor untuk mengambil alih chip VGA dengan satu operasi tulis. Tom tidak yakin ini akan memberikan hasil yang baik, tetapi itu adalah satu-satunya hal yang bisa dia lakukan, jadi dia menerapkan sistem ini dan mentransfer chip ke produksi.

Ternyata FIFO untuk satu operasi bekerja sangat keren: pada saat itu Video Seven VGA-chip adalah yang tercepat di pasar; mereka menjadi bukti kejeniusan Tom dan bukti apa yang mampu diciptakan pencipta di bawah tekanan keadaan. Namun, hal hebat tentang cerita ini adalah bahwa desain Paradise FIFO tidak ada hubungannya dengan desain Tom, dan itu tidak berhasil sama sekali . Paradise memasukkan buffer baca FIFO antara memori tampilan dan tahap output video chip VGA, yang memungkinkan untuk membaca output video terlebih dahulu sehingga ketika CPU perlu mengakses memori tampilan, piksel dapat diambil dari FIFO, dan perintah CPU dijalankan secara instan. Ini benar-benar meningkatkan kinerja, tetapi tidak sebanyak buffer tulis FIFO Tom.

Dan kasus ini dapat dianggap sebagai perumpamaan yang baik tentang sifat dari proses kreatif yang dapat dicapai seseorang. Potongan-potongan berita tentang chip Paradise hampir tidak mengandung informasi faktual, tetapi mereka memaksa Tom untuk melampaui batas yang secara tidak sadar ia tetapkan, mengembangkan desain awal chip tersebut. Saya percaya bahwa ini adalah elemen paling penting dari setiap desain yang cerdik, baik dari bidang perangkat keras, perangkat lunak atau bidang kreatif lainnya, dan dialah yang lahir dalam berita Tom tentang Paradise: kemampuan untuk mendeteksi batas yang Anda buat dalam proses mengerjakan proyek, dan mengatasinya perbatasan.

Masalahnya, tentu saja, adalah bagaimana mengatasi perbatasan, keberadaan yang bahkan Anda tidak tahu. Tidak ada formula untuk sukses, tetapi dua prinsip dapat melayani tujuan ini dengan baik: pertama, sederhanakan, kedua, terus-menerus mencoba sesuatu yang baru.

Biasanya, ketika Anda merasa bahwa kode semakin rumit, Anda mulai membuat perubahan kecil pada struktur beku, dan ada kemungkinan besar bahwa Anda dapat meningkatkan produktivitas dan mengurangi jumlah kode dengan menciptakan desain lagi. Struktur yang benar-benar bagus harus memberikan momen kepuasan yang mendalam ketika semuanya jatuh ke tempatnya, dan Anda terkejut melihat betapa kecilnya jumlah kode yang dibutuhkan dan seberapa baik semua case batas bekerja.

Dalam proses peninjauan struktur, penting untuk mempelajari ide-ide yang muncul dalam pikiran, tidak peduli seberapa gila mereka. Banyak dari ide-ide hebat yang saya dengar pada mulanya tampak tidak masuk akal karena tidak sesuai dengan gambaran dunia saya yang ada. Seringkali ide-ide ini benar-benar gila, tetapi sama seperti berita Paradise chip merangsang imajinasi Tom, eksplorasi agresif dari ide-ide yang tampaknya delusi dapat membuka kemungkinan baru bagi Anda.

Ilustrasi yang bagus: evolusi mesin grafis 3D Quake.

Tugas grafik 3D paling rumit di dunia

Saya menghabiskan tujuh bulan terakhir bekerja pada Quake, pewaris DOOM dari id Software, dan saya berasumsi bahwa tiga bulan kemudian, pada saat Anda membaca artikel ini, Quake akan dirilis sebagai shareware.

Dalam hal grafis, Quake akan untuk DOOM seperti DOOM untuk pendahulunya, Wolfenstein 3D. Quake menambahkan 3D nyata yang sewenang-wenang (pemain dapat melihat ke atas dan ke bawah, bersandar ke samping dan bahkan jatuh ke satu sisi), pencahayaan terperinci dan bayangan, monster dan karakter 3D alih-alih sprite DOOM. Segera saya akan membicarakan semua ini lebih terinci, tetapi bulan ini saya ingin membicarakan tugas itu, yang dalam buku saya saya sebut paling sulit dalam grafik tiga dimensi: menentukan permukaan yang terlihat (menggambar permukaan yang sesuai untuk setiap piksel), dan tentang tugas yang sangat dekat dengannya - tentang kliping (secepat mungkin membuang poligon tak terlihat sebagai cara untuk mempercepat penentuan permukaan yang terlihat). Demi singkatnya, saya akan menggunakan VSD singkatan untuk menunjukkan definisi penentuan permukaan yang terlihat dan pemusnahan.

Mengapa saya menganggap VSD tugas paling sulit dari grafik 3D? Meskipun tugas-tugas rasterisasi, misalnya, pemetaan tekstur, sama menakjubkan dan pentingnya, mereka dalam lingkup yang sangat terbatas, dan setelah munculnya akselerator 3D, solusi mereka akan dipindahkan ke perangkat keras; selain itu, skala mereka hanya bergantung pada resolusi layar, yaitu, mereka cukup sederhana.

Sebaliknya, VSD adalah tugas yang tidak terbatas dan puluhan pendekatan sedang digunakan untuk menyelesaikannya. Tetapi yang lebih penting, kinerja VSD dalam skala solusi naif tergantung pada kompleksitas adegan, yang biasanya meningkat sebagai fungsi kuadratik atau kubik, dan karenanya dengan cepat menjadi faktor pembatas dalam menciptakan dunia yang realistis. Saya percaya bahwa dalam beberapa tahun ke depan, VSD akan menjadi masalah yang semakin dominan dalam grafik 3D real-time untuk PC, karena detail dunia 3D akan terus meningkat. Sudah hari ini, tingkat gempa ukuran padat dapat mengandung sekitar 10.000 poligon, yaitu hampir tiga kali lebih banyak dari tingkat DOOM yang sebanding dalam ukuran.

Struktur Tingkat Gempa

Sebelum mempelajari VSD, izinkan saya menyebutkan bahwa setiap level Quake disimpan sebagai satu pohon BSP tiga dimensi yang besar. Pohon BSP ini, seperti BSP lainnya, membagi ruang, dalam hal ini, di sepanjang bidang poligon. Namun, tidak seperti pohon BSP yang saya tunjukkan sebelumnya, pohon Quake BSP tidak menyimpan poligon di simpul pohon sebagai bagian dari bidang pemisah, tetapi dalam daun kosong (tidak terisi), seperti yang ditunjukkan pada Gambar 1 di tampilan atas.


Gambar 1. Dalam Gempa, poligon disimpan dalam daun kosong. Area gelap diisi daun (volume terisi, seperti bagian dalam dinding)

Urutan rendering yang benar dapat diperoleh dengan rendering daun dalam urutan BSP "depan ke belakang" atau "kembali ke depan". Selain itu, karena daun BSP selalu cembung, dan poligon adalah batas-batas daun BSP yang terlihat ke dalam, poligon dari lembaran apa pun tidak akan pernah bisa tumpang tindih dan dapat ditarik dalam urutan apa pun. (Ini adalah properti umum polyhedra cembung.)

Memotong dan menentukan permukaan yang terlihat

Idealnya, proses VSD harus bekerja sebagai berikut: pertama, Anda harus membuang semua poligon yang berada di luar piramida visibilitas, dan juga memotong semua bagian tak terlihat dari poligon yang sebagian terlihat. Maka Anda hanya perlu menggambar piksel dari setiap poligon yang benar-benar terlihat dari sudut pandang saat ini, seperti yang ditunjukkan pada Gambar 2 di tampilan atas, tanpa membuang waktu berulang kali menggambar ulang piksel; perhatikan berapa sedikit poligon pada Gambar 2 yang perlu Anda gambar. Dan akhirnya, di dunia yang ideal, memeriksa visibilitas bagian-bagian poligon harus murah, dan waktu pemrosesan harus sama untuk semua sudut pandang yang memungkinkan, sehingga permainan bekerja dengan lancar.


Gambar 2. Arsitektur VSD yang ideal membuat hanya bagian yang terlihat dari poligon yang terlihat.

Dalam proses menyelesaikan tugas ini, mudah untuk menentukan poligon mana yang benar-benar di luar lingkup piramida visibilitas atau terpotong sebagian, dan sangat mungkin untuk mengetahui dengan tepat piksel mana yang akan digambar. Sayangnya, dunia jauh dari ideal, dan semua cek ini mahal, jadi triknya adalah mempercepat atau melewati pemeriksaan yang berbeda, semuanya menciptakan hasil yang diperlukan.

Seperti yang saya jelaskan secara rinci dalam artikel sebelumnya, dengan BSP, Anda dapat dengan mudah dan murah berkeliling dunia dalam urutan depan-ke-belakang atau belakang-ke-depan. Solusi VSD yang paling sederhana adalah dengan hanya melintasi pohon itu kembali ke depan, memotong setiap poligon dengan piramida visibilitas dan menggambarnya jika wajahnya diarahkan ke kamera dan tidak sepenuhnya terpotong (algoritma artis). Tetapi apakah ini solusi yang memadai?

Untuk dunia yang relatif sederhana, ini cukup berlaku. Namun, skalanya tidak baik. Salah satu masalah adalah bahwa ketika poligon baru ditambahkan ke dunia untuk memotong poligon yang tidak terlihat, semakin banyak transformasi dan pemeriksaan diperlukan; setelah ambang tertentu, ini akan mulai secara signifikan memperlambat kinerja.

Untungnya, masalah khusus ini memiliki solusi yang baik. Seperti disebutkan di atas, setiap daun di pohon BSP menggambarkan subruang cembung, dan node yang terhubung ke daun membatasi ruang. Yang kurang jelas adalah bahwa setiap node dalam pohon BSP juga menggambarkan subruang - subruang yang terdiri dari semua anak-anak dari simpul tersebut, seperti yang ditunjukkan pada Gambar 3. Anda dapat mengambilnya dengan cara ini: setiap node membagi menjadi dua bagian subruang yang dibuat oleh node yang terletak di atas dalam tree, dan elemen turunan node selanjutnya membingkai subruang ini menjadi semua daun yang berasal dari simpul tersebut.


Gambar 3: Node E menggambarkan ruang bagian gelap yang berisi daun 5, 6, 7 dan simpul F.

Karena subruang dari simpul dibatasi dan cembung, kita dapat memeriksa apakah itu sepenuhnya di luar piramida visibilitas. Jika demikian, maka semua anak - anak dari simpul pasti akan benar-benar terputus dan dapat dibuang tanpa pemrosesan tambahan. Karena bagian utama dunia biasanya terletak di luar piramida visibilitas, banyak poligon dunia dapat terputus hampir tanpa biaya oleh fragmen besar subruang node. Melakukan pemeriksaan ideal untuk memotong subruang cukup mahal, oleh karena itu, biasanya untuk setiap node, pembatas jajaran genjang atau bola digunakan untuk memotong cek.

Artinya, memotong sepanjang piramida visibilitas bukanlah masalah, dan Anda dapat menggunakan BSP untuk mundur. Jadi apa masalahnya?

Menggambar ulang

Masalah yang penulis utama dari DOOM dan teknologi Quake yang dihadapi John Carmack ketika mengembangkan Quake adalah bahwa di dunia yang kompleks, banyak adegan dalam piramida visibilitas memiliki sejumlah besar poligon. Sebagian besar poligon ini tumpang tindih sebagian atau seluruhnya oleh poligon lain, tetapi algoritma artis yang dijelaskan di atas memerlukan gambar setiap piksel dari setiap poligon dalam piramida visibilitas. Namun, mereka sering diberikan hanya untuk digambar ulang oleh orang lain. Pada tingkat Gempa 10.000 poligon, mudah untuk mendapatkan kasus terburuk menggambar ulang ketika piksel diambil 10 kali atau lebih; yaitu, dalam beberapa bingkai, setiap piksel rata-rata akan diambil 10 kali atau lebih. Tidak ada rasterizer yang cukup cepat untuk mengimbangi urutan besarnya yang diperlukan untuk membuat adegan; lebih buruk, algoritma artis menciptakan perbedaan kinerja yang sangat besar antara kasus terbaik dan terburuk, yang mengarah pada perubahan signifikan dalam frame rate saat memindahkan pemirsa.

Jadi, John dihadapkan dengan masalah mengurangi jumlah redrawing ke level yang dapat diterima. Idealnya, setiap piksel harus diambil hanya satu kali, tetapi tidak lebih dari dua atau tiga kali dalam kasus terburuk. Sedangkan untuk memotong piramida visibilitas, idealnya semua poligon yang tak terlihat dalam piramida dipotong dengan hampir tanpa biaya tambahan. Nilai tambah juga memungkinkan untuk hanya menggambar bagian yang terlihat dari poligon yang terlihat sebagian, tetapi pada saat yang sama keseimbangan harus dipertahankan: operasi harus menghabiskan kurang dari menggambar ulang.

Ketika saya datang ke id pada awal Maret, John sudah memiliki prototipe mesin dan rencana garis besar, jadi saya berasumsi bahwa pekerjaan kami hanya akan menyelesaikan dan mengoptimalkan mesin ini. Namun, jika saya tahu cerita id, saya bisa mencari tahu apa itu. John menciptakan tidak hanya DOOM, tetapi juga mesin untuk 3D Wolf dan beberapa game sebelumnya lainnya, dan selama proses pengembangan ia membuat beberapa versi berbeda dari setiap mesin (begitu ia menciptakan empat mesin dalam empat minggu), yaitu, dalam empat tahun ia menulis sekitar 20 mesin . Keinginan John yang tak kenal lelah untuk semakin banyak teknologi baru dan berkualitas tinggi dari mesin Quake akan berakhir hanya setelah rilis game.

Tiga bulan setelah kedatangan saya, hanya satu elemen dari struktur VSD asli tetap di mesin, dan keinginan John untuk "mencoba hal-hal baru" berjalan sejauh yang saya belum pernah melihat hal seperti itu sebelumnya.

Pohon besar

Dalam proyek Quake asli John, rendering dilakukan dari depan ke belakang menggunakan pohon BSP kedua yang melacak sudah menggambar dan masih mengosongkan bagian layar yang perlu diisi dengan poligon yang tersisa. Secara logis, pohon BSP ini dapat dianggap sebagai wilayah dua dimensi yang menggambarkan bagian layar yang diisi dan kosong, seperti yang ditunjukkan pada Gambar 4, tetapi sebenarnya itu adalah pohon tiga dimensi, yang dikenal sebagai "pohon balok". Pohon balok adalah seperangkat sektor 3D (tandan) yang dibatasi oleh pesawat yang diproyeksikan dari beberapa titik pusat (dalam kasus kami, sudut pandang), seperti yang ditunjukkan pada Gambar 5.


Gambar 4. Pohon balok gempa secara efektif membagi layar menjadi area 2D


Gambar 5. Pohon balok gempa terdiri dari sektor 3D, atau balok, diproyeksikan dari sudut pandang ke tepi poligon.

Dalam proyek John, sebuah pohon berkas awalnya terdiri dari satu berkas yang menggambarkan piramida visibilitas; segala sesuatu di luar bundel ini dianggap diisi (yaitu, tidak perlu menggambar apa pun di sana), dan segala sesuatu di dalam bundel itu dianggap kosong. Ketika mencapai poligon baru dengan mengitari pohon BSP dunia dari depan ke belakang, poligon ini diubah menjadi balok dengan menggambar bidang dari tepinya melalui sudut pandang, dan semua bagian balok yang melintas balok kosong di pohon balok dianggap ditarik dan ditambahkan ke pohon balok sebagai balok yang diisi. Ini berlanjut, baik sampai poligon berakhir, atau sampai pohon umbi menjadi penuh sepenuhnya. Setelah pohon balok selesai, bagian-bagian poligon yang terlihat terperangkap dalam pohon balok ditarik.

Keuntungan bekerja dengan pohon bundel tiga dimensi alih-alih wilayah 2D adalah untuk menentukan sisi mana dari bundel pesawat tempat verteks poligon aktif, cukup untuk memeriksa tanda produk vektor sinar ke verteks dan normal ke pesawat, karena semua pesawat bundel melewati awal koordinat (sudut pandang). Selain itu, karena bidang balok sepenuhnya dijelaskan oleh satu normal, untuk menghasilkan balok dari tepi poligon, hanya produk skalar dari tepi dan balok dari tepi ini ke sudut pandang sudah cukup. Akhirnya, untuk grup yang dipotong oleh piramida visibilitas yang dijelaskan di atas, seseorang dapat menggunakan bola pembatas node BSP.

Pada awalnya, properti pohon bundel (berakhir ketika pohon bundel menjadi penuh) tampak menarik karena sepertinya itu akan membatasi kinerja dalam kasus terburuk. Sayangnya, pemandangan masih memungkinkan di mana Anda bisa melihat semuanya sampai ke langit atau dinding belakang dunia, jadi dalam kasus terburuk, Anda masih harus memeriksa semua poligon di piramida visibilitas sehubungan dengan pohon tandan. Masalah serupa juga dapat terjadi dengan retakan kecil karena keterbatasan dalam akurasi numerik. Cukup banyak waktu yang dihabiskan untuk memotong melalui pohon balok, dan dalam adegan dengan jarak pandang yang panjang, misalnya, ketika dilihat dari atas tingkat, total biaya pemrosesan balok mengurangi laju bingkai Gempa menjadi kecepatan penyu. Yaitu, pada akhirnya ternyata solusi dengan bundel tree menderita hampir penyakit yang sama dengan algoritma artis: kasus terburuk jauh lebih buruk daripada kasus rata-rata, dan tidak skala dengan baik dengan meningkatnya kompleksitas tingkat.

Mesin 3D baru setiap hari

Setelah pohon balok mulai bekerja, John bekerja tanpa lelah untuk mempercepat mesin 3D, terus-menerus berusaha memperbaiki strukturnya, daripada membuat perubahan pada implementasinya.Setidaknya seminggu sekali, dan sering setiap hari, dia pergi ke kantor saya dan berkata: "Tadi malam saya tidak bisa tidur, jadi ini yang saya pikirkan ...", dan saya tahu bahwa dia sedikit lagi menegangkan otak saya sedikit. John mencoba banyak cara untuk meningkatkan pohon tandan, dan mencapai beberapa keberhasilan, tetapi jauh lebih menarik adalah banyaknya pendekatan yang sangat berbeda yang ia hasilkan. Beberapa dari mereka hampir tidak disebutkan, sementara yang lain dilaksanakan semalam atau pada akhir pekan pengkodean yang intens. Dalam kedua kasus, mereka dibuang atau dikembangkan sebagai hasilnya sampai mereka mulai memenuhi kriteria yang diperlukan. Berikut ini beberapa contoh pendekatan semacam itu. Saya akan membicarakannya secara mendetail, berharap mereka akan membangunkan imajinasi Anda dengan cara yang sama seperti penyangga FIFO Paradise membangunkan imajinasi Tom Wilson.

Subdivisi raycast: sinar dipancarkan ke layar dibagi menjadi kotak 8x8; ini adalah operasi yang sangat efektif karena persimpangan pertama dengan permukaan dapat ditemukan hanya dengan membatasi balok ke pohon BSP, mulai dari sudut pandang, hingga lembar yang diisi tercapai. Jika sinar tetangga tidak jatuh pada permukaan yang sama, maka sinar dipancarkan di tengah-tengah di antara mereka, dan ini berlanjut sampai semua sinar tetangga jatuh pada satu permukaan atau berada dalam piksel tetangga; kemudian sebuah blok digambar di sekitar setiap sinar dari poligon tempat sinar itu jatuh. Pendekatan ini berskala sangat baik, dan dibatasi oleh jumlah piksel, dan menggambar ulang tidak terjadi. Masalahnya jatuh: ada kemungkinan besar bahwa poligon kecil akan muncul di antara sinar dan menghilang.

Permukaan tanpa puncak: Dunia direpresentasikan sebagai seperangkat bidang permukaan. Poligon secara tidak langsung muncul di persimpangan pesawat dan dihapus dari pesawat pada tahap terakhir sebelum rendering. Ini memberikan kliping cepat dan jumlah data yang sangat kecil (dibandingkan dengan poligon, pesawat dijelaskan jauh lebih padat), tetapi butuh banyak waktu untuk mengekstraksi poligon dari pesawat.

Gambar penyangga : z-, , , . , , , , . : , 256 0-8 ; x86 8 .

: Poligon dirasterisasi ke dalam interval, yang ditambahkan ke daftar interval global dan terputus dari daftar ini sehingga hanya interval terdekat yang tersisa di setiap piksel. Sedikit penyortiran diperlukan dengan pergi dari depan ke belakang, karena jika ada persimpangan, interval yang sudah ada dalam daftar lebih dekat. Ini menghilangkan kebutuhan untuk menggambar ulang, tetapi dengan biaya interval perhitungan aritmatika; selain itu, setiap poligon masih harus dikonversi ke interval.

Portal: lubang dilacak di mana tidak ada poligon di permukaan, karena rentang visibilitas hanya dapat diperluas melalui portal tersebut. Rendering dilakukan dari depan ke belakang, dan ketika sebuah portal terdeteksi, poligon dan portal di belakangnya dibatasi hingga batasnya hingga tidak ada poligon dan portal yang terlihat. Dengan penerapan berulang prinsip ini, ini memungkinkan Anda untuk menggambar hanya bagian-bagian yang terlihat dari poligon yang terlihat, tetapi dengan mengorbankan sejumlah besar kliping melalui portal.

Terobosan

, — , , BSP- , BSP- . , DOOM (2D), BSP- DOOM 2D- . 3D , . BSP , , . , , BSP.

Pada hari Senin pagi, John terlihat seperti seorang pria yang memasuki dunia yang berbeda, dan juga seperti seorang pria yang tidak banyak tidur. Sepanjang akhir pekan ia bekerja pada solusi dengan pemrosesan langsung BSP, dan mencapai pekerjaan yang memuaskan, dan juga membuat catatan tentang bagaimana menyelesaikannya. Pada pukul 3:30 pagi pada hari Senin, ketika John sedang berbaring di tempat tidur dan memikirkan portal, ia berpikir bahwa Anda dapat melakukan pra-komputasi dan menyimpan di setiap lembar daftar semua daun yang terlihat dari lembar ini, dan kemudian hanya menggambar yang terlihat daun kembali ke depan tergantung pada lembar mana sudut pandang berada, sepenuhnya mengabaikan semua daun lainnya.

Kompleksitasnya dalam ukuran: set awalnya berpotensi set terlihat (PVS) mengambil beberapa megabyte. Namun, PVS dapat disimpan sebagai vektor bit dengan 1 bit per lembar. Sangat mudah untuk mengompres struktur seperti itu dengan kompresi sederhana nol byte. John juga menyarankan untuk mengubah heuristik BSP sehingga menghasilkan lebih sedikit daun. Ini kebalikan dari apa yang saya usulkan beberapa bulan yang lalu, yaitu, pilihan pemisah poligon berikutnya, memisahkan jumlah poligon lain yang paling sedikit, dan menurut data terbaru itu ternyata menjadi heuristik terbaik. Pendekatan John diizinkan untuk membatasi ruang di luar level sehingga penangan BSP dapat menghapus permukaan eksternal yang tidak akan pernah dilihat oleh pemain,sebagai hasilnya, mengurangi ukuran PVS untuk level yang cukup besar menjadi 20 kilobyte.

20 ( PVS), (PVS , , , 50%, 150%). , PVS ; , VSD, . , — , , , .

John mengatakan perhitungan awal PVS adalah pengembangan logis dari pendekatan yang ia pertimbangkan, dan tidak ada momen "eureka". Namun demikian, ini adalah penemuan desain yang benar-benar baru, lebih baik secara kualitatif, yang, bersama dengan rasterizer dengan penyortiran tepi yang sepenuhnya menghilangkan redrawing, sangat dekat dengan persyaratan "ideal" yang kami pilih sejak awal.

Sederhanakan dan coba sesuatu yang baru

Apa artinya ini?Persis seperti yang saya katakan di awal: sederhanakan dan coba sesuatu yang baru. PVS prakomputasi lebih sederhana daripada skema lain yang kami ulas sebelumnya (meskipun precomputing PVS adalah tugas yang menarik yang akan kami bahas di lain waktu). Pada dasarnya, PVS yang dihitung sebelumnya hanyalah versi terbatas dari algoritma artis selama eksekusi program. Apakah ini berarti bahwa pendekatan ini tidak terlalu mendalam?

Tidak semuanya.Semua struktur yang benar-benar luar biasa tampak sederhana dan bahkan jelas, tetapi hanya setelah ditemukan. Tetapi proses penemuan itu sendiri membutuhkan ketekunan dan kemauan yang luar biasa untuk mencoba banyak ide yang berbeda sampai Anda menemukan yang tepat, seperti yang terjadi dalam kasus ini.

Teman saya Chris Hecker memiliki teori bahwa semua pendekatan pada akhirnya datang ke satu, karena mereka semua mencerminkan keadaan internal dan fungsi yang sama. Dari sudut pandang teori-teori yang mendasari, ini benar: tidak peduli bagaimana Anda menghitung pemetaan tekstur perspektif - menggunakan divisi atau perhitungan hiperbolik tambahan, angka melakukan tugas yang sama. Namun, ketika datang ke implementasi, perbedaan besar dapat dibuat oleh pergeseran sederhana dari solusi dalam waktu, atau peningkatan dalam optimasi untuk kemampuan perangkat keras atau caching. Teman saya Terje Mathisen suka mengulangi bahwa "hampir semua pemrograman dapat dilihat sebagai latihan dalam caching"; itulah yang dilakukan Yohanes. Tidak peduli seberapa cepat dia melakukan perhitungan VSD-nya, mereka tidak akan pernah menjadi secepat precomputing dan mencari visibilitas.Langkah paling cerdasnya adalah dia pindah dari mentalitas "percepatan kode" dan menyadari bahwa pada kenyataannya, Anda dapat melakukan pra-kalkulasi (dasarnya cache) PVS dan mencarinya.

Hal yang paling sulit di dunia adalah menjauh dari solusi biasa yang cukup baik ke masalah yang kompleks dan mencoba mencari solusi lain yang lebih baik. Tampak bagi saya bahwa untuk ini yang terbaik adalah mencoba ide-ide gila baru dan selalu, selalu berusaha untuk menyederhanakan. Salah satu tujuan John adalah memiliki lebih sedikit kode di setiap game 3D berikutnya daripada di game sebelumnya; dia percaya bahwa jika dia belajar lebih banyak, dia akan dapat menyelesaikan masalah dengan lebih efisien dalam jumlah kode yang lebih kecil.

Dan sementara sistem ini bekerja dengan cukup baik untuknya.

Belajar sekarang, bayar di muka

Ada satu hal lagi yang ingin saya sebutkan di akhir artikel. Berapa banyak yang saya ingat, Dr. The Dobb's Journal selalu mengatakan bahwa berbagi informasi pemrograman adalah berkah. Saya tahu banyak programmer yang membuat lompatan dalam pengembangan mereka berkat Tiny C Hendrix, atau D-Flat Stevens, atau hanya karena membaca binder tahunan DDJ . (Di antara mereka, misalnya, saya.) Banyak perusahaan cukup memahami pertukaran informasi dengan cara yang sama sekali berbeda - sebagai potensi kehilangan keuntungan, dan inilah yang membuat DDJ sangat berharga bagi komunitas programmer.

Berkat filosofi ini, Perangkat Lunak id memungkinkan saya untuk memberi tahu di artikel ini bagaimana Quake bekerja bahkan sebelum dirilis. Dan itulah mengapa id memposting kode sumber 3D lengkap Wolfenstein di ftp.idsoftware.com/idstuff/source [approx. transl .: sekarang kode sumber diletakkan di github ] ; Anda tidak bisa hanya mengkompilasi ulang kode dan menjualnya, tetapi Anda bisa mengetahui cara kerja game berskala penuh yang berhasil; periksa file wolfsrc.txt dari direktori di atas untuk perincian tentang bagaimana kode dapat digunakan.

Karena itu, ingat: ketika legal, dalam jangka panjang pertukaran informasi menguntungkan kita semua. Anda dapat membayar hutang untuk informasi yang diterima di sini dan di tempat lain, membagikan semua yang Anda bisa dengan menulis artikel atau buku, atau menerbitkan pengetahuan di Web. Tak satu pun dari kita belajar di ruang hampa; kita semua berdiri di atas bahu raksasa - Wirth, Knut dan ribuan lainnya. Gantikan bahu Anda untuk membangun masa depan!

Referensi

Foley, James D., et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (, BSP-, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (), http://theory.lcs.mit.edu/~seth/ .

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs , SIGGRAPH 91 proceedings, pp. 61-69.