Computer Graphic Output Primitif dan Algoritma Garis Erwin Yudi Hidayat
[email protected] Computer Graphics C Version 2 Ed by Donald Hearn Addison Wesley is an imprint of
[email protected]
CG - Udinus || 10/11/2012
Output Primitif
Output primitif adalah struktur dasar geometri yang paling sederhana dari gambar grafika komputer. Setiap output primitif mempunyai data koordinat dan informasi lain tentang bagaimana cara object ditampilkan pada layar. Titik dan garis lurus adalah bentuk geometri paling sederhana dan komponen gambar.
[email protected]
CG - Udinus || 10/11/2012
Output Primitif
Setelah berhasil membangun output primitif, langkah selanjutnya adalah melakukan pengaturan terhadap atribut output primitif. Atribut adalah semua parameter yang mempengaruhi bagaimana primitive grafis ditampilkan. Atribut dari output primitif dapat berupa:
Ukuran garis batas Tipe garis batas Warna garis batas Warna objek (Fill color / Area Filling)
[email protected]
CG - Udinus || 10/11/2012
Atribut Output Primitif
Atribut dasar untuk titik adalah ukuran dan warna. Atribut dasar untuk garis adalah tipe (type), tebal (width) dan warna (color).
[email protected]
CG - Udinus || 10/11/2012
Teknologi Display
Cathode Ray Tubes (CRT) Liquid Crystal Display (LCD)
[email protected]
CG - Udinus || 10/11/2012
CRT
Elektron ditembakkan dari satu atau lebih electron gun Kemudian medan magnet yang ada di dalam tabung akan mendefleksi dan mengatur intensitas pancaran sinar elektron ke tiap pixel pada permukaan tabung dan akan membentuk gambar di monitor Medan magnet tersebut dihasilkan oleh kumparan yang diatur oleh sebuah rangkaian elektronik khusus yang ada di sekitar leher tabung Untuk membentuk gambar, sinar tersebut bergerak horisontal dari kiri ke kanan (raster)
[email protected]
CG - Udinus || 10/11/2012
CRT
[email protected]
CG - Udinus || 10/11/2012
Raster Scan Display
Pancaran Elektron bergerak baris per baris dari atas ke bawah Definisi gambar disimpan dalam memori yang disebut refresh buffer atau frame buffer. Setiap titik pada layar disebut pixel / pel yaitu picture element. Refreshing rate memiliki nilai 60 s/d 80 frame per detik. Horizontal retrace adalah kembalinya scan ke bagian kiri layar setelah refreshing tiap scan line. Vertical retrace adalah kembalinya scan ke atas setelah selesai satu frame (1/80 s/d 1/60 detik).
[email protected]
CG - Udinus || 10/11/2012
Random Scan Display
Pancaran Elektron diarahkan hanya ke bagian layar dimana gambar dibuat Random-scan hanya membuat gambar dengan satu garis pada suatu saat Refreshing rate tergantung jumlah garis. Definisi gambar disimpan dlm satu blok perintah line drawing disebut refresh display file / display list / display program / refresh buffer. Random-scan display menghasilkan gambar yang lebih halus dibandingkan dengan raster-scan, karena pancaran elektron langsung mengikuti jalur pada garis.
[email protected]
CG - Udinus || 10/11/2012
LCD
Menggunakan kristal cair untuk menampilkan gambar Terdiri dari 2 bagian utama : backlight dan kristal cair Backlight mirip seperti neon dengan warna putih Kristal cair berfungsi untuk menyaring cahaya backlight menjadi warna-warna tertentu dengan cara mengubah sudut dari kristal cair Sudut kristal cair tersebut berubah akibat tegangan listrik
[email protected]
CG - Udinus || 10/11/2012
Sistem Koordinat
Koordinat nyata
Koordinat sistem (koordinat cartesian)
Koordinat tampilan / layar
[email protected]
CG - Udinus || 10/11/2012
Koordinat Nyata
Adalah koordinat yang pada saat itu objek yang bersangkutan berada, misal koordinat sebuah kursi tergantung dari letak kursi itu ada dimana, bagaimana letaknya.
[email protected]
CG - Udinus || 10/11/2012
Koordinat Cartesian
Setiap titik ditentukan lokasinya melalui pasangan nilai x dan y nilai koordinat x bertambah positif dari kiri ke kanan dan nilai y bertambah positif dari bawah ke atas
[email protected]
CG - Udinus || 10/11/2012
Koordinat Monitor
Arah sumbu koordinat layar berkebalikan dengan yang digunakan di koordinat kartesian Pada layar komputer sumbu x bertambah positif ke kanan dan sumbu y bertambah positif ke bawah
[email protected]
CG - Udinus || 10/11/2012
Koordinat Layar
sebuah titik pada koordinat cartesian digambar ulang ke layar komputer maka secara visual lokasi titik tersebut akan berubah
[email protected]
CG - Udinus || 10/11/2012
Menggambar Elemen Geometri
Titik Garis Polyline Polygon
[email protected]
CG - Udinus || 10/11/2012
Titik
Mengkonversi sebuah koordinat tunggal yang diberikan oleh sebuah program aplikasi dalam suatu operasi tertentu dengan menggunakan peralatan output, sebagai contoh monitor
[email protected]
CG - Udinus || 10/11/2012
Garis
Garis dibuat dengan menentukan posisi titik diantara titik awal dan akhir dari suatu garis, yaitu (x1,y1) dan (x2,y2).
[email protected]
CG - Udinus || 10/11/2012
Pixel
unsur gambar atau representasi sebuah titik terkecil dalam sebuah gambar grafis. akronim bahasa Inggris Picture Element yang disingkat menjadi Pixel. Monitor ribuan piksel yang terbagi dalam baris-baris dan kolom-kolom. Jumlah piksel yang terdapat dalam sebuah monitor dapat kita ketahui dari resolusinya. Resolusi maksimum yang disediakan oleh monitor adalah 1024x768, maka jumlah pixel yang ada dalam layar monitor tersebut adalah 786432 piksel. Semakin tinggi jumlah piksel yang tersedia dalam monitor, semakin tajam gambar yang mampu ditampilkan oleh monitor tersebut.
[email protected]
CG - Udinus || 10/11/2012
Polyline
Menghubungkan tiap titik dengan garis lurus sehingga menjadi kurva terbuka
Contoh Polyline
[email protected]
CG - Udinus || 10/11/2012
Polygon
Sama dengan polyline hanya membentuk kurva tertutup
Contoh Polygon
[email protected]
CG - Udinus || 10/11/2012
Garis
Dinyatakan dengan 4 nilai : x1,y1,x2,y2 Koordinat / titik awal (x1,y1) Koordinat / titik akhir (x2,y2)
[email protected]
CG - Udinus || 10/11/2012
Bentuk Garis
Cenderung mendatar
Gradien bernilai 0 < m <1 Pixel bertambah 1 pada sumbu x dan bertambah sebesar m pixel pada sumbu y
[email protected]
CG - Udinus || 10/11/2012
Bentuk Garis
Cenderung tegak
Gradien bernilai m > 1 Pixel bertambah 1 pada sumbu y dan bertambah sebesar 1/m pixel pada sumbu x
[email protected]
CG - Udinus || 10/11/2012
Bentuk Garis
Miring 45
o
Gradien bernilai m = 1 Pixel bertambah 1 pada sumbu x dan bertambah sebesar 1 pixel pada sumbu y
[email protected]
CG - Udinus || 10/11/2012
Gradien
m = gradien / kemiringan garis
Persamaan garis lurus : Y = mx + c M : gradien C : konstanta
[email protected]
CG - Udinus || 10/11/2012
Algoritma DDA
Algoritma Digital Differential Analyzer (DDA) adalah algoritma sederhana untuk menggambar garis Garis dikelompokkan ke dalam 3 bentuk : mendatar, cenderung tegak dan miring 45 derajat Nilai untuk gradien : m>1, m=1, 0<m<1
[email protected]
CG - Udinus || 10/11/2012
Langkah² Algoritma DDA 1.
2.
3. 4.
Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. Tentukan salah satunya sebagai titik awal (x1, y1) dan yang lain sebagai titik akhir (x2, y2). Hitung : dx = x2 − x1 dan dy = y2 − y1 Tentukan step, dengan ketentuan berikut:
5.
x_inc = dx / step y_inc = dy / step 6.
[email protected]
Koordinat selanjutnya :
x = x + x_inc y = y + y_inc 7.
bila |dx| > |dy|, maka step = |dx| bila tidak, maka step = |dy|
Hitung penambahan koordinat piksel dengan persamaan:
8.
Lakukan pembulatan u = Round(x), v = Round(y), kemudian plot piksel (u, v) pada layar Ulangi point 6 dan 7 untuk menentukan posisi piksel berikutnya sampai x = x2 dan y = y2. CG - Udinus || 10/11/2012
Algoritma DDA
Hasil dari fungsi : bilangan riil Koordinat pixel : integer Harus dibulatkan ke dalam integer terdekat
[email protected]
CG - Udinus || 10/11/2012
Contoh
Diketahui 2 buah titik A(2,1) dan titik B(8,5) bila titik A sebagai titik awal dan titik B sebagai titik akhir, tentukan titik-titik antara yang menghubungkan titik A dan titik B sehingga membentuk garis AB dengan menggunakan algoritma DDA.
[email protected]
CG - Udinus || 10/11/2012
Contoh
Titik awal (x1, y1) = A(2,1) Titik akhir (x2, y2) = B(8,5) dx = x2 − x1 = 8 −2 = 6 dy = y2 − y1 = 5 − 1 = 4
Karena: |dx| > |dy|, maka step = |dx| = 6 x_inc = dx / step = 6/6 = 1 y_inc = dy / step = 4/6 = 0,67
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-1: (x,y) = (2,1) x+x_inc = 2 + 1 = 3 y+y_inc = 1 + 0,67 = 1,67 Koordinat selanjutnya : (x,y) = (3; 1,67) Pembulatan (3; 1,67) ≈ (3,2). Gambar titik (3,2) dilayar ==================================== Iterasi ke-2: (x,y) = (3; 1,67) x+x_inc = 3 + 1 = 4 y+y_inc = 1,67 + 0,67 = 2,34 Koordinat selanjutnya : (x,y) = (4; 2,34) Pembulatan (4; 2,34) ≈ (4,2). Gambar titik (4,2) dilayar ==================================== Iterasi ke-3: (x,y) = (4; 2,34) xA+x_inc = 4 + 1 = 5 yA+y_inc = 2,34 + 0,67= 3,01 Koordinat selanjutnya : (x,y) = (5; 3,01) Pembulatan (5; 3,01) ≈ (5,3). Gambar titik (5,3) dilayar
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-4: (x,y) = (5; 3,01) xA+x_inc = 5 + 1 = 6 yA+y_inc = 3,01 + 0,67 = 3,68 Koordinat selanjutnya : (x,y) = (6; 3,68) Pembulatan (6; 3,68) ≈ (6,4). Gambar titik (6,4) dilayar ==================================== Iterasi ke-5: (x,y) = (6; 3,68) xA+x_inc = 6 + 1 = 7 yA+y_inc = 3,68 + 0,67 = 4,35 Koordinat selanjutnya : (x,y) = (7; 4,35) Pembulatan (7; 4,35) ≈ (7,4). Gambar titik (7,4) dilayar ==================================== Iterasi ke-6: (x,y) = (7; 4,35) xA+x_inc = 7 + 1 = 8 yA+y_inc = 4,35 + 0,67 = 5,02 Koordinat selanjutnya : (x,y) = (8; 5,02) Pembulatan (8; 5,02) ≈ (8,5). Gambar titik (8,5) dilayar
[email protected]
CG - Udinus || 10/11/2012
Contoh
Karena x = x2 = 8, y = y2 = 5, maka iterasi dihentikan, sehingga diperoleh titik-titik pembentuk garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4) dan (8,5). Bila digambar pada raster graphics diperoleh gambar:
[email protected]
CG - Udinus || 10/11/2012
Algoritma Bressenham
Dikembangkan oleh Bresenham Berdasarkan selisih antara garis yang diinginkan terhadap setengah ukuran dari pixel yang sedang digunakan
[email protected]
CG - Udinus || 10/11/2012
Algoritma Bressenham
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
[email protected]
CG - Udinus || 10/11/2012
Langkah² Algoritma Bresenham Notes: algoritma midpoint Bresenham (untuk kemiringan 0 < m < 1)
5.
Untuk setiap xk sepanjang jalur garis, dimulai dengan k=0
1.
2.
3. 4.
Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. Tentukan salah satu sebagai titik awal (x0, y0) dan titik akhir (x1, y1). Hitung dx, dy, 2dx, 2dy dan 2dy − 2dx Hitung parameter: po = 2dy − dx
[email protected]
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 7.
Ulangi nomor 5 untuk menentukan posisi piksel berikutnya, sampai x = x1 dan y = y1
CG - Udinus || 10/11/2012
Contoh
Diketahui 2 buah titik A(2,1) dan titik B(8,5) bila titik A sebagai titik awal dan titik B sebagai titik akhir, tentukan titik-titik antara yang menghubungkan titik A dan titik B sehingga membentuk garis AB dengan menggunakan algoritma Bressenham.
[email protected]
CG - Udinus || 10/11/2012
Contoh
Titik awal (x0, y0) = A(2,1) Titik akhir (x1, y1) = B(8,5) dx = x1 − x0 = 8 −2 = 6 dy = y1 − y0 = 5 − 1 = 4 2.dx = 2.6 = 12 2.dy = 2.4 = 8 2dy − 2dx = 8 − 12 = −4 po = 2.dy − dx = 8 − 6 = 2
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-1 (k = 0): Titik awal = (2,1) Po = 2 > 0, maka titik selanjutnya adalah x = 2 + 1 = 3 dan y = 1 + 1 = 2, koordinat selanjutnya: (3,2) p1 = p0 + 2dy – 2dx = 2 − 4 = −2 ==================================== Iterasi ke-2 ( k = 1): Titik awal = (3,2) P1 = −2 < 0, maka titik selanjutnya adalah x = 3 + 1 = 4 dan y = 2, koordinat selanjutnya : (4,2) p2 = p1 + 2dy = −2 + 8 = 6 ==================================== Iterasi ke-3: (k=2) Titik awal = (4,2) P2 = 6 > 0, maka titik selanjutnya adalah x = 4 + 1 = 5 dan y = 2 + 1 = 3, koordinat selanjutnya : (5,3) p3 = p2 + 2dy – 2dx = 6 − 4 = 2
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-4: (k=3) Titik awal = (5,3) P3 = 2 > 0, maka titik selanjutnya adalah x = 5 + 1 = 6 dan y = 3 + 1 = 4, koordinat selanjutnya : (6,4) p4 = p3 + 2dy – 2dx = 2 − 4 = −2 ==================================== Iterasi ke-5: (k=4) Titik awal = (6,4) P3 = −2 < 0, maka titik selanjutnya adalah x = 6 + 1 = 7 dan y = 4, koordinat selanjutnya : (7,4) p5 = p4 + 2dy = −2 + 8 = 6 ==================================== Iterasi ke-6: (k=5) Titik awal = (7,4) P5 = 6 > 0, maka titik selanjutnya adalah x = 7 + 1 = 8 dan y = 4 + 1 = 5, koordinat selanjutnya : (8,5)
[email protected]
CG - Udinus || 10/11/2012
Contoh
Karena x = x1 = 8, y = y1 = 5, maka iterasi dihentikan, sehingga diperoleh titik-titik pembentuk garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4) dan (8,5). Bila digambar pada raster graphics diperoleh gambar:
[email protected]
CG - Udinus || 10/11/2012
Notes!
Untuk kemiringan −1 < m < 0 , kita tinggal mengganti komponen berikut:
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
[email protected]
CG - Udinus || 10/11/2012
Notes! Notes: Untuk kemiringan m > 1) 1.
2.
3. 4.
Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. Tentukan salah satu sebagai titik awal (x0, y0) dan titik akhir (x1, y1). Hitung dx, dy, 2dx, 2dy dan 2dx − 2dy Hitung parameter: po = 2dx − dy
[email protected]
5.
Untuk setiap yk sepanjang jalur garis, dimulai dengan k=0
bila pk < 0 maka titik selanjutnya adalah: (xk, yk+1) dan pk+1 = pk + 2dx bila tidak, titik selanjutnya adalah (xk+1, yk+1) dan pk+1 = pk + 2dx – 2dy 7.
Ulangi nomor 5 untuk menentukan posisi piksel berikutnya, sampai x = x1 dan y = y1
CG - Udinus || 10/11/2012
Algoritma Pembentuk Lingkaran
Persamaan umum lingkaran dengan pusat lingkaran (xp, yp) dan jari-jari r adalah: atau
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) menghasilkan posisi koordinat piksel yang tidak merata, karena terjadinya gaps yang disebabkan adanya perubahan gradient
[email protected]
CG - Udinus || 10/11/2012
Algoritma Pembentuk Lingkaran
Terjadinya gaps yang disebabkan adanya perubahan gradient menghasilkan posisi koordinat piksel yang tidak merata
[email protected]
CG - Udinus || 10/11/2012
Algoritma Pembentuk Lingkaran
Simetris Delapan Titik
Pembuatan kurva lingkaran dapat dilakukan dengan menentukan titik awal (x,y) yang terletak pada lingkaran, maka tujuh titik yang lain (yang terletak pada lingkaran juga) dapat ditentukan sebagai berikut: (−x,y), (x, −y), (−x, −y), (y,x), (−y,x), (y, −x), (−y, −x)
[email protected]
CG - Udinus || 10/11/2012
Algoritma Pembentuk Lingkaran
Algoritma Midpoint
Algoritma midpoint juga disebut algoritma lingkaran Bressenham Pembentukan semua titik berdasarkan titik pusat dengan penambahan semua jalur di sekeliling lingkaran
Garis lingkaran berada diantara titik (xk+1, yk) dan (xk+1, yk − 1)
[email protected]
CG - Udinus || 10/11/2012
Langkah² Algoritma Midpoint 1.
2.
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: p0= 5/4 –r -> Jika jari-jari r pecahan p0= 1 –r -> Jika jari-jari r bulat
3.
4.
5.
Untuk setiap posisi xk, dimulai dengan k = 0:
bila pk < 0 maka titik selanjutnya adalah: (xk+1, yk) dan pk+1 = pk + 2xk+1 + 1
[email protected]
6.
bila tidak, titik selanjutnya adalah: (xk+1, yk - 1) dan pk+1 = pk + 2xk+1 + 1 – 2 yk+1
Tentukan titik simetris pada ketujuh oktan yang lain Gerakkan setiap posisi piksel (x, y) pada garis lingkaran dengan titik pusat (xp, yp) dan plot nilai koordinat: x = x + x p; y = y + y p Ulangi langkah 3 sampai dengan 5 hingga x ≥ y
CG - Udinus || 10/11/2012
Contoh
Buatlah gambar kurva lingkaran dengan pusat lingkaran (0,0) dan jari-jari 8, perhitungan berdasarkan dari oktan kuadran pertama dimana x = 0 sampai x = y. Koordinat titik awal dimulai dari (x,r) = (0,8). Karena jari-jari r bulat, maka gunakan p0 = 1 – r.
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-1 (k = 0; x0 = 0; y0 = r = 8; p0 = 1 – r = 1 – 8 = -7) Karena p0 < 0, maka : x1 = x0 + 1 = 0 + 1 = 1 dan y1 = y0 = 8; jadi titik selanjutnya: (1,8) p1 = p0 + 2 x1 + 1 = –7 + 2.(1) + 1 = – 4 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (1,8), (–1,8), (1, –8), (–1, –8), (8,1), (–8,1), (8, –1), (–8, –1) ==================================== Iterasi ke-2 (k = 1; x1 = 1; y1 = 8; p1 = -4) Karena p1 < 0, maka : x2 = x1 + 1 = 1 + 1 = 2 dan y2 = y1 = 8; jadi titik selanjutnya: (2,8) p2 = p1 + 2 x2 + 1 = –4 + 2.(2) + 1 = 1 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (2,8), (–2,8), (2, –8), (–2, –8), (8,2), (–8,2), (8, –2), (–8, –2) ====================================
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-3 (k = 2; x3 = 2; y3 = 8; p3 = 1) Karena p2 > 0, maka x3 = x2 + 1 = 2 + 1 = 3 dan y3 = y2 – 1 = 8 –1 = 7 , jadi Titik selanjutnya : (3,7) p3 = p2 + 2 x3 + 1 – 2 y3 = 1 + 2.(3) + 1 – 2.(7) = – 6 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (3,7), (–3,7), (3, –7), (–3, –7), (7,3), (–7,3), (7, –3), (–7, –3) ==================================== Iterasi ke-4 (k = 3; x1 = 3; y1 = 7; p1 = -6) Karena p3 < 0, maka x4 = x3 + 1 = 3 + 1 = 4 dan y4 = y3 = 7, jadi Titik selanjutnya : (4,7) p4 = p3 + 2 x4 + 1 = –6 + 2.(4) + 1 = 3 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (4,7), (–4,7), (4, –7), (–4, –7), (7,4), (–7,4), (7, –4), (–7, –4) ====================================
[email protected]
CG - Udinus || 10/11/2012
Contoh
Iterasi ke-5 (k = 4; x3 = 4; y3 = 7; p3 = 3) Karena p4 > 0, maka x5 = x4 + 1 = 4 + 1 = 5 dan y5 = y4 – 1 = 7 –1 = 6 , jadi Titik selanjutnya : (5,6) p5 = p4 + 2 x4 + 1 – 2 y4 = 3 + 2.(5) + 1 – 2.(6) = 2 Dengan algoritma simetris delapan titik, maka diperoleh titik-titik berikut : (5,6), (–5,6), (5, –6), (–5, –6), (6,5), (–6,5), (6, –5), (–6, –5) ==================================== Iterasi ke-6 (k = 5; x1 = 5; y1 = 6; p1 = 2) Karena p5 > 0, maka x6 = x5 + 1 = 5 + 1 = 6 dan y6 = y5 – 1 = 6 –1 = 5 , jadi Titik selanjutnya : (6,5) Iterasi dihentikan karena X > Y.
[email protected]
CG - Udinus || 10/11/2012
Contoh
Bila digambar, hasil untuk oktan ke-1 ditunjukkan oleh gambar berikut:
Posisi piksel pada pembentukan lingkaran dengan titik pusat (0,0) dan jari-jari 8
[email protected]
CG - Udinus || 10/11/2012
[email protected]
CG - Udinus || 10/11/2012
