digiyudi

Rangkuman Pertemuan 7 Grafik Komputer
Scan Converting : Ellips and Polygon Filling

Algoritma Bresenham untuk Ellipse

- Ellipse : F (x, y) = b2 x2 + a2 y2 – a2 b2 = 0
- Gradien F (x, y) = dF/δx. i + dF/dy. j
= 2b2x i + 2a2y j
- If a2(yp-1/2) £ b2(xp+1), ganti dari region 1 ke region 2

Region 1

- Titik tengah pertama ada di (xp+1, yp-1/2)
- Jika posisi awal (xp, yp) dari sebuah elips adalah (0, b)
o d lama (awal) = F(1,b-1/2) = b2 + a2(b-1/2)2 – a2b2
= b2 – a2b+a2/4
- Kasus E,
o d baru = F(xp+2,yp-1/2) = d old + b2(2xp+3)
- Kasus SE,
o d baru = F(xp+2,yp-3/2) = d old + b2(2xp+3) + 2a2(1- yp)

Region 2

- Titik tengah adad di (xp+1/2, yp-1)
o d lama (awal) = F(xp+1/2,yp-1) = b2(xp+1/2)2 + a2(yp-1)2 – a2b2
- Kasus SE,
o d baru = d old + b2(2xp+2) + a2(3-2yp)
o xp = xp + 1
o yp =yp – 1
- Kasus S,
o d baru = d old + a2(3 – 2yp)
o yp = yp – 1

Mendefinisikan dan mengisi region dari pixel-pixel

Metode dari mendefinisikan region
- Pixel-defined: menspesifiksikan pixel dalam warna dan jarak geometris.
- Simbolis: menyediakan sifat-sifat (property) pixel dalam region.
- Contoh dari simbolis:
o Berada di dalam lingkaran dengan radius R
o Berada dalam poligon yang spesifik
o Kedekatan terhadap beberapa pixel

Pixel-Defined Regions

- Definisi : Region R adalah himpunan dari semua pixel yang mempunyai warna C yang terhubung dengan sebuah pixel S yang diberikan.
- 4-adjacent : pixel-pixel yang terletak setelah yang lainnya secara horizontal atau vertikal, tidak secara diagonal.
- 8-adjacent : pixel-pixel yang terletak setelah yang lainnya secara horizontal, vertikal, atau diagonal.
- 4-connected : jika terdapat sebuah jalur yang tidak terputus dari pixel-pixel 4-adjacent yang menghubungkannya.
- 8-connected : jalur yang tidak terputus dari pixel-pixel 8-adjacent yang menghubungkannya.

4 dan 8-Connectivity

Algoritma Recursive-Flood Fill

- Merupakan sebuah algoritma rekursif
- Dimulai dari pixel inisial dari warna intColor
- Tentukan tetangga 4-connected ke newColor secara rekursif.
- Flood-Fill : floods region dengan newColor
- Ide dasar:
o Mulai dari pixel (x, y)
o Jika (x, y) mempunyai warna intColor, ubah warna tersebut menjadi newColor
o Lakukan hal yang sama untuk semua tetangga secara rekursif.

- Pada recursive flood-fill biasanya beberapa pixel di-test ulang beberapa kali sebelum algoritma berakhir.
- Hubungan (coherence) antar region dapat digunakan untuk meningkatkan performa.

Region Filling Using Coherence

- Pixel-pixel interior pada scan-line dapat diorganisir ke dalam spans (rentang), atau grup-grup dari pixel interior.
- Tiap span diubah dari point mulai yang paling kiri.
- Saat sebuah span diubah, starting pixel dari tetangganya dan span-span yang tidak diproses diidentifikasi dan di-push ke dalam stack.
- Semua span diproses dalam sebuah recursive depth-first order.

Rangkuman Pertemuan 8 Grafik Komputer
Scan Converting : Polygon Filling

Polygon Scan-Conversion

Potong garis scan dengan edge-edge polygon dan mengisi diantara sepasang perpotongan.
Untuk y = ymin to ymax
- Potong garis scan y dengan tiap edge
- Urutkan perpotongan dengan x menaik [p0,p1,p2,p3]
- Isi pair-wise (p0 > p1, p2 >p3, …)

Special Handling

- Perpotongan adalah sebuah edge end point, dikatakan: (p0, p1, p2)
- (p0, p1, p2), sehingga kita tetap dapat mengisi pair-wise
- Pada kenyataanya, jika kita menghitung perpotongan dari garis scan dengan edge e1 dan e2 secara terpisah, kita akan mendapatkan point perpotongan p1 sebanyak 2 kali.

- Tapi bagaimana dengan contoh kasus yang 1 ini : (p0, p1, p2, p3)

Rules (Aturan)

Aturan:
Jika perpotongan adalah ymin dari sebuah edge end point, hitung perpotongan tersebut. Tetapi selain dari itu, jangan dihitung.

Dari kasus di atas: jangan hitung p1 untuk e2

Peningkatan Performa

- Tujuannya adalah menghitung perpotongan-perotongan dengan lebih efisien. Brute force: potong semua edge dengan setiap garis scan.
o Temukan ymin dan ymax untuk tiap edge dan potong edge hanya saat dia melewati garis scan.
o Hanya hitung perpotongan dari edge dengan garis scan pertama kali dia memotong.
o Hitung dx/dy
o Untuk setiap penambahan garis scan, hitung perpotongan yang baru dengan x = x + dx/dy

Tabel Edge

Tabel Edge yang Aktif

Daftar dari edge-egde yang aktif untuk arus garis scan, diurutkan dalam x yang menaik/meningkat.

Algoritma Polygon Scan-Conversion

Construct the Edge Table (ET);
Active Edge Table (AET) = null;
for y = Ymin to Ymax
Merge-sort ET[y] into AET by x value
Fill between pairs of x in AET
for each edge in AET
if edge.ymax = y
remove edge from AET
else
edge.x = edge.x + dx/dy
sort AET by x value
end scan_fill

Kelompok:
Danu Kurniawan 1100030660
Toddy Prasetyo 1100031083
Yuditra Carolus P. 1100031152
Valentinus Ricky A. 1100031171
Bramono Wicaksono 1100032426
Even 1100032653
Kent Hakiki 1100031631

Rangkuman Pertemuan 5 Grafik Komputer
Scan Converting : Lines

Rasterisasi (Scan Conversion)

Sebuah fungsi pokok dari grafik komputer adalah mengkonversi deskripsi geometri tingkat tinggi menjadi warna pixel dalam buffer frame.
Algoritma-algoritma rasterisasi antara lain: garis (lines), lingkaran (circles), ellipse (elips), dan polygons (segi banyak).

Operasi-operasi Rasterisasi

- Gambar garis, lingkaran, dan elips pada layar
- Lakukan manipulasi pixel maps: copying, scaling, rotating, dan lain-lain
- Susun gambar-gambar
- Gambar dan buat polygon
- Metode aliasing dan antialiasing

Algoritma Rasterisasi Garis

Yang diberikan / diketahui:
Segment endpoints (integers x1, y1; x2, y2)

Identifikasi / hasil:
Himpunan (x, y) untuk menampilkan segment

Tujuan dari semua algoritma penggambaran garis adalah untuk mengkonstruksikan perkiraan terbaik yang mungkin dari sebuah garis ideal yang melekat / terdapat pada sebuah tampilan raster:
- Penampilan yang berkelanjutan
- Tingkat ketebalan dan terang yang sama
- Apakah pixel-pixel yang paling mendekati garis ideal tersebut menyala
- Seberapa cepat sebuah garis dibentuk / dihasilkan

Rasterisasi Garis DDA

Secara sederhana menghitung Y sebagai sebuah fungsi dari X
- Secara konseptual: gerakan garis scan vertikal dari X1 ke X2
- Apakah ekspresi dari Y sebagai sebuah fungsi dari X
- Tentukan pixel (x, round (y(x)))

float m = (float) dy / (float) dx;
float b = y1 – m * x1;
y = round (m*(x+1) + b);

Contoh rasterisasi garis DDA menggunakan OpenGL:

Rasterisasi garis DDA memiliki pengecualian sekitar garis-garis vertical. Untuk setiap x, kita memiliki:
- 1 floating point pembagian
- 1 floating point perkalian
- 1 floating point pengurangan
- 1 pemanggilan untuk fungsi pembulatan

Rasterisasi Garis DDA (perbaikan)

Jika menggambar garis secara incremental, y tidak perlu dihitung ulang pada setiap tahap (0 < slope < 1):

y1 = mx1 + b;
y2 = mx2 + b = m(x1 + 1) + b = y1 + m

Algoritma Bresenham

Observasi
- Jika kita sedang berada di pixel P (xp,yp), pixel selanjutnya haruslah E(xp+1,yp) atau NE (xp+1,yp+1)
- Pilih E jika segmen melewati bagian bawah atau melalui midpoint M, selain dari itu pilihlah NE

Bentuk Implisit F(x,y)

Bentuk implisit dari persamaan garis
- Bentuk implisit : F(x,y) = ax + by + c = 0
- Bentuk lekukan : y = dy/dx*x + b
- F(x,y) = dy*x – dx*y + dx*b = 0

- (x1,y1) = (1,1); (x2,y2) = (4,2)
dx = 3 dan dy = 1
- F (x, y) = dy * x – dx * y + c = x – 3y + c
F(1,1) = 1 – 3 + c = 0; sehingga c = 2
Akhirnya kita dapatkan F (x, y) = x – 3y + 2
- Masukkan (2,1) and (2,2) ke fungsi F( ) :
F (2,1) = 2 – 3 + 2 = 1 (positif)
F (2,2) = 2 – 6 + 2 = -2 (negatif)

Setelah mengisi point (xp,yp).....

Untuk 0<=slope<=1, point keputusan adalah
- M =xp + 1, yp + ½
- F(xp+1,y+1/2) = dy*(xp+1) – dx*(yp+1/2) + dx*b = 0

Menghitung tanda dari nilai ini menentukan pixel mana yang akan diisi berikutnya
- Jika F(M) > 0, isi ke dalam tetangga dari NE (M di bawah garis)
- Jika F(M) £ 0, isi ke dalam tetangga dari E (M di atas garis)

Lakukan secara incremental…..

Asumsikan jika kita menghitung F(xp+1, yp+1/2) dan nilainya negatif, jadi kita isikan ke dalam tetangga E. Kemudian point keputusan selanjutnya adalah
– F(xp+2,yp+1/2) = a(xp+2) + b(yp+1/2) + c

Sekarang, trik dari penghitungan incremental…
– d baru = F(xp+2,yp+1/2) = a(xp+2) + b(yp+1/2) + c
– d lama = F(xp+1,yp+1/2) = a(xp+1) + b(yp+1/2) + c
– d baru = d lama + a

Apakah yang akan terjadi jika tanda dari F(x, y) berada di point keputusan yang pertama jika nilainya positif ? Tetangga NE yang akan dipilih, dan point keputusan selanjutnya adalah F(xp+2,yp+3/2)

Sekarang, trik dari penghitungan incremental…
– d baru = F(xp+2,yp+3/2) = a(xp+2) + b(yp+3/2) + c
– d lama = F(xp+1,yp+1/2) = a(xp+1) + b(yp+1/2) + c
– d baru = d lama + a + b

Algoritma Bresenham untuk Garis

- Isikan ke dalam point (x0,y0)
- Hitung point keputusan yang pertama dan d lama
- Isikan ke dalam tetangga yang terpilih (if d lama < 0 then E else NE)
- Untuk x dari x0 + 1 sampai xi, lakukan
o Hitung d baru dengan menambahkan a atau a + b ke d lama
o Uji tanda dari d baru, pilih dan isikan ke dalam pixel-pixel
o d lama = d baru
- d = F(x0 + 1, y0 + ½) = F(x0,y0) + a + b/2
- Tapi tunggu! Kita katakan bahwa kita ingin melakukan perhitungan matematis integer. b/2 bukanlah sebuah integer
- Substitusikan G (x,y) = 2 * F (x,y)
o Kita dapatkan d = G(x0+1,y0+1/2) = 2a + b
- Jika G adalah negatif, pilih E dan tambahkan dengan 2a
- Jika G adalah positif, pilih NE dan tambahkan dengan 2a + 2b

Rangkuman Pertemuan 6 Grafik Komputer
Scan Converting : Lines and Circles

Algoritma Bresenham untuk Garis (m > 1)

- Jika slope (gradien) > 1, maka tetangga selanjutnya yang mungkin adalah pixel N dan NE.
o Point keputusanny adalah F(x+1/2,y+1)
- Ketika tetangga N dipilih:
- Sekarang, trik dari penghitungan incremental…
o d baru = F(xp+1/2,yp+2) = a(xp+1/2) + b(yp+2) + c
o d lama = F(xp+1/2,yp+1) = a(xp+1/2) + b(yp+1) + c
o d baru = d lama + b
- Ketika tetangga NE dipilih:
- Sekarang, trik dari penghitungan incremental…
o d baru = F(xp+3/2,yp+2) = a(xp+3/2) + b(yp+2) + c
o d lama = F(xp+1/2,yp+1) = a(xp+1/2) + b(yp+1) + c
o d baru = d lama + a + b
- Seperti sebelumnya, pertama-tama lakukan penghitungan d lama yang pertama dengan
o d = F(x0 + ½ , y0 + 1) = F(x0,y0) + a/2 + b
- Substitusikan G(x,y) = 2 * F(x,y)
o Sehingga kita mendapatkan d = G(x0+1/2,y0+1) = a + 2b
- Jika G adalah negatif, pilih N dan tambahkan dengan 2b
- Jika G adalah positif, pilih NE dan tambahkan dengan 2a + 2b

Algoritma Circle Scan-Converting

- Persamaan lingkaran: sebuah bentuk standar dari persamaan lingkaran adalah teorema phytagoras
o X2 + Y2 = R2
o Y = SQRT (R2 – X2)
- Dapat digunakan untuk menggambar sebuah lingkaran dengan melangkah sepanjang sumbu x dalam unit langkah dari XC – R ke XC + R dan hitung nilai Y yang sesuai pada setiap posisi.

Algoritma Bresenham untuk Lingkaran

Ketika menggunakan algoritma Bresenham untuk rasterisasi lingkaran, perhatian terutama pada octant ke 2:
- x = 0 s/d x = y = R/Ö2
- F(x,y) = x2 + y2 – R2
- F(x,y) ³ 0 , titik berada diluar lingkaran
- F(x,y) < 0 , titik berada d dalam lingkaran

Menghitung d awal

- d lama = F(xp+1, yp-1/2) = (xp+1)2 + (yp-1/2)2 – R2
- Posisi awal dari pixel adalah di (0,R)
- Titik tengah adalah di (1, R-1/2)
- F(1, R-1/2) = 1 + (R2- R +1/4) – R2 = 5/4 – R
- Jika d lama < 0,
o pilih E dan titik tengah selanjutnya adalah (xp+2,yp-1/2)
o d baru = F(xp+2,yp-1/2)
= (xp+2)2 + (yp-1/2)2 – R2
= d lama + 2xp + 3
- Jika d lama > 0,
o pilih SE dan titik tengah selanjutnya adalah (xp+2,yp-3/2)
o d baru = F(xp+2, yp-3/2)
= (xp+2)2 + (yp-3/2)2 –R2
= d lama + 2xp – 2yp + 5

Kelompok:
Danu Kurniawan 1100030660
Toddy Prasetyo 1100031083
Yuditra Carolus P. 1100031152
Valentinus Ricky A. 1100031171
Bramono Wicaksono 1100032426
Even 1100032653
Kent Hakiki 1100031631