5 AlgoritmaRendering. 5.1 Pendahuluan

5 5.1

AlgoritmaRendering Pendahuluan Dengan memperhatikan proses geometris dalam bab yang lalu, kini kita akan melihat algoritma bukan-geometrik yang diperlukan dalam pemipaan rendering. Kita terutama akan memperhatikan obyek jaring poligon meskipun teknik yang kadang-kadang digunakan untuk pemyataan yang lain akan diuraikan. Rendering adalah penyajian istilah umum yang menguraikan keseluruhan proses perjalanan yang bermula dari basis data obyek tiga-dimensi menjadi sebuah proyeksi bayangan dua-dimensi pada permukaan pandang. Rendering ini melibatkan sejumlah proses yang terpisah: (1) penetapan sebuah model poligon yang akan berisi semua informasi yang secara berurutan diperlukan dalam proses pembayangan; (2) penggunaan transformasi linear terhadap model jaringn poligon, sebagai contoh, transformasi untuk menempatkan obyek dalam sebuah gambar, dan transformasi pandangan; (3) pemilihan poligon memiliki tampang belakang; (4) pemotongan poligon terhadap volume pandang; (5) pelacakan yang merubah atau rasterisasi poligon, yakni mengubah model yang didasarkan pada vertex menjadi sebuah himpunan koordinat pixel; (6) penggunaan algoritma penghilangan permukaan yang tersembunyi; (7) pembayangan pixel individual dengan menggunakan interpolasi atau pola pembayangan yang semakin bertambah. Dua proses yang pertama berhubungan dengan bab yang lebih awal dan kini kita memperhatikan sisanya. Dalam strategi rendering yang paling terkenal operasi 5, 6, dan 7 dikerjakan secara serentak dalam sebuah algoritma tunggal yang bebas. Akan tetapi, buku pelajaran grafik komputer biasanya penggalan dari proses 159

160

Pengantar Komputer Graftk

rendering. Mereka biasanya berisi sebuah bab yang membandingkan algoritma penghilangan permukaan yang tersembunyitanpa memperhatikanbagaimanaalgoritma ini diintegrasikandengan proses yang lain. Di dalam buku ini kita mengabaikan klasifikasi dan deskripsi beberapa algoritma penghilangan permukaan yang tersembunyi yang mendukung sebuah pendekatan yang menuju bagian kedua dari proses rendering. Daripada memperlakukan mereka sebagai proses yang tidak terhubung, kita akan mencoba sebisa mungkin untuk memperlihatkan bagaimana mereka bekerja bersama-sama. Akan tampak bahwa kebanyakan sistem rendering sudah beres untuk beberapa manifestasi pendekatan penyangga-Z, dan sebagai gantinya workstation grafik kini tersedia perangkat-keras penyangga-Z. Algoritma penghilangan permukaan yang tersembunyi dipakai dalam konteks khusus seperti simulator penerbangan. Sebuah sistem rendering yang lengkap yang didasarkan pada pendekatan ini diberikan dalam Lampiran C.

5.2

Memilih dan mengkliping Penyisihan atau penghilangan tam pang belakang telah diperkenalkan dalam Bab 2. Ini adalah sebuah operasi yang membandingkan orientasi poligon yang lengkap dengan titik pandang atau pusat proyeksi dan menghilangkan poligon yang tidak dapat dilihat. Jika sebuah gambar hanya berisi sebuah obyek cembung tunggal, maka penyisihan mensama-ratakan penghilangan permukaan yang tersembunyi. Sebuah algoritma penghilangan permukaan tersembunyi yang umum selalu diperlukan bila salah satu poligon sebagian mengaburkan yang lain. Secara rata-rata, setengah poligon didalam sebuah polihedron adalah tampang belakang dan keuntungan dari proses ini adalah bahwa sebuah pengujian singkat menghilangkan poligon ini dari fikiran dengan sebuah algoritma penghilangan permukaan tersembunyi yang lebih.mahal. Pengujian jarak penglihatan adalah secara langsung dan dikerjakan dengan cara yang paling bagus dalam ruang pandang. Kita menghitung normal sebelah luar untuk sebuah poligon (Bagian 1.5.3) dan menguji tanda dari perkalian titik normal ini dan vektor dari pusat proyeksi (Gambar 5.1). Jadi: jarak pandang:= Np.N > 0

Algoritma Rendering

161

dimana Np adalah normal poligon N adalah vektor garis pandang

Di dalam Bab 3 kita menguraikan geometri dan spesifikasi frustum pandang, yang akan anda ingat memberi kita batasan berikut di dalam koordinat homogen: -w:!;;;x:!;;;w -w:!;;;y:!;;;w O:!;;;z:!;;; w

Kini kita akan melihat bagaimana kita dapat memperluas definisi ini, yang memberi tabu kepada kita jika sebuah titik tunggal berada di dalam frustum pandang, menuju poligon. Obyek yang perlu dipotong paling mudah ditangani dengan pemotong poligon dengan pemasukan kembali Sutherland-Hodgman (Sutherland-Hodgman, 1974). Ini diperluas dengan mudah menjadi tiga dimensi. Sebuah poligon diuji terhadap sebuah batas potongan dengan pengujian maSing-masingedge poligon terhadap batas potongan tunggal yang berjarak tak terhingga. Struktur ini diperlihatkan dalam Gambar 5.2. Kita memperhatikan kalang yang paling dalam pada algoritma ini, dimana sebuah edge tunggal diuji terhadap sebuah batas potongan tunggal. Di dalam langkah ini keluaran proses tersebut adalah nol, sebuah atau dua buah vertex untuk menambah daftar vertex yang menentukan poligon yang dipotong. Gambar 5.3 memperlihatkan empat kasus yang memungkinkan. Sebuah edge ditentukan oleh vertex S dan F. Di dalam kasus yang pertama edge berada di dalam batas potongan dan vertex F yang masih ada ditambahkan pada daftar keluaran. Di dalam kasus yang kedua edge tersebut melintas batas potongan dan sebuah vertex baru I dihitung dan berupa keluaran. Kasus yang ketiga memperlihatkan edge sebuah edge yang sepenuhnya berada di luar batas potongan. Prosedur ini tanpa keluaran. (Perpotongan untuk edge yang disebabkan penyimpangan yang berada di luar dihitung di dalam iterasi sebelumnya dan potongan untuk slope yang menyebabkan penyimpangan di dalam dihitung di dalam iterasi yang berikutnya.) Kasus yang terakhir menghasilkan sebuah vertex yang baru lagi yang ditambahkan pada daftar keluaran.

162

Penganlar Komputer Graftk

View point

Invisil1lc

:"
l

I

Visil1lc

Gambar 5.1 Penyisihan atau penghilangan tampang belakang.

Untuk menghitung apakah sebuah titik atau vertex berada di dalam, di luar atau pada batas potongan kita menggunakan pengujian perkalian titik. Gambar 5.4 memperlihatkan sebuah batas potongan C dengan normal yang berada di luar

BuEJEJ Bonum dip

Left dip

RighI dip

Top dip

Gambar 5.2 Pemotong Sutherland-Hodgman yang memotong masing-masing poligon terhadap masing-masing slope pada masing-masing potongan persegi.

A/goritma Rendering

163

1

F Case

1

Case 3

- output

- no

-

Case 2 output 1

F

output

Case .t - output

1 then F

Gambar 5.3 Pemotong Sutherland-Hodgman - di dalam kalang poligon masing-masing slope sebuah poligon diuji terhadap masing-masing batas potongan.

Out-ide

Clip h"ul1dar~ C

x

~F

~~

s~ 1'(

\ \

"~ " N,-(P(t)-X)
, , . (P(/) - :() > 0

~ S is outside

Gambar 5.4 Pengujian perkalian titik untuk menentukan apakah sebuah garis berada di dalam atau di luar batas potongan.

164

Pengantar Komputer Graftk

Nc dan sebuah garis dengan titik akhir S dan F. Kita menyatakan garis secara parameter sebagai:

-

(5.1)

p(t) =S + (F S)t dimana 0:::;;t:::;;1

Kita mendetinisikan sembarang titik pada batas potongan tersebut sebagai X dan sebuah vektor dari X menuju sembarang titik pada garis tersebut. Perkalian titik vektor ini dan normal memungkinkan kita membedakan apakah sebuah titik berada pada garis tersebut berada di luar, di dalam, atau pada batas potongan. Di dalam kasus yang diperlihatkan dalam Gambar 5.4: Nc . (S - X) > 0 Nc . (F - X) < 0

=> S adalah di luar daerah potongan. => F adalah di dalam daerah potongan.

dan Nc' (P(t) -X)

=0

menentukan titik potong garis tersebut dan batas potongan. Dengan menyelesaikan Persamaan 5.1 untuk t memungkinkan perpotongan vertex dihitung dan ditambahkan kepada daftar keluaran. Dalam praktek algoritma tersebut ditulis secara rekursif. Begitu sebuah vertex dikeluarkan prosedur memanggil dirinya sendiri dengan vertex tersebut dan tidak ada penyimpanan sementara yang diperlukan bagi poligon yang dipotong sebagian. Struktur ini membuat algoritma tersebut dikenal cocok bagi pengimplementasian perangkat-keras.

5.3

Teknik penambahan bayangan Kebanyakan gambar saat ini dihasilkan dalam gratik komputer yang menggunakan model pantulan Phong, yang diuraikan dalam Bab 4, terhadap model poligon. Model poligon dibedakan oleh kenyataan bahwa informasi geometris hanya tersedia pada vertex sebuah poligon. Teknik bayangan yang bertambah atau interpolatif menerapkan model pantulan terhadap poligon, menghitung intensitas

Algoritma Rendering

165

pada vertex, kemudian menginterpolasikan nilai untuk titik yang berada di dalam. Titik yang berada di dalam dievaluasi dengan urutan garis pelacakan (dari kiri ke kanan) dan pola tersebut mudah diintegrasikan ke dalam sebuah penyangga-Z atau algoritma penghilangan garis pelacakan yang tersembunyi. Sambil lalu, mengenai istilah: istilah 'bayangan' kurang begitu digunakan unookmenandakan penggunaan pada sebuah model pantulan 'titik' pada seluruh permukaan sebuah obyek. Istilah 'rendering' tampak digunakan untuk mamaksudkan proses lengkap yang bermula dari sebuah basis data obyek menjadi obyek bayangan akhir pada sebuah layar. Dua teknik bayangan bertambah yang umum adalah: interpolasi Gouraud (Gouraud, 1971) dan interpolasi Phong (Phong, 1975). Interpolasi Phong memberikan sorotan yang lebih teliti dan umumnya merupakan model yang lebih disukai. Metode Gouraud cenderung dibatasi pada pemakaian dimana komponen difusi cukup, atau untuk melihat terlebih dahulu gambar sebelum rendering akhir. Bayangan Phong lebih mahal daripada bayangan Gouraud dan mengikuti hukum grafik komputeryang pertama,yang tampak bahwa waktu pemrosesanyang diperlukan bertambah secara eksponensial dengan mutu gambar yang dilihat. Akan tetapi bayangan Gouraud hampir menjadi hampir standar dalam perangkatkeras grafik yang ada sekarang ini dan bayangan Phong juga tersedia. Kecenderungan ini tercermin. dalam PInGS+ standar yang diajukan yang berisi utilitas bayangan Phong dan Gouraud (PInGS, 1988). Bagian ini berhubungan dengan kedua metode tersebut dan kita juga melihat bagaimana untuk menggabungkan metode ini dan meningkatkan kecepatan proses pembayangan tanpa kehilangan mutu. Dengan perhitungan bayangan secara efisien merupakan sebuah pokok bahasan yang diabaikan dalam grafik komputer. Perhitungan Phong dapat melampaui lebih dari 50% waktu rendering total; pengalamatan masalah pada bayangan dengan menggunakan sebuah metode yang efisien hams diperhatikan sepenting mutu model pantulan. Ini merupakan perintah dalam bidang seperti animasi tiga-dimensi dimana harus dihasilkan bingkai dalam jumlah yang banyak. Permasalahan lain yang hams dialamatioleh teknik bayangan interpolasiadalah jarak penglihatan poligon akhir. Batas poligon hams tidak tampak dalam versi bayangan akhir dan beberapa kesan mengenai permukaan yang asli bahwa jaring poligon kira-kira dikembalikan lagi. Kita hanya mengidentifikasi dua fungsi dari sebuah pola bayangan untukjaring poligon:

u

166

_____

Pengantar Komputer Grajik

(1) menggunakan beberapa metode interpolasi untuk titik yang berada di bagian dalam, dan (2) untuk mengurangijarak pandang perkiraanjarak pandang poligon. Pola bayangan pertama yang digunakan dalam grafik komputer dikembangkan oleh Bouknight (1970) dan Wylie dan kawan-kawan (1967). Metode Wyllie menghitung intensitas pada vertex facet segitiga yang berdasarkan pada jarak dari titik pandang dan kemudian menggunakan interpolasi linear untuk menetapkan intensitas pada titik yang berada di dalam. Dalam pekerjaan Bouknight peningkatannya berupa penghilangan permukaan yang tersembunyi dan poligon tersebut berupa bayangan yang tetap; jadi, sebuah intensitas tunggal dihitung untuk masing-masing poligon dan digunakan pada seluruh luasanya. Metode ini meskipun memberikan kesan tertentu pada ruang tiga-dimensi (Plate 7) meninggalkan struktur jaring poligon yang jelas mencolok.

5.3.1

Bayangan Gouraud Pola pertama yang diakui secara umum bahwa mengatasi kerugian bayangan tetap pada poligon dengan menggunakan interpolasi intensitas bilinear. Ini dikenal sebagai bayangan Gouraud (Gouraud, 1971). Ini merupakan pola yang sederhana dan ekonomis yang tidak seluruhnya menghilangkan jarak pandang dimana intensitas potongan linear berupoligon. la terkena 'Mach banding' bah melintas sebuah pemicu batas poligon. Sistem penglihatan manusia menuju perasaan batas sebagai pita yang sangat cerah. Penjelasan standar untuk hal ini adalaha bahwa sistem penglihatan manusia peka terhadap intensitas turunan pertama karena kita perlu untuk mendeteksi dan mempertinggi slope. Pola Gouraud secara normal terbatas pada komponen difusi dari model pantulan yang dikembangkan dalam Bab 4. Ini karena bentuk sorotan specular, dengan menggunakan pola ini, sangat tergantung pada jaring poligon yang mendasari. Sebuah contoh yang jelas bahwa bayangan Gouraud sama sekali hilang adalah kasus pada sebuah sorotan dalam pertengahan sebuah poligon. Jika tidak ada komponen sorotan pada sembarang vertex maka tidak ada cara untuk mengembalikan sorotan tersebut dengan interpolasi. Komponen difusi dari Persamaan 4.2 adalah:

-

A/goritma Rendering

167

Gambar 5.5 Normal vertex NA adalah rata-rata dari normal NI. N2. N3. dan N4. normal poligon yang bertemu pada vertex tersebut.

Jika kita menganggap bahwa sumber cahaya tersebut berada pada jarak yang tak terhingga makaLtNbernilai tetap pada permukaan poligon. Yang berupa variabel hanya r, jarak menuju titik pandang. Jika kita mengabaikan kenyataan bahwa perubahan r pada poligon tersebut tidak linear (atau meskipun mengabaikan r sarna sekali), kemudian kita menghitung intensitas pada sumbu dan menggunakan interpolasi bilinear untuk menghitung semua intensitas yang lain. Teknik tersebut pertama menghitung intensitas pada masing-masing vertex poligon dengan menggunakan Persamaan 4.2. Catat bahwa operasi ini harus dilaksanakan dalam ruang koordina alamoNormal N digunakan di dalam persamaan ini disebut juga 'normal vertex' dan ini dihitung sebagai nilai rata-rata normal pada poligon yang patungan vertex tersebut (Gambar 5.5). Ini merupakan ciri penting dari metode tersebut dan normal vertex merupakan perkiraan normal permukaan yang sebenarnya (dengan menyatakanjaring poligon) pada titik tersebut. Plate 7 memperlihatkan sebuah obyek bingkai kawat dengan normal vertex yang bertumpang-tindih. Kini sebagaimana yang dijelaskan dalam Bab. 2, merupakan hal yang biasa untuk menghitung normal vertex hanya sekali saja dan menyimpan vertex ini sebagai bagian dari basis data obyek. Akan tetapi, apakah yang terjadi jika poligon dipotong? KIta harus menghitung kembali normal vertex dan intensitas vertex. 'Perhatikan Gambar 5.6 yang memperlihatkan sebuah potongan melintang melalui tiga poligon. Sebelum pemotongan dua buah normal vertex adalah N) dan

168


N2. Setelah pemotongan normal vertex yang baru N2' dapat dihitung dengan interpolasi antara NI dan N2. Jadi obyek tersebut dibayangi sampai batas potongan sebagaimana jika bagian yang terpotong tersebut masih ada. Pengaruh ini diperlihatkan dalam Plate 2. Lewat struktur data yang menyimpan obyek akan menghitung intensitas, Iv, untuk masing-masing vertex. Kemudian proses interpolasi yang menghitung intensitas pada sebuah permukaan poligon dapat diintegrasikan dengan sebuah algoritma pengubahan pelacakan yang mengevaluasi posisi slope sebuah poligon dari vertex dalam struktur data tersebut. Intensitas pada slope masing-masing garis pelacakan dihitung dari intensitas vertex dan intensitas sepanjang garis pelacakan dari ini (Gambar 5.7). Persamaan interpolasi tersebut adalah sebagai berikut: 1 la = (lICv, - Y2) + 12(}' I - y,» }'I - Y2 1 (l1(Ys - y.d + 1.~(YI- Ys» Ib = YI- Y-I

Is =

1 Xb

-

Xa

.

(la(.\:b- xs) +

Ib(Xs - xa»

Untuk etisiensi komputasional persamaan ini diimplementasikan sebagai perhitungan yang bertambah. Hal ini khususnya penting dalam kasus persamaan yang ketiga, yang dievaluasi untuk setiap pixel. Jika kita mendetinisikan Ax sebagai pertambahanjarak sepanjang garis pelacakan maka M, perubahan intensitas, dari salah satu pixel menuju pixel yang berikunya adalah: ~X

~/s

= Xb -

Is.n

= Is.n-I + ~/s

Xa

(lb

-

fa)

Terlepas dari 'Mach banding', dua kesalahan yang telah diketahui yang dapat diperkenalkan dalam bayangan Gouraud adalah:

.

Anomali yang dapat tampak dalam urutan animasi karena interpolasi intensitas dilaksanakan di dalam koordinat layar dari normal vertex yang dihitung di dalam koordinat alam. Ini bukan invarian terhadap transformasi seperti rotasi dan dalam gangguan pada urutan bingkai-demi-bingkai yang dianimasi dapat disebabkan oleh hal ini.

A/goritma Rendering

Clip boundary

Inside

:

Outside

Gambar 5.6 Normal vertex dan potongan: N2' diinterpolasikan dari NI dan N2.

Gambar 5.7 Notasi yang digunakan untuk persamaan interpolasi intensitas.

169

170

Pengantar Komputer Grafik

Vertex normals

Gambar 5.8 Permukaan berlekuk yang biasa yang menghasilkan normal vertex yang identik dari normal permukaan yang tidak identik.

.

Proses perata-rataan normal permukaan untuk memberikan normal vertex untuk perhitungan intensitas dapat menyebabkan kesalahan yang dihasilkan dalam, misalnya, lekuk yang dimuluskan. Gambar 5.8 memperlihatkan tiga buah normal yang semuanya menunjuk pada arah yang sarna.Ini akan menghasilkan sebuah permukaanyang kelihatanrata.

Pada tahap ini berguna untuk memperhatikan posisi dari perhitungan intensitas vertex dalam pemipaan rendering secara keseluruhan. Hubungi lagi Garnbar 2.22 yang memperlihatkan sebuah pemipaan rendering tiga-dimensi yang umum. Ingat bahwa perhitungan intensitas vertex dilaksanakan dalam ruang koordinat alam. Jika kita melakukan pemisahan yang juga dalarn ruang koordinat alam, maka intensitas vertex tersebut dapat dihitung sekali saja dan bebas dari sembarang perubahan di dalam transformasi pandangan. Strategi ini dapat berguna, misalnya, 'berjalan melalui' animasi dimana hanya titik pandang mengubah urutan bingkai animasi. Akan tetapi, masukkan dalarn benak bahwa sembarang pemotongan yang berlangsung memerlukan perhitungan intensitas vertex yang baru. Jadi pemipaan tiga-dimensi kita yang umum dapat diuraikan untuk bayangan Gouraud, seperti yang diperlihatkan dalam Gambar 5.9.

A/goritma Rendering

171

Calculate vertex intensities

Calculate newvertex normals

World co<'rdinate space

-tI

r ompose scene Define view reference

'3D "creen 'pace

I I

Clip to 3D view volume

Deiine lighting

View 'pace

H

I I I I I I I JI

Gambar 5.9 Penguraian pemipaan rendering tiga-dimensi (Gambar 2.22) untuk bayangan Gouraud.

5.3.2

InterpolasiPhong Sebuah metode oleh Bui-Tuong Phong (1975) mengatasi beberapa kekurangan bayangan Gouraud, dan pantulan ruang dapat berhasil digabungkan di dalam pola tersebut. Secara khusus kini kita memiliki sebuah sorotan ruang di pertengahan sebuah poligon meskipun kenyataannya adalah bahwa masaing-masing sudut normal vertex tidak menghasilkan sebuah sorotan. Ciri-ciri daTimetode tersebut adalah:

.

Interpolasi bilinear masih digunakan dengan demikian titik yang berada di dalam poligon dapat dihitung secara bertambah.

.

Atribut yang diinterpolasi adalah normal vertex, bukan intensitas vertex. Normal vertex ini dihitung, sebagaimana sebelumnya, dengan merata-ratakan vektor normal dari permukaan yang patungan vertex tersebut.

.

Intensitas yang terpisah dievaluasi untuk masing-masing pixel dari normal yang diinterpolasi. Lagi kita perlu menganggap bahwa sumber cahaya dan titik pandang keduanya pada jarak yang tidak terhingga dengan demikian intensitas pada sebuah titik hanya merupakan sebuah fungsi normal yang diinterpolasikan.

.

172


Tahap pertama di dalam proses tersebut sama seperti untuk metode Gouroud untuk sembarang poligon kita mengevaluasinormal vertex. Untuk masing-masing garis pelacakan di dalam poligon tersebut kita mengevaluasi dengan interpolasi linear vektor pada ujung masing-masing garis (Gambar 5.10). Dua vektor ini, No dan Nb, kemudian digunakanuntuk interpolasiNs. Jadi kita menurunkan sebuah vektor normal untuk masing-masing pixel pada poligon tersebut dengan demikian perkiraan terhadap normal yang nyata pada permukaan yang berlekuk-Iekuk dapat diperkirakan dengan poligon tersebut. Ciri ini diperhitungkan untuk mutu bayangan Phong. Ns, vektor normal yang diinterpolasi, kemudian digunakan di dalam perhitungan intensitas. Interpolasi vektor, tentu saja, dilaksanakan di dalam koordinat alam. Gagasan ini dinyatakandi dalam Gambar 5.11, yang memperlihatkan bahwa vektor interpolasi cenderung mengembalikan lagi lekukan pada permukaan yang asli yang diperkirakanoleh sebuahjaring poligon. Dengan meninjau notasi yang digunakan dalam Gambar 5.7 dan Gambar 5.10 kita memiliki:

-

(5.2)

Ini adalah persamaan vektor yang masing-masingakan diimplementasikansebagai sebuah himpunan yang terdiri dari tiga persamaan, salah satu untuk masing-masing dari komponen vektor di dalam ruang alam. Ini membuat fase interpolasi tiga kali lebih mahal daripada bayangan Gouraud. Sebagai tambahan, itu merupakan pemakaian dari persamaan intensitas model Phong pada setiap pixel. Komputasi yang bertambah dapat digunakan seperti interpolasi intensitas, dan Persamaan 5.2, misalnya, akan diimplementasikan sebagai: Nsx,n = Nsx.n-l + t:.Nsx Nsy,n = NSY.n-1 + t:.Nsy Ns~.n = Ns~.n-l + t:.Ns~

dimana Nsx, Nsy, dan Nsz adalah komponen dari sebuah vektor normal garis pelacakan yang umum Ns dan

A/goritma Rendering

Curr~ntscanlin~

Gambar 5.10 Di dalam metode Phong vektor interpolasi menggantikan interpolasi intensitas.

V~ncx normal

Intcrpolatcd normals

Gambar 5.11 Vektor interpolasi untuk mengembalikan lekukan.

V~rtcx normal

173

174


Plate 7 adalah gambaran komposit yang memperlihatkan obyek yang sarna setelah bayangan tetap, bayangan Gouraud dan bayangan Phong.

5.3.3

Perbandinganbayangan Gourauddan Phong Bayangan Gouraud efektif untuk membayangi permukaan yang memantulkan cahaya yang menyebar. Pantulan specular dapat dimodelkan dengan menggunakan bayangan gouraud, akan tetapi bentuk dari sorotan specular yang dihasilkan tergantung pada posisi relatif paligon yang mendasari. Keuntungan dari bayangan Gouraud adalah bahwa secara komputasional ia lebih murah bagi dua model tersebut, hanya memerlukan evaluasi persamaan intensitas pada vertex poligon, dan kemudian interpolasi linear dari nilai ini untuk masing-masing pixel. Bayangan Phong menghasilkan sorotan yang kurang tergantung pada poligon yang mendasari. Akan tetapi lebih banyak perhitungan yang diperlukan yang melibatkan interpolasi normal permukaan dan evaluasi fungsi intensitas untuk masing-masing pixel. Kenyataan-kenyataan ini menyarankan pendekatan secara langsung untuk mempercepat bayangan Phong dengan menggabungkan bayangan Gouraud dan Phong.

5.3.4

pemercepatbayangan Phong Dalam sembarang konteks praktis, seperti produksi urutan animasi, pemakaian metode pemercepat pada bayangan Phong merupakan tambahan yang pokok terhadap pantulan Phong dan pola interpolasi. Bagian ini menguraikan dua teknik pemercepat yang berguna. Teknik pemercepat biasanya dibagi dalarn dua kategori: geometrik dan numerik. Pendekatan geometrik ditemukan dalam (Phong, 1975) dan (Bergman dan kawan-kawan, 1986). Metode Phong didasarkan pada vektor pantulan dan transformasi koordinat ekstra untuk meluruskansumber cahaya (anggap hanya ada satu) sepanjang sumbu z. Bergman menggunakan sebuah pengujian sederhana yang membandingkan arah dari normal vertex poligon dengan arah sorotan maksimum. Ini hanya akan mendeteksi sorotan specular yang berhubungan dengan kasus yang paling sederhana (kasus 1) yang diberikan di bawah ini. Meskipun poligon yang disorot kebanyakan masuk dalarn kategori ini sisanya secara estetika cukup berarti. Hal ini khususnya penting dalam urutan animasi untuk mendeteksi semua

A/goritma Rendering

175

poligon yang disorot jika tidak maka sorotan bisa bertukar on dan off. Peningkatan dalam (Bergman dan kawan-kawan, 1986) adalah pada perkembangan interaktif kecepatan tinggi dari gambar tunggal, dimana cukup hanya dengan pengujian sorotan yang sederhana. Pendekatan numeris terhadap bayangan yang efisien telah diselidiki oleh Duff (1979) serta Bishop dan Weimar (1986). Ini adalah optimisasi dari metode Phong dasar. Bishop, misalnya, menggunakan sebuah deret Taylor dua-dimensi untuk memperkirakan persamaan Phong, yang mengklaim bahwa tidak ada kerugian visual yang didatangkan dalam melakukan hal ini karena interpolasi normal Pho!lg sendiri merupakan sebuah perkiraan. Teknik tersebut menghasilkan sebuah metode yang mengevaluasi sebuah suku ambient, difusi, dan specular untuk masing-masing pixel dengan lima tambahan ditambah lagi satu a:ksesmemori per pixel. Kini kita menguraikan dua metode yang meningkatkan kecepatan bayangan dengan m~nggabungkan bayangan Gouraud dan Phong. Teknik yang pertama dan sangat sederhana yang menghasilkan penghematan kira-kira 35% dalam fase bayangan. Metode yang kedua - pengujian H - adalah pendekatan geometrik yangjauh lebih rumit daripada mendeteksi poligon ini yang akan tampak sebuah sorotan. Ini menghasilkan penghematan yang bahkan jauh lebih besar sebagaimana yang akan diuraikan. Kedua metode tersebut secara efektif merupakan gabungan dari bayangan Gouraud dan Phong.

Peningkatan

kecepatan

bayangan Phong yang sederhanc;r

Di dalam bayangan Phong sebuah normal vertex diinterpolasi secara normal menuju arah yang lain, setiap saat satu langkah pixel. Pada masing-masing pixel ia dinormalisasi, dan intensitas dihitung dari persamaan intensitas Phong standar. Kenyataannya tidak ada kehilangan mutu gambar jika digunakan interpolasi langkah-ganda, dengan pixel perantara yang dihitung dari perata-rataan yang sederhana. Catat bahwa dalam persamaan ini terhadap bayangan interpolasi Gouraud dimana masing-masing poligon memproyeksikan pada sebuah luasan layaryang lebarnyatiga pixel. Pada resolusiini,tentu saja,kerugiandari penggunaan bayangan Gouraud tidak kelihatan. Anda akan ingat bahwa bayangan gouraud tidak dapat digunakan untuk sorotan, secara umum, karena luasan poligon yang besar dimana interpolasi dilaksanakan membawa pada sorotan yang jelek.

176


Pendeteksian

sorotan

-

pengujian H

Secara umum sebuah obyek akan memiliki poligon yang disorot dalam jumlah yang relatif sedikit, sehingga secara komputsional ia akan lebih efisien untuk poligon yang disorot bayangan Phong, dan sisanya bayangan Gouraud (Harrison, Mitchel, dan Watt, 1988). Akan tetapi dalam praktek, komponen difusi diproduksi untuk sebuah pixel khusus oleh dua metode interpolasi yang agak berbeda, dan ini diperlukan Gouraud untuk membayangi seluruh obyek. Kemudian suku specular Phong dievaluasi pada poligon yang tersorot, dan digabungkan dengan nilai difusi Gouraud. Agar memungkinkan pengimplementasian algoritma bayangan gabungan, sebuah pengujian harns ditentukan untuk memastikan poligon yang manakah yang sebagian atau sepenuhnya berada di dalam sebuah luasan sorotan specular. Pengujian ini dikenal sebagai pengujian sorotan atau H-test (Harrison, Mitchell, dan Watt, 1988). Pendeteksian sorotan didasarkan pada hierarki pengujian sederhana yang memperkirakan nilai dari fungsi sorotan pada suatu garis antara dua pucak. Agar menjadi kumpulan dari suku specular (NH) (vektor H adalah vektor tengah dari yang diuraikan dalam Bab 4) kita dapat mengatakan: NH~T dimana T adalah sebuah suku ambang. Nilai suku ini diuji pada pasangan vertex untuk memperkirakan perubahan magnitudonya sepanjang edge. Sebuah hierarki dari lima pengujian sederhana membentuk perkiraan ini:

. . .

. .

Pengujian A menentukan apakah NH pada sembarang vertex lebih besar daripada nilai ambang. Pengujian B menentukan apakah NH mencapai maksimum sepanjang sembarang edge poligon. Pengujian C menentukan apakah maksimum dari pengujian B lebih besar daripada nol. Pengujian D menentukan apakah maksimum ini lebih besar dari nilai ambang. Pengujian E dilakukan sekali setiap poligon, dan menentukan jika sebuah poligon memiliki sebuah maksimum sepanjang edgenya.

Gambar 5.12 memperlihatkan empat kemungkinan sorotan yang berbeda untuk sebuah poligon:

A/goritma Rendering

(I)

177

Sebuah sorotan dapat meliput satu vertex atau lebih, yang memotong garis antara vertex ini dan dua vertex yang berdekatan.

(2) Sebuah sorotan dapat menyebar pada sebuah garis tunggal antara dua vertex, tetapi tidak pada sembarang vertex. (3) Sebuah sorotan dapat terdapat di dalam sebuah poligon, atau (4) Tidak ada sorotan yang berhubungan dengan poligon tersebut. Lima pengujian (A-E) digunakan untuk memastikan empat kasus sorotan manakah yang terjadi. Cara mana pengujian diorganisasikan untuk melakukan hal ini diperlihatkan dalam Gambar 5:13.Sandi Qntukalgoritma dalam bentuk sebuah fungsi diperlihatkan dalam Program 5.1.

5.4

Rasterisasi Dengan melihat bagaimana titik umum dalam sebuah poligon dapat ditetapkan intensitas yang ditentukan dari nilai vertex, kini kita melihat bagaimana kita menentukan pixel yang sebenarnya untuk mana kita memerlukan nilai intensitas. Proses tersebut dikenal sebagai rasterisasi atau perubahan pelacakan. Kita memperhatikan hal ini merupakan masalah yang agak menipu dalam dua bagian. Pertama, bagaimana kita menentukan pixel yang mana edge sebuah poligon tidak memihak? Kedua, bagaimana kita mengorganisasi informasi ini untuk menentukan titik bagian dalam?

5.4.1

Rasterisasi tepi Ada dua cara yang berbeda untuk rasterisasi sebuah tepi, yang didasarkan pada apakah penggambaran garis atau pengisian luasan benda padat yang digunakan. Penggambaran garis tidak tercantum dalam buku ini, karena kita tertarik pada obyek yang berupa benda padat. Akan tetapi, ciri utama dari algoritma penggambaran garis (seperti algoritma Bresenham (Bresenham, 1965» adalah bahwa mereka harus menghasilkan sebuah urutan linear dari pixel dengan tanpa celah (Gambar 5.14). Untuk pengisian luasan benda padat, cukup dengan pendekatan yang kurang teliti. KIta dapat mengisi sebuah poligon dengan menggunakan potongan garis datar; ini dapat dianggap sebagai perpotongan poligon dengan sebuah garis pelacakan tertentu. Jadi untuk sembarang garis pelacakan, apa yang

178


(2).

(3)

(4)

Gambar 5.12 Kemungkinan sorotan yang terhadap sebuah poligon tunggal.

Polygon

Tr:.~IA

Tr:.~IS8. C
For

t

<1m' vertex.

is :v.;.,;!:

T"!

Fur ,/nl" edge. is N.H';!: fat any point on

Yes ~

Case I

Yes ~

Case 2

Yes ~

Case 3

that edge"!

Tr:sIE

For ;,11cdgcs. docs N.H exhibit a maximum ?

t

No Case 4

No highlight

Gambar 5.13 Pengujian bagi sorotan.

Highlight

Algoritma Rendering

Program 5.1 Algoritma pengujian H. function H_test (T: real; Hv: vector): boolean; type vector

=record xc, yc, zc: real; end:

var a, b, c, d, e, f g. h: real; aILedges_max: boolean; highlight: boolean: Av, Bv, Hv: ~'ector; begin alLedges_max : = true: highlight: = false: while more_ vertices and not highlight do begin geLnexLnormal (Av): if dot (A v, H v) > T then {the current vertex is within the} {range of a specular highlight} highlight : = true end; reset_polygon_data: while more_ vertices and not highlight do begin geLnexLpair_of_normals (Av. B(1): a := dot (At'. Hv); b := dot (Bu. Hv): c := dot (At'. Bv): d:= b..c - a: e := a*c - b: f := d*e: if f> 0 then {the specular intensity reaches a maximum along} {the current edge} begin

g := a*d T

b*e:

if d*g > 0 then

{the maximum is greater than zero} {the maximum highlight := true is greater than the threshold}

if g..g >= T *T *(d*d + 2*c*f + e*e) then

end else {the current edge did not have a maximum} alLedges_max : = false end; H_test := highlight or aILedges_max;

end {H_test};

179

180


diperlukan adalah batas potongan sebelah kiri dan sebelan kanan, jadi perpotongan antara garis pelacakan tersebut dengan ujung poligon sebelah kiri dan sebelah kanan. Ini berarti bahwa, untuk masing-masing edge, kita perlu menghasilkan sebuah urutan pixel yang berhubungan dengan perpotongan edge dengan garis pelacakan (Gambar 5.14b). Urutan ini bisa memiliki celah, pada saat diinterpretasikan sebagai sebuah garis, seperti yang diperlihatkan pada edge sebelah kanan dalam diagram tersebut. Cara yang sudah menjadi kesepakatan untuk perhitungan koordinat pixel ini adalah dengan menggunakan apa yang direferensikan sebagai sebuah "digital differential analyser" atau DDA. Semua ini sebenamya berisi menemukan berapa banyak koordinat x bertambah setiap garis pelacakan, dan kemudian diulang dengan menambahkan pertambahan ini. Ambil (xsJ's),(xeJ'e)sebagaititik awal dan akhir pada edge (kita anggap bahwa ye > ys). Algoritma yang paling sederhana untuk perasteran cukup bagi ujungujung poligon adalah: x :=xs m := (xe - xs)/(ye - ys) for y := ys to ye do output (round(x), y) x :=x + m

I

I

/ 1/

/ V

J

I

....

..,.. V-

(a)

I,.-

..,.V-

J

I

....

..,..

(bl

Gambar 5.14 Urutan pixel yang diperlukan untuk (a) penggambaran garis dan (b) pengisian poligon.

Algoritma Rendering

181

Kekurangan utama dari pendekatan ini adalah bahwa m dan x perlu dinyatakan sebagai nilai 'floating-point', dengan sebuah 'floating-point' tambahan dan perubahan real-menjadi-integer setiap kali mengelilingi kalang. Sebuah metode oleh .Swanson dan Thayer (1986) memberikan sebuah versi sbuah integer saja pada algoritma ini. Ia dapat diturunkan dari yang diuraikan diatas dafam dua tahap logika. Pertama, kita memisahkan x dan m ke dalam bagian bulat dan pecahan. Kemudian setiap kali mengelilingi kalang, secara terpisah kita tambahkan dua bagian tersebut, dengan menambahkan sebuah 'carry' kepada bagian integer maka bagian pecahan menjadi overflow. Juga pada awalnya kita menetapkan bagian pecahan dari x bemilai -0.5 untuk membuat pembulatan agar mudah, semudah penyederhanaan keadaan overflow. Di dalam pseudocode: xi := xs

xf:= -0.5 mi := (xe - xs) div (ye - ys) mf := (xe - xs)/(ye - ys) - mi for y : = ys to ye do

output (xi, y) xi := xi + mi xf:=xf+mf if xf > 0.0 then {xi . := xi + 1;. xf := xf - 1.0} Karena bagian pecahan kini tidak tergantung pada bagian integer, ia memungkinkan untuk menskalanya dengan 2(ye - ys), dengan pengaruh perubahan segala sesuatu menjadi algoritma aritmatika: xi := xs xf := -eye - ys) mi := (xe - xs) div (ye -- ys) mf := 2*[(xe - xs) mod (ye - ys)] for y := ys to ye do output (xi, y) xi := xi + mi xf := xf + mf if xf > 0 then {xi := xi + 1; xf:= xf

- 2*(ye -

ys)}

Meskipun ini tampak melibatkan dua pembagian bukan satu, mereka keduanya bulat bukan 'floating point'. Juga, diberikan perangkat-keras yang sesuai,

182


mereka keduanya dapat dievaluasi dari pembagian yang sarna, karena yang kedua (mod) hanya merupakan sisa dari yang pertama (div). Akhimya, ia hanya menunjukkan bahwa 2(ye - ys) yang berada di dalam kalang adalah tetap dan dalam praktek hanya dievaluasi sekali di luamya.

5.4.2

Rasterisasipoligon Kini kita tahu bahwa untuk memperoleh pixel sepanjang edge poligon, perlu untuk mengalihkan perhatian kita untuk memenuhi poligon itu sendiri. Karena kita memperhatikan bayangan, 'pengisian sebuah poligon' berarti memperoleh koordinat pixel dari titik yang berada di dalam dan menetapkan pada titik ini sebuah nilai yang dihitung dengan menggunakan salah satu dari pola bayangan yang bertambah yang diuraikan dalam Bagian 5.3. Kita perlu membangkitkan pasangan potongan titik dan mengisi secara mendatar diantara mereka. Ini biasanya dicapai dengan penyusunan sebuah daftar edge untuk masing-masing poIigon. Secara prinsip, ini dilakukan dengan menggunakan sebuah larik yang terdiri dari daftar yang terhubung, dengan sebuah eIemen untuk masing-masing garis pelacakan. Pada awalnya semua elemen ditetapkan bemilai DOl.Kemudian masing-masing edge poligon tersebut selanjutnya dirasterisasi, dan koordinat x dari masing-masing pixel (x,y) jadi yang dihasilkan disisipkan ke dalam daftar yang terhubung yang berhubungan dengan nilai y. Masing-masing daftar yang terhubung kemudian disortir dengan urutan x yang bertambah. Hasilnya adalah seperti yang tampak dalam Gambar 5.15. Kemudian pengisian poligon tercapai, untuk masing-masing garis pelacakan, dengan mengambil pasangan nilai x yang berurutan dan pengisian diantani mereka (karena sebuah poligon harus tertutup, maka akan ada eIemen dalam jumlah genap di dalam daftar yang terhubung tersebut). Catat bahwa metode ini cukup berdayaguna untuk menanggulangi poligon cembung dengan lubang-Iubang. Dalam praktek, pensortiran daftar yang berhubungan dicapai dengan menyisipkan nilai dalarn tempat yang sesuai di dalarn tempat yang pertama, daripada dengan penyortiran yang besar pada akhimya. Juga, seperti menghitung nilaix dan menyimpannya untuk masing-masingpixel pada sebuah edge, nilai bayangan yang sesuai akan dihitung dan disimpan pada saat yang sarna (sebagai contoh, nilai intensitas untuk bayangan Gouraud; komponenx, y, dan z dari vektor normal yang diinterpolasi untuk bayangan Phong).

Algoritma Rendering

183

I. Transfonnasi global pada sebuah model jaring

-

poligon sebuah silinder yang dipuntir dan disadap.

yang berlekuk-lekuk,

View rotated through 90"

r

+I I

" I

2. Sebuah volumepandang yang berinteraksi dengan sebuah obyek yang memiliki bayangan. Dengan membawa bidang dekat dan jauh .agar berimpit

bidang berimpit dengan obyek.

dengan sebuah obyek;

(I,,,,gah)dekat

bidang impit; (kanan) kedua

I

I

I

Viewrotated through 90"

184


3.

Penggunaan

model pantulan Phong dengan tanpa menggunakan jarakjauh

digerakkan sekitar bola kuning. ('Orange

suku ambient, sebuah sumber cahaya titik yang berof confusion'

seizin Steve Maddock)

,--1..-:

0

,,'\

,/' I

" ' \\ \ I

J/

\,

"'''..

t 4. (Alas dati katlatl bawah) Contoh 20 bola (setelah dilukis oleh Roy Hall). (kanan alas) Potongan melalui tonjolan specular yang memperlihatkan variasi magnitudo dari komponen difusi, specular, dan ambient pada pennukaan dari masing-masing bola berikut: baris yang paling atas, bola 1 dan bola 4; baris yang paling bawah, bola I dan bola 4).

~ c

. ~

~

,,;''' '/

~ IncreasinIt1'k.~

A/goritma Rendering

185

]I~-

~l

::1

..=::::

5. Penggunaan profil LUT untuk mengendalikan wama dan derajad specular sebuah obyek. (alas) Semua obyek memiliki sebuah profil yang mirip, tembaga (obyek a) diperlihatkan. (Iel/gah) Perubahan posisi daerah campuran. (bawah) Pengaruh khllslls.

186


n~~~ral

C0-

Near grazing

",-Phung

4>= 9ft'

6. Model Cook dan Torrance yang digunakan untuk mensimulasikan bOOanyang berbeda. Masing-masing profil RGB memperlihatkan ketergantungan F pada '" untuk suatu bOOan:(alas Jcjrt)emas; (kiri bawah) perak; (kallall bawah) tembaga.

A/goritma Rendering

187

7. Teko teh Utah dan pilihan bayangan. Catat bahwa jarak pandang potongan linear sepanjang edge bayangan hitam karena pernyataan ini hanya berisi 512 poligon. (kiri alas) Bingkai kawat ditarnbah normal vertex. (liallallalas) Poligon yang berbayang tetap. (kiri bawah) Bayangan Gouraud. (Kallall bawah) Bayangan Phong.

8. Rendering tarnbalan pararnetrik pada tingkat sub pembagian yang berbeda (128, 512, 2048, dan 8192 poligon). (Seizin Steve Maddock)

188


9. Perubahan posisi sumber cahaya dalam sebuah algoritma bayangan.

10. Metode pemetaan tekstur dua-dimensi. (ata.f) Teko teh rekursif; tekstur dua-dimensi yang biasa yang diselungkupi dengan menggunakan penyaringan mip-map. (hawah) Pemetaan tonjolan (seizin J. Blinn).

A/goritma Rendering

II.

Pennukaan

yang dimodulasi

189

oleh medan tekstur

tiga-dimensi. (kin) Kubus dari kubus: titik tengah pada masing-masing kubus digunakan untuk memperoleh sebuah wama dari ku~us RGB. (bawah) Urat kayu: fungsi hannonik (sintesa Fourier). (kiri hawah) Tekstur pualam: sarna dengan fungsi hannonik ditambah noise. (kallall hawah) Penggunaan fungsi noise tiga-dimensi.

12. Pemetaan lingkungan: sebelah kid.

(I«mall) lingkungan

yang dipetakan gud teh yang dihasilkan

dad peta lingkungan

sintetik yang diperlihatkan

di

190


13. Ray tracking spheres. (ala.v)Cahaya pelacak kedalaman 6. (pusal) Bagian dari gambar sebelah atas yang dilacak pada kedalaman 1. 2, 3, dan 4. (bawah) Bola pantul dan pendar terhadap latar belakang yang terpotong (gambaran oleh komputer Apollo).

~

transp.lrcnl

~

1 I I I I I I I I I

~-----------IncrcilsingrcnCClivity~

~

transparcnt

~

I I I I I 1 I I I I

A/goritma Rendering

191

-

14. Gerakan kubus dan data CFD. (kin) Simulasi CFD Navier Stokes pada pengapian pipa aliran yang terbalik. Aliran terjadi dari kiri ke kanan dan dari kanan. Antarmuka antara aliran ini menentukan kecepatan permukaan yang sarna yakni nol. Algoritma kubus yang bergerak digunakan untuk memeras permukaan ini yang kemudian dirender secara biasa. (/canan) Sebuab tekstur yang dipetakan pada permukaan kecepatan nol. Skala pseudocolor yang menyatakan suhu medan digabungkan dengan wama yang digunakan untuk bayangan dalam garnbar pada sebelab kiri.

IS. Versi perenderan volume pada sebuab tengkorak. Sifat tidak tembus cabaya dari tulang ditetapkan bernilai I dan semua sifat tidak tembus dari baban yang lain ditetapkan bernilai nol. (Seizin Klaus de Geuss)

16. Sarna seperti Plate 15 kecuali babwa sifat tidak tembus yang bukan nol ditetapkan pada baban yang bukan tulang. (Seizin Klaus de Geuss)

--17. Plate ini memperlihatkan tengkorak bersama-sarna dengan informasi lain yang bertumpang tindih. Struktur kritis dideteksi di dalam data sebagai obyek yang terpisab. Obyek ni disayat sebagai bola untuk bola mata dan silinder umum untuk volume batas tulang belakang. Mereka dirender secara normal dengan menggunakan wama orange. Gagasan tersebut adalab babwa volume batas yang disayat dijarnin agar berisi obyek yang sebenamya. Sebuab tumor otak diperlihatkan berwama hijau dan tiga berkas cabaya untuk mengobati diperlihatkan sebagai obyek bingkai kawat. Wama biru pada tengkorak menunjukkan perpotongan setiap berkas cabaya dengan permukaan kulit. (Seizin Klaus de Geuss)

-

18. Plate 18 sampai 21 semuanya dirender dengan sifa! tulangyang tidak tembus pandang yang ditetapkan bernilai kurang dari satu dan semua pandangan melihat ke bawab berkas cabaya perawatan. Plate ini memperlihatkan sebuab berkas cabaya yang berpotongan dengan bola mata. (Seizin Klaus de Geuss)

192


19. Berkas cahaya dalarn Plate 18 dibentuk kembali agar menjauhi bola mata. (Seizin Klaus de Geuss)

20.

21. Sebuah berkas yang tidak memotong sembarang struktur laitis. (Seizin Klaus de Geuss)

22. Algoritma kubus yang bergerak yang diterapkan pada data CT. Permukaan yang sarna ditentukan oleh koefisien penyerapan sinar-X bagi tulang.

Berkas cahaya yang lain berpotongan

dengan bola mata. (Seizin

Klaus de Geuss)

Algoritma Rendering

193

23. Gambaran radiosity. (alas) Interior Belanda, oleh Vermeer. Gambar ini diilhami oleh kerja seorang tukang cat Belanda pada abad ke 17. Jan Varmer, yang peka terhadap sifat pengaruh-mempengaruhi antara cahaya dan permukaan yang membantu memberi hasil pengecatannya menjadi pengaruh yang dramatis. Metode radiosity digunakan untuk menghitung penyebaran pencahayaan global selama penyiapan proses yang bebas pandang. Setelah pandangan ditentukan, sebuah penyangga-Z yang didasarkan pada algoritma yang sarna untuk mendistribusikan cahaya pelacakan yang digunakan untuk menghitung pantulan specular pada lantai marmer. (Seizin John Wallace. C>1987 oleh Cornell University, Program of Computer Graphics). (bawah) Pabrik baja yang disimulasikan. Gambar tersebut diciptakan dengan menggunakan versi modifikasi dari algoritma radiosity hemicube, yang dihitung pada VAX 8700 dan ditampilkan pada Hewlett-Packard Rennaissance Display. Lingkungan tersebut berisi kira-kira 55.000 elemen, dan merupakan salah satu lingkungan yang paling kompleks yang dihitung pada saat ini. (Seizin Stuard Feldman dan John Wallace, Program of Computer Graphics, Cornell University)

194


24. Metode radiosity untuk interaksi difusi. (alas) Hasil dari gambar jendela yang rnenyala dengan rnenggunakan sub pernbagian potongan untuk rnenghasilkan elernen yang diperlihatkan. (leallall alas) Permukaan yang asli; (leallQIJImgah) Permukaan yang dibagi rnenjadi tambalan; (kallall bawah) Potongan tersebut dibagi lagi rnenjadi elernen dengan rnenggunakan rnetode sub penstrukturan.

25. Supersampling dan penyaringan. Baris atas: gambar ukuran penuh. Baris bawah: gambar lOx, dari kiri ke kanan: sebuah gambar yang tidak disaring, penyaring 3 x 3, penyaring 5 x 5.

A/goritma Rendering

195

26. Bentuk-bentuk pohon yang dihasilkan secara rekursif. (alas) Keduanya menjalankan program dengan menggunakan parameter 'skeletal' yang sarna. (bawah) Keduanyamenjalankan program dengan menggunakan parameter 'bushy'.

27.

(Kin) Sebuah bingkai dari Luxo Jr. yang diproduksi

oleh John Lasetter, Bill Reeves, Eben Ostby dan Sam Leffler; 0 1986 Pixar; Luxo""

adalah merek dagang dari Jak Jacobson Industries. Film tersebut dianimasi oJeh sebuah sistem animasi bingkai kunci dengan prosedur bantuan animasi, bingkai tersebut dirender dengan menggunakan sumber cahayajamak dan prosedur teknik penteksturan. (/canan) Bingkai ini dari Luxo Jr. yang menampakkan gerakan yang kabur sebagaimana diuraikan dalam Bat> 13.

196


G Yellow

G

28.

(Atlll") Kubus RGB. (bawah) Bidang dalarn kubus RGB yang sejajar dengan bidang BG.

Algoritma Rendering

197

29. Model wama HSV dan HLS. (alas) Model wama HSV: irisan melalui sumbu nilai pada interval 20°. (bawah) Model ama HLS: tiga irisan melalui sumbu L pada interval 60°.

Red

Cyan

Red

Cyan

y Green

Y,:O Red

30.

(Kiri alas) Monitor tangga nada solid dalam ruang CIE xyY; (atas) Tiga potongan melintang melalui ruang solid CIE xyY; (/conan ala<)

Posisi potongan melintang pada bidang Y = O.

198


u

L

Green ,

I I

,"

T

I

Red

I I

--'-- ,

"'" Blue

'V......... ." L=50

31. (Kiri alas) Monitor tangga nada solit dalam ruang LOu'v; (alas) Tiga potongan melintang melalui solid dalam ruang LOu'v; (alas /canan) Posisi potongan melintang dalam bidang L yang tetap.

32. Pembetulan gamma memperlihatkan pergeseran kontras dan kroma. Batang atas di dalam masing-masinggambar dikoreksi gamma. (lei,,) Wamalerengmemperlihatkan pergeserankroma.(/canan)Wamaacakyangmemper\ihatkan pergeserankontras.

Algoritma Rendering

199

Jika obyek hanya berisi poligon cernbung rnaka daftar x yang terhubung hanya akan berisi dua koordinat x; struktur data pada daftar edge tersebut disederhanakan dan tidak diperlukan pensortiran. Ini bukan rnerupakan kekangan besar dalarn praktek grafik kornputer untuk rnernaksa sebuah obyek rnenjadi poligon cernbung. Salah satu yang telah dicatat sejauh ini adalah pernikiran dirnanakah sebenarnya letak batas sebuah poligon. Ini dapat rnenunjukkan dirinya sendiri di dalarn poligon yang berdekatan apakah oleh celah yang tarnpak antara rnereka, atau oleh saling turnpang tindih rnereka. Sebagai contoh, dalam Gambar 5.16, lebar dari poligon tersebut adalah 3 satuan, dengan dernikian ia rnerniliki luas 9 satuan satuan, padahal ia dirender dengan sebuah luasan 16 satuan. Penyelesaian sederhana bagi rnasalah ini adalah, dan salah satu yang biasa didukung dalarn buku pelajaran, adalah dengan rnernikirkantitik sederhana pada pixel agar terletak pada pusatnya, jadi, pada (x + 0.5,y + 0.5). (Sebuah pixel dapat dianggap sebagai sebuah persegi yang rnerniliki luasan yang tertentu dengan ukuran 1.0 x 1.0, dan titik cupliknya adalah titik yang berada di dalarn luasan pixel tersebut dirnana gambar dicuplik untuk rnenentukan nilai pixel tersebut.) Dengan dernikian, rnisalnya, perpotongan sebuah edge dengan sebuah garis pelacakan dihitung untuk y + 0.5 bukan untuky, sebagairnana yang kita anggap diatas. Ini rnerupakan hal yang kacau balau, dan tidak rnencanturnkankernungkinan penggunaan aritmatika bulat saja. Sebuah penyelesaian yang lebih sederhana adalah dengan rnenganggap bahwa titik cuplik berada pada salah satu dari ernpat sudut.pixel tersebut; kita

Gambar

5.15

Sebuah contoh mengenai sebuah daftar yang dipertahankan dalam rasterisasi poligon.

200


Gambar 5.16 Masalah dengan batas poligon

-

sebuah poligon 9-pixel mengisi 16 pixel.

memilih sudut kanan atas dari pixel tersebut. Ini memiliki akibat bahwa seluruh gambar diganti setengah pixel sebelah kiri bawah, yang dalam praktek tidak berarti. Hasil dari hal ini adalah bahwa ia memberikan aturan rasterisasi sederhana berikut ini: (1)

Edge datar dibuang.

(2)

Sebuah edge yang pergi dari garis scan )'bawahmenuju Yatasharus menghasilkan nilai untuk garis scan )'bawahmenuju YatasI Gadi, kehilangan garis scan _

atas), ataujika)'bawah= Yatas maka ia tidak menghasilkan nilai. (3)

Hal yang sarna, potongan mendatar hams diisi dari Xkirimenuju Xkanan -I

(dengan tanpa pixel yang dihasilkan j ika Xkiri = Xkanan. Sambillalu, di dalam aturan 2 dan 3, apakah elemen yang pertama atau elemen yang terakhir yang diabaikan adalah berubah-ubah, dan pilihan didasarkan pada kenyamanan pemrograman. Empat permutasi yang memungkinkan dari dua aturan ini menentukan titik cuplik sebagai salah satu dari empat sudut pixel. Pengaruh aturan ini dapat didemonstrasikan dalarn Gambar 5.17. Oi sini kita memiliki tiga poligon yang berdekatan A, E, dan C, dengan edge a, b, c, dan d. Pembulatan nilai x yang dihasilkan oleh edge ini untuk pelacakan yang diperlihatkan masing-masing adalah 2, 4, 4, dan 7. Kemudian aturan 3 memberikan pixel 2 dan 3 untuk poligon A, tidak ada untuk poligon E, dan 4 dan 6 untuk poligon C, semuanya tidak ada celah, dan tidak ada tumpang-tindih. Alasan mengapa edge datar dibuang adalah karena edge yang berdekatan dengan ia akan siap menyumbang nilai x untuk membuat segmen (misalnya, dasar poligon pada Gambar 5.15 - catat juga bahwa demi kesederhanaan, pengubahan pelacakan pada poligon ini

Algoritma Rendering

201

tidak dilaksanakan secara ketat sesuai dengan aturan rastetisasi yang disebutkan di atas).

5.4.3

Urutan rendering Ada dua cara dasar pengurutan renderingsebuah gambar. Yakni: berdasarkanpada poligon-demi-poligon, di mana masing-masing poligon selanjutnya dirender, yang terisolasi dari sernua yang tersisa; dan di dalam urutan garis pelacakan, di mana pot?ngan pada semua poligon di dalam gambar tersebut yang melintas sebuah garis pelacakan tertentu yang dirender, sebelum bergerak pada baris pelacakan berikutnya. Di dalam buku pelajaran standar, klasifikasi ini memiliki kebiasaan menjadi membingungkan dengan klasifikasi algoritma penghilangan petmukaan yang tersembunyi. Kenyataannya, urutan rendering sebuah gambar menempatkan kekangan pada algoritma permukaan tersembunyi yang manakah yang dapat digunakan, akan tetapi ia sendiri ia tidak tergantung pada metode yang digunakan untuk penghilangan permukaan yang tersembunyi. Untuk melompat ke depan dengan jelas, ada beberapa algoritma penghilangan permukaan yang tersembunyi yang cocok dengan dua metode tersebut.

..

dengan poligon dengan garis pelacakan

penyangga-z penyangga-z, penyangga-z garis pelacakan, algoritma garis pelacacakan yang merentang

Rendering dengan poligon memiliki sejumlah keuntungan. Ia sederhana untuk diimplementasikan, ia memerlukan sedikit data yang aktif pada setiap saat. Karena hal inilah, ia menempatkan tanpa batas atas pada kerumitan gambar, tidak seperti rendering garis pelacakan yang perlu mempertahankan secara serentak di dalam rasterisasi memori, bayangan, dan barangkali informasi tekstur untuk semua poligon yang melintas sebuah garis pelacakan tertentu. Kerugian utama dari rendering dengan poligon adalah adalah bahwa ia tidak membuat penggunaan efisiensi yang memungkinkan mengukur seperti penggunaan informasi secara bersama antara poligon (misalnya kebanyakan edge di dalam sebuah gambar digunakan bersama oleh dua poligon). Metode tersebut dapat hanya dapat digunakan dengan algoritma penghilangan permukaan yang tersembunyi penyanggaZ, yang sebagaimana akan kita lihat, agak mahal bila dilihat dari sisi penggunaan memori. Juga, algoritma yang berdasar garis pelacakan memiliki sifat bahwa gambar lengkap yang dihasilkan dalam urutan garis pelacakan, yang memiliki

202


Gambar 5.17 Tiga buah poligon yang memotong sebuah garis pelacakan.

keuntungan untuk pengimplementasian perangkat-keras dan operasi 'antialiasing'. Sebuah perbedaan penting antara dua metode rendering tersebut adalah dalam konstruksi daftar edge. Ini diuraikan dalam suku-suku rendering pada basis poligon-demi-poligon. Akan tetapi, jika rendering dilakukan dalam urutan garis pelacakan, muncul dua masalah. Salah satunya adalah rasterisasi semua edge poligon sebelum menggunakanjumlah memori yang sangat besar, yang menetapkan batas bawah genap pada kerumitan maksimum sebuah gambar. Sebagai gantinya, ia biasa untuk mempertahankan sebuah daftar 'edge aktif'. Bila sebuah garis pelacakan baru dimulai, semua edge akan mulai pada garis pelacakan tersebut ditambahkan pada daftar, sementara yang berakhir padanya dihilangkan. Untuk masing-masing edge di dalam daftar aktif, nilai yang sedang berlangsung bagi x, informasi bayangan, dan lain sebagainya disimpan, bersama-sama dengan pertambahan nilai ini. Setiap saat sebuah edge yang baru ditambahkan, nilai ini diinisialisasi; kemudian pertambahan ditambahkan untuk masing-masing garis pelacakan yang baru. , Masalah yang lain adalah dalam penentuan potongan, karena kini banyak poligon yang aktif pada garis pelacakan tertentu. Secara umum, beberapa informasi tambahan akan perlu disimpan dengan masing-masing edge dalam daftar edge aktif, yang menunjukkan poligon tersebut milik siapa. Rincian yang sebenarnya dari hal ini sangat tergantung pada algoritma penghilangan permukaan yang tersembunyi yang digunakan. Biasanya sebuah daftar poligon yang aktif

Algoritma Rendering

203

dipertahankan yang menunjukkan bahwa bahwa poligon tersebut berpotongan dengan garis pelacakan yang sedang berlangsung, dan oleh karena itu ini dapat mengh~ilkan edge aktif.Oaftar inidiperbaharuipada setiapgaris pelacakan,poligon

yangbarnditambahkandanyangtidakaktifdihapus.

'

Garis besar dari perender poligon-demi-poligon adalah: for each poligon do menyusun sebuah daftar edge dari edge poligon for y := ymin to ymax do for masing-masing pasang (Xl,xl+l)dalam EdgeList[y] do potongan bayangan datar (x!,y) to (Xll+!'Y) sementara pada sebuah perender garis pelacak adalah

menghapus daftar edge aktif for masing-masing garis pelacakan do for masing-masing edge mulai pada garis pelacakan tersebut do tambahkan edge ke daftar edge aktif inisialisasinilai bayangannyadan rasterisasiserta pertarnbahan mereka hilangkan edge yang berakhir pada garis pelacakan tersebut uraikan daftar edge aktif untuk memperoleh potongan render tambahkan pertambahan kepada semua edge aktif Akhirnya, ia bermanfaat untuk menunjukkan bahwa mungkin untuk mencapai gabungan dari dua metode ini. Seringkali ia memungkinkan untuk membagi sebuah gambar menjadi sejumlah obyek yang tidak terhubung. Jika gambar tersebut dirender pada basis obyek-demi-obyek,dengan menggunakan pengurutan garis lacak dalam masing-masing obyek, maka keuntungan dari informasi yang digunakan bersama benar-benar berada di dalam masing-masing obyek, dan tidak ada batas atas pada kerumitan gambar, hanya kerumitan pada masing-masing obyek individual.

5.5

Penghilangan permukaan yang tersembunyi Algoritma penghilangan permukaan yang tersembunyi yang utama diuraikan dalam kebanyakan buku pelajaran grafik komputer dan yang diklasifikasikan

204


sebelumnya, akan tetapi masih ada sangkut pautnya, paper oleh Sutherland, Sproull, dan Schumacker (1974). Dalam paper ini algoritma tersebut dicirikan sebagai apakah mereka terutama beroperasi dalam ruang obyek atau ruang (Iayar) gambar, dan penggunaan "pertalian (coherence)" yang berbeda yang digunakan algoritma tersebut. Coherence adalah istilah yang digunakan untuk menguraikan proses di mana satuan geometris, seperti luasan atau potongan garis lacak, sebagai pengganti titik tunggal, dioperasikan oleh algoritma penghilangan permukaan yang tersembunyi. Ada dua pendekatan yang terkenal untuk penghilangan permukaan yang tersembunyi. Sistem ini didasarkan pada garis lacak dan sistem yang berdasarkan penyangga-Z. Pendekatan lain untuk penghilangan permukaan yang tersembunyi adalah seperti sub pembagian luasan (Warnock, 1969), atau pota daftar kedalaman (Newell, Newell dan Sancha, 1972) khususnya tidak terkenal atau disiapkan untuk pemakaian khusus misalnya simulasi penerbangan.

5.5.1

Perbandingan kedalaman Akhirnya penghilangan permukaan yang tersembunyi menurunkan perbandingan kedalaman titik-demi-titik. Algoritma tertentu beroperasi pada satuan luasan, potongan garis lacak atau bahkan poligon yang lengkap, akan tetapi merekan harus berisi ketentuan untuk kasus yang paling buruk, yakni perbandingan kedalaman antara dua titik. Kebanyakan algoritma penghilangan permukaan yang tersembunyi melakukan perbandingan ini dalam ruang layar tiga dimensi. Ruang ini didefinisikan dalam Bagian 3.7 dan kita ulangi, agar enak, persamaan untuk z.. Zs

1(1 - d/zv) f - d

Transformasi ini, misalnya, sebuah kotak di dalam ruang pandang seperti yang diperlihatkan dalam Gambar 5.18. Proyeksi perspektif kotak tersebut di dalam ruang pandang kini sarna dengan proyeksi sejajar dari kotak yang ditransformasi- . kan dalam ruang layar tiga-dimensi. z" = 0 ditransformasikanmenujuz..=- 00 dan sinar dari titik pandang atau pusat proyeksi kini sejajar. Pengujian kedalaman dalam ruang pandang untuk menentukan apakah PI lebih dekat ke pusat proyeksi daripada P2 yang melibatkan kerumitan yang hanya berartijika kedua titik tersebut berada pada proyektor yang sarna. Kini jika kita membuat perbandingan di dalam ruang layar kita mengetahui bahwa semua titik dengan koordinat yang

Algoritma Rendering

205

sarna (x."y.,.)terletak pada proyektor yang sarna. Akana tetapi harus ada yang dikorbankan. Interval yang sarna dalam z,. tidak memetakan pada interval yang sarna dalam Z.\.Begitu z" mendekati bidang potongan yangjauh, z..jauh lebih cepat mendekati satu. Pengaruhnya, obyek dimampatkan sebagai sebuah fungsi nilai z,,-nya dan ini memitiki proses pencabangan untuk ketepatan

- khususnya pen-

ting dalam kasus algoritma penyangga-Z.

5.5.2

Algoritma penyangga-Z Algoritma penyangga-Z, dikembangkan oleh Catmull (1975), ada di mana-mana dal.am grafik komputer seperti model pantulan Phong dan interpolator, dan gabungan ini mewakili pilihan rendering yang paling terkenal. Dengan menggunakan pola klasifikasi Sutherland (Sutherland, Sproull, dan Schumacker, 1974), ini adalah sebuah algoritma yang beroperasi dalam ruang (Iayar) gambar. Pixel dalam interior sebuah poligon dibayangi, dengan menggunakan pola bayangan yang bertambah, dan kedalaman mereka dievaluasi dengan interpolasi dari nilai vertex poligon sebagaimana yang diuraikan dalam bagian sebelumnya. Algoritma penyangga-Z adalah sarna, untuk masing-masing titik (xs,y.,)menuju pencarian yang berhubungan dengan nilai z pada masing-masing interior titik potigon, untuk memperoleh titik dengan nilai z minimum. Pencarian ini diimplementasikan dengan mudah menggunakan penyangga-Z yang memegang sebuah titik yang sedang berlangsung (x,Y) nilai x yang paling kecil yang dihadapi. Selama pemrosesan sebuah poligon, apakah kita akan menulis intensitas sebuah titik (x,y) kedalam penyangga bingkai, atau tidak, tergantung pada pakah kedalaman z, dari titik yang sedang berlangsung, lebih kecil dari kedalaman yang sejauh ini dihadapi seperti yang disimpan dalam penyangga-Z. Salah satu keuntungan teoritis dari penyangga-Z adalah bahwa ia merupakan bentuk pernyataan obyek yang bebas. Meskipun kita lihat ia paling sering digunakan dalam konteks rendering jaring po1igon,.ia dapat digunakan dengan sembarang pernyataan - semua yang diperlukan adalah kemampuan untuk menghitung sebuah nilai z untuk masing-masing titik pada permukaan sebuah obyek. Ia dapat digunakan dengan obyek CSG, dan obyek yang dirender secara terpisah dapat digabungkan menjadi sebuah gambar obyek jamak dengan menggunakan informasi penyangga-Z pada masing-masing obyek. Aspek ini akan diuji sebentar lagi.

206


\'

~ -x x,

Gambar 5.18 Transformasi kotak dan berkas cahaya dari ruang mata menuju ruang layar.

Keuntungan yang sangat besar dari algoritma penyangga-Z adalah kesederhanaan pengimplementasiannya. Kerugiannya yang utama adalah jumlah memori yang diperlukan bagi penyangga-Z. Ukuran penyangga-Z tergantung pada ketelitian nilai kedalaman masing-masing titik (x,y) yang disimpan, yang merupakan fungsi kerumitan dari gambar. Biasanya dianggap cukup antara 20 sampai 32 bit dan gambar tersebut diskalakan ke jangkauan nilai z yang tetap dengan demikian ketelitian dalam gambar tersebut maksimum. Ingat dalam bagian 5.5.1 bahwa kita telah membahas pemampatan nilai Z,\. Ini berarti bahwa sepasang titik yang berbeda nilai z,. dapat dipetakan kedalam nilai Z.\ yang sama. Catat bahwa untuk penyangga-penyangga dengan kurang dari 24 bit per pixel, katakan, kenyataannya penyangga-Z akan lebih besar dari penyangga bingkai. Pada waktu dulu, penyangga-Z cenderung menjadi bagian dari memori utama dari pengolah 'host', namun kini terminal grafik tersedia dengan penyangga-Z yang telah diopersiapkan dan ini merupakan penyelesaian yang terbaik. Masalah memori dapat dikurangi dengan pembagian penyangga-Z menjadi strip atau bagian dalam ruang layar. Sebagai imbangannya untuk hal ini adalah lewatan yang banyak melalui bagian geometrik dari perender. Poligon dijemput

Algoritma Rendering

207

dari basis data dan dirender jika proyeksi mereka berada di dalam bagian penyangga-Z dalam ruang layar. Penggunaan yang menarik dari penyangga-Z disarankan oleh Foley dan kawan-kawan (1989). Ini melibatkan perenderan obyek tertentu akan tetapi meninggalkan isi penyangga-Z yang tidak dimodifikasi oleh obyek tersebut. Gagasan tersebut dapat diterapkan terhadap interaksi dimana sebuah obyek kursor tiga-dimensi dapat digerakkan dalam sekitar sebuah gambar. Kursor adalah obyek yang terpilih, dan pada saat ia dirender dalam posisinya yang sedang berlangsung, penyangga-Z tidak dituliskan. Meskipun demikian penyangga-Z digunakan untuk melakukan penghilangan permukaan yang tersembunyi pada suatu' obyek dan akan bergerak sekitar gambar tersebut yang mengaburkan obyek yang sama dan d;kaburkan oleh yang lain.

5.5.3

Penyonggo-Zdon pemyataon C5G Algorirma penyangga~Z dapat digunakan agar menguntungkan dalam rendering obyek CSG. Sebagaimana yang akan anda ingat dari Bagian 2.6.3, yang menguraikan sebuah algoritma pelacakan sinar untuk rendering obyek seperti ini, renderingmelibatkan perhitungan sebuah pernyataan batas dari sebuah obyek yang rumit yang dibuat dari obyek sederhana yang digabungkan dengan operator boolean dan diuraikan atau dinyatakan oleh sebuah pohon susunan. Masalah yang ada dengan metode pelacakan sinar adalah mengenai biaya yang mahal. Sebuah pelacak sinar rekursif adalah sebuah metode yang menemukan perpotongan antara sinar dengan arah sembarang dan obyek dalam suatu gambar. Model ini beroperasi secara rekursif terhadap sembarang kedalaman untuk mengevaluasi interaksi specular. Akan tetapi, dengan obyek CSG, semua sinar sejajar dan kita hanya tertarik pada benturan yang pertama, dengan demikian dalam hal ini pelacakan cahaya tidak sesuai dan sebuah pendekatan penyangga-Z lebih mudah untuk diimplementasikan dan tidak mahal (Rossignac dan Requicha, 1986).

.

Pelacakan sinar for masing-masing pixel do hasilkan sebuah sinar dan tentukan semua permukaan obyek yang berpotongandengansinartersebutevaluasipohonCSG untukmenentukan batas permukaan yang pertama sepanjang sinar tersebut

208


.

Penyangga-Z for masing-masing obyek sederhana do for permukaan obyek sederhana F do for masing-masingtitik P dengankerapatankisi yang cukup pada F do Proyek P dan gunakan penyangga-Z if sekarang dapat dilihat then if dengan pengevaluasianpohon CSG Pberada pada batas permukaan then

render kedalam penyangga bingkai Kedua algoritma tersebut harus menerapkan sebuah pengujian yang menurunkan pohon CSG dan mengevaluasi operasi himpunan boolean untuk memperoleh batas suatu obyek, akan tetapi penyangga-Z menghindari pengujian perpotongan yang berhubungan dengan masing-masing cahaya pixel.

5.5.4

Penyangga-Zdan penggabungan Sebuah keuntunganpenting dari algoritmayang berdasar pada penyangga-Zadalah bahwa nilai z yang berhubungan dengan masing-masing pixel dapat disimpan dan digunakan untuk memungkinkan penggabungan elemen gambar yang dihasilkan secara terpisah. Gambar tiga-dimensi sering disusun dari banyak sub-gambar yang terpisah. Sebuah sistem untuk penggabungan elemen yang terpisah dalam sebuah gambar, pixel demi pixel, diajukan oleh Porter dan Duff (1984) dan Duff (1985). Ini adalah sistem sederhana yang dibuat mengitari sebuah pernyataan RGBaZ untuk pixel dalam sebuah sub-gambar. Pada saat penulisan, bingkai 24-bit menyimpan memori z 16-bit yang berhubungan semakin bertambah umum - konfirmasi perangkat-keras pada ketenaran sistem rendering yang berdasar penyangga-Z. Juga, setidaknya satu perusahaan (Pixar) kini telah menggabungkan sebuah memori a atau channel yang memungkinkan parameter kelima ini dihubungkan dengan masing-masing pixel. Parameter ini memungkinkan sub-sub gambar dibuat secara terpisah dan digabungkan, meyimpan informasi sub-pixel yang dihitung dalam rendering masing-masing sub-gambar. Gabungan dibuat dengan menggunakan sebuah operator biner yang menggabungkan dua buah sub-gambar: c =f opb

Algoritma Rendering

209

Sebagai contoh, perhatikan operator ZlIIin.Kita bisa memiliki dua buah sub-gambar, katakan pada obyek tunggal, yang dirender secara terpisah, nilai Z pada masing-masing pixel di dalam rendering akhir terdapat di dalam channel Z. Penggabungan dalam konteks ini berarti pengaruh penghilangan permukaan yang tersembunyi antara obyek terse but dan didefinisikan sebagai: RGBc = (if Zj < Zb then RGBrelse RGBb) Zc = min(Zj,Zb)

untuk masing-masing pixel. Parameter a (0 ~ a ~ 1) adalah bagian dari luasan pixel yang tercakup obyek. la digunakan sebagai sebuah faktor yang mengendalikan campuran warna dalam dua gambar. Penggunaan channel a secara efektif memperluas luasan anti-aliasing yang melintas gabungan dari gambar. Tentu saja parameter ini secara normal oleh perender penyangga-Z dasar, karena hal ini, metode tersebut hanya cocok bila digunakan sehubungan dengan metode penghilangan permukaan yang tersembunyi penyangga-A (Carpenter, 1984), perluasan anti-aliasing terhadap penyangga-Z yang diuraikan dalam Bab 11. Operator "over" didefinisikan sebagai: RGBc = RGBr+ (1 - f!-r)RGBb ac

= ar + (1 - ar)ab

Ini berarti bahwa afberkurang lebih dari RGBbada dalam pixel. Operator gabungan "comp" menggabungkan kedua operator di atas. Ini mengevaluasi pixel yang dihasilkan bila nilai Z pada sudut dari pixel tersebut berbeda antara RGBr dan RGBb.Zjdibandingkan dengan Zb pada masing-masing empat sisi. Ada 16 hasil yang memungkinkan untuk hal ini dan jika nilai Z tidak sarna pada empat sudut tersebut, maka pixel tersebut dikatakan membingungkan. Interpolasi linear sepanjang edge berlangsung dan pecahan [3dihitung (Juasan pixel di mana fberada di depan b). Kemudian kita memiliki operator "compo": RGBc = [3(fover b) + (1 -(3)(b over t)

Sebuah contoh yang lain mengenai penggabungan dalam sintesa gambar tigadimensi diberikan oleh Nakamae dan kawan-kawan (1986). Ini adalah sebuah metode pembuatan gambar tunggal dari beberapa gambar yang lain, titik dimana untuk mengintegrasikan sebuah gambar tiga-dimensi yang dihasilkan komputer, katakan, sebuah bangunan baru, dengan sebuah foto nyata pada sebuah gambar.

210


Keberhasilan dari metode tersebut adalah karena kenyataan bahwa pencahayaan untuk obyek yang dihasilkan dihitung dari pengukuran fotografi latar belakang dan karena pengaruh atmosfir yang diintegrasikan kedalam gambar yang diselesaikan.

5.5.5

Penyangga-Zdan rendering Penyangga-Z menentukan tidak ada kekangan pada pengorganisasian basis data (selain yang diperlukan oleh interpolasi bayangan) dan dalam bentuknya yang paling sederhana dapat dikemudikan pada basis poligon-demi-poligon, dengan poligon yang dinyatakan dalam sembarang urutan yang tepat. Pada prinsipnya, untuk masing-masing poligon kita hitung: (1) nilai (x,y) pada pixel interior, (2) kedalaman z untuk masing-masing titik (x,y), dan (3) intensitas, I, untuk masing-masing titik (x,y). Jadi kita memiliki tida proses interpolasi bilinear yang terjadi secara bersamaan dan tiga buah kalang yang bersarang. Nilai z dan intensitas, I, tersedia pada masing-masing vertex dan pola interpolasi untuk z dan I didistribusikan antara dua kalang yang berada di dalam pada algoritma tersebut. Sebuah versi yang diperluas pada algoritma dengan poligon dengan penghilangan permukaan yang tersembunyi penyangga-Z adalah sebagai berikut: for semua x,y do Z-penyangga-Z[x,y] := maximum_depth for masing-masing poligon do susunsebuahdaftaredgedari edgepoligon(jadiuntukmasing-masing edge, hitunglah nilai x, x, dan I untuk masing-masing garis lacak dengan interpolasi dan simpan mereka dalam daftar edge tersebut) for y := ymin to ymax do for masing-masing segmen dalam EdgeList[y] do mengambil Xleft,Xright,Zleft,Zright,Ileft,Iright for x: = Xleft to Xright do interpolasi linear z dan I masing-masing antara Zleft,Zright dan lleft,Iright

if z < Z_Buffer[x,y] then

A/goritma Rendering

211

Z_Buffer[x,y] := z frame_buffer[x,y] := I Struktur algoritma tersebut mengungkap ketidak efisiensian utama dari metode tersebut, bahwa perhitungan bayangan dilakukan pada pixel yang tersembunyi yang kemudian apakah diabaikan atau ditulis kembali secara berurutan. Jika interpolasi Phong digunakan maka perhitungan model pantulan akhir, yang merupakan fungsi dari normal yang diinterpolasi, juga harus tampak dalam kalang yang paling dalam; jadi menginterpolasikan N bukan I, dan mengganti garis yang terakhir dengan: frame

_buffer[x,y]

:= ShadingFunction(N)

Prosedur yang mengimplementasikan teknik di atas diberikan dalam Lampiran C. Penambahan prosedur ini kepada sandi dalam Lampiran B menghasilkan sebuah sistem rendering yang lengkap.

5.5.6

Garislacak penyangga-Z Ada bermacam-macam algoritma penyangga-Z yang digunakan dengan perender yang berdasar garis lacak, dikenal (tidak mengherankan) sebagai sebuah garis lacak penyangga-Z. Ini hanya merupakan penyangga-Z yang tingginya hanya satu pixel, dan digunakan untuk menyelesaikan masalah permukaan yang tersembunyi untuk sebuah garis lacak tertentu. Ini diinisialisasi kembali untuk masingmasing garis lacak yang baru. Keuntungan utamanya terletak pada jumlah memori yang diperlukan adalah relatif sedikit bila dibandingkan dengan penyangga-Z yang penuh; kenyataannya merupakan hal yang sangat umum untuk melihat sebuah program yang berdasar pada garis lacak penyangga-Z yang berjalan pada sistem yang tidak cukup untuk mendukung sebuah penyangga-Z yang penuh.

5.5.7

Penghilanganpennukaantersembunyiyang merentang Sebuah algoritma penghilangan permukaan tersembunyi yang merentang mencoba, untuk masing-masing garis lacak, untuk memperoleh rentangan yang melintas bayangan yang dapat dilakukan. Masalah penghilangan permukaan yang teserribunyi diselesaikan dengan pembagian garis lacak menjadi panjang yang lewat mana sebuah permukaan tunggal dominan. Ini berarti bahwa perhitungan bayangan dilakukan hanya sekali per pixel, menghilangkan ketidak-efisiensian

212


dasar yang ada dalam metode penyangga-Z. Bandingkan ini adalah masalah yang merentang tidak perlu berhubungan dengan segmen poligon, yang membuatnya lebih sulit untuk melakukan perhitungan bayangan yang bertambah (nilai mulai dihitung pada sebuah titik sembarang sepanjang segmen poligon, bukan ditetapkan pada nilai pada edge sebelah kiri). Kerugian utama yang lain adalah bertambahnya kerumitan algoritma itu sendiri, sebagaimana yang akan kita lihat. Ini umumnya diakui bahwa algoritma rentangan lebih efisien daripada algoritma yang didasarkan pada penyangga-Z, kecuali untuk jumlah poligon yang sangat banyak (Foley dan kawan-kawan, 1989; Sutherland" Sproull, dan Schumacker, 1974). Akan tetapi karena gambar yang amat sangat rumit kini menjadi norma, ia menjadi jelas bahwa, secara keseluruhan, penyangga-Z lebih efisien, kecuali kalau digunakan sebuah fungsi bayangan yang sangat kompleks.

5.5.8

Algoritmagaris lacak yang merentang Gagasan dasar, sebagaimana yang telah dijelaskan, lebih dari hanya sekedar penyelesaian masalah permukaan yang tersembunyi pada basis pixel-demi-pixel dengan menggunakan perhitungan z yang bertambah, algoritma garis lacak yang merentang menggunakan rentangan sepanjang garis lacak lewat mana tidak ada perselisihan kedalaman. Proses penghilangan permukaan yang tersembunyi menggunakan pertalian dalam x dan berhubungan dengan satuan dari beberapa pixel. Pengertian mengenai pemrosesan adalah bahwa pensortiran dalam x diperlukan untuk masing-masing garis lacak dan rentangan yang harus dievaluasi. Cara yang paling mudah untuk melihat bagaimana sebuah algoritma garis lacak bekerja adalah dengan memperhatikan situasi dalam ruang layar tiga-dimensi (x."y,,z.,).Sebuah algoritma garis lacak secara efektif menggerakkan sebuah bidang lacak, jadi, sebuah bidang yang sejajar dengan bidang (x1,y,),ke bawah sumbu y,. Bidang ini memotong obyek dalam suatu gambar dan mengurangi masalah permukaan yang tersembunyi pada ruang dua-dimensi. Di sini potongan pada bidang garis lacak dengan poligon obyek menjadi garis-garis (Gambar 5.19). Segmen garis ini kemudian dibandingkan untuk menyelesaikan masalah permukaan yang tersembunyi dengan memperhatikan rentangan. Sebuah rentangan adalah bagian dari segmen sebuah garis yang terkandung antara potongan edge dari semua poligon yang aktif. Sebuah rentangan dapat dianggap sebagai sebuah satuah koheren, dalam masalah penghilangan permukaan yang tersembunyi adalah tetap dan dapat diselesaikan dengan perbandingan kedalaman pada salah

Algoritma Rendering

213

Scan line plane

Y.

.r, Spans

x,

Gambar 5.19 Sebuah bidang garis lacak digerakkan ke bawah melalui suatu gambar yang menghasilkan segmen garis dan rentangan.

satu ujung rentangan. Catat bahwa pendekatan yang semakin rumit harus diambil jika diperbolehkan penembusan poligon. Dapat dilihat dari tinjauan geometris ini bahwa tahap pertama dalam algoritma garis lacak yang merentang adalah untuk mensortir edge poligon dengan nilai vertex y.. Ini menghasilkan sebuah daftar edge aktif yang diperbaharui begitu garis lacak bergerak ke bawah pada sumbu y.. Jika penemb4san poligon tidak diperbolehkan maka masing-masing potongan edge dengan garis lacak yang sedang berlangsung menentukan sebuah titik pada garis lacak dimana sesuatu sedang berubah, dan dengan demikian kumpulan ini menentukan semua titik batas rentangan. Dengan pergi melalui daftar edge aktif secara urut, memungkinkan untuk menghasilkan sebuah himpunan segmen garis, yang masing-masing menyatakan perpotongan pada bidang garis lacak dengan sebuah poligon. Kemudian ini disortir dengan urutan xs yang bertambah. Kalang yang paling banyak kemudian memproses masing-masing rentangan dalam garis lacak yang sedang berlangsung. Segmen garis aktif dipotong terhadap

214


batas rentangan dan dibagi-bagi oleh batas ini. Kedalaman masing-masing segmen sub-bagian kemudian dievaluasi pada salah satu. dari batas rentangan dan penghilangan permukaan yang tersembunyi dipengaruhi oleh pencarian dalam sebuah rentangan untuk segmen sub-bagian yang paling dekat. Proses ini diperlihatkan dalam Gambar 5.20. Dalam pseudocode algoritma tersebut adalah: for masing-masing poligon do Menghasilkan dan tempat sortir dalam ys yakni informasi edge poligon. for masing-masing garis lacak do for masing-masing poligon aktif do Tentukan segmen atau perpotongan pada bidang lacak dan po ligon. Sortir segmen aktif ini dalam x". Perbaharui pesat perubahan per garis lacak dari parameter bayangan.

Hasilkan batas rentangan. for masing-masing rentangan do Po tong segmen aktif untuk batas rentangan. Evaluasi ~dalaman untuk semua segmen yang dipotong pada salah satu batas rentangan. Selesaikan masalah permukaan yang tersembunyi untuk rentangan tersebut dengan menentukan segmen dengan z" minimum. Bayangi segmen garis yang terpotong yang dapat dilihat. Perbaharui parameter bayangan untuk semua segmen garis oleh pesat perubahan per pixel kali lebar rentangan.

Catat bahwa pengintegrasian ingormasi bayangan jauh lebih tidak praktis daripada dengan penyangga-Z. Rekaman nilai pada ujung segmen garis yang dipotong harus dijaga dan diperbaharui. Ini menempatkan kerumitan gambar yang lain (bersama-sama dengan jumlah poligon absolut) diatas efisiensi dan keperluan akan memori yang diperlukan proses tersebut.

5.5.9

Tltikbanding Dari sebuah pengimplementasian titik pandang yang mudah yang paling baik adalah penyangga-Z. la memiliki keperluan akan memori yang cukup berarti, khususnya untuk penyangga bingkai yang memiliki resolusi tinggi. Akan tetapi, ia menempatkan tidak ada batas atas pada kerumitan gambar, keuntungannya

Algoritma Rendering

z,

z,

.~~. .

.

':''''I. : ~ I

:I I I

. ~

I

.: I

I

I I

215

I

I

,---;

,

I

':I

I I

I I

-,

I I

I I I I I I

x,

Which are used to subdivide a line

Acti\.: lin.: segm':nls produce ,pan boundari.:s

I , I , I

z,

I I I I I

":

II .I

+,: I

I I

I

.:

:I :...0

t--r I I I

I,

"0"

I I '

=\

{

t

z,

:: :::

I

, I { 1-..1

II

x,

I

II

~,

.

0""":

': , 0-,

,_: I

I

I

II

:::

.: I

:

I

x,

Within a span the hidden surface problem is resolved by considering depths along one of the span boundaries.

Gambar 5.20 Pemrosesan rentangan.

adalah bahwa kini ia rnenjadi sernakin penting. Ia rnerender garnbar satu obyek setiap saat dan untuk rnasing-rnasing obyek setiap saat satu poligon. Keduanya ini alarni dan urutan yang bagus selarna yang diperhatikan adalah pernikiran rnengenai basis data. Kekangan yang penting rnenernpatkan pada jenis obyek yang dapat dirender oleh penyangga-Z yang tidak dapat berhubungan dengan obyek yang ternbus pandang tanpa rnodifikasi yang rnernerlukan biaya. Poligon yang ternbus sebagian dapat:

·

·

ditutupi seluruhnya oleh poligon yang lebih dekat yang burarn, dalarn kasus dirnana tidak ada rnasalah, atau rnenjadi poligon yang paling dekat, dalarn kasus dirnana sernua poligon yang berada dibelakangnya harus dipertahankan sedernikian rupa sehingga sebuah

216


gabungan yang sesuai daripada poligon yang tembus pandang dan berikutnya yang paling dekat dapat dihitung. (Poligon berikutnya yang paling dekat tentu saja tidak diketahui sehingga semua poligon diproses.) Dibandingkan dengan algoritma garis lacak, penyelesaian anti-aliasing, khususnya implementasi perangkat-keras, lebih sulit. Cook (Cook, Carpenter, dan Catmull, 1987) menunjukkan bahwa sebuah penyangga-Z

memiliH keuntungan "sistem" yang amat sangat penting. la menyediakan "pintu belakang" yakni dapat menggabungkantitik contoh dengan titik contoh dari algoritma lain yang memilikikemampuanyang lain sepertiradiosityatau pelacakansinar. Jika keperluanakan memoriluarbiasabanyaknyamaka sebuahpenyangga-Zgaris lacak merupakanpenyelesaianberikutnyayang paling bagus. Kecualikalau perender berkelja secaraefisienpada gambaryang sederhana,ini meragukanjika merenungkan peningkatankerumitanyang memerlukanalgoritmagaris lacakyang merentang. Menurutsejarahadapergeserandalampenelitianyangjauh darimasalahpermukaan yang tersembunyi kearah sintesa gambar nyata. Ini dimotivasi oleh tersedianya dengan mudah terminal resolusi ruang dan warna yang tinggi. Semua algoritma penghilangan permukaanyang tersembunyiyang "klasik" dikembangkan sebelum datangnya kerumitan bayangan dan ia kelihatan sebagaimana halnya jika penyangga-Z akan menjadi yang masih bertahan dan paling terkenal untuk rendering yang biasa.

Prayek, catatan, dan saran Proyek berikut ini pasti memerlukan sebuah sistem rendering yang diuraikan dalam bab ini. Mereka kebanyakan memperhatikan mutu-kecepatan dalam teknik bayangan yang bertambah. Sebagaimanabiasa masing-masingproyek diklasifikasi dengan judul dan yang ditandai (*) agak panjang dan dapat digunakan sebagai tugas kursus yang utama atau proyek. 5.1 Bayangan Phong Perluaslah sandi yang diberikan dalam Lampiran C dengan mencantumkan bayangan Phong dan, untuk sebuah obyek, hasilkan sebuah tampilan yang mirip dengan Plate 7 yang memperlihatkan: (1) sebuah bingkai kawat ditambah normal vertex,

Algoritma Rendering

217

(2) sebuah versi bayangan datar atau tetap, (3) sebuah obyek yang dibayangi Gouraud, dan (4) sebuah obyek yang dibayangi Phong. Pisahkan waktu yang diperlukan program anda dalam bayangan yang sebenamya dan bandingkan waku untuk (2), (3), dan (4). 5.2 Pemvisualisasian pita Mach (*) Selidikilahhubungan antarajarak pandangpita Mach dan resolusi poligonal.Hal ini dapat dilakukan dengan menghasilkan sejumlah variabel poligon, untuk, katakan, sebuah toroidadenganpenyapuanvolume,bayanganGouraudsuatu obyek,dan akhir pemrosesan gambar sedemikianrupa sehinggapita-pitaMach dapat dilihat. Pita-pita Mach dapat disorot oleh penurunan gambar dua kali terhadap ruang dan pengambangan nilai intensitas tinggi. Untuk menurunkan sekali, kita dapat menggunakan perkiraan berikut. Untuk semua pixel: E':= {[(A + B + C) - (G + H + 1)]2 + [(A + D -i- G) - (C+ F+ f)f}12

dimana E' adalah nilai baru untuk pixel E dan A, B,..., I adalah larik 3x3 dari pixel yang berpusat pada E: ABC DEF GHI 5.3 Pemercepat Phong yang sederhana Implementasikan metode interpolasi langkah ganda untuk meningkatkan kecepatan Phong sebagaimana yang diuraikan dalam Bagian 5.3.4 dan selidikilah keampuhan metode tersebut dengan melakukan pembandingan waktu dan mutu gambar antara metode pemercepat dan metode standar. Untuk perbandingan mutu gambar, hasilkan sebuah gambar nomal yang dibayangi Phong dan sebuah gambar gambar yang sarna dengan menggunakan teknik pemercepat. Kurangkan dua gambar tersebut dan tampilkan sebuah gambar yang berbeda.

218


5.4

Intensitas

vertex

Untuk sebuah obyek jaring poligon dengan struktur quadrilateral yang biasa, pengaruh tekstur yang berguna dapat diperoJeh dengan pengurangan intensitas vertex yang secara diagonal berlawanan dengan vertex menuju nol seperti yang diperlihatkan dalam Gambar 5.21. Intensitas vertex yang bukan nol dapat ditetapkan agar bernilai sarna dan bayangan Goraud digunakan untuk merender obyek tersebut. 5.5 Intensitas vertex Oi dalam sebuah obyek yang dibayangi Gouraud, pemetaan bermacam-macam intensitas menuju variasi warna-warni dengan menggunakan lintasan yang sesuai di dalam ruang HSV (lihat Bab 14). Catat bahwa ini harus dilakukan dengan menghitung terlebih dahulu lintasan HSV, menyimpan hasil di dalam sebuah L~T dan menggunakan sebuah pola Gouraud persamaan-tunggal untuk mengindeks kedalam LUT. 5.6 Pemercepat Phong Implementasikan pengujian H (lihat Bagian 5.3.4) dan bandingkan unjuk kerjanya terhadap metode numeris (Bishop dan Weimar, 1986). 5.7 Model pantulan benda padat Hasilkan sebuah versi yang dirender dari model pantulan bingkai kawat benda padat (Proyek 4.3 dan Proyek 4.6). Tambahkan silinder yang tipis dan kerucut dengan warna yang berbeda untuk menyatakan vektor L, N, dan R (lihat, misalnya Gambar 4.13). 5.8 Model sumber pencahayaan (*) Implementasikan metode Warn (Warn, 1983) untuk pengendalian sifat alami dan arah sebuah sumber cahaya. Gunakan model pantulan Phong bersama-sama dengan sebuah bidang pandang yang sesuai dengan interaksi sumber cahaya. Perluaslah pola tersebut agar mencantumkan penutup cahaya dan kerucut.

Algoritma Rendering

219

Gambar 5.21 Dengan menggunakan bayangan Gouraud dan struktur jaring poligon seperti pengaruh tekstur.

5.9 Perender dengan poligram penyangga-Z Implementasikan sistem rendering yang diuraikan dalam Lampiran C. Jika anda kekurangan bentuk memori untuk penyangga-Z kemungkinannya adalah agar menggunakan memori setengah layar seperti halnya yang setengah untuk penyangga-Z. Jika memori layar digunakan untuk kedalaman, gambar penyangga-Z dapat ditampilkan dengan menggunakan teknik peningkat pseudocolor (Bab 14). Jadi, petakan variasi kedalaman dalam penyangga-Z kedalam perubahan warna sedemikian rupa sehingga variasi kedalaman lebih mudah terlihat daripada jika tidak mereka akan tinggal sebagai variasi intensitas dalam memori layar.

5.10 Rendering sederhana dengan menggunakan poligon yang dibayangi secara merata Implementasikan sebuah pola rendering sederhana bahwa poligon dengan intensitas rata-rata, menggunakan utilitas pengisi poligon dengan cepat. Tangani penghilangan permukaan dengan membuat daftar poligon yang berisi intensitas rata-rata dan kedalaman rata-rata dan sortirlah daftar tersebut menurut kedalaman. Kemudian poligon tersebllt dibayangi secara urut menllrllt kedalamannya poligon yang palingjauh dihadapi yang pertama.

220


Apakah kekangan dari metode penghilangan permukaan yang tersembunyi yang ditempatkan pada sifat alami gambar atau obyek? 5.11 Transparency Metode rendering yang digunakan dalam Proyek 5.10 dapat dengan mudah diadaptasikan untuk menangani permukaan yang tembus pandang sebagian. Adaptasikan program pada Proyek 5.10 untuk melakukan ini. 5.12 Resolusi penyangga-Z Selidikilah hubungan antara kerumitan gambar dan resolusi penyangga-Z (jadi, resolusi elemen, bukan resolusi ruang). Anda dapat melakukan ini dengan menetapkan sebuah obyek yang dibentuk dari perpotongan dua oyek (katakan, sebuah bola atau sebuah silinder) dan amatilah pengaruh potongan penyangga-Z menuju jangkauan yang lebih rendah dan semakin rendah pada kurva perpotongan antara dua obyek tersebut. 5.13 Penyangga-Z garis lacak (*) Sebuah garis lacak adalah bentuk khusus dari algoritma umum penyangga-Z di mana rendering maju satu garis lacak setiap saat. Semua poligon ini yang meliputi garis lacak yang sedang berlangsung harus diproses dan ini berarti mempertahankan sebuah daftar poligon aktif bersama-sama dengan keadaan intensitas dan interpolasi kedalaman yang sedang berlangsung untuk masing-masing poligon. Bila perpotongan sebuah garis lacak dan sebuah poligon aktif diinisialisasi, interpolasi dimulai lagi dan dibuat perbandingan penyangga-Z: Implementasikan pendekatan ini dan selidikilah perluasan pemrosesan tambahan dibanding dengan metode penyangga-Z yang biasa.

5 AlgoritmaRendering. 5.1 Pendahuluan

Recommend Documents