poli gon

Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000

Author: Suryana Setiawan, MSc 1

Primitif Grafika Poligon

Poligon adalah sederetan garis lurus (polyline) yang sambung-menyambung secara siklik sehinggamelingkupi suatu area. Garis-garis tersebut kita sebut garis tepi (edge). Titik pertemuan setiap pasangsisi kita sebut verteks. Dalam representasinya biasanya suatu poligon dinyatakan dengan koordinatverteks-verteks ini dan penggambaran tepi-tepi poligon dilakukan dengan penggambaran setiap garisantara dua verteks bertuturan dengan algoritma yang sudah dibahas. Untuk kasus di mana piksel-pikseldi dalam area poligon perlu di-"warna"-i maka kita perlu mengenal algoritma pengisian poligon berikutini.

Ide dasarApa bila kita mengenahui adanya suatu piksel yang berada dalam area poligon maka piksel-piksel laindapat dengan mudah dicapai dari piksel ini dengan suatu algoritma rekursif. Namun secara umum halitu tidak selalu bisa terjadi. Algoritma Scanline memecahkan masalah ini dengan melakukan• Scan secara horisontal dari kiri ke kanan: mendapatkan titik-titik perpotongan dengan tepi-tepi

poligon, mengurutkannya dari kiri ke kanan (menurut harga absis) kemudian memberi warnapiksel-piksel di antara dua pasang urutan ganjil-genal titik potong tsb.

• Hal tersebut dilakukan berulang dari yang paling bawah (harga ordinat verteks terkecil) ke yangpaling atas (harga ordinat verteks terbesar).

Kerangka Algoritmamencari ordinat tekecil dan terbesar dalam ymin dan ymax// inisialisasi mencari ymin dan ymax...for (yi = ymin; yi <= ymax; yi++) { //mencari titik potong

... //mengurutkan horisontal dari kiri ke kanan p1, p2, … , pn

... //untuk setiap pasang pi & pi+1 (i=ganjil) plot di antaranya

...}

Masalah Garis Tepi HorisontalDalam algoritma ini jika suatu garis tepi diketahui horisontal (kedua ordinatnya sama) maka garis inibisa diabaikan.

Kasus Titik Ujung Garis TepiJika suatu garis scan melintasi suatu titik pertemuan dua garis tepi (atau verteks) maka akan ada duatitik potong disitu. Kita perlu membedakan kasus di mana kedua titik potong tersebut hanya dianggapsatu titik potong atau tetap dua potong. Kita jadikan hanya satu titik potong jika kedua ruas garis

A

E

D

C

B

Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000

Author: Suryana Setiawan, MSc 2

tersebut berarah sama seperti pada garis BC dan DE. Sementara itu, tetap dua titik potong jika keduaruas garis tersebut berlawanan arah seperti garis DE dan EA. Jika salah satunya garis horisontal makaini tidak akan bermasalah karena sudah diabaikan sebelumnya.

Efisiensi Algoritma• Pencarian titik potong merupakan proses yang bisa diefisienkan memanfaatkan sifat koherensi

inkremental. Jika xi adalah absis titik potong suatu tepi antara (xA, yA) dan (xB, yB) pada garis scanke i maka pada garis scan ke i+1 adalah xi+1 = xi + dx dengan dx = (xB - xA)/(yB - yA). Sebelumiterasi maka x = xA (asumsi yA < yB).

• Selain itu titik potong baru akan ada jika garis scan yi berharga antara yA dan yB. Dalam hal yA < yB,dan yi < yA maka tidak ada titik potong. Kemudian setelah yi ≥ yA suatu counter yang menghitungmundur bisa digunakan untuk memeriksa apakah masih terdapat titik potong atau tidak. Sebelumiterasi dilakukan inisialisasi counter = (yB - yA + 1).

• Masalah kedua kasus verteks di atas dengan mudah ditangani dengan mengurangi counter ini jikaberarah sama.

Tabel Garis TepiDengan demikian perlu suatu tabel yang menyimpan informasi masing-masing garis tepi ini yangsebelum iterasi diinisialisasi sbb:

private InfoTepi [] tabelTepi = new InfoTepi[nTepi];

private class InfoTepi { int counter; double x,dx; int yAwal; void InfoTepi(int x1, int y1, int x2, int y2){ dx = (y2-y1)/(x2-x1); if (y1 < y2) { x = x1; yAwal = y1; counter = y2-y1+1; } else { x = x2; yAwal = y2; counter = y1-y2+1; } } void updateTepi() { counter--; x += dx; }}

Pengurutan Horisontal & Plot PixelSuatu array diperlukan untuk mencatat dan mengurutkan absis dari titik-titik potong yang terjadi padagaris scan yang sedang berlangsung berdasarkan tabel tepi tersebut. Tahapannya sebagai berikut: (1)memeriksa setiap tepi pada tabel apakah berpotongan dengan garis scan, kemudian (2) jikaberpotongan maka harga x. Kemudian meplot pixel-pixel antara setiap pasangan. Code untuk proses iniadalah sbb.

// memeriksa crossdouble []cross = new double[nTepi];int p = 0;for (int i=0; i < nTepi; i++) { if (tabelTepi[i].yAwal >= yi && tableTepi[I].counter > 0) {

Diktat Kuliah Grafika Komputer Fakultas Ilmu Komputer Universitas Indonesia Semester II 1999/2000

Author: Suryana Setiawan, MSc 3

// jika berpotongan maka harga x cross [p] = tabelTepi[i].x; p++; }}// mengurutkan dengan algoritma sorting apa saja p data terkiricross = Sort(cross, p);

// plot antara setiap pasanganfor (int i=0; i < p; i += 2) { drawLine(round(cross [i]), yi, round(cross [I+1]), yi);}