Analisis Algoritma Clipping, Rasterization, Dan Hidden Surface Removal
Analisis Algoritma Clipping, Rasterization, dan Hidden Surface Removal
Suci Istachotil Jannahh
5108100131
Kelas C
Suci Istachotil Jannahh
5108100131
Kelas C
ABSTRAK
Di dalam makalah ini terdapat analisis algoritma-algoritma yang terbaik untuk diimplementasikan dalam library OpenGL. Dalam implementasinya untuk sanggup menampilkan suatu objek dari titik-titik kordinat pixel sampai menjadi objek yang siap untuk ditampilkan dengan sempurna, dalam artian kadangkala ketika menampilkan objek tersebut ada sedikit dilema contohnya objek tersebut berpotongan, koordinatnya melebihi batas window. Untuk mengatasinya dibutuhkan algoritma clpping, rasterization, dan Hidden Surface Remove.
Metode clipping yaitu metode yang dipakai untuk menentukan garis yang perlu digambar atau tidak.Alasan dilakukanna clpping yaitu 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 gambaran vektor ke gambaran bitmap. Sedangkan Hidden Surface Removal merupakan suatu algoritma yang dipakai untuk menghilangkan penampilan bab yang tertutup oleh objek di depannya. Apabila ada dua bidang yang berpotongan, jikalau objek tersebut ditampilkan biasa tanpa memakai algoritma Hidden surface removal maka bab 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 mempunyai kelebihan dan kekurangan untuk dianalisis. Contohnya pada algoritma clpping didapatkan algoritma Liang-Barsky yang terbaik alasannya yaitu kecepatan waktu yang efisien dan juga stabil. Untuk metode rasterization didapat algoritma Midpoint yang terbaik alasannya yaitu 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 alasannya yaitu 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 yaitu algoritma scan Line alasannya yaitu pada algoritma ini memakai 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 sanggup terlepas dari pembuatan dan manipulasi gambar (visual) secara digital. Bentuk sederhana dari grafika komputer yaitu grafika komputer 2D yang kemudian bermetamorfosis grafika komputer 3D, pemrosesan gambaran (image processing), dan pengenalan pola (pattern recognition). Grafika komputer sering dikenal juga dengan istilah visualisasi data.
Dalam makalah ini akan dijelaskan tiga metode wacana meningkatkan secara optimal atau gambaran komputer. Metode-metode tersebut yaitu clipping, rasterization, dan hidden surface removal. Ketiga metode ini tentu mempunyai beberapa algoritma yang sanggup dibandingkan algoritma mana yang terbaik. Pada metode clipping dilakukan pemrosesan untuk menentukan bab 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 gambaran vektor ke gambaran 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 yaitu 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 dipakai untuk menghilangkan penampilan bab yang tertutup oleh objek yang didepannya. Apabila ada dua bidang yang berpotongan, apabila ditampilkan biasa tanpa memakai algoritma Hidden surface removal maka bab yang berpotongan itu akan tidak kelihatan. Algoritma Hidden Surface Removal ini perlu dilakukan untuk menampilkan bidang perpotongan tersebut.
Dari beberapa analisis nanti diharapkan mendapat algoritma terbaik dari masing-masing metode yang nantinya akan dipakai untuk pengimplementasian ke dalam library OpenGL.
METODE CLIPPING
Ada beberapa teknik yang sanggup dipakai untuk melaksanakan proses clipping, diantaranya adalah
1. Vertex Clipping
Untuk menentukan letak suatu titik di dalam clipping window sanggup dipakai 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 semoga teknik ini sanggup dijalankan. Jika salah satu tidak terpenuhi maka titik tersebut tidak berada dalam clipping window.
Contoh perkara :
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, sanggup dilihat bahwa titik P2 berada diluar area Clipping Window alasannya yaitu titik P2 koordinat y-nya melebihi Ymax dari clipping window sehingga titik P2 tidak akan ditampilkan.
Metode Clipping titik ini sanggup diaplikasikan pada scene yang menampilkan ledakan atau percikan air pada gelombang bahari yang dibentuk model dengan mendistribusikan beberapa partikel.
2. Line Clipping
Line clipping atau clipping garis diproses dengan inside-outside test dengan menilik endpoint dari garis tersebut. Berdasarkan test tersebut garis sanggup 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 agresi clipping alasannya yaitu pada kondisi invisible, garis tidak perlu ditampilkan sedangkan pada kondisi visible garis sanggup pribadi ditampilkan. Untuk segmen garis dengan endpoint (x1,y1) dan (x2,y2) serta keduanya terletak di luar clipping window mempunyai persamaan,
x = x1 + u(x2 – x1)
y = x1 + u(x2 – x1)
0 ≤ u ≤ 1.
Persamaan tersebut sanggup dipakai untuk mengenali nilaiparameter u untuk koordinat pemotongan dengan batas clipping window.
Secara umum algoritma line clipping sanggup digambarkan sebagai berikut,
Ada beberapa algoritma dalam melaksanakan teknik line clipping, diantaranya yaitu sebagai berikut Cohen – Sutherland, Liang – Barsky, Cyrus – Beck, dan Nicholl – lee – Nicholl. Dan algoritma yang paling populer yaitu 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 sanggup 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 mengambarkan bahwa titik berada pada region yang bersangkutan. Jika tidak maka diset nilai 0.
Algoritma Liang-Barsky
Algoritma ini memakai persamaan parameter garis dan gambaran pertidaksamaan dari range clipping box untuk menentukan titik temu antara garis dan clipping box. Kita harus melaksanakan pengujian sebanyak mungkin sebelum menghitung interseksi garis. Misalnya bentuk parameter biasanya garis lurus
Dan titik akan berada di clipping window jika
dan
Dinyatakan dalam empat pertidaksamaan
dimana
Untuk perhitungannya yaitu sebagai berikut
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 sanggup dieliminasi.
3. 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.
3. Polygon Clipping
Polygon merupakan bidang yang tersusun dari verteks (titik sudut) dan edge (garis penghubung setiap verteks). Untuk sanggup melaksanakan proses clipping pada polygon dibutuhkan algoritma yang lebih kompleks dari kedua teknik clipping yang telah di bahas sebelumnya. Salah satunya yaitu algortima Sutherland-Hodgman. Ide dasarnya yaitu memperhatikan edge pada setiap arah pandang, kemudian clipping polygon dengan persamaan edge kemudian lakukan clipping tersebut pada semua edge sampai polygon terpotong sepenuhnya. Ada beberapa ketentuan dari algoritma Sutherland-Hodgman, diantaranya adalah
1. Polygon sanggup dipotong dengan setiap edge dari window sekali pada suatu waktu
2. Vertex yang telah dipotong akan disimpan untuk kemudian dipakai untuk memotong edge yang masih ada
3. Perhatikan bahwa jumlah vertex biasanya berubah-ubah dan sering bertambah
METODE RASTERIZATION
Rasterization yaitu sebuah proses mengkonversi sebuah penggambaran vertex menjadi sebuah penggambaran pixel. Rasterization juga biasa disebut scan conversion. Algoritma scan conversion memakai metode incremental yang memanfaatkan koherensi. Sebuah metode incremental menghitung sebuah nilai gres dengan cepat dari nilai lama, bukan menghitung nilai gres dari awal yang sanggup memperlambat. Koherensi dalam ruang atau waktu yaitu istilah yang dipakai untuk menawarkan bahwa benda-benda didekatnya (misalnya pixels) mempunyai kualitas yang menyerupai 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 yaitu 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 menawarkan bahwa ini yaitu x dan y clipping window) ke integer. Alamat ini (x,y), menurut 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 nyata 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 dihentikan 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 sentra fragmen raster (ingat bahwa pusat-pusat fragmen terletak pada nilai koordinat jendela half-integer). Jika lebarnya genap maka sentra titik adalah
Pusat fragmen raster yaitu nilai koordinat half-integer window dalam persegi yang berpusat di (x,y).
“Rasterization non-antialiasing. Tanda silang menawarkan sentra 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 kawasan yang berada dalamlingkaran berdiameter sama dengan lebar titik ketika ini dan berpusat pada titik (Xw, Yw). Perhatikan gambar di bawah ini
Pada gambar di atas, titik hitam menawarkan titik yang akan diraster. Daerah gelap mempunyai lebar yang ditentukan. Tanda x menawarkan sentra fragmen yang dihasilkan oleh rasterization. Perhitungan fragmen didasarkan pada bab 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 perkara dimana memodifikasi untuk segmen y-major yang sudah jelas.
Idelanya, GL memakai hukum ‘diamond-exit’ untuk menentukan fragmen yang diproduksi oleh rasterization segmen garis. Untuk setiap fragmen f dengan sentra di window koordinat x dan y mendifinisikan wilayah berbentuk ‘diamond’ yang merupakan intersection empat half plan.
Ketika Pa dan Pb berada di sentra fragmen, karakterissasi fragmen mengurasi untuk algoritma Bresenham dengan satu modifikasi. Hasil baris dalam deskripsi ini yaitu ‘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 lingkaran (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 yaitu y = mx + b dan m = (y2-y1)/(x2-x1) dan intersep y yaitu 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 menentukan NE atau E yaitu dengan menghitung di mana sisi garis M terletak. y = dy/dx * x + b
Oleh alasannya yaitu 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 yaitu untuk menentukan apakah poligon back facing atau front facing. Aturan untuk menetukan fragmen yang dihasilkan oleh rasterization disebut titik sampling. Fragmen sentra 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 yaitu 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 sanggup digunakan. Yang pertama yaitu 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 yaitu dengan winding rule yang berorientasi garis.
Perbedaan even-odd rule dan winding rule :
Perbedaan hanya terdapat di interseksi polygon itu sendiri
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 sentra fragmen mungkin dipakai 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 akrab 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 bab permukaan objek menurut posisi z yang paling akrab dengan bidang pandang dengan proyeksi orthogonal atau proyeksi tegak lurus.
Pada gambar 1 menunjukkan tiga permukaan bidang pada banyak sekali kedalaman z dengan posisi (x,y) yang sama untuk setiap permukaan. Sedangkan pada gambar 2 sanggup 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 yaitu 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. jikalau z>depth (x,y), masukkan depth (x,y) = z dan refresh (x,y) = i, dimana i yaitu harga dari intensitas pada posisi (x,y) di atas permukaan.
Pada langkah terakhir, jikalau 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 memakai algoritma Z buffer yaitu sebagai berikut
· Menginisialisasi isi Buffer
· Melakukan uji penampakan keseluruhan bab permukaan setiap link mulai dari awal link sampai selesai link sebanyak satu kali
· Memindahkan/menampilkan seluruh isi Z buffer
2. Algoritma Scan-Line
Algoritma Scan-Line dipakai untuk memecahkan dilema penggunaan memori yang besar dengan satu baris scan untuk memproses semua permukaan objek. Algoritma melaksanakan 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 dibentuk 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 yaitu sebagai berikut
· Menginisialisasi Buffer secara berulang
· Melakukan scan baris yang diperlukan. Berpindah dari awal link ke selesai link sebanyak Ymaks – Ymins.
· Memindahkan/menampilkan isi buffer satu baris secara berulang.
3. Analisis
Dari segi penggunaan memori, untuk algoritma z buffer, memori yang dibutuhkan yaitu 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 dibutuhkan kawasan pada memori dengan ukuran 640 X 680 * 6 byte sama dengan 1843200 byte (1,8 MB). Sedangkan untuk scan line memori yang dibutuhkan yaitu sebesar jumlah kolom bidang layar yang akan digambar dikalikan dengan besar variabel kedalaman dan warna. Untuk buffer scan depth hanya dibutuhkan 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). Makara total hanya membutuhkan 6400 Kb (6,25).
Untuk analisis perbandingan kecepatan sanggup dilihat pada tabl di bawah ini
DAFTAR PUSTAKA
http://caig.cs.nctu.edu.tw/course/CG2007/slides/raster.pdf
http://www.opengl.org/documentation/specs/version1.1/glspec1.1/node41.html
http://reference.findtarget.com/search/Hidden%20surface%20determination/
http://cs.fit.edu/ wds/classes/graphics/Rasterize/rasterize/rasterize.html
http://en.wikipedia.org/wiki/Rasterisation
http://meilgrafico.wordpress.com/2010/10/30/computer-graphics-clipping-algoritm/
Diktat Kuliah Grafika Komputer BAB IV Clipping