Puncak teknologi saat itu.Pada tahun 1993, id Software merilis
Doom , penembak orang pertama yang dengan cepat berubah menjadi sebuah fenomena. Hari ini diyakini bahwa ini adalah salah satu permainan yang memiliki dampak terbesar dalam sejarah.
Sepuluh tahun setelah rilis
Doom , pada tahun 2003, jurnalis David Kouchner menerbitkan buku Perangkat Lunak id yang disebut
Masters of Doom , yang sejak itu menjadi deskripsi kanonik dari proses pembuatan
Doom . Saya membaca
Masters of Doom beberapa tahun yang lalu dan saya hampir tidak ingat apa-apa, tetapi satu cerita dari sebuah buku tentang programmer utama John Carmack telah tersimpan dalam ingatan saya. Deskripsi saya tidak akan sepenuhnya akurat (lihat di bawah untuk detail lebih lanjut), tetapi singkatnya, pada tahap awal pengembangan
Doom , Carmack menyadari bahwa penyaji 3D yang ia tulis untuk permainan mulai melambat saat merender tingkat tertentu. Ini tidak bisa diterima, karena
Doom harus menjadi gim yang aktif dan bahkan panik. Menyadari bahwa masalah penyaji sangat mendasar sehingga ia harus mencari algoritma rendering yang lebih optimal, Carmack mulai membaca artikel penelitian. Sebagai hasilnya, ia menerapkan teknik yang disebut binary space partisiing (BSP), yang belum pernah digunakan dalam video game sebelumnya, dan dengan demikian secara signifikan mempercepat mesin
Doom .
Kisah bagaimana Carmack menerapkan penelitian ilmiah mutakhir untuk video game selalu membuat saya terkesan. Menurut pendapat saya, berkat hal inilah Carmack menjadi sosok yang legendaris. Dia pantas dikenal sebagai programmer permainan video yang brilian karena banyak alasan, tetapi sebagai yang utama, saya selalu ingat episode dengan membaca artikel ilmiah dan partisi ruang biner.
Jelas, cerita ini mengesankan, karena istilah "partisi ruang biner" tampaknya menjadi sesuatu yang rumit tidak hanya untuk implementasi, tetapi bahkan untuk pemahaman. Untuk waktu yang lama saya berasumsi bahwa Carmack membuat lompatan intelektual ke depan, tetapi karena saya tidak tahu apa itu partisi ruang biner, dan seberapa baru teknik ini ketika Carmack memutuskan untuk menggunakannya, saya tidak sepenuhnya yakin. Seberapa cerdik penambahan partisi ruang biner ke
Doom dalam skala dari Homer Simpson ke Albert Einstein?
Saya juga bertanya-tanya dari mana datangnya BSP dan bagaimana gagasan itu sampai ke Carmack. Oleh karena itu, posting ini akan dikhususkan tidak hanya untuk John Carmack dan
Doom , tetapi juga untuk sejarah struktur data "pohon partisi ruang biner" (atau pohon BSP). Ternyata pohon BSP, seperti banyak aspek lain dari ilmu komputasi, berasal dari penelitian yang dilakukan untuk militer.
Ya, itu benar: E1M1, level
Doom pertama, muncul berkat Angkatan Udara AS.
Tugas VSD
Pohon BSP adalah solusi untuk salah satu tugas paling sulit dalam grafik komputer. Untuk membuat adegan tiga dimensi, renderer harus menentukan apa yang terlihat dan apa yang tidak terlihat dari titik saat ini. Ini tidak terlalu sulit jika Anda memiliki banyak waktu, tetapi mesin permainan real-time yang menghargai diri sendiri harus menentukan bagian dunia yang terlihat dan tidak terlihat setidaknya 30 kali per detik.
Tugas ini sering disebut tugas penentuan permukaan yang terlihat (VSD). Programmer Michael Abrash, yang bekerja dengan Carmack on
Quake (game Software id berikutnya setelah
Doom ), menulis tentang tugas VSD dalam bukunya yang terkenal
Graphics Programming Black Book :
Saya ingin berbicara tentang tugas grafis 3D yang paling sulit, menurut saya: menentukan permukaan yang terlihat (menggambar permukaan yang diinginkan di setiap piksel) dan kerabat dekatnya - tugas menyisihkan (secepat mungkin melempar poligon yang tak terlihat untuk mempercepat penentuan permukaan yang terlihat). Demi singkatnya, saya akan menunjukkan dengan singkatan VSD baik definisi permukaan yang terlihat dan kliping.
Mengapa saya menganggap VSD tugas 3D paling sulit? Meskipun masalah rasterisasi, seperti pemetaan tekstur, juga merupakan tugas yang luar biasa dan penting, ini adalah tugas dengan skala yang cukup terbatas, solusinya bergeser ke tampilan akselerator 3D pada peralatan; Selain itu, mereka hanya skala ketika resolusi layar meningkat, yang cukup lumayan.
Sebaliknya, VSD adalah tugas yang tidak terbatas, dan sekarang puluhan solusi digunakan untuk menyelesaikannya. Yang lebih penting lagi, kinerja naif VSD berskala langsung dengan kerumitan pemandangan, yang biasanya meningkat sebagai fungsi persegi atau kubik, sehingga dengan cepat menjadi faktor pembatas dalam membuat dunia yang realistis.
Abrash menulis tentang kerumitan masalah VSD pada akhir 90-an, beberapa tahun setelah
Doom membuktikan bahwa orang biasa ingin dapat memainkan game yang berat secara grafis di komputer rumah mereka. Pada awal 90-an, ketika Perangkat Lunak id baru mulai menerbitkan game, mereka harus bekerja secara efektif pada komputer yang tidak pantas: mesin rumahan dirancang untuk bekerja dengan teks, spreadsheet, dan aplikasi serupa lainnya. Untuk mencapai tujuan ini, perusahaan harus mendekati fiksi, terutama dalam kasus beberapa game 3D yang diterbitkan oleh id Software sebelum
Doom . Dalam permainan ini, desain semua level dibatasi sedemikian rupa untuk menyederhanakan solusi masalah VSD.
Misalnya, dalam
Wolfenstein 3D , game yang dirilis id Software sebelum
Doom , setiap level terdiri dari dinding yang disejajarkan di sepanjang sumbu. Dengan kata lain, di alam semesta Wolfenstein mungkin ada tembok utara / selatan atau dinding timur / barat, dan tidak ada yang lain. Selain itu, dinding dapat ditempatkan pada jarak tetap di grid - semua koridor memiliki lebar satu sel grid, atau dua, dll, tetapi tidak pernah 2,5 sel. Meskipun itu berarti bahwa tim Perangkat Lunak id dapat membuat level yang terlihat hampir sama, pembatasan ini membuatnya sangat mudah bagi Carmack untuk menulis penyaji untuk
Wolfenstein .
Penyaji
Wolfenstein memecahkan masalah VSD dengan memindahkan sinar (ray marching) ke dunia maya dari layar. Biasanya, render render yang dirender sinar adalah renderer raycasting - mereka sering lambat karena menyelesaikan masalah VSD di raycaster membutuhkan menemukan persimpangan pertama antara ray dan beberapa objek di dunia, yang membutuhkan banyak perhitungan. Tetapi karena semua dinding di
Wolfenstein dilapisi dengan kisi-kisi, satu-satunya tempat di mana balok dapat melintasi dinding adalah garis kisi. Oleh karena itu, cukup bagi pemberi render untuk memeriksa setiap titik persimpangan ini. Jika penyaji mulai dengan memeriksa titik persimpangan yang paling dekat dengan sudut pandang pemain, kemudian memeriksa yang kedua di dekatnya, dan seterusnya, dan selesai ketika bertemu dinding pertama, maka masalah VSD diselesaikan dengan cara yang paling sepele. Sinar hanya bergerak maju dari masing-masing piksel hingga mencapai sesuatu, yang sangat murah dalam hal kecepatan jam prosesor. Dan karena semua dinding memiliki ketinggian yang sama, itu cukup bagi kita untuk memancarkan sinar untuk setiap
kolom piksel.
Penyederhanaan rendering ini membuat
Wolfenstein cukup cepat untuk bekerja pada PC rumahan yang lemah di era ketika tidak ada kartu grafis khusus. Tetapi pendekatan seperti itu tidak akan berhasil di
Doom , karena tim id memutuskan bahwa dalam permainan barunya akan ada elemen-elemen baru seperti dinding diagonal, tangga dan langit-langit dengan ketinggian berbeda. Ray marching tidak lagi cocok, jadi Carmack menulis jenis penyaji yang berbeda. Penyaji
Wolfenstein , tempat sinar digunakan untuk setiap kolom piksel, diusir dari gambar, dan penyaji
Doom seharusnya ditolak dari benda. Ini berarti bahwa alih-alih melintasi piksel layar dan menentukan warnanya, penyaji
Doom harus beralih pada objek dalam adegan dan memproyeksikan masing-masing dari mereka pada gilirannya ke layar.
Dalam renderer seperti itu, cara sederhana untuk menyelesaikan masalah VSD adalah dengan menggunakan z-buffer. Setiap kali kami memproyeksikan objek ke layar, pemeriksaan dilakukan untuk setiap piksel yang ingin kami gambar. Jika bagian dari objek yang akan ditarik lebih dekat ke pemain daripada objek yang sudah digambar dalam piksel, maka kita dapat menulis ulang informasinya. Jika tidak, Anda harus membiarkan piksel tidak berubah. Pendekatan ini sederhana, tetapi z-buffer membutuhkan banyak memori, dan renderer masih dapat menghabiskan banyak jam prosesor untuk memproyeksikan geometri level yang tidak akan dilihat oleh pemain.
Pada awal 1990-an, solusi z-buffer memiliki satu kelemahan lagi: pada PC IBM-kompatibel menggunakan sistem adapter video yang disebut VGA, menulis ke buffer frame output adalah operasi yang mahal. Oleh karena itu, waktu yang dihabiskan untuk rendering piksel, yang kemudian hanya akan ditimpa, sangat mengurangi kinerja renderer.
Karena menulis ke buffer bingkai sangat mahal, penyaji yang ideal adalah memulai dengan menggambar objek yang paling dekat dengan pemain, lalu objek langsung di belakangnya, dan seterusnya, hingga penulisan untuk setiap piksel layar diselesaikan. Pada tahap ini, penyaji seharusnya memahami bahwa sudah waktunya untuk berhenti, sehingga menghemat waktu yang ia bisa habiskan untuk menjelajahi objek yang jauh yang tidak dilihat oleh pemain. Tetapi memesan objek pemandangan dengan cara ini, dari yang paling dekat ke yang terjauh, sama saja dengan memecahkan masalah VSD. Pertanyaan lagi muncul di hadapan kita: apa yang bisa dilihat pemain?
Pertama, Carmack mencoba menyelesaikan masalah ini dengan mengandalkan diagram tingkat
Doom . Penyaji nya mulai dengan menggambar dinding ruangan di mana pemain berada, dan kemudian dia menuangkan ke kamar tetangga untuk menggambar dinding di kamar-kamar ini, yang bisa terlihat dari kamar saat ini. Jika setiap kamar cembung, ini akan memecahkan masalah VSD. Kamar non-cembung dapat dibagi menjadi "sektor" cembung. Anda dapat melihat bagaimana teknik rendering ini terlihat seperti pelambatan yang kuat dalam
video di atas , di mana pengguna YouTuber dengan nama panggilan Bisqwit menunjukkan renderernya sendiri yang bekerja sesuai dengan algoritma umum yang sama. Algoritma ini berhasil digunakan dalam game 3D Duke Nukem, dirilis tiga tahun setelah
Doom , ketika prosesornya menjadi lebih kuat. Tetapi pada tahun 1993, pada saat itu, penyaji
Doom menggunakan algoritma ini mengalami masalah dengan tingkat yang kompleks. Ini sangat jelas ketika sektor dibangun satu sama lain, dan ini adalah satu-satunya cara untuk membuat, misalnya, tangga melingkar. Tangga melingkar membutuhkan beberapa turunan rekursif ke sektor yang sudah ditarik, secara drastis mengurangi kecepatan engine.
Sekitar waktu yang sama, ketika tim id menyadari bahwa mesin
Doom mungkin terlalu lambat, id Software diminta untuk port
Wolfenstein 3D ke Super Nintendo. SNES bahkan lebih kuat daripada PC yang kompatibel dengan IBM pada waktu itu, dan ternyata penyaji
Wolfenstein dengan teknologi ray-marching, meskipun sederhana, tidak berjalan pada peralatan Super Nintendo dengan kecepatan yang cukup. Oleh karena itu, Carmack mulai mencari algoritma yang lebih baik. Bahkan, untuk port Super Nintendo
Wolfenstein -lah Carmack pertama kali mengeksplorasi dan mengimplementasikan partisi ruang biner. Di
Wolfenstein itu cukup sederhana karena semua dinding sejajar dengan sumbu;
Doom membuatnya lebih sulit. Tetapi Carmack menyadari bahwa pohon-pohon BSP akan memecahkan masalah kecepatan di
Doom juga .
Binary Space Split
Partisi ruang biner menyederhanakan solusi untuk masalah VSD dengan pra-pemisahan adegan 3D. Untuk saat ini, cukup bagi Anda untuk memahami mengapa pemartisian berguna: jika Anda menggambar garis (yang sebenarnya adalah pesawat dalam 3D) melalui seluruh adegan, mengetahui di sisi mana garis pemutar atau kamera berada, maka kita juga akan tahu bahwa tidak ada yang sisi lain dari garis tidak akan dapat menghalangi objek dari sisi garis di mana kamera berada. Jika Anda mengulangi proses berulang kali, kami mendapatkan adegan 3D, dibagi menjadi banyak bagian. Ini tidak akan menjadi perbaikan dari adegan aslinya, kecuali bahwa kita sekarang tahu lebih banyak tentang bagaimana bagian-bagian berbeda dari adegan itu bisa tumpang tindih.
Yang pertama menulis tentang pembagian adegan 3D ini adalah para peneliti mencoba mencari tahu untuk Angkatan Udara AS apakah grafik komputer cukup progresif untuk digunakan dalam simulator penerbangan. Mereka menerbitkan temuan mereka dalam laporan 1969 berjudul, "Penelitian tentang Penggunaan Gambar Buatan Komputer dalam Simulasi Visual." Laporan tersebut menyimpulkan bahwa grafik komputer dapat digunakan untuk melatih pilot; Pada saat yang sama, para peneliti memperingatkan bahwa implementasi sistem akan menjadi rumit oleh tugas VSD:
Salah satu tugas paling signifikan yang perlu diselesaikan ketika menghitung gambar secara real time adalah tugas prioritas, atau garis tersembunyi. Dalam persepsi visual kita sehari-hari tentang dunia di sekitar kita, alam sendiri menyelesaikan masalah ini dengan kesederhanaan sepele; titik objek buram tumpang tindih semua titik lain yang terletak di sepanjang garis pandang yang sama dan lebih jauh. Dalam kasus komputer, tugas ini sangat sulit. Jumlah perhitungan yang diperlukan untuk menentukan prioritas, dalam kasus umum, tumbuh secara eksponensial dengan meningkatnya kompleksitas lingkungan, dan segera melebihi beban komputasi yang terkait dengan pencarian gambar objek dengan mempertimbangkan perspektif.
Salah satu solusi yang disebutkan oleh para peneliti ini, yang mereka katakan sebelumnya digunakan dalam proyek NASA, didasarkan pada penciptaan apa yang saya sebut "matriks tumpang tindih". Para peneliti menunjukkan bahwa pesawat yang membagi pemandangan menjadi dua bagian dapat digunakan untuk menyelesaikan "setiap konflik prioritas" antara objek di sisi yang berlawanan dari pesawat. Dalam kasus umum, Anda mungkin perlu menambahkan pesawat ini ke TKP secara eksplisit, tetapi dengan struktur geometri tertentu, Anda dapat mengandalkan wajah objek yang ada. Peneliti mendemonstrasikan contoh di bawah ini, di mana
p1 ,
p2, dan
p3 membagi permukaan. Jika sudut pandang kamera berada di sisi depan atau “benar” dari salah satu bidang ini, maka
pi adalah 1. Matriks menunjukkan hubungan antara tiga objek tergantung pada tiga bidang pemisahan dan lokasi sudut pandang kamera - jika objek
ai tumpang tindih objek
aj , maka elemen
aij dari matriks akan sama dengan 1.
Para peneliti telah mengusulkan untuk mengimplementasikan matriks ini dalam perangkat keras dan menghitung ulangnya di setiap bingkai. Bahkan, matriks harus bertindak sebagai saklar besar atau sejenis built-in z-buffer. Saat merender objek saat ini, video bukan output untuk bagian-bagian objek ketika 1 berada di kolom objek, tetapi objek baris yang sesuai diambil.
Kelemahan serius dari pendekatan ini adalah bahwa matriks ukuran
n2 diperlukan untuk menggambarkan adegan dengan objek
n . Oleh karena itu, para peneliti memutuskan untuk memeriksa apakah mungkin untuk menyajikan matriks tumpang tindih dalam bentuk "daftar prioritas", yang akan memiliki ukuran hanya
n dan menentukan urutan di mana objek harus ditarik. Mereka segera memperhatikan bahwa dalam adegan-adegan tertentu, misalnya, dalam yang ditunjukkan di atas, pemesanan tidak mungkin diselesaikan (karena ada siklus yang tumpang tindih), sehingga mereka mencurahkan banyak waktu untuk definisi matematika dari adegan "benar" dan "salah". Pada akhirnya, mereka sampai pada kesimpulan bahwa setidaknya untuk adegan "benar" (dan desainer adegan dapat dengan mudah menghindari kasus "salah"), daftar prioritas dapat dihasilkan. Tetapi mereka meninggalkan daftar generasi sebagai latihan untuk pembaca. Tampaknya kontribusi utama karya 1969 ini adalah untuk menunjukkan bahwa setidaknya
secara teoritis harus ada kemungkinan menggunakan pesawat pembagi untuk mengatur objek di tempat kejadian.
Dan hanya dalam artikel 1980 berjudul "On Surface Permukaan Generasi oleh A Priori Tree Structures" adalah algoritma spesifik yang ditunjukkan untuk ini. Pada artikel ini, ditulis oleh Henry Fuchs, Zvi Kedem, dan Bruce Naylor, pohon BSP pertama kali dijelaskan. Para penulis mengatakan bahwa struktur data baru mereka adalah "solusi, pendekatan alternatif, pertama kali digunakan sepuluh tahun yang lalu, tetapi karena beberapa kesulitan tidak begitu luas," - sehingga mereka menanggapi solusi yang dipilih dalam pekerjaan untuk Angkatan Udara AS pada tahun 1969. Setelah membangun pohon BSP, dapat dengan mudah digunakan untuk mengatur objek dengan prioritas di tempat kejadian.
Fuchs, Kedem, dan Naylor memberikan deskripsi yang cukup jelas tentang operasi pohon BSP, tetapi saya akan mencoba memberikan yang kurang formal, tetapi singkat.
Kita mulai dengan memilih satu poligon dalam adegan, dan membuat bidang di mana poligon terletak pada bidang pemisah. Poligon tunggal ini juga menjadi simpul akar pohon. Poligon yang tersisa dari adegan akan berada di satu atau sisi lain dari bidang pemisah akar. Poligon di sisi "depan" atau di setengah "depan" dari bidang muncul di subtree kiri dari simpul akar, dan poligon di sisi "belakang" atau di "setengah" ruang setengah dari pesawat muncul di subtree kanan. Kemudian kami mengulangi proses ini secara rekursif, memilih poligon dari sub pohon kiri dan kanan sebagai permukaan pemisah baru untuk setengah ruangnya, yang menghasilkan setengah ruang dan sub pohon lagi. Proses berakhir ketika poligon berakhir.
Katakanlah kita ingin membuat geometri adegan kembali ke depan.
(Ini disebut "algoritma artis" karena ini berarti bahwa poligon yang lebih jauh dari kamera akan diisi dengan poligon yang lebih dekat ke kamera, membuat rendering yang benar.) Untuk melakukan ini, kita hanya perlu memutar pohon BSP kita secara berurutan; keputusan tentang apakah subtree kiri atau kanan harus dibuat didasarkan pada di mana sudut pandang kamera - di ruang setengah depan atau belakang relatif terhadap bidang pembagi yang terkait dengan simpul ini. Yaitu, di setiap simpul pohon, pertama-tama kita membuat semua poligon di sisi "jauh" pesawat, kemudian poligon pada bidang pemisahan, dan kemudian poligon di sisi "dekat" dari pesawat. Poligon "Dekat" dan "jauh" didefinisikan relatif terhadap sudut pandang kamera. Ini memecahkan masalah VSD karena, seperti yang kita pelajari beberapa paragraf lalu,poligon di sisi jauh dari bidang pemisahan tidak dapat tumpang tindih dengan apa pun di sisi depan.Diagram di bawah ini menunjukkan konstruksi dan traversal pohon BSP yang menggambarkan adegan 2D sederhana. Dalam 2D, garis pemisah digunakan alih-alih membagi bidang, tetapi gagasan dasarnya tetap sama.Fitur yang sangat nyaman dari pohon BSP yang ditekankan Fuchs, Kedem, dan Naylor beberapa kali adalah bahwa itu perlu dibangun hanya sekali. Ini tampaknya mengejutkan, tetapi satu pohon BSP dapat digunakan untuk membuat adegan terlepas dari sudut pandang kamera. Pohon BSP tetap dapat digunakan sampai poligon adegan bergerak. Itulah sebabnya pohon BSP sangat berguna untuk render waktu nyata - semua pekerjaan kompleks untuk membangun pohon dapat dilakukan di muka, dan bukan pada saat render.Fuchs, Kedem, dan Naylor melaporkan bahwa penelitian lebih lanjut membutuhkan penciptaan pohon BSP yang “baik”. Kualitas pohon BSP tergantung pada poligon yang Anda pilih untuk menentukan bidang pemisahan. Sebelumnya, saya melewatkan titik ini, tetapi jika Anda menggunakan pesawat yang memotong poligon lain ketika membelah, maka agar algoritma BSP bekerja, Anda perlu membagi poligon yang disilang menjadi dua, sehingga satu setengah mengacu pada satu setengah ruang dan yang lainnya ke yang lain. Jika ini sering terjadi, maka membangun pohon BSP secara signifikan meningkatkan jumlah poligon di tempat kejadian.Bruce Naylor, salah satu penulis artikel 1980, kemudian menulis tentang masalah ini dalam artikelnya tahun 1993, Constructing Good Partitioning Trees. Menurut kolega dan rekan pendiri Software Carmack John Romero, artikel ini adalah salah satu karya yang dibaca Carmack ketika ia mencoba mengimplementasikan pohon-pohon BSP di Doom .Pohon BSP di Doom
Ingatlah bahwa dalam konsep pertama renderer Doom , Carmack mencoba mengatur urutan rendering untuk geometri level dengan mengisi renderer keluar dari ruangan di mana pemain berada di kamar tetangga. Pohon BSP adalah cara yang lebih mudah untuk menentukan urutan ini, karena mereka menghindari masalah penyaji harus berulang kali mengunjungi satu ruangan (atau sektor), membuang-buang siklus prosesor.“Menambahkan pohon BSP ke Doom ” dalam praktik berarti menambahkan generator pohon BSP ke editor tingkat Doom . Setelah menyelesaikan pembuatan level Doompohon BSP dihasilkan dari geometri level. Menurut Fabien Sanglar, proses generasi bisa memakan waktu hingga delapan detik untuk satu tingkat dan 11 menit untuk semua tingkat Doom pertama . Proses pembangkitan sangat panjang sebagian karena fakta bahwa algoritma generasi Carmack BSP sedang mencoba untuk menemukan pohon BSP "baik" menggunakan berbagai heuristik. Penundaan delapan detik tidak dapat dimaafkan selama pertandingan, tetapi pada generasi awal tampaknya cukup dapat diterima, mengingat peningkatan kinerja yang diberikan pohon-pohon BSP untuk pemberi render. Pohon BSP yang dihasilkan dari tingkat individu disimpan sebagai bagian dari data tingkat yang dimuat ke dalam permainan saat diluncurkan.Carmack membuat perubahan penting pada algoritma pohon BSP yang dijelaskan dalam artikel 1980: setelah Doom diluncurkandan membaca pohon BSP level saat ini ke dalam memori, renderer menggunakan pohon ini untuk menggambar objek tidak dari depan ke depan, tetapi dari depan ke belakang. Dalam sebuah artikel tahun 1980, Fuchs, Kedem, dan Naylor mendemonstrasikan bagaimana pohon BSP dapat digunakan untuk mengimplementasikan algoritma artis dengan rendering back-to-back, tetapi sejumlah besar pengecatan ulang terjadi dalam algoritma artis, yang bisa mahal pada PC yang kompatibel dengan IBM. Oleh karena itu, penyaji Doom dimulai dengan geometri yang lebih dekat dengan pemain, dan kemudian menggambar yang terjauh. Pemesanan terbalik seperti itu mudah diimplementasikan menggunakan pohon BSP, karena Anda cukup membuat keputusan backtrace di setiap simpul pohon. Untuk mencegah geometri yang lebih jauh ditarik di atas lebih dekat, Doom renderermenggunakan sejenis buffer-z implisit, yang menyediakan banyak manfaat buffer-z reguler, sambil mengonsumsi lebih sedikit memori. Ada satu larik yang melacak tumpang tindih dalam dimensi horizontal, dan dua larik lain yang melacak tumpang tindih dalam arah vertikal di atas dan di bawah layar. Penyaji Doom dapat melakukannya tanpa menggunakan buffer-z yang sebenarnya, karena Doom , sebenarnya, bukan permainan tiga dimensi. Struktur data yang lebih murah bekerja di dalamnya karena unsur-unsur tertentu tidak mungkin dalam Doom : array tumpang tindih horizontal bekerja karena tidak ada dinding yang miring, dan tumpang tindih susunan vertikal bekerja karena tidak ada dinding di mana, misalnya, ada dua yang terletak satu di atas jendela lainnya.Doom II , serumit pendahulunya.Tapi tidak ada yang mengeluh tentang pengulangan darah.Kata Baru dalam Teknologi Gempa Satu-satunya tugas rumit yang tersisa adalah bagaimana mengintegrasikan karakter Doom yang bergerak ke dalam geometri statis tingkat yang digambar menggunakan pohon BSP. Musuh di Doom tidak bisa menjadi bagian dari pohon BSP karena mereka bergerak; Pohon BSP hanya bekerja dengan geometri tetap. Oleh karena itu, penyaji Doompertama menggambar geometri statis level, melacak (menggunakan struktur data lain yang hemat memori) segmen layar di mana gambar dilakukan. Lalu ia menarik musuh dari belakang ke depan, memotong mereka di sepanjang segmen layar yang tumpang tindih dengan mereka. Proses ini tidak seoptimal rendering dengan pohon BSP, tetapi karena biasanya ada lebih sedikit musuh daripada geometri, kecepatan tidak menjadi masalah di sini.Menggunakan pohon BSP di Doom adalah kemenangan besar. Jelas, Carmack cukup cerdas untuk menyadari bahwa pohon BSP akan menjadi solusi ideal. Tetapi apakah keputusan ini cerdik ?Dalam bukunya yang bagus tentang mesin game DoomFabien Sanglar mengutip John Romero yang mengatakan bahwa artikel Bruce Naylor, "Membangun Pohon Pemisahan yang Baik", terutama tentang menggunakan pohon BSP untuk memotong wajah belakang model 3D. Menurut Romero, Carmack berpikir algoritma mungkin masih berguna untuk Doom , jadi dia mengimplementasikannya. Ini cukup terpuji untuk Carmack karena dia menyiratkan bahwa dia melihat kegunaan pohon BSP dalam video game waktu nyata bahkan ketika orang lain masih menggunakan teknik ini untuk membuat adegan statis. Kisah menyanjung yang sama adalah di Masters of Doom: Kouchner menyarankan agar Carmack membaca artikel Naylor dan bertanya-tanya: "bagaimana jika Anda dapat menggunakan pohon BSP untuk membuat tidak hanya satu gambar 3D, tetapi seluruh dunia virtual?"Temuan ini mengabaikan sejarah pohon BSP. Ketika peneliti Angkatan Udara AS pertama kali menyadari bahwa membelah adegan dapat membantu mempercepat rendering, mereka tertarik pada percepatan rendering waktu nyata, karena pada akhirnya mereka mencoba membuat simulator penerbangan. Contoh simulator penerbangan sekali lagi disebutkan dalam artikel 1980. Fuchs, Kedem, dan Naylor menulis bahwa pohon BSP dapat berguna dalam simulator penerbangan yang digunakan pilot untuk melakukan beberapa pendaratan di bandara yang sama. Karena geometri bandara tidak pernah berubah, pohon BSP hanya dapat dihasilkan satu kali. Jelas, mereka berpikir tentang simulasi real-time. Dalam pengantar artikel, mereka bahkan menjelaskan penelitian mereka dengan menguji kemungkinan menggunakan sistem grafis real-time untuk membuat gambar dalam waktu tidak lebih dari 1/30 detik.BSP- . , , BSP- , — . , .
BSP- , 1991 , 1990
Computer Graphics: Principles and Practice . , . 1991 BSP-, ,
Doom, hingga struktur data "implisit z-buffer", yang tidak memungkinkan menggambar poligon jauh di atas yang tetangga. Artikel ini memberikan gambaran yang sangat baik tentang pohon-pohon BSP, serta kodesemu untuk membangun dan menampilkan pohon. (Berkat perpustakaan yang luar biasa di universitas saya, saya dapat menggulir ke edisi 1990). Komputer Grafik: Buku Prinsip dan Praktek adalah karya klasik pada grafik komputer, sehingga Carmack dapat memiliki satu juga.Tingkat subsektor E1M1: Hangar.Meski begitu, Carmack menghadapi tugas baru - “Bagaimana saya bisa membuat orang pertama penembak yang berjalan pada komputer dengan prosesor yang bahkan tidak mampu melakukan operasi floating point?” - melakukan penelitian sendiri, dan membuktikan bahwa pohon BSP adalah Ini adalah struktur data yang berguna untuk gim video waktu nyata. Saya masih berpikir bahwa ini adalah hasil yang mengesankan, meskipun pohon BSP ditemukan sepuluh tahun sebelumnya, dan telah dipelajari secara teoritis dalam detail yang cukup pada saat Carmack membacanya. Mungkin pencapaian utama yang harus kita puji adalah mesin Doom secara keseluruhan, yang telah menjadi contoh kode yang hebat. Saya sudah pernah membicarakan ini sekali, tetapi saya ulangi bahwa buku karya Fabien Sanglar tentang mesin permainanDoom ( Game Engine Black Book: DOOM ) adalah ikhtisar yang sangat baik dari semua komponen mesin permainan dan interaksinya. Kita tidak boleh lupa bahwa tugas VSD hanyalah satu dari banyak tugas yang harus diselesaikan oleh Carmack agar mesin Doom bekerja . Dan dia mampu, selain segalanya, untuk membaca tentang struktur data kompleks yang tidak diketahui oleh sebagian besar programmer dan mengimplementasikannya. Ini mengatakan banyak tentang tingkat pengetahuan teknis dan komitmennya terhadap ideal.