Teknik Occlusion Culling Untuk Pemprosesan Geometri Bagi Aplikasi Telusur Maya

AbSTRAK

Realiti maya merupakan suatu kaedah moden dalam menyelesaikan masalah dan merangka strategi. Ia dikatakan dapat menjimatkan kos dan masa bagi penghasilan sesuatu produk. Aplikasi telusur maya membenarkan pengguna menjelajahi dunia 3 dimensi dengan bantuan grafik komputer. Enjin realiti maya merupakan komponen terpenting dalam suatu sistem realiti maya.. Perkara asas bagi enjin pula merupakan paparan grafik. Namun, dalam pembangunan sistem yang melibatkan grafik 3 dimensi, terdapat konflik keperluan iaitu sama ada untuk mencapai kadar realistik ataupun mencapai kadar masa nyata. Kajian penyelidikan ini adalah bertujuan untuk menghasilkan penambahbaikan terhadap kaedah pemprosesan geometri bagi aplikasi telusur maya dalam persekitaran 3D. Kajian ini difokuskan terhadap suatu persekitaran 3D yang kompleks dengan bilangan objek yang banyak dan statik. Kertas kerja ini akan menerangkan tentang implementasi teknik occlusion culling (OC) bagi aplikasi telusur maya.

Kata Kunci: Occlusion Culling, Telusur Maya, Grafik Komputer


1. PENGENALAN

Sistem realiti maya digunakan dalam pelbagai bidang dalam pelbagai industri seperti simulasi penerbangan, pembuatan, pertahanan, penyelidikan saintifik, pembinaan dan pelancongan. Secara umum, sistem realiti maya diperlukan untuk tujuan latihan, pembelajaran, perancangan, eksplorasi dan hiburan. Di samping itu juga, ia digunakan sebagai alat untuk menyelesaikan masalah dan merangka strategi. Aplikasi telusur maya dalam sistem realiti maya memerlukan pengguna agar menyelusuri ke dalam persekitaran 3 dimensi dalam dunia maya. Contoh aplikasi telusur maya adalah seperti simulasi seni bina (Airey et al., 1990), simulasi pemanduan (Cremer et al., 1996) dan juga visualisasi untuk sesuatu sejarah silam (Hirayu et al., 2000), (Ripper Kos et al., 2000), (DeLeon & Berry, Jr., 2000).

Kunci utama dalam menentukan keberkesanan sesuatu aplikasi telusur maya bergantung kepada kaedah interaksi antara sistem dengan pengguna dan sejauh mana persekitaran hasil penjanaan komputer itu adalah realistik. Realistik seperti yang diterjemahkan oleh Chiu dan Shirley (1994) membawa maksud sejauh mana imej yang dihasilkan dapat digambarkan dalam mental pengguna adalah sama seperti pengalaman sebenar di dunia nyata.

Untuk menghasilkan imej yang realistik, tahap kompleksiti terhadap geometri pada model 3 dimensi dalam sesuatu aplikasi telusur perlu dipertingkatkan (Dzwig, 1988),(Ramasubramanian et al., 1999). Namun, apabila tahap kompleksiti dipertingkatkan, kos komputasi akan bertambah. Maka ini akan menambahkan beban komputer dan pemprosesan menjadi tinggi yang akan menyebabkan pergerakan dalam dunia maya akan tersekat-sekat.

2. LATAR BELAKANG MASALAH

Simulasi banyak digunakan dalam kehidupan seharian terutamanya dalam industri yang memerlukan ketelitian dan melibatkan kos operasi yang tinggi dan berisiko.

Dalam perlaksanaan simulasi secara visual ini, antara perkara yang sering dititikberatkan ialah ketepatan dunia simulasi dengan keadaan sebenar. lni bermaksud, sejauh mana pergerakan dan suasana dalam simulasi itu sama dengan situasi sebenar. Kebanyakan aplikasi telusur maya yang melibatkan simulasi secara visual yang ada di pasaran sekarang memerlukan mesin-mesin khas atau simulator yang melibatkan kos yang tinggi.

Simulasi dalam persekitaran 3 dimensi memerlukan objek yang terdapat di dalamnya diwakilkan secara tepat. Namun, untuk mewakilkan setiap objek dalam persekitaran 3 dimensi dengan tepat, ia akan melibatkan kos komputasi yang tinggi. Kos komputasi yang tinggi bermaksud keperluan ruang storan yang besar, pemproses yang berkuasa tinggi dan ruang ingatan yang besar. Beban komputasi yang dihasilkan oleh aplikasi simulasi ini adalah disebabkan oleh penggunaan grafik 3 dimensi yang tinggi. Grafik ini dihasilkan dengan menggunakan model-model geometri yang terdiri daripada ribuan poligon bagi satu perwakilan objek.

Dalam pembangunan sistem yang melibatkan grafik 3 dimensi, terdapat konflik keperluan iaitu sama ada untuk mencapai kadar realistik ataupun mencapai kadar mas a nyata (Angelidis & Fouquier, 2001). Ini bermaksud, apabila kadar realistik ingin dipertingkatkan, maka sistem akan menjadi lebih perlahan kerana ia memerlukan pemprosesan yang agak banyak. Begitu juga di sebaliknya, jika ingin menambahkan kadar masa nyata, maka hasil yang akan diperoleh adalah kurang realistik. Aplikasi telusur maya memerlukan lebih keperluan masa nyata berbanding dengan keperluan realistik. Ini kerana terdapat banyak interaksi yang perlu dilakukan oleh pengguna terhadap sistem. Jadi jika keperluan realistik dilebihkan maka aplikasi telusur maya ini tidak begitu bermakna. Namun begitu, keperluan realistik ini masih boleh dicapai walaupun tanpa mengorbankan banyak keperluan masa nyata (Luebke, 2001).

Persekitaran 3D yang dipenuhi dengan banyak bangunan dan objek-objek di dalamnya adalah mustahil untuk dilaksanakan dalam kadar interaktif secara masa nyata dengan teknologi perkakasan yang sedia ada (Cohen-Or, 2000). Aplikasi telusur maya boleh dikategorikan kepada dua iaitu aplikasi telusur maya luaran (Wonka, 2001), (Wimmer, 2001) dan dalaman (Funkhouser, 1993).

Di dalam aplikasi telusur maya luaran, objek-objek terdiri daripada bangunan-bangunan yang kosong iaitu hanya bahagian luaran bangunan sahaja yang dimasukkan dalam aplikasi manakala bahagian dalaman bangunan tidak disertakan. Kebanyakan aplikasi telusur maya luaran ini memanipulasikan penggunaan tekstur (Wonka et al.,2001), (Wonka et ai., 2003). Contoh aplikasi telusur maya luaran adalah seperti simulasi perbandaran. Dalam aplikasi telusur maya dalaman, objek-objek dalaman kebiasaanya dimodelkan dengan terperinci. Ia biasa digunakan oleh pereka dalaman dan arkitek untuk memberi gambaran awal tentang hiasan dalaman dan susun letak perabot di dalam bangunan. Namun dalam keadaan tertentu, terdapat juga aplikasi telusur maya yang menggabungkan antara bahagian luaran dan dalaman bagi bangunan.

Justeru matlamat kajian penyelidikan ini adalah untuk melakukan penambahbaikan terhadap teknik pemprosesan geometri. Ini adalah bertujuan untuk mempertingkatkan lagi kadar masa nyata bagi sesuatu aplikasi telusur maya.

3. KENAMPAKAN

Dalam proses projeksi daripada persekitaran 3D kepada skrin paparan, banyak perkara yang boleh menjimatkan kos komputasi. Tidak semua objek yang terdapat dalam persekitaran akan dimasukkan ke paparan dalam masa yang sama.

Oleh itu, sistem tidak perlu mengambil kira objek-objek yang tidak termasuk dalam kawasan paparan untuk dimuatkan dalam ruang ingatan. Namun, untuk menentukan objek yang termasuk dalam kawasan paparan ini bukanlah satu masalah yang mudah. Setiap kali ada perubahan terhadap paparan, contohnya seperti pergerakan kamera secara horizontal atau vertikal, akan melibatkan banyak perkara yang perlu dikira. Ini memerlukan pengiraan semula paparan yang hendak disimpan dalam ruang ingatan. Masalah ini telah lama dikaji oleh penyelidik -penyelidik iaitu seawal kemunculan bidang grafik komputer (Sutherland et al., 1974).

Rajah 1: Perbezaan kaedah kenampakan.

Rajah 1 menunjukkan perbezaan di antara kaedah kenampakan yang berbeza Cohen-Or et al. (2000). Kaedah penentuan kenampakan ini bukan sahaja berguna untuk paparan tetapi juga untuk penghasilan bayang-bayang dan pengesanan perlanggaran (Govindaraju, 2004).



3.1. View Frustum Culling (VFC)

Kaedah VFC merupakan kaedah penentuan kenampakan yang ringkas dan umum mula dihasilkan oleh Clark (1976). Ia boleh digunakan terhadap semua model dalam grafik komputer. Di dalam kaedah ini, hanya objek yang termasuk dalam kawasan frustum sahaja yang akan dipaparkan. Untuk perwakilan frustum, sebuah piramid dengan empat satah digunakan. Di dalam piramid tersebut terdapat dua satah yang mewakili bahagian terdekat dan bahagian terjauh. Bahagian terdekat dan terjauh ini merupakan sempadan yang menentukan kenampakan. Setiap objek dibatasi dengan kotak pembatas sarna ada Axis-Aligned Bounding Box (AABB). Semasa perlaksanaan aplikasi, jika keseluruhan sempadan kotak pembatas berada di luar view frustum, maka objek yang dibatasinya tidak dimasukkan dalam pengiraan kenampakan. Algoritma yang telah diubahsuai dengan menggunakan konsep berhierarki telah dihasilkan oleh Assarsson & Moller (2000).

3.2. Back Face Culling (BFC)

Permukaan bagi sesuatu objek yang membelakangi pemerhati tidak kelihatan. Oleh itu, adalah rugi bagi sesuatu sistem masa nyata untuk memperuntukkan ruang ingatan untuk sesuatu yang tidak kelihatan dalam paparan. Kaedah BFC ini mengendalikan poligon yang membelakangi pemerhati agar tidak dipaparkan (Zhang & Hoff, 1997).

3.3. Occlusion Culling (OC)

Kaedah pemilihan kenampakan ini bertujuan untuk menentukan Potentially Visible Set (PVS) atau set yang berpotensi nampak dengan membuang geometri yang terlindung. Satu kajian tinjauan telah dilakukan oleh Cohen-Or et ai. (2000) terhadap algoritma pemilihan bahagian terlindung (OC). Secara umumnya, algoritma OC ini dikelaskan kepada tiga iaitu:
a. Konservatif atau anggaran
b. Ruang objek atau ruang imej
c. Pengiraan dari titik atau kawasan
Beberapa algoritma yang efektif telah dibangunkan untuk persekitaran yang khusus. Sebagai contoh, sel dan portal untuk model senibina (Airey, 1990), (Teller, 1992) dan algoritma untuk set data perbandaran atau persekitaran yang besar menggunakan convex occluder yang mengambil kira kawasan yang agak luas (Coorg & Teller, 1997), (Hudson et al., 1997), (Schaufler et al., 2000), (Wonka et al., 2000), (Wonka et al., 2001).

Algoritma konservatif mengira PVS yang mengandungi semua primitif yang kelihatan termasuklah sebilangan kecil primitif yang terlindung (Coorg & Teller, 1997), (Greene et al., 1993), (Hudson et al., 1997), (Zhang, 1998). Algoritma berdasarkan anggaran pula menentukan secara kasar tentang objek yang dapat dilihat (Bartz et al., 1999), (Klosowski & Silva, 2000), (Zhang, 1998).

Algoritma berasaskan objek dapat menghasilkan pemilihan lebih efisien dan tepat jika diberikan sedikit set occluder yang besar. Bagi algoritma berasaskan objek, kaedah persempadanan dan pembahagian digunakan oleh Coorg & Teller (1997) dan Hudson et al. (1997). Sesuatu objek akan dibahagikan kepada beberapa bahagian dan hanya memaparkan bahagian yang termasuk dalam paparan sahaja. Kaedah ini dikatakan agak sukar dan rumit untuk dilaksanakan. Durand et al.(2000), Schaufler et al. (2000) dan Wonka et al. (2000) menggunakan algoritma berasaskan kawasan untuk mengurangkan beban komputasi semasa perlaksanaan.

Hasilnya dapat dilaksanakan dengan baik untuk persekitaran yang luas. Tetapi
agak sukar untuk menghasilkan occluder fusion yang terdiri daripada occluder kecil yang banyak. Untuk persekitaran seperti ini, algoritma berasaskan ruang imej seperti ini, algoritma berasaskan ruang imej seperti hierarchical z-buffer Greene et al. (1993), Greene (1999) atau hierarchical occlusion maps (HOM) adalah lebih efektif Zhang (1998).

Bagi algoritma berasaskan objek, kaedah persempadanan dan pembahagian digunakan oleh Coorg & Teller (1997) dan Hudson et al. (1997). Sesuatu objek akan dibahagikan kepada beberapa bahagian dan hanya memaparkan bahagian yang termasuk dalam paparan sahaja. Kaedah ini dikatakan agak sukar dan rumit untuk dilaksanakan. Durand et al. (2000), Schaufler et al. (2000), Wonka et al. (2000) menggunakan algoritma berasaskan kawasan untuk mengurangkan beban komputasi semasa perlaksanaan. Hasilnya dapat dilaksanakan dengan baik untuk persekitaran yang luas.

Algoritma penentuan bahagian terlindung dari kawasan mengira PVS terlebih dahulu untuk mengurangkan beban semasa aplikasi dilaksanakan (Durand et al., 2000), (Wonka et al., 2000). Algoritma ini baik bila dilaksanakan terhadap persekitaran yang besar. Terdapat penyeimbangan di antara kualiti PVS dan juga penggunaan memori. Algoritma ini juga terlalu konservatif dan sukar untuk mendapatkan pilihan yang terbaik. Di sebaliknya, algoritma penentuan bahagian terlindung dari titik lebih tepat dalam pemilihan tetapi ia memerlukan kos komputasi yang tinggi. Kaedah terkini oleh Aila (2005) menghasilkan algoritma yang lebih efisien untuk pengiraan kenampakan dan bayang-bayang untuk persekitaran 3D masa nyata.

Kaedah pra-pemprosesan pula digunakan untuk menentukan kawasan dan set paparan yang berpotensi untuk kelihatan dalam persekitaran 3D atau potentially visible set (PVS). Namun algoritma ini masih menggunakan komputasi yang tinggi kerana set data yang dipilih agak besar. Menurut El-Sana et al. (2001), tidak ada satu algoritma yang dapat menentukan PVS pada masa nyata untuk persekitaran kompleks.

4. IMPLEMENTASI

Bahagian ini menerangkan tentang bagaimana kaedah implementasi teknik kenampakan dalam aplikasi telusur maya.

4.1 Pembangunan Persekitaran Maya

Perkara asas bagi aplikasi telusur maya ialah membangunkan persekitaran maya. Persekitaran maya terdiri daripada ruangan 3D yang mengandungi objek-objek bergeometri di dalamnya. Persekitaran maya yang dibangunkan untuk kajian ini dibangunkan menggunakan C++, OpenGL, GLVU dan GLUI. Objek 3D yang digunakan merupakan data-data dari projek Ancient Malacca yang dibangunkan oleh Perbadanan Pembangunan Multimedia (MDC). Objek 3D tersebut dimodelkan dengan menggunakan perisian 3D Studio Max.

4.2 Implementasi Teknik Kenampakan

Beberapa teknik kenampakan telah diimplemenkan terhadap persekitaran maya yang dibangunkan. Tujuan utama implementasi teknik ini adalah untuk memastikan bahawa dengan teknik kenampakan, prestasi aplikasi telusur maya dapat dipertingkatkan.

Rajah 2 menunjukkan aplikasi telusur maya yang dibangunkan tanpa sebarang teknik kenampakan. Setiap objek dibatasi dengan kotak pembatas AABB. Keseluruhan objek yang dimuatkan dalam aplikasi telusur maya ialah sebanyak 137 objek.

Rajah 2: Aplikasi Telusur Maya tanpa kaedah kenampakan.

Rajah 3 pula menunjukkan aplikasi telusur dengan implementasi teknik kenampakan iaitu VFC, BFC dan OC. Teknik OC yang digunakan adalah berasaskan geometri. Didapati hasil paparan adalah sama seperti tanpa teknik kenampakan, tetapi kadar fps yang berbeza. Bilangan objek yang disimpan dalam ruang ingatan juga adalah lebih rendah iaitu hanya 20% objek sahaja yang disimpan. Bilangan poligon yang disimpan juga hanya 12,428 poligon berbanding 71,442 poligon tanpa proses kenampakan.

Rajah 3: Aplikasi Telusur Maya dengan implementasi teknik VFC, BFC dan OC.

5. PENGUJIAN

Satu set laluan pergerakan kamera telah ditetapkan. Ini adalah bertujuan bagi memastikan laluan yang dilalui oleh kamera dalam persekitaran maya adalah sama bagi kesemua ujikaji yang melibatkan teknik kenampakan yang berbeza. Pengujian dilakukan menggunakan mesin dengan spesifikasi seperti berikut:
a. Intel Pentium 4 HT 3.2 GHz
b. Ingatan Utama 512RAM
c. Kad Paparan Grafik nVidia
GeForce FX5950
Perbandingan teknik kenampakan terhadap aplikasi telusur maya yang telah diuji dapat ditunjukkan dalam graf dalam rajah 4.
Graf dalam rajah 4 merupakan graf kadar kerangka per saat (fps) lawan masa. Semakin tinggi kadar fps, semakin baik sesuatu aplikasi telusur maya itu. Jika tiada VFC, fps bagi aplikasi telusur adalah yang paling rendah. Manakala jika menggunakan VFC sama ada tanpa kotak pembatas ataupun dengan kota pembatas menunjukkan kadar fps tertinggi. Dengan implementasi teknik OC berasaskan kotak pembatas, bilangan objek dapat dikurangkan dan kadar fps dapat dipertingkatkan. Namun hasil yang dipaparkan adalah tidak tepat kerana bilangan objek yang terlindung yang dibuang adalah berdasarkan kotak pembatas. Teknik OC berasaskan geometri pula memerlukan kos komputasi yang tinggi namun hasil yang dipaparkan adalah lebih tepat. Oleh itu, kadar fps adalah lebih rendah berbanding dengan implementasi teknik OC berasaskan kotak pembatas.

Rajah 4: Perbandingan pengujian teknik kenampakan terhadap aplikasi telusur maya.


6. KESIMPULAN

Untuk menghasilkan satu aplikasi telusur maya yang baik, teknik mempertingkatkan kadar paparan adalah sangat diperlukan. Antara tumpuan penyelidikan ini ialah berkaitan dengan teknik OC dan aras perincian berperingkat (LOD). Ini adalah perlu bagi mengimbangi keperluan realistik dan masa nyata. Hasil daripada implementasi teknik OC dalam kertas kerja ini mendapati penggunaannya dapat menambahkan kelajuan (mengurangkan beban komputasi) tanpa menjejaskan paparan visual.

Sebagai kesimpulan, adalah diharapkan kajian penyelidikan ini dapat dilaksanakan dengan jayanya secara mendalam dan terperinci. Hasil daripada kajian ini dapat dimanfaatkan dan memberi sumbangan kepada bukan sahaja kepada komuniti akademik yang mengkaji tentang grafik komputer, tetapi juga pembangun sistem simulasi secara visual dan pembangun permainan komputer khususnya serta pengguna dan pembangun sistem realiti maya umumnya.