ABSTRAK
Di dalam makalah ini terdapat analisis algoritma-algoritma yang terbaik
untuk diimplementasikan dalam library OpenGL. Dalam implementasinya untuk dapat
menampilkan suatu objek dari titik-titik kordinat pixel hingga menjadi objek
yang siap untuk ditampilkan dengan sempurna, dalam artian kadangkala saat
menampilkan objek tersebut ada sedikit masalah misalnya objek tersebut berpotongan,
koordinatnya melebihi batas window. Untuk mengatasinya diperlukan algoritma
clpping, rasterization, dan Hidden Surface Remove.
Metode clipping adalah metode yang digunakan untuk menentukan garis yang
perlu digambar atau tidak.Alasan dilakukanna clpping adalah untuk menghindari
perhitungankoordinat pixel yang rumit dan interpolasi parameter. Clpping
dilakuakn sebelum proses rasterization. Setelah proses clipping selanjutnya
dilakukan proses rasterization yang mana dilakukan pengkonversian suatu citra
vektor ke citra bitmap. Sedangkan Hidden Surface Removal merupakan suatu
algoritma yang digunakan untuk menghilangkan penampilan bagian yang tertutup
oleh objek di depannya. Apabila ada dua bidang
yang berpotongan, jika objek tersebut ditampilkan biasa tanpa menggunakan algoritma Hidden surface
removal maka bagian yang berpotongan itu akan tidak kelihatan. Algoritma Hidden Surface Removal ini perlu
dilakukan untuk menampilkan bidang perpotongan tersebut.
Tiap metode mempunya beberapa algoritma dan tentunya tiap algoritma
memiliki kelebihan dan kekurangan untuk dianalisis. Contohnya pada algoritma
clpping didapatkan algoritma Liang-Barsky yang terbaik karena kecepatan waktu
yang efisien dan juga stabil. Untuk metode rasterization didapat algoritma
Midpoint yang terbaik karena operasi bilangan pada Midpoint dilakukan dengan
cara menghilangkan operasi bilangan riel dengan bilangan integer yang mana
bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel.
Oleh karena itu, komputasi midpoint lebih cepat delapan kali pada pembuatan
garis lurus dan lima belas kali pada penggambaran lingkaran. Sedangkan pada
metode Hidden Surface Remove, algoritma yang terbaik adalah algoritma scan Line
karena pada algoritma ini menggunakan memori yang lebih sedikit dan dari segi
kecepatan juga lebih unggul.
Kata kunci: clipping, rasterization, hidden surface
removal (hsr)
PENDAHULUAN
Pada bidang ilmu
Grafika Komputer tentunya tidak dapat terlepas dari pembuatan dan manipulasi
gambar (visual) secara digital. Bentuk sederhana dari
grafika komputer adalah grafika
komputer 2D yang kemudian berkembang menjadi grafika komputer 3D, pemrosesan citra (image processing), dan pengenalan pola (pattern
recognition). Grafika komputer sering dikenal juga
dengan istilah visualisasi data.
Dalam makalah ini
akan dijelaskan tiga metode tentang optimasi atau citra komputer. Metode-metode
tersebut adalah clipping, rasterization, dan hidden surface removal. Ketiga
metode ini tentu memiliki beberapa algoritma yang dapat dibandingkan algoritma
mana yang terbaik. Pada metode clipping dilakukan pemrosesan untuk menentukan
bagian mana yang perlu ditampilkan dalam clipping window. Clipping perlu dilakukan untuk menghindari perhitungan koordinat pixel
yang rumit dan interpolasi parameter. Setelah itu dilakukan proses
rasterization untuk mengkonversi suatu citra vektor ke citra bitmap. Pada langkah
rasretization ini, koordinat dalam bentuk geometri dikonversi atau diubah
kedalam fragmen pada koordinat screen. Setelah langkah ini, tidak ada lagi kata
“poligon”. Semua geometri yang membentuknya ke dalam proses rasretization
adalah dengan dinormalisasikan pembagian wilayah. Pada proses ini perlu
mengkonversi kontinu (floating pixel) geometri ke dalam diskrit (integer).
Setelah itu ada metode Hidden Surface removal yang digunakan untuk
menghilangkan penampilan bagian yang tertutup oleh objek yang didepannya. Apabila ada dua bidang yang
berpotongan, apabila ditampilkan biasa tanpa menggunakan algoritma Hidden
surface removal maka bagian yang berpotongan itu akan tidak kelihatan. Algoritma Hidden
Surface Removal ini perlu dilakukan untuk menampilkan bidang perpotongan tersebut.
Dari beberapa analisis nanti diharapkan mendapatkan algoritma terbaik
dari masing-masing metode yang nantinya akan digunakan untuk pengimplementasian
ke dalam library OpenGL.
METODE CLIPPING
Ada beberapa teknik yang dapat digunakan
untuk melakukan proses clipping, diantaranya adalah
1.
Vertex Clipping
Untuk
menentukan letak suatu titik di dalam clipping window dapat digunakan rumus
Xmin
≤ x ≤ Xmax
Ymin
≤ y ≤ Ymax
Dimana
Xmin, Ymin, Xmax, Ymax merupakan batas clip window untuk clipping window yang
berbentuk persegi empat dengan posisi standar. Kedua kondisi di atas harus
terpenuhi agar teknik ini dapat dijalankan. Jika salah satu tidak terpenuhi
maka titik tersebut tidak berada dalam clipping window.
Contoh
kasus :
Terdapat
dua buah titik, yaitu P1(2,2) dan P2(3,6) dengan Xmin = 1, Xmax = 5, Ymin = 1,
dan Ymax = 5
Dari gambar di atas, dapat
dilihat bahwa titik P2 berada diluar area Clipping Window karena titik P2 koordinat
y-nya melebihi Ymax dari clipping window sehingga titik P2 tidak akan
ditampilkan.
Metode Clipping titik ini dapat
diaplikasikan pada scene yang menampilkan ledakan atau percikan air pada
gelombang laut yang dibuat model dengan mendistribusikan beberapa partikel.
2.
Line Clipping
Line
clipping atau clipping garis diproses dengan inside-outside test dengan
memeriksa endpoint dari garis tersebut. Berdasarkan test tersebut garis dapat
dikategorikan menjadi empat jenis
Nama
|
Kondisi
|
Invisible
(garis 1)
|
Tidak
keliatan, terletak di luar clipping
window
|
Visible
(garis 2)
|
Terletak
di dalam clipping window
|
Half
partial (garis 3)
|
Terpotong
sebagian oleh clipping window
|
Full
partial (garis 4)
|
Terpotong
penuh oleh clipping window
|
Untuk
garis yang invisible dan visible tidak perlu dilakukan aksi
clipping karena pada kondisi invisible,
garis tidak perlu ditampilkan sedangkan pada kondisi visible garis bisa langsung ditampilkan. Untuk segmen garis dengan
endpoint (x1,y1) dan (x2,y2) serta keduanya terletak di luar clipping window memiliki persamaan,
x =
x1 + u(x2 – x1)
y =
x1 + u(x2 – x1)
0 ≤ u
≤ 1.
Persamaan
tersebut dapat digunakan untuk mengenali nilaiparameter u untuk koordinat
pemotongan dengan batas clipping window.
Ada beberapa algoritma dalam melakukan teknik line
clipping, diantaranya adalah sebagai berikut Cohen – Sutherland, Liang –
Barsky, Cyrus – Beck, dan Nicholl – lee – Nicholl. Dan algoritma yang paling
terkenal adalah algoritma Cohen-Sutherland dimana setiap endpoint atau titik
ujung dari garis direpresentasikan ke dalam empat digit angka biner yang
disebut region code dan Liang-Barsky.
Metode
Cohen-Sutherland
Pada metode Cohen-Sutherland masing-masing digit tersebut akan menentukan posisi titik relatif
terhadap batas clipping yang berbentuk segiempat. Untuk lebih jelasnya dapat dilihat pada gambar dan tabel di bawah ini.
4
|
3
|
2
|
1
|
0
|
0
|
0
|
0
|
Bit
ke-1 : region Kiri (L)
Bit
ke-2 : region Kanan (R)
Bit
ke-3 : region Bawah (B)
Bit
ke-4 : region Atas (T)
Bit
dengan nilai 1 menandakan bahwa titik berada pada region yang bersangkutan.
Jika tidak maka diset nilai 0.
Algoritma Liang-Barsky
Algoritma ini menggunakan
persamaan parameter garis dan gambaran pertidaksamaan dari range clipping box
untuk menentukan titik temu antara garis dan clipping box. Kita harus melakukan
pengujian sebanyak mungkin sebelum menghitung interseksi garis. Misalnya bentuk
parameter biasanya garis lurus
1. Garis paralel ke tepi
clipping window mempunyai batas pk
= 0
2. Jika untuk setiap k, qk
< 0, maka garis sepenuhnya berada di luar dan dapat dieliminasi.
3.
Bila pk < 0 maka
dihasilkan garis dari luar ke dalam clipping window. Bila pk > 0 maka dihasilkan garis dari dalam ke luar.
Bila pk < 0 maka
dihasilkan garis dari luar ke dalam clipping window. Bila pk > 0 maka dihasilkan garis dari dalam ke luar.
4.
Untuk setiap pk tidak sama dengan 0 maka
dihasilkan titik interseksi
5.
Untuk
setiap line, hitung u1 dan
u2. Untuk u1, lihat batas pk<0 (luaràdalam). Ambil u1 untuk
menjadi yang terbesar di antara dan
untuk u2, lihat batas pk>0 (dalamàluar). Ambil u2 untuk
menjadi yang minimum dari . Jika u1>u2 maka garis berada di luar dan
ditolak.
Untuk
setiap line, hitung u1 dan
u2. Untuk u1, lihat batas pk<0 (luaràdalam). Ambil u1 untuk
menjadi yang terbesar di antara dan
untuk u2, lihat batas pk>0 (dalamàluar). Ambil u2 untuk
menjadi yang minimum dari . Jika u1>u2 maka garis berada di luar dan
ditolak.
3.
Polygon Clipping
Polygon merupakan bidang yang
tersusun dari verteks (titik sudut) dan edge (garis penghubung setiap verteks).
Untuk dapat melakukan proses clipping pada polygon diperlukan algoritma yang
lebih kompleks dari kedua teknik clipping yang telah di bahas sebelumnya. Salah
satunya adalah algortima Sutherland-Hodgman. Ide dasarnya adalah memperhatikan edge pada
setiap arah pandang, lalu clipping polygon dengan persamaan edge kemudian
lakukan clipping tersebut pada semua edge hingga polygon terpotong sepenuhnya.
Ada beberapa ketentuan dari algoritma Sutherland-Hodgman, diantaranya adalah
1. Polygon dapat dipotong
dengan setiap edge dari window sekali pada suatu waktu
2. Vertex yang telah
dipotong akan disimpan untuk kemudian digunakan untuk memotong edge yang masih
ada
3. Perhatikan bahwa jumlah
vertex biasanya berubah-ubah dan sering bertambah
METODE RASTERIZATION
Rasterization adalah sebuah proses
mengkonversi sebuah penggambaran vertex menjadi sebuah penggambaran pixel.
Rasterization juga biasa disebut scan conversion. Algoritma scan conversion
menggunakan metode incremental yang memanfaatkan koherensi. Sebuah metode
incremental menghitung sebuah nilai baru dengan cepat dari nilai lama, bukan
menghitung nilai baru dari awal yang dapat memperlambat. Koherensi dalam ruang
atau waktu adalah istilah yang digunakan untuk menunjukkan bahwa benda-benda
didekatnya (misalnya pixels) memiliki kualitas yang mirip dengan objek.
Pada langkah rasretization ini, koordinat
dalam bentuk geometri dikonversi atau diubah kedalam fragmen pada koordinat
screen. Setelah langkah ini, tidak ada lagi kata “poligon”. Semua geometri yang
membentuknya ke dalam proses rasretization adalah dengan dinormalisasikan
pembagian wilayah. Pada proses ini perlu mengkonversi kontinu (floating pixel)
geometri ke dalam diskrit (integer).
1.
Rasterization Titik
Dalam keadaan default,
sebuah titik diraster dengan memotong kordinat Xw dan Yw (ingat bahwa subcript
menunjukkan bahwa ini adalah x dan y clipping
window) ke integer. Alamat ini (x,y), berdasarkan pada data terkait dengan
simpul yang sesuai ke titik, dikirim sebagai sebuah fragmen tunggal untuk tahap
per-fragme dari GL tersebut.
Efek dari lebar titik lebih
dari 1. 0 tergantung pada keadaan antialiasing titik. Jika antialiasing
dnonaktifkan, lebar aktual ditentukan oleh pembulatan lebar dipasok ke integer
terdekat, kemudian mengapit ke titik lebar non-antialiasing maksimum implementation-dependent. Meskipun nilai
implementation-dependent tidak
dapatdi-query, tapi harus tidak kurang dari lebar titik maksimum antialasing implementation-dependent, dibulatkan ke
nilai integer terdekat, serta tidak boleh kurang dari 1. Jika lebarnya
merupakan ganjil maka
Persamaan di atas
dihitung dari Xw dan Yw vertex dan grid persegi berlebar ganjil berpusat di
(x,y) mendefinisikan pusat fragmen raster (ingat bahwa pusat-pusat fragmen
terletak pada nilai koordinat jendela half-integer). Jika lebarnya genap maka
pusat titik adalah
Pusat fragmen raster adalah nilai koordinat
half-integer window dalam persegi yang berpusat di (x,y).
“Rasterization
non-antialiasing. Tanda silang menunjukkan pusat fragmen yang dihasilkan oleh
rasterization untuk setiap titik yang terletak di wilayang gelap. Garis
putus-putus pada grid terletak pada koordinat half-integer.”
Jika antialasing
diaktifkan, maka rasterization titik menghasilkan fragmen untuk setiap persegi
fragmen yang memotong daerah yang berada dalamlingkaran berdiameter sama dengan
lebar titik saat ini dan berpusat pada titik (Xw, Yw). Perhatikan gambar di
bawah ini
Pada gambar di atas,
titik hitam menunjukkan titik yang akan diraster. Daerah gelap memiliki lebar
yang ditentukan. Tanda x menunjukkan pusat fragmen yang dihasilkan oleh
rasterization. Perhitungan fragmen didasarkan pada bagian wilayah gelap yang
menutupi persegi fragmen.
2.
Rasterization Line
Line segmen
rasterization dimulai dengan mengkarakterisasi segmen sebagai x-major dan
y-major. Segmen garis x-major mempunyai
penurunan interval mendekati [-1,1] dan semua segmen garis lainnya merupakan
y-major (slope atau turunan ditermain oleh endpoint segmen). Rasterization
ditentukan hanya untuk segmen x-major kecuali dalam kasus dimana memodifikasi
untuk segmen y-major yang sudah jelas.
Idelanya, GL menggunakan
aturan ‘diamond-exit’ untuk menentukan fragmen yang diproduksi oleh
rasterization segmen garis. Untuk setiap fragmen f dengan pusat di window
koordinat x dan y mendifinisikan wilayah berbentuk ‘diamond’ yang merupakan
intersection empat half plan.
Ketika Pa dan Pb berada
di pusat fragmen, karakterissasi fragmen mengurasi untuk algoritma Bresenham
dengan satu modifikasi. Hasil baris dalam deskripsi ini adalah ‘setengah
terbuka’. Artinya bahwa fragmen terakhir (sesuai dengan Pb) tidak ditarik. Ini
berati bahwa ketika proses raster segmen garis tersambung,endpoint akan
diproduksi hanya sekai bukan dua kali (seperti yang terjadi pada algoritma
Bresenham’s).
Beberapa algoritma yang
digunakan
a.
Algoritma Naive
Algoritma ini dimulai
dari segmen garis pada koordinat dengan nilai bulat (integer) untuk endpoint
·
m = (y2 - y1) / (x2 - x1)
·
y = m*x+b
·
2 operasi floating-point per piksel
b.
Algoritma DDA (Digital Differential Analyzer)
Misalkan po = (xo,yo)
dan p1 = (x1,y1) menjadi dua endpoint dari suatu garis. Kita akan mengasumsikan
bahwa titik tersebutberada di koordinat xo,yo,xi,yi. Dimana intersep titik dari
po, p1 adalah y = mx + b dan m = (y2-y1)/(x2-x1) dan intersep y adalah b=y1-mx1.
void
Line_DDA(intx1, inty1, intx2, inty2)
{
floatdy= y2-y1;
floatdx = x2-x1;
floatm = dy/dx;
floaty = y1;
for (intx=x1; x<=x2; x++)
{
putpixel(x,round(y));
y += m;
}
}
c.
Algoritma Midpoint
Untuk menerapkan
kriteria midpoint, kita hanya perlu menghitung
d = F(M) = F(xp+1, yp+0.5)
If d>0then
move to NE
else
move to E
Dari
gambar diatas untuk memilih NE atau E yaitu dengan menghitung di mana sisi
garis M terletak. y =
dy/dx * x + b
Oleh karena itu :
F(x,y) = dy*x – dx*y + b*dx = 0
0 à tepat di garis
F(x,y) = >0
à di bawah garis
<0 à di atas garis
Jika E maka :
dnew = F(xp+2,yp+0.5)
= dy*(xp+2) – dx*(yp+0.5) + b*dx
Δd = dnew
– d = dy
dnew = d +
Δd = d + dy
Jika NE maka :
dnew
= F(xp+2,yp+1.5) = dy*(xp+2) –dx*(yp+1.5)
+ b*dx
Δd = dnew
– d = dy – dx
dnew = d +
Δd = d + dy – dx
3.
Rasterization Polygon
Langkah pertama
rasterization poligon adalah untuk menentukan apakah poligon back facing atau
front facing. Aturan untuk menetukan fragmen yang dihasilkan oleh rasterization
disebut titik sampling. Fragmen pusat yang berada di dalam poligon ini
diproduksi ole rasterization. Perlakuan khusus diberikan kepada sebuah fragmen
yang pusatnya terletak di tepi batas poligon.
Poligon stippling
bekerja dengan banyak cara yang sama sebagai garis stippling, maskinh fragmen
tertentu yang dihasilkan oleh rasterization sehingga mereka tidak dikirim ke
tahap GL berikutnya. Hal ini terlepas dari keadaan poligon antialiasing.
·
Polygon Convex
Untuk poligon convex
pertama yang harus dilakukan adalah cari vertex atas dan vertex bawah. Kemudian
list edge yang berada di sepanjang sisi kiri dan kanan. Untuk setiap scan line
dari atas ke bawah, cari jarak antara endpoint kiri dan kanan (xl,xr) kemudian
isi pixelnya.
·
Poligon Concave
Ada tiga pendekatan yang
bisa digunakan. Yang pertama adalah dengan even-odd rule yang mana untuk setiap
scan linenya kita perlu mencari semua scan line atau interseksi poligon.
Kemudian urutkan dari kiri ke kanan dan mengisikan rentang interior diantara
interseksi. Pendekatan keduua adalah dengan winding rule yang berorientasi
garis.
4.
Resterization Antialiasing
Antialiasing poligon
merester poligon dengan memproduksi sebuah fregmen dimanapun interior poligon
persegi berpotongan. Sebuah datum yang terkait ditugaskan untuk fragmen dengan
mengintegrasikan nilai datum yang sama dengan wilayah intersect dari fragmen
persegi dengan interior poligon dan membagi nilai integrasi dengan wilayah
intersect. Untuk fragmen persegi berada sepenuhnya di dalam poligon. Nilai
suatu datum di pusat fragmen mungkin digunakan sebagai pengganti
mengintegrasikan nilai seluruh fragmen.
Ada dua algoritma yaitu
Algoritma Bresenham (Aliased-line) yang mana hanya satu point di setiap kolom
dan Algoritma Grupta-Sproull (Antialiased-line) yang mana intensitas point
tergantung oleh jangkauan garis piksel.
METODE HIDDEN SURFACE REMOVAL
1.
Algoritma Z Buffer
Algoritma Depth Buffer mempergunakan image space
sebagai dasar proses perhitungan tampak atau tidaknya permukaan suatu objek.
Algoritma ini menguji tampak atau tidaknya setiap pixel pada suatu permukaan
objek yang satu terhadap permukaan objek yang lain dan harga permukaan yang
paling dekat dengan bidang pandang yang akan tersimpan dalam Depth Buffer dan
selanjutnya harga intensitas warna dari permukaan pixel tersebut disimpan di
dalam Refresh Buffer atau algoritma Depth Buffer ini akan menampilkan bagian
permukaan objek berdasarkan posisi z yang paling dekat dengan bidang pandang
dengan proyeksi orthogonal atau proyeksi tegak lurus.
Pada gambar 1
memperlihatkan tiga permukaan bidang pada berbagai kedalaman z dengan posisi
(x,y) yang sama untuk setiap permukaan. Sedangkan pada gambar 2 dapat dilihat
bahwa permukaan S1 mempunyai harga z terkecil pada posisi (x,y) sehingga harga
z disimpan pada Depth Buffer dan harga intensitas S1 pada (x,y) disimpan pada
Refresh Buffer. Jadi, algoritma ini membutuhkan dua buffer untuk
implementasinya.
Langkah-langkah
algoritma Depth Buffer adalah sebagai
berikut
1. Inisialisasi Depth Buffer dan refresh
Buffer sehingga untuk semua koordinat posisi (x,y) depth (x,y) = 0 dan refresh
(x,y) = background.
2. Untuk setiap posisi pada permukaan,
bandingkan harga kedalaman terhadap harga yang tersimpan pada Depth Buffer
untuk menentukan penampakan.
a. Hitung harga z untuk setiap posisi (x,y)
pada permukaan.
b. jika z>depth (x,y), masukkan depth (x,y)
= z dan refresh (x,y) = i, dimana i adalah harga dari intensitas pada posisi
(x,y) di atas permukaan.
Pada langkah terakhir,
jika z lebih kecil dari harga Depth Buffer untuk posisi tersebut, titik tidak
tampak. Depth Buffer berisi harga z untuk permukaan yang tampak dan Refresh
Buffer berisi hanya harga intensitas.
Alur proses Hidden
Surface Removal dengan menggunakan algoritma Z buffer adalah sebagai berikut
·
Menginisialisasi
isi Buffer
·
Melakukan
uji penampakan keseluruhan bagian permukaan setiap link mulai dari awal link
hingga akhir link sebanyak satu kali
·
Memindahkan/menampilkan seluruh isi Z buffer
2.
Algoritma Scan-Line
Algoritma Scan-Line
digunakan untuk memecahkan masalah penggunaan memori yang besar dengan satu
baris scan untuk memproses semua permukaan objek. Algoritma melakukan scan
dengan arah sumbu y sehingga memotong semua permukaan bidang dengan arah sumbu
x dan z dan membuang garis-garis yang tersembunyi. Pada setiap posisi sepanjang
baris scan, perhitungan kedalaman dibuat untuk setiap permukaan untuk
menentukan mana yang terdekat dari bidang pandang. Ketika permukaan yang tampak
sudah ditentukan, harga intensity dimasukkan ke dalam buffer.
Alur proses algoritma
Scan Line secara garis besar adalah sebagai berikut
·
Menginisialisasi Buffer secara berulang
·
Melakukan scan baris yang diperlukan. Berpindah dari awal link ke akhir
link sebanyak Ymaks – Ymins.
·
Memindahkan/menampilkan isi buffer satu baris secara berulang.
3. Analisis
Dari segi penggunaan memori,
untuk algoritma z buffer, memori yang diperlukan adalah sebesar bidang layar
yang akan digambar dikali dengan besar variabel kedalaman z dan warna. Sebagai
contoh, proses Hiddden Surface removeal dilakukan pada layar dengan bidang
berukuran 640 x 680 pixel. Untuk z buffer diperlukan daerah pada memori dengan
ukuran 640 X 680 * 6 byte sama dengan 1843200 byte (1,8 MB). Sedangkan untuk
scan line memori yang diperlukan adalah sebesar jumlah kolom bidang layar yang
akan digambar dikalikan dengan besar variabel kedalaman dan warna. Untuk buffer
scan depth hanya diperlukan 640*6 = 3840 byte (3,75 Kb). Dengan dimensi yang
sama maka dibutuhkan 640*4 byte (ukuran tiap integer variabel warna) sama
dengan 6400 byte (2,5 Kb). Jadi total hanya membutuhkan 6400 Kb (6,25).
Untuk analisis
perbandingan kecepatan dapat dilihat pada tabl di bawah ini
Tidak ada komentar:
Posting Komentar