Output primitif adalah struktur
dasar geometri yang paling sederhana dari gambar grafika komputer. Titik dan
garis adalah contoh
dari output
primitif yang dapat digunakan untuk membentuk gambar, misalnya lingkaran,
kerucut, permukaan berbentuk persegi, kurva dan permukaan berbentuk lengkung,
warna area dan karakter, dan lain-lain. Gambar-gambar seperti rumah, tembok,
gedung dan lain-lain merupakan obyek yang lengkap yang ditempatkan pada
koordinat tertentu pada layar, dimana obyek-obyek tadi sebenarnya tersusun dari
kumpulan titik dan garis sebagai penyusunnya.
2.1 Piksel (Picture Element)
Piksel adalah elemen gambar terkecil berupa sebuah titik yang
ditempatkan dilayar.
 |
Gambar menunjukkan sebuah piksel mempunyai koordinat (2,3) pada layar. Jumlah
Piksel untuk setiap gambar tergantung dari kemampuan Graphics card. Terdapat beberapa tampilan format gambar:
|
Standart
|
x-maksimal
|
y-maksimal
|
Jumlah keseluruhan Piksel
|
|
VGA
SVGA
XGA
SXGA
|
640
800
1024
1280
|
480
600
768
1024
|
307 200
480 000
786 432
1 228 800
|
Sebagai pembanding adalah tayangan televisi standart dengan jumlah titik
gambar sebesar 400.000 Piksel. Bandingkan dengan WebCam standar VGA dan juga
dengan HP yang memiliki fasilitas perekam 2 Mega Piksel.
Resolusi Piksel adalah jumlah piksel persatuan panjang.
Jika layar mempunyai dimensi p
inchi sepanjang x dan q inchi
sepanjang y, maka :
N/P /
M/P = N/M
resolusi-x = 
piksel/inchi
(ppi) (2-1)
piksel/inchi
(ppi) (2-1)
resolusi-y = 
piksel/inchi (ppi) (2-2)
piksel/inchi (ppi) (2-2)
Aspek rasio = N/M = 
(2-3)
(2-3)
Frame buffer adalah area memory
tempat informasi gambar disimpan. Jika
system mempunyai n bit memori untuk
tiap-tiap piksel, maka ukuran frame
buffer adalah = MNn/8
byte. Jumlah warna yang bisa
ditampilkan secara bersama-sama dilayar adalah 2n. Sistem dikatakan mempunyai n
bit planes.
|
Screen Mode
|
Piksels
|
Screen Ratio
|
Bit planes
|
Colors
|
Memory
|
|
CGA(med res)
|
320x200
|
4:3
|
2
|
4
|
16K
|
|
CGA(high res)
|
640x200
|
4:3
|
1
|
1
|
16K
|
|
EGA
|
640x350
|
4:3
|
4
|
16
|
112K
|
|
VGA
|
640x480
|
4:3
|
8
|
256
|
307K
|
|
Super VGA-1
|
800x600
|
4:3
|
24
|
16.7M
|
1.5M
|
|
Super VGA-2
|
1024x768
|
4:3
|
16
|
65K
|
1.6M
|
Atribut dari piksel
adalah warnanya (indeks warna) i,
dimana 0 £
i £ 2n. Biasanya indeks warna yang bernilai 0 melambangkan
warna hitam.
Monitor
monokrom yang mempunyai satu bit plane hanya bisa menampilkan dua
warna, yaitu warna hitam (0) sebagai backgrounddan warna putih (1)sebagai
foreground. Monitor monokrom yang mempunyai 8 bit
plane bisa menampilkan 256 warna yang berbeda, yang disebut dengan
grayscale dengan indeks warna dimulai dari 0 (hitam) sampai dengan 255 (putih).
Contoh 2.1
Diketahui sebuah sistem dengan 1280 X 1024 frame
buffer, mempunyai 4 bits per piksel. jika sistem tersebut dapat mentransfer
data 104 bits per detik, berapa lama waktu yang dibutuhkan untuk
loading ?
Jawab:
Jumlah piksel pada frame
buffer = 1280 x 1024 = 1310720 piksel
Jumlah bit pada frame buffer
= 1310720 piksel x 4 bit /piksel =
5242880 bit
Waktu loadingnya = 
2.2 Warna
Sudah dikatakan diatas bahwa
warna merupakan atribut dari piksel. Selain piksel, yang lebih penting
diperhitungkan lagi adalah warna dari piksel itu sendiri. Setiap piksel mengandung informasi mengenai warna
dengan jumlah yang beragam. Pada awalnya saat teknik penggambaran belum begitu
maju, hanya disediakan 16 kemungkinan warna setiap Pikselnya. Tetapi Graphics card sekarang ini sudah mampu
menampilkan gambar dengan berbagai macam kedalaman seperti pada tabel dibawah
ini:
|
Jumlah Byte setiap Piksel
|
Jumlah tampilan warna
|
Color Quality
|
|
1 (8 bit)
2 (16 bit)
3 (24 bit)
4 (32 bit)
|
256
65 536
16 777 216
4 294 967 296
|
Low
Medium
High
Highest
|
Untuk menampilkan suatu gambar
pada layar monitor sering kali tidak cukup hanya dengan 256 tampilan warna.
Tetapi jika jumlah tampilan warna diperbesar maka memerlukan ruang (memori)
lebih banyak lagi. Lihat tabel kebutuhan memori di bawah ini:
|
x/y-Format
|
1 B / Piksel
|
2 B / Piksel
|
3 B / Piksel
|
4 B / Piksel
|
|
640 x 480
800 x 600
1024 x 768
1280 x 1024
|
300 kB
469 kB
768 kB
1311 kB
|
600 kB
938 kB
1536 kB
2622 kB
|
900 kB
1406 kB
2304 kB
3933 kB
|
1200 kB
1876 kB
3072 kB
5244 kB
|
Untuk menampilkan gambar pada
layar monitor tabung sehingga tanpa efek kerdipan (flicker-free) diperlukan
pengulangan tayang sebanyak 75 kali dalam satu detik.
Abel
pembanding layar monitor
|
Televisi standar
|
Gambar komputer
(600 x 800 x 3
Byte)
|
Photo-CD
|
|
800 kilo Byte
|
1.5 Mega Byte
|
20 Mega Byte
|
2.3 Algoritma Pembentuk Garis
Software untuk menggambar garis
lurus pada setiap paket grafika komputer secara tradisi sebagai fungsi
elementarnya sudah tersedia, tetapi ada baiknya kita simak lebih seksama
bagaimana algoritma sebagai dasar penggambaran titik-titik pada raster graphics. Raster graphics diartikan sebagai grafik yang dibangun
atas dasar titik-titik pada kolom dan baris yang juga mengandung informasi
warna. Gambar 2.2 adalah sebuah garis lurus yang melalui titik (x1,y1) dan (x2,y2).
 |
Gambar 2.2: Garis lurus yang melalui titik
P1(x1,y1)
dan P2(x2,y2)
Secara umum garis lurus dinyatakan dalam
persamaan :
y = mx + c (2-4)
dimana : m adalah gradient dan c
adalah konstanta.
Bila garis melalui titik (x1,
y1) dan titik
(x2, y2) maka gradien m dihitung
menggunakan persamaan (2-5)
 |
(2-5)
Persamaan garis bergradien m yang melewati titik (x1, y1)
adalah
 |
(2.6)
Berdasarkan persamaan (2-4), garis yang melalui titik (x1, y1) dan titik
(x2, y2) dapat ditulis sebagai berikut
 |
atau
 |
atau
(2-7)
bila ∆x = 1, maka persamaan (2-7) menjadi
(2-8)
Algoritma untuk menggambar garis pada komputer didasarkan pada persamaan
(2-6) dan (2-8).
Tugas dari
algoritma pembentuk garis adalah menentukan titik-titik diantara dua titik
ujung (x1,y1) dan (x2,y2) yang akan
digambar sebagai garis.
Kriteria
algoritma pembentuk garis yang baik:
1. Garis antara
dua titik ujung tersebut sebisa mungkin harus lurus
2. Kerapatan
titik-titik konstan (tidak ada gap antara dua titik yang bersebelahan)
3. Kerapatan
titik-titik tidak tergantung pada kemiringan garis
4. Waktu proses
algoritma harus cepat
2.3.1 Algoritma
Brute
Force Untuk Membentuk Garis
Algoritma brute force untuk membentuk garis didasarkan pada persamaan (2-6),
yaitu :
1. Tentukan
dua titik ujung (x1,y1)
dan (x2,y2)
2. Jika x1
= x2 (garis vertikal),
maka
(a) y = y
+ 1 dan x tetap
(b)
gambar titik (x,y) di layar
(c)
Selesai
3. Jika y1 = y2 (garis horisontal), maka
(a) x = x
+ 1 dan y tetap
(b)
gambar titik (x,y) di layar
(c)
Selesai
{anggap x2 > x1 , (jika sebaliknya, gantilah x2 dengan x1
)}
4. Hitung
kemiringan garis m =
(y2 − y1)/( x2 − x1)
5. N = x2 + x1 −1
6. x = x1
7. Ulang
sebanyak N kali:
(a)
(b) lakukan pembulatan ya = Round(y),
(c) gambar titik (x,ya) di layar
(d) x = x + 1
8. selesai
Perhatikan langkah 7(b), karena
posisi piksel adalah integer (bilangan bulat), dan nilai gradien m biasanya pecahan, maka nilai y adalah bilangan pecahan, sehingga kita perlu melakukan pembulatan terhadap nilai y. Perhatikan Gambar 2.3 berikut.
Gambar 2.3: Pembulatan nilai y dilakukan karena posisi piksel adalah
bulat (integer)
Kelemahan algoritma Brute Force :
Algoritma ini terlalu lambat karena: pada setiap iterasi terdapat perkalian
bilangan pecahan (floating point),
penjumlahan bilangan pecahan, dan proses pembulatan angka pecahan menjadi bulat
(integer).
DDA adalah algoritma pembentukan garis berdasarkan perasamaan (2-8). Garis
dibuat menggunakan titik awal (x1, y1) dan
titik akhir (x2, y2). Setiap koordinat
titik (xk, yk) yang membentuk garis diperoleh
dari perhitungan, kemudian hasil perhitungan dikonversikan menjadi nilai
integer. Berikut adalah langkah-langkah pembentukan garis berdasarkan algoritma
DDA:
===================================================================
1. Tentukan dua titik yang akan
dihubungkan dalam pembentukan garis.
2. Tentukan salah satunya sebagai
titik awal (x1, y1) dan yang lain sebagai titik
akhir (x2, y2).
3. Hitung : dx = x2
− x1 dan dy = y2 − y1
4. Tentukan step, dengan
ketentuan berikut:
- bila |dx|
> |dy| maka step = |dx|
- bila
tidak, maka step = |dy|
5. Hitung penambahan koordinat piksel
dengan persamaan:
x_inc
= dx / step
y_inc = dy / step
6. Koordinat selanjutnya :
x = x + x_inc y
= y + y_inc
7. Lakukan pembulatan u = Round(x), v = Round(x), kemudian plot piksel (u, v) pada layar
8. Ulangi point 6 dan 7 untuk menentukan
posisi piksel berikutnya sampai x = x2 atau y = y2.
•
Algoritma
DDA lebih cepat dibanding dengan algoritma Brute Forse dan baik digunakan untuk
|m|<=1, untuk kemiringan
garis m > 1, tukarlah x dengan y sudah tidak terjadi gap
antara titik yang satu dengan yang lain.
Kelemahan Algoritma DDA
•
Prosedur untuk menggambar garis masih menggunakan
fungsi pembulatan x maupun y, sehingga memerlukan waktu.
•
variabel x, y maupun m
memerlukan bilangan real karena
kemiringan merupakan nilai pecahan.
2.3.3 Algoritma Bressenham
Algoritma garis Bressenham disebut juga Midpoint Line Algorithm.
Algoritma temuannya tidak lagi menggunakan floating point arihtmetic, sehingga tidak perlu membulatkan nilai
posisi piksel setiap waktu dan dalam
pengulangan (looping) hanya
menggunakan pengoperasian incremental. Algoritma ini hampir dapat dipergunakan
dan diimplementasikan pada semua hardware dan software untuk keperluan
penggambaran garis. Algoritma
Bressenham dapat memperbaiki
pengendalian plotter, sehingga dia mendapatkan hak paten. Algoritma ini hanya berlaku untuk nilai kemiringan garis : 0 < m < 1.
Perhatikan Gambar 2.7. Misalkan kemiringan garis m, yang besarnya adalah 0 < m < 1, titik awal garis di (x0, y0) dan titik akhir garis di (x1, y1).
Anggap posisi titik sekarang (xp, yp) dan sekarang kita harus memilih antara titik E
(East) atau NE (Northeast). Misalkan Q adalah titik potong garis dengan garis x = xp+1, dan M
adalah titik tengah antara E dan NE. Jika titik tengah M terletak diatas garis,
E dipilih, tetapi jika titik tengah M terletak dibawah garis, NE dipilih.
Gambar 2.7: Garis mempunyai kemiringan 0 < m < 1, pada titik x = xp+1, garis
berada diantara dua titik E dan NE yang mempunyai titik tengah di M.
Dalam hal ini kita harus
menentukan apakah garis berada diatas titik tengah M atau dibawah titik tengah
M. Untuk melakukan ini, kita amati bahwa setiap garis bisa dinyatakan sebagai
berikut
F(x, y) = ax + by + c = 0
Hitung: dy = y1 – y0 dan dx
= x1 – x0, maka garis juga bisa
ditulis sebagai
y = mx
+ B = (dy/dx) x + B
atau
(dy/dx)
x – y + B = 0
Kalikan dengan dx
menjadi
(dy)x – (dx)y
+ (dx)B = 0
Diperoleh a
= dy, b = −dx
dan c = (dx)B.
- Jika F(x, y) = 0, maka (x, y) terletak pada garis
- Jika F(x, y) > 0, maka (x, y) terletak dibawah garis
- jika F(x, y) < 0, maka (x, y) terletak diatas garis
Untuk menerapkan kriteria midpoint, kita hitung:
F(M) = F(xp + 1, yp + ½) = a (xp + 1) + b (yp
+ ½) + c
Dan menguji tanda dari
d = F(M).
- Jika d >0, M terletak dibawah garis, maka NE dipilih.
- Jika d = 0, pilih E ( sebenarnya memilih NE juga bisa)
- Jika d < 0, M terletak diatas garis, maka E dipilih.
Misalkan E dipilih, M bertambah satu langkah dalam arah x, dan kita mempunyai d
baru misalnya dbaru.
dbaru
= F(xp + 2, yp + ½) = a (xp
+ 2) + b (yp + ½) + c
dlama
= F(xp + 1, yp + ½) = a (xp
+ 1) + b (yp + ½) + c
jadi dbaru
– dlama = a = dy.
Jadi setelah E dipilih, pertambahan untuk mendapatkan d yang baru adalah a = dy.
Misalkan NE dipilih, M adalah pertambahan satu langkah
kearah x dan y sehingga
dbaru = F(xp + 2, yp + 3/2) = a
(xp + 2) + b (yp
+3/2) + c
dlama = F(xp + 1, yp + ½) = a (xp + 1) + b (yp
+ ½) + c
jadi dbaru – dlama = a + b = dy – dx.
Untuk memulai algoritma, titik awal adalah (xp , yp ) = (x0, y0). Untuk menghitung nilai d yang pertama untuk memulai algoritma, midpoint pertama adalah (x0 + 1, y0 + ½) dan
F(M) = F(x0 + 1, y0 + ½) = a (x0 + 1) + b (y0
+ ½)+ c
=
ax0 + by0 + c + a + b/2
=
0 + a + b/2 karena (x0, y0) terletak pada garis.
Jadi kita mulai dari d
= a + b/2 = dy – dx/2
Untuk menghilangkan pecahan, definisikan F dengan mengalikan
2, diperoleh
F(x,y) = 2 (ax + by + c) = 0.
Definisi ini akan menyebabkan nilai d menjadi d =
2dy
– dx
Dengan begini algoritma midpoint Bresenham (untuk kemiringan 0 <
m < 1) adalah :
1. Tentukan dua titik yang akan
dihubungkan dalam pembentukan garis.
2. Tentukan salah satu sebagai
titik awal (x0, y0) dan titik akhir (x1,
y1).
3. Hitung dx, dy, 2dy dan 2dy − 2dx
4.
Hitung parameter : po = 2dy − dx
5. Untuk setiap xk sepanjang jalur
garis, dimulai dengan k = 0
- bila pk < 0 maka titik selanjutnya adalah:
(xk+1, yk) dan pk+1
= pk + 2dy
- bila
tidak, titik selanjutnya adalah:
(xk+1, yk+1) dan pk+1
= pk + 2dy – 2dx
6. Ulangi nomor 5 untuk menentukan
posisi piksel berikutnya, sampai
x = x1 atau y
= y1.
2.4 Algoritma Pembentuk Lingkaran
Persamaan umum
lingkaran dengan pusat lingkaran (xp,
yp) dan jari-jari r adalah:
 |
(2-9)
Atau
 |
(2-10)
Untuk menggambar
piksel-piksel dalam kurva lingkaran, dapat digunakan sumbu x dari x = (xp-r) sampai x = (xp+r) sebagai parameter dan sumbu y
sebagai hasil dari persamaan (2-10). Algoritma ini memerlukan
waktu operasi yang besar, karena mengandung operasi perkalian dua bilangan integer,
membutuhkan fungsi SQRT (untuk menghitung akar suatu bilangan) dan fungsi ROUND
(untuk membulatkan bilangan pecahan menjadi bilangan integer), dan menghasilkan
posisi koordinat piksel yang tidak merata, karena terjadinya gaps yang
disebabkan
adanya perubahan gradient
seperti tampak pada gambar 2.9.
Gambar 2.9:
Untuk menghindari posisi
koordinat piksel yang tidak merata, koordinat piksel (x,y) dinyatakan dengan menggunakan koordinat polar dalam persamaan
(2-11)
dan 
(2-11)
Akan tetapi penggambaran
lingkaran menggunakan persamaan (2-11) memerlukan waktu operasi yang besar karena
mengandung operasi perkalian bilangan riel, perhitungan trigonometri, dan
membutuhkan banyak segmen garis.
2.4.1 Simetris Delapan Titik
Pembuatan kurva
lingkaran dapat dilakukan dengan menentukan titik awal (x,y), maka delapan titik dapat ditentukan sebagai berikut :
(x,y),
(−x,y), (x, −y), (−x, −y), (y,x), (−y,x),
(y, −x),
(−y, −x)
Dengan
demikian sebenarnya hanya diperlukan
untuk menghitung segmen 45° dalam menentukan lingkaran
selengkapnya.
 |
Gambar 2.10: Delapan titik simetris pada lingkaran
2.4.2 Algoritma Lingkaran
Midpoint
Algoritma lingkaran midpoint juga disebut algoritma lingkaran Bressenham.
Pembentukan semua titik berdasarkan titik pusat dengan penambahan semua jalur
di sekeliling lingkaran. Komputasi untuk membuat kurva lingkaran dimulai dengan
mengidentifikasi bagian-bagian dari lingkaran yang dapat ditentukan dengan
menggunakan sifat simetri, hal ini dilakukan dengan cara membagai lingkaran
dengan masing-masing mempunyai sudut sebesar 45° , sehingga dalam sebuah
lingkaran dibagi menjadi 8 bagian. Perhatikan Gambar 2.11.
Gambar 2.11: garis lingkaran
berada diantara titik (xk+1,
yk) dan (xk+1, yk −
1)
Anggap bahwa kita mempunyai titik (xk, yk).
Selanjutnya adalah memilih titik (xk+1, yk)
atau (xk+1, yk − 1) yang paling
mendekati lingkaran. Persamaan untuk lingkaran
 |
Sehingga
 |
Untuk memilih titik (xk+1,
yk) atau (xk+1, yk − 1)
yang paling mendekati lingkaran, kriteria yang digunakan adalah titik tengah (xk+1,
yk − ½ ) yaitu
 |
Jika pk< 0 titik
tengah berada didalam lingkaran, maka titik (xk+1,
yk) dipilih.
Jika pk> 0 titik
tengah berada diluar lingkaran, maka titik (xk+1,
yk − 1) dipilih.
Hitung
 |
Atau
 |
Dimana yk+1
adalah yk atau yk-1 tergantung tanda dari pk. Dalam
hal ini kriteria pertama yang dihitung adalah
 |
Jika jari-jari lingkaran bernilai integer (bilangan bulat), kita bisa
membulatkan nilai p0 menjadi berikut
Kemudian jika pk < 0 maka:
 |
Jika pk > 0 maka:
 |
•
Langkah-langkah
Algoritma Lingkaran Midpoint adalah:
- Tentukan jari-jari r dan pusat lingkaran (xp, yp), kemudian setting sedemikian rupa sehingga titik awal berada pada: (x0, y0) = (0 , r)
- Hitung nilai parameter :
 |
Jika jari-jari r pecahan
|
Jika jari-jari r bulat
3. Untuk setiap posisi xk, dimulai
dengan k = 0 berlaku ketentuan:
- bila pk
< 0 maka titik selanjutnya
adalah (xk+1, yk) dan pk+1
= pk + 2 xk+1 + 1
- bila tidak, titik selanjutnya adalah (xk+1,
yk - 1)
dan pk+1 = pk
+ 2 xk+1 + 1 – 2 yk+1
- Tentukan titik simetris pada ketujuh oktan yang lain
- Gerakan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (xp, yp) dan plot nilai koordinat : x = x + xp, y = y + yp
6. Ulangi
langkah 3 sampai dengan 5 hingga x ≥ y
2.5 Area Filling
Dalam grafis, selain dibutuhkan primitif-primitif grafis, dibutuhkan juga
warna untuk mempercantik tampilan dari output primitif tersebut. Khusus untuk
output primitif yang memiliki hole,
maka diperlukan algoritma khusus untuk mengisi warna pada hole tersebut. Teknik atau algoritma
untuk pengisian warna pada hole disebut
area filling. Ada dua macam dasar
pendekatan area filling pada sistem
raster yaitu :
— Scan-Line
Fill Algorithm untuk Polygon
Pengisian warna yang
paling mudah dilakukan adalah polygon, karena masing-masing titik potong
scan-line dengan batas polygon diperoleh dengan cara menyelesaikan sepasang
persamaan linier secara bersamaan, dimana
persamaan untuk scan-line adalah sederhana yaitu y = konstan. Pertama
menentukan titik potong antara batas polygon dengan screen scan line. Kemudian
mengisi warna piksel-piksel pada scan-line yang terletak didalam polygon. Dimulai
dari kiri atas layar, kemudian bergerak ke kanan hingga batas kanan layar. Ulangi
untuk baris-baris berikutnya. Jika ditemukan batas polygon, maka piksel diberi
warna tertentu, hingga ditemukan batas polygon berikutnya. Untuk mengetahui
piksel tersebut terletak didalam polygon atau diluar polygon digunakan Inside-Outside test.
·
Inside-Outside
test
Berbagai proses grafis
seringkali memerlukan cara untuk mengidentifikasi bagian dalam dari sebuah
obyek. Identifikasi obyek sederhana seperti convex polygon, lingkaran, atau
ellip sangat mudah dilakukan secara langsung. Tetapi untuk obyek-obyek yang
sangat kompleks hal ini sangat sulit dilakukan. Sebagai contoh perhatikan
gambar 2.11 berikut
Gambar
2.11: Obyek berupa polygon yang saling berpotongan kompleks hendak ditentukan
bagian interior dan bagian exteriornya.
Untuk mengidentifikasi
bagaian interior dan bagian exteriornya digunakan aturan ganjil-genap yang
biasa disebut sebagai odd-even rule atau odd parity rule. Caranya adalah menggambar garis dari posisi P ke titik
dengan jarak tertentu di luar koordinat objek. Kemudian menghitung jumlah edge
poligon yang berpotongan dengan garis.
•
Jika sisi
poligon yang berpotongan dengan garis jumlahnya ganjil maka P berada di bagian
dalam (interior).
•
Jika sisi
poligon yang berpotongan dengan garis jumlahnya genap maka P berada di bagian
luar (exterior).
Karena area dengan batas-batas berupa kurva
merupakan persamaan non-linier, maka scan-line fill untuk area seperti ini
lebih sulit dilakukan dibanding polygon. Kita tidak bisa menggunakan cara yang
sama seperti pada polygon, karena perhitungan titik potong antara batas area dengan screen scan line dilakukan dengan
persamaan kurva dan kemiringan batas area secara berubah kontinu, sehingga
sangat sulit ditentukan. Karena itu pendekatan yang digunakan untuk pengisian
warna adalah posisi dimulai dari piksel bagian dalam area dan memberi warna
piksel demi piksel sampai batas area. Metode ini memerlukan input berupa posisi
awal dari piksel yang berada didalam area untuk diwarnai dan beberapa informasi
warna untuk piksel yang berada didalam area dan diluar area.
Jika batas dari beberapa wilayah sudah ditentukan
mempunyai warna tunggal, kita bisa mengisi warna bagian dalam wilayah tersebut
piksel demi piksel sampai ditemukan warna batas wilayah tadi. Metode ini
disebut Boundary-Fill Algorithm. Dengan teknik ini pengisian warna dimulai
dari sebuah titik yang berada didalam wilayah (x,y) dan menguji warna piksel dari titik tetangganya. Ada 2
metoda untuk menguji titik tetangga :
— 4
tetangga, menguji titik yang berada diatas, bawah, kanan dan kiri
— 8
tetangga, menguji titik yang berada diatas, bawah, kanan, kiri, pojok kiri
atas, pojok kiri bawah, pojok kanan atas dan pojok kanan bawah.
a) 4- tetangga
b) 8-tetangga
2.5.1 Scan
Line Polygon Fill Algorithms
1. tentukan
kumpulan titik-titik sebagai pembentuk poligon.
2. Ulangi
untuk semua sisi poligon
(a) tentukan
dua titik (x1, y1) – (x2, y2)
sebagai pembentuk sisi-sisi poligon
(b) tentukan
Ymin, Ymax, Xmin, Xmax
(c) Hitung
1/m = (x2 – x1)/(y2 – y1)
(d) Untuk
y = Ymin sampai dengan
y = Ymax , lakukan
y = y
+ 1
x = x +
1/m
lakukan pembulatan untuk x
3. Buatlah tabel scan dimulai dari nilai y terkecil hingga y terbesar untuk menentukan pasangan (x1 – x2)
4. Warnai dengan warna tertentu piksel-piksel
yang terletak diantara titik (x1
– x2)
5. selesai
2.5.2 Boundary Fill Algorithm
Prosedur boundary-fill menerima
tiga parameter yaitu: koordinat titik (x,y),
warna isi dan warna garis batas. Proses pengisian warna tertentu dimulai dari
titik (x,y), kemudian memeriksa
posisi titik tetangganya, apakah titik tetangga tersebut memiliki warna batas:
o
Jika
tidak, warnai titik tersebut dengan
warna tertentu.
o
Selanjutnya periksa lagi posisi dan warna
titik tetangganya.
o
Proses
diulangi terus hingga seluruh titik pada area pengisian telah diuji.
2.5.3 Flood-Fill Algorithm
Terkadang kita ingin mewarnai ( atau memberi warna
yang baru) pada sebuah area yang mempunyai warna lebih dari satu. Perhatikan
gambar 2.12 berikut
 |
Gambar 2.12: penggantian warna obyek menggunakan Flood-Fill Algorithm . (a) lingkaran berwarna merah, segitiga berwarna
hijau dan persegi berwarna biru. Obyek tersebut warnanya diubah menjadi (b)
lingkaran berwarna abu-abu, segitiga berwarna kuning dan persegi berwarna
coklat
Algoritma ini dimulai dari titik yang berada
didalam area (x,y) dan mengganti
semua pikselnya dengan warna baru sehingga bagian dalam area mempunyai warna
yang sama. Pengujian titiktetangga bisa menggunakan 4-tetangga atau 8-tetangga.
2.6 Implementasi Menggunakan
Matlab
2.6.1 Algoritma Brute Force
% =================================
% Program membuat garis
% Menggunakan algoritma Brute Force
% Matlab Programming
% by : Jearren
% =================================
clear all; %hapus semua
variable
clc; %hapus
tampilan yg ada dilayar
%input dua titik (x1,y1)
dan (x2,y2)
x1 = input('x1 = ');
y1 = input('y1 = ');
x2 = input('x2 = ');
y2 = input('y2 = ');
if (x1>x2)
a=x1;
x1=x2;
x2=a;
a=y1;
y1=y2;
y2=a;
end
if x1==x2
x=x1*ones(1,length(y1:y2));
y=y1:y2;
elseif y1==y2
y=y1*ones(1,length(x1:x2));
x=x1:x2;
elseif (x1<x2)&(y1~=y2)
m=(y2-y1)/(x2-x1);
if m<1
x=x1:x2;
y=round(m*(x-x1)+y1);
else
m=1/m;
y = y1:y2;
x=round(m*(y-y1)+x1);
end
end
plot(x,y,'-ro')
xlabel('Nilai-X')
ylabel('Nilai-Y')
title('Menggambar Garis Menggunakan Algoritma Brute Force')
if (y1>y2) %agar ylim bertambah dari kecil ke besar
a=y1;
y1=y2;
y2=a;
end
xlim([x1-2 x2+2])
ylim([y1-2 y2+2])
grid on
Contoh : menggambar garis yang melalui titik (2,2) dan (18,5) menggunakan
algoritma Brute force.
2.6.2 Algoritma DDA
%
=================================
% Program membuat garis
% Menggunakan algoritma
DDA
% Matlab Programming
% by : Jearren
% =================================
clear all; %hapus
semua variable
clc; %hapus
tampilan yg ada dilayar
%input dua titik (x1,y1) dan (x2,y2)
x1 = input('x1 = ');
y1 = input('y1 = ');
x2 = input('x2 = ');
y2 = input('y2 = ');
if (x1>x2)
a=x1;
x1=x2;
x2=a;
a=y1;
y1=y2;
y2=a;
end
if x1==x2
x=x1*ones(1,length(y1:y2));
y=y1:y2;
elseif y1==y2
y=y1*ones(1,length(x1:x2));
x=x1:x2;
elseif (x1<x2)&(y1~=y2)
dx=(x2-x1);
dy=(y2-y1);
if abs(dx)>
abs(dy)
step=abs(dx);
else
step=abs(dy);
end
x_inc=dx/step;
y_inc=dy/step;
x_bulat=x1;
y_bulat=y1;
x=x1;y=y1;
for i=1:step
x=x+x_inc;
y=y+y_inc;
x_bulat=[x_bulat
round(x)];
y_bulat=[y_bulat
round(y)];
end
x=x_bulat; y=y_bulat;
end
plot(x,y,'-ro')
xlabel('Nilai-X')
ylabel('Nilai-Y')
title('Menggambar Garis Menggunakan Algoritma DDA')
if (y1>y2) %agar ylim bertambah dari kecil ke
besar
a=y1;
y1=y2;
y2=a;
end
xlim([x1-2 x2+2])
ylim([y1-2 y2+2])
grid on
Contoh : menggambar garis yang melalui titik (2,2) dan (18,5) menggunakan
algoritma DDA.
2.6.3
Algoritma
Bressenham
% =================================
% Program membuat garis
% Menggunakan algoritma Bressenham
% Matlab Programming
% by : Jearren
% =================================
clear all; %hapus
semua variable
clc; %hapus
tampilan yg ada dilayar
%input dua titik (x1,y1)
dan (x2,y2)
x1 = input('x1 = ');
y1 = input('y1 = ');
x2 = input('x2 = ');
y2 = input('y2 = ');
if (x1>x2)
a=x1;
x1=x2;
x2=a;
a=y1;
y1=y2;
y2=a;
end
if x1==x2
x=x1*ones(1,length(y1:y2));
y=y1:y2;
elseif y1==y2
y=y1*ones(1,length(x1:x2));
x=x1:x2;
elseif (x1<x2)&(y1~=y2)
dx=(x2-x1);
dy=(y2-y1);
x=x1;
y=y1;
x_bulat=x1;
y_bulat=y1;
if abs(dx)>abs(dy) %untuk 0 < |m| < 1
step=abs(dx);
p=2*abs(dy)-abs(dx);
for i=1:step
if p<0
x=x+1;
p=p+
2*abs(dy);
else
x=x+1;
if dy>0
y=y+1;
else
y=y-1;
end
p=p+
2*abs(dy) -2*abs(dx);
end
x_bulat=[x_bulat
x];
y_bulat=[y_bulat y];
end
else %untuk |m| >1
step=abs(dy);
p=2*abs(dx)-abs(dy);
for i=1:step
if p<0
if dy<0
y=y-1;
else
y=y+1;
end
p=p+ 2*abs(dx);
else
if dy<0
y=y-1;
else
y=y+1;
end
if dx>0
x=x+1;
else
x=x-1;
end
p=p+
2*abs(dx) -2*abs(dy);
end
x_bulat=[x_bulat
x];
y_bulat=[y_bulat y];
end
end
x=x_bulat;
y=y_bulat;
end
plot(x,y,'-ro')
xlabel('Nilai-X')
ylabel('Nilai-Y')
title('Menggambar Garis Menggunakan Algoritma Bressenham')
if (y1>y2) %agar ylim bertambah dari kecil ke
besar
a=y1;
y1=y2;
y2=a;
end
xlim([x1-2 x2+2])
ylim([y1-2 y2+2])
grid on
Contoh : menggambar garis yang melalui titik (2,2) dan (18,5) menggunakan
algoritma Bressenham.
2.6.4
Area
Filling
% =================================
% Program Area Filling
% Matlab Programming
% by : Jearren
% =================================
clear all; %hapus
semua variable
clc;
jum = input('Jumlah Titik pembentuk poligon = ');
selesai= 1;
x=[];y=[];
for i=1:jum
clc;
x1 = input('Titik pembentuk poligon x = ');
y1 = input('Titik pembentuk poligon y = ');
x=[x x1];
y=[y y1];
end
if length(x)>2
fill(x,y,'r')
xlim([min(x)-2 max(x)+2])
ylim([min(y)-2 max(y)+2])
grid on
end
Contoh : menggambar poligon yang melalui titik-titik
: (1,1), (4,3), (5,7), (3,9) dan (-2,4) menggunakan Area Filling.
Tidak ada komentar:
Posting Komentar