Analisis Algoritma Clipping, Rasterization, dan Hidden Surface Removal



Analisis Algoritma Clipping, Rasterization, dan Hidden Surface Removal

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 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.

1. 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.

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.











download makalah

1 komentar:

Unknown mengatakan...

thx's ya kaka

Posting Komentar