Minggu, 07 Oktober 2007

Keperluan, Masalah dan Teknik Dalam Visualisasi Secara Masa Nyata Terhadap Grafik 3D Yang Kompleks

Visualisasi atau simulasi secara visual merupakan suatu kaedah moden dalam menyelesaikan masalah dan merangka strategi. Ia juga dikatakan dapat menjimatkan kos dan masa bagi penghasilan sesuatu produk. Namun, dalam penghasilan simulasi secara visual terdapat masalah dari segi menyeimbangkan antara keperluan realistik, ketepatan dan interaktiviti. Cabaran paling utama ialah bagaimana untuk mengekalkan kualiti visual tanpa menjejaskan beban ingatan semasa proses penghasilan sesuatu simulasi. Kertas kerja ini membincangkan tentang keperluan, masalah dan teknik dalam visualisasi secara masa nyata terhadap grafik 3D yang kompleks. Keperluan terhadap visualisasi secara masa nyata diterangkan, manakala masalah yang dihadapi oleh kebanyakan pembangun aplikasi grafik 3D dikupas. Seterusnya, teknik-teknik sama ada yang telah digunakan atau yang sedang dikaji dibincangkan. Antara teknik yang sedang dikaji oleh penyelidik-penyelidik ialah seperti simplifikasi poligon dan pemprosesan kawasan paparan tampak. Kajian ini difokuskan terhadap suatu persekitaran 3D yang kompleks dengan bilangan objek yang banyak. Masa nyata adalah merujuk kepada kadar paparan yang dapat mencapai sekitar 15 Hz. Ini adalah penting agar interaksi dalam sesuatu simulasi dapat dilaksanakan secara interaktif. Dengan pertambahan bilangan objek maka bilangan poligon juga akan bertambah dan secara langsung akan menambahkan lagi beban terhadap pemprosesan bagi mencapai kadar masa nyata. Justeru, suatu teknik yang baik diperlukan agar pertambahan bilangan objek tidak akan menjejaskan kualiti hasil.

Katakunci : Visualisasi, Grafik 3D Kompleks, Masa-nyata, Simplifikasi Poligon


1 e-mail : shah@fsksm.utm.my
2 e-mail : yuwaldi@ftsm.ukm.my


1 Pengenalan

Perwakilan data visual yang kompleks sering menjadi motivasi utama dalam penyelidikan grafik komputer. Dalam persekitaran grafik komputer 3D, sering terdapat objek yang terlalu kompleks untuk dipaparkan dalam masa yang bersesuaian malah ia terlalu kompleks untuk dipaparkan meskipun menggunakan mesin yang berkuasa tinggi. Sekitar tahun 1980an dan 1990an, aplikasi 3D dibebankan dengan paparan imej yang tidak realistik dan keperluan mesin yang bukan sahaja mahal tetapi bersaiz besar. Kini, telefon mudah alih yang bersaiz sekecil buah pisang telah mampu memaparkan animasi 3D yang realistik.

Simulasi visual digunakan dalam pelbagai bidang dalam pelbagai industri seperti simulasi penerbangan, pembuatan, pertahanan, penyelidikan saintifik, pembinaan dan pelancongan. Secara umumnya, simulasi visual diperlukan untuk tujuan latihan, pembelajaran, perancangan, eksplorasi dan hiburan. Di samping itu juga, ia digunakan untuk menyelesaikan masalah dan merangka strategi.

Namun, untuk menghasilkan suatu simulasi secara visual dalam persekitaran 3D bukanlah suatu perkara yang mudah. Objek-objek dalam sistem simulasi tersebut perlu dimodelkan secara 3D. Untuk memodelkan objek-objek secara 3D, kaedah konvensional yang digunakan ialah dengan menggunakan perwakilan geometri. Geometri bagi sesuatu objek adalah terdiri daripada beberapa bilangan poligon sebagai permukaannya. Setiap poligon ini perlu diproses dan disimpan oleh perkakasan komputer. Bagi sesuatu sistem simulasi 3D, bilangan poligon yang digunakan untuk mewakili objek di dalamnya adalah sangat banyak. Justeru, ia akan melibatkan kos komputasi yang sangat tinggi. Walaupun teknologi komputer semakin hari semakin canggih dan suatu hari ia pastinya dapat menampung bilangan poligon yang banyak, namun ia masih mempunyai limitasi. Ini kerana bilangan poligon yang mampu diproses masih ada hadnya. Oleh itu, satu mekanisma diperlukan untuk membolehkan suatu simulasi visual itu dilaksanakan tanpa ada limitasi terhadap bilangan poligon yang perlu diproses.

Perkara ini merupakan isu yang masih hangat dibincangkan oleh penyelidik-penyelidik seperti [Lindstrom, 2003], [Cohen, 2003], [Govindaraju et. al., 2003] dan [Yoon et. al., 2003]. Sebagai contoh, model stesen janakuasa dalam Rajah 1 yang dihasilkan secara terperinci menggunakan perisian Rekabentuk Berpandukan Komputer (CAD) diwakili oleh lebih kurang 12 juta segitiga dan 1200 objek bergeometri [Aliaga et. al., 1999]. Model ini tidak dapat dilaksanakan dengan menggunakan komputer peribadi yang berkuasa biasa.

2 Sistem Visualisasi Masa nyata

Pengukuran kadar untuk sesuatu imej dipaparkan di atas skrin monitor dikenali sebagai frame per second (fps) atau Hertz (Hz). Semakin tinggi nilai fps, maka semakin baik kualiti masa nyata bagi sesuatu sistem simulasi secara visual. Ia merupakan perkara yang sangat mempengaruhi kos komputasi. Antara faktor-faktor yang mempengaruhi kadar fps ialah seperti kompleksiti persekitaran dan kualiti visual. Masa nyata dapat ditentukan dengan bilangan rangka yang dapat dipaparkan dalam masa satu saat. Sesuatu sistem visualisasi dikatakan dapat mencapai kadar masa nyata sekiranya nilai fps pada kadar 15 Hz.[Moller dan Haines, 2002]

Contoh sistem visualisasi masa nyata ialah seperti simulator penerbangan. Sistem simulator penerbangan digunakan oleh pelatih jurterbang untuk mengendalikan penerbangan. Oleh itu, sistem ini mestilah bertindakbalas seperti keadaan kapal terbang yang sebenar pada persekitaran dunia nyata. Banyak data-data yang perlu diproses selain daripada paparan grafik dalam sistem ini. Oleh itu, paparan grafik untuk visualisasi seharusnya tidak membebankan kemampuan mesin. Satu lagi contoh aplikasi sistem visualisasi masa nyata ialah telusur bandaran seperti projek Virtual Dublin [Hamill dan O’Sullivan, 2004]. Dalam aplikasi ini keseluruhan bandaraya Dublin hendak dimodelkan dengan terperinci. Satu mekanisma untuk mengawal pemprosesan grafik digunakan.

3 Keperluan dan Masalah Masa Nyata Dalam Visualisasi Kompleks

Menurut Maciel [1995], kos komputasi bagi sesuatu sistem simulasi secara visual adalah bergantung kepada faktor di bawah:
a)Bilangan poligon dan operasi geometrik seperti pencahayaan.
b)Penggunaan imej terhadap objek, contohnya pemetaan tekstur.
c)Gaya pengaturcaraan dalam aplikasi tersebut
d)Sistem perkakasan bagi grafik itu sendiri

Kebanyakan sistem visualisasi yang terdapat di pasaran sekarang memerlukan mesin-mesin khas atau simulator yang melibatkan kos yang tinggi. Ini kerana, penggunaan mesin yang berkos rendah seperti komputer peribadi masih tidak dapat menampung beban komputasi yang dihasilkan oleh aplikasi simulasi.

Simulasi dalam persekitaran 3D memerlukan objek yang terdapat di dalamnya diwakilkan secara tepat. Namun, untuk mewakilkan setiap objek dalam persekitaran 3D dengan tepat, ia akan melibatkan kos komputasi yang tinggi. Kos komputasi yang tinggi bermaksud 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 3D yang tinggi. Grafik ini dihasilkan dengan menggunakan model-model geometri yang terdiri daripada ribuan poligon bagi satu perwakilan objek.

Dengan adanya teknologi pengimbas 3D, proses permodelan objek menjadi lebih mudah. Namun ia memerlukan mesin yang berkuasa tinggi untuk menyimpan data-data geometri bagi model 3D yang telah diimbas.

Akan datang, dengan tren terkini, penggunaan komputer telapak semakin popular. Aplikasi 3D seperti permainan semakin mendapat tempat di kalangan pengguna dan banyak dihasilkan. Justeru bagi menyokong penggunaan aplikasi grafik 3D pada komputer telapak ini, data yang digunakan mestilah sekecil dan secekap mungkin bagi membolehkan ia dimuatkan dalam ruang ingatan yang agak terhad.

Selain itu Funkhouser et. al.[1996], Angelidis dan Fouquier [2001], Lindstrom dan Silva [2001] dan Baxter [2002] membincangkan kepentingan masa nyata dalam persekitaran 3D yang kompleks mengikut aplikasi sistem masing-masing.


4 Aliran Pemprosesan Grafik

Secara konsepnya, aliran untuk menghasilkan paparan bagi suatu sistem grafik 3D adalah seperti dalam rajah 2 berikut [Foley et. al. , 1990]. Tujuan saluran paparan bagi suatu sistem grafik ini adalah untuk memberikan penerangan tentang proses yang berlaku daripada model 3D hinggalah ia dipaparkan pada skrin monitor 2D. Saluran grafik ini dibahagikan kepada dua peringkat utama iaitu peringkat geometri dan peringkat raster. Sesuatu model 3D geometri perlu melalui setiap proses dalam saluran grafik tersebut sebelum ia dapat dipaparkan di skrin.

Daripada aliran pemprosesan grafik tersebut, didapati setiap satu proses akan memberikan kesan terhadap prestasi komputasi. Justeru, untuk mempertingkatkan kadar masa nyata bagi suatu sistem visualisasi, terutamanya yang melibatkan grafik 3D yang kompleks, proses pengoptimuman perlu dilakukan. Proses ini boleh dilakukan terhadap kedua-dua peringkat iaitu peringkat geometri dan peringkat pemprosesan raster.

Bagi peringkat geometri, antara kaedah yang boleh digunakan ialah pemprosesan geometri. Dalam pemprosesan geometri, bilagan poligon yang diproses boleh dioptimumkan dengan hanya menyimpan maklumat geometri bersesuaian dengan penggunaannya. Manakala bagi proses raster, hanya bahagian poligon atau geometri yang kelihatan sahaja yang perlu diproses. Ini dapat dilakukan dengan kaedah pemprosesan paparan tampak dan pembuangan permukaan terlindung.


5 Teknik Pengoptimuman

Terdapat banyak teknik yang dihasilkan untuk mengurangkan bebanan dalam memproses data visualisasi ini. Antaranya adalah seperti pemprosesan geometri atau juga dikenali sebagai level-of-detail (LOD. Selain itu, teknik pemprosesan permukaan tampak dan permodelan berasaskan imej juga merupakan teknik yang sering digunakan. Dalam kertas kerja ini, teknik yang akan dibincangkan adalah pemprosesan geometri dan pemprosesan permukaan tampak.

5.1 Pemprosesan Geometri

Sesuatu sistem simulasi visual boleh dipertingkatkan dari segi keupayaan masa nyatanya dengan mengawal perwakilan geometrik bagi objek-objek yang terdapat dalamnya. Ia dapat dilakukan dengan kaedah-kaedah seperti simplifikasi objek, perwakilan multiresolusi dan tahap keperincian atau level-of-detail (LOD).

LOD ialah satu teknik mewakilkan suatu objek berpoligon dengan pelbagai tahap perwakilan. Ia melibatkan pengurusan ruang ingatan yang digunakan bagi sesuatu simulasi. Teknik ini diimplemen dengan mengurangkan bilangan poligon yang digunakan tetapi mengekalkan sifat yang penting bagi sesuatu objek. Kaedah biasa yang digunakan ialah dengan mengira jarak objek dengan kedudukan paparan atau kamera. Terdapat dua jenis LOD iaitu:
a.LOD Diskrit
b.LOD Selanjar.

Teknik LOD diskrit mula diperkenalkan oleh Clark [1976]. Dalam teknik ini, suatu objek disimpan dalam ruang ingatan dalam multiresolusi dan ditukar secara berkala dan pantas semasa perlaksanaan (runtime). Teknik ini banyak digunakan dalam sistem grafik komputer [Luebke, 2001], [Luebke et. al., 2001]. Rajah 3 berikut menunjukkan penggunaan perwakilan model yang sama dengan bilangan poligon yang berbeza.

Bagi teknik LOD selanjar, resolusi sesuatu objek telah berkurang dan bertambah secara automatik tanpa melibatkan pertukaran model objek semasa perlaksanaan sistem. Contoh teknik ini ialah progressive mesh [Hoppe, 1996] dan simplifikasi topologi [Lindstrom, 2000], [El-Sana dan Varshney,1998] dan [He,1996]. Soetebier et. al. [2004] menggunakan struktur data khusus untuk menguruskan pertukaran antara model-model objek supaya lebih efisyen tanpa melibatkan banyak komputasi.

5.2 Pemprosesan Permukaan Tampak

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 dalam paparan dalam masa yang sama. Oleh itu, sistem tidak perlu mengambil kira objek-objek yang tidak termasuk dalam kawasan paparan atau region-of-interest (ROI) untuk dimuatkan dalam ruang ingatan. Namun, untuk menentukan objek yang terkandung dalam ROI ini bukanlah satu masalah yang mudah. Setiap kali ada perubahan terhadap paparan, contohnya seperti pergerakan kamera secara melintang atau menegak, 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]. Satu kajian tinjauan telah dilakukan oleh [Cohen-Or et. al. 2001] terhadap algoritma Occlusion Culling. Secara umumnya, algoritma occlusion culling ini dikelaskan kepada tiga iaitu:
a.Berasaskan kawasan atau titik.
b.Ruang imej atau objek
c.Persekitaran cell-portal atau generic

Bagi algoritma berasaskan objek, kaedah persempadanan dan pembahagian digunakan oleh [Coorg dan 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.

Kebanyakan algoritma direkabentuk khas untuk persekitaran yang tertentu. Sebagai contoh kajian oleh [Airey et. al., 1990], [Teller, 1992] dan [Luebke dan George, 1995] menggunakan model senibina. Simulasi perbandaran yang mengambil kira kawasan yang agak luas dilaksanakan oleh [Coorg dan Teller, 1997] , [Hudson et. al., 1997], [Schaufler et. al., 2000], [Wonka et. al.,2000] dan [Wonka et. al., 2001].

Kaedah pra-pemprosesan untuk kawasan dan set paparan yang berpotensi untuk kelihatan dalam persekitaran 3D atau potentially visible set (PVS) digunakan dalam sistem simulasi telusur dalam bandaraya. 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. Greene et. al. [1993] dan Zhang et. al. [1997] masing-masing menggunakan hierarchical z-buffer dan hierarchical occlusion maps. Klosowski and Silva [2000] menghasilkan algoritma Prioritized-Layered Projection (PLP) yang hanya menggunakan anggaran sahaja. Kaedah seperti ini juga dilaksanakan oleh [Bartz et. al. 1999]. Hasil tinjauan oleh [Cohen-Or et. al. 2003] menyatakan masih ramai yang belum melakukan penyelidikan Occlusion Culling ini bagi objek dinamik.


6 Kesimpulan

Dunia kini dibanjiri dengan kehadiran gajet-gajet elektronik yang canggih, Suatu hari pastinya sistem visualisasi yang kompleks dapat dilaksanakan menggunakan gajet-gajet tersebut. Kajian tentang kaedah atau teknik untuk mengoptimumkan penggunaan ruang ingatan bagi suatu sistem visualisasi yang kompleks bagi dilaksanakan dalam persekitaran masa nyata ini adalah sangat perlu. Masalah ini penting untuk diselesaikan dengan segera seiring dengan perkembangan teknologi perkakasan. Suatu algoritma yang umum adalah perlu supaya dapat diimplimenkan ke atas apa-apa jenis visualisasi. Ini dapat menyelesaikan masalah penggunaan algoritma tertentu hanya untuk sistem visualisasi tertentu sahaja. Ia bukan sahaja berguna kepada pembangun tetapi juga perlu bagi pengguna agar hasil visualisasi ini dapat digunakan tanpa perlu kos yang tinggi. Selain itu, ia juga diharapkan dapat menjimatkan kos pembangunan suatu sistem simulasi visual atau simulator iaitu dari segi keperluan perkakasan yang lebih murah. Di samping itu juga, kos upah tenaga mahir dalam pembangunan juga dapat dikurangkan iaitu seperti pengaturcara, jurutera sistem dan artis 3D.

Tidak ada komentar: