BAB-9 POLIGON dan KURVA

Grafika Komputer Pertemuan Ke-10

BAB-9 POLIGON dan KURVA Poligon adalah bentuk yang disusun dari serangkian garis. Kurva Bezier digunakan untuk membentuk garis lengkung menggunakan algoritma Biezer. By: I Gusti Ngurah Suryantara, S.Kom., M.Kom

9.1. PENDAHULUAN Poligon adalah bentuk yang disusun dari serangkaian garis. Gambar 9.1 memperlihatkan beberapa bentuk poligon. Titik sudut dari poligon disebut vertex sedangkan garis penyusun poligon disebut edge.

Gambar 9.1. Gambar sebuah poligon.

Dari Gambar 9.1. dapat disimpulkan bahwa sebuah poligon selalu mempunyai dasar: 1. Jumlah vertex. 2. Koordinat vertex. 3. Data lokasi tiap vertex.

116

Grafika Komputer Pertemuan Ke-10 Poligon digambar dengan menggambarkan masing-masing edge dengan setiap edge merupakan pasangan dari vertexi – vertexi+1 kecuali untuk edge terakhir merupakan pasangan dari vertexn – vertex1. Operasi yang dapat dikenakan pada sebuah poligon antara lain: 1. Menginisialisasi poligon. Inisialisasi terhadap poligon perlu dilakukan untuk mengatur agar field vertnum berisi 0. 2. Menyisipkan vertex. Menyimpan informasi tentang vertex dan menyesuaikan informasi tentang jumlah vertex dengan menambahkan satu ke vertnum. 3. Menggambar poligon. Mengunjungi vertex satu persatu dan menggambar edge dengan koordinat (vertexi.x, vertexi.y) – (vertexi+1.x – vertexi+1.y) dari vertex nomor satu sampai vertnum -1. khusus untuk edge terakhir mempunyai koordinat (vertexvertnum.x , vertexvertnum.y) – (vertex1.x – vertex1.y). 4. mewarnai poligon. Mengisi area yang dibatasi oleh edge poligon dengan warna tertentu.

9.2. MENGISI POLIGON Ada beberapa algoritma yang dapat digunakan untuk mengisi area didalam sebuah poligon. Algoritma tersebut antara lain: 1. Algoritma Flood Fill. 2. Algoritma ScanLine Fill. 3. Inside-Outside Test. 4. Algoritma Boundray-Fill. Pada materi ini akan dibahas Flood Fill dan Boundray Fill. 9.2.1. Algoritma Flood Fill Algoritma yang paling mudah untuk mengisi poligon adalah algoritma Flood fill. Algoritma ini bekerja dengan cara pemakai menentukan warna poligon serta lokasi titik yang menjadi titik awal dan kemudian algoritma akan memeriksa titik-titik tetangga, apabila warna titik tetangga tidak sama dengan warna isi poligon maka titik tersebut akan diubah warnanya, proses tersebut dilanjutkan sampai seluruh titik yang berada didalam poligon selesai diproses. Penentuan titik tetangga dapat menggunakan metode 4-koneksi atau 8-koneksi seperti pada gambar 9.2.

(a). 4-Koneksi

(b). 8-Koneksi

Gambar 9.2. 4-koneksi dan 8-koneksi

117

Grafika Komputer Pertemuan Ke-10 Algoritma mengisi poligon menggunakan flood fill dengan 4 koneksi yang diimplementasikan secara rekursif diperlihatkan pada listing berikut. Void FloodFill( int x, int y, int fillColor, int oldColor) { If (getPixel (x,y) = = oldColor) { setColor(fillColor); setPixel(x,y); FloodFill(x+1,y,fillColor,oldColor); FloodFill(x-1,y,fillColor,oldColor); FloodFill(x,y+1,fillColor,oldColor); FloodFill(x,y-1,fillColor,oldColor); } } Ketepatan algoritma floofFill ditentukan oleh titik awal dan apakah poligon yang diwarnai merupakan poligon tertutup. Apabila tidak tertutup, meskipun hanya satu titik yang terbuka maka pengisian akan melebar ke area diluar poligon.

9.2.2. Algoritma ScanLine Fill

Void BoundaryFill( int x, int y, int fill, int Boundray) { Int current Current = getPixel(x,y); If ((current !=Boundray) && (current != fill)) { setColor(fill); setPixel(x,y); Boundray (x+1,y,fill, Boundray); Boundray (x-1,y,fill, Boundray); Boundray (x,y+1,fill, Boundray); Boundray (x,y-1,fill, Boundray); } }

118

Grafika Komputer Pertemuan Ke-10

9.3. KURVA Kali ini kita akan mempelajari bagaimana membuat kurva menggunakan algoritma Bezier. Algoritma membuat kurva bezier diusulkan oleh seorang ahli mesin dari perancis yang bekerja di perusahaan Renault dan digunakan untuk merancang badan mobil. 9.3.1. Kurva Bezier Kita sudah mempelajari bagaimana membentuk garis lurus, seperti dengan menggunakan algoritma DDA dan algoritma Bresenham. Pada bab ini kita akan membahas pembuatan kurva. Pembuatan kurva yang akan dibahas dengan menggunakan algoritma yang diusulkan oleh Bezier. Pierre Bezier seorang ahli mesin perancis yang bekerja diperusahaan renult. Bezier lahir pada tanggal 1 September 1910 dan meninggal pada tgl 25 Novmber 1999. Bezier memperoleh gelar dalam bidang mekanikal dari Ecole Nationale Superieure d’Seni et Metiers tahun 1930. Gelar kedua dibidang elektro pada tahun 1931 di Ecole Superieure d’Electricite, dan doktor pada tahun 1977 bidang matematik dari Universitas Paris. Ia bekerja untuk renult dari 1933-1975, di mana dia mengembangkan UNISURF USD CAM sistem. Dari tahun 1958-1979 dia profesor produksi di teknik konservatori nasional et des seni metiers. Pada tahun 1985 ia telah diakui oleh ACM SIGGRAPH dengan Steven A Coons atas kontribusi untuk komputer grafis dan teknik interaktif.

KURVA BÉZIER Kurva Bezier disusun dari n+1 titik kontrol dan bentuk kurval diperoleh sebagai hasil dari perhitungan fungsi polinomial yang dibentuk dari koordinat titik kontrol. Koordinat titik kurva diperoleh dengan persamaan. n P(u) =

Σ

pkBk,n(u) rumus 1

k=0

Setiap Bk,n(u) merupakan fungsi polinomial yang didefinisikan sebagai rumus 2 dan u bergerak dari 0 ke 1 serta pk menyatakan koordinat dari titik kontrol ke k. Pertambahan nilai u akan menentukan kehalusan kurva. Bk,n (u) = C(n,k)uk(1-u)n-k

rumus 2

Dan C(n,k) merupakan fungsi binomial seperti ada rumus 3 n! C(n,k) = ----------------------k!*(n-k)! Dengan n! Menyatakan fungsi faktorial.

119

rumus 3

Grafika Komputer Pertemuan Ke-10 Fungsi Bk,n (u) disebut juga sebagai fungsi blending karena menyebabkan titik kontrol melebur (blnd) membentuk kurva. Persamaan 1 dapat dituliskan kedalam bentuk yang lebih eksplisituntuk tipa koordinat titik diperlukan pada rumus 4. n x(u) =

Σ

xk Bk,n (u)

k=0 n

y(u) =

Σ

yk Bk,n (u) rumus 4

k=0

Salah satu kelemahan kurva Bezier adalah kurva yang dihasilkan tidak dapat secara ketat mengikuti bentuk dari titik kontrol sehingga dapat merepotkan bila kita ingin membuat bentuk kurva tertentu karena membutuhkan titik kontrol yang lokasinya berjauhan. LATIHAN Hitung (x,y) koordinat kurva bezier yang memiliki 4 titik kontrol yaitu p0(0,0), p1(1,2), p2((3,3) dan p3(4,0). JAWAB Untuk empat point kontrol, n = 3 Langkah pertama hitung seluruh fungsi blending, Bkn untuk k-0,...,n menggunakan rumus: n! k n-k Bkn(u) = C(n,k)u (1-u) = ------------ uk (1-u)n-k k!. (n-k)! 3! B03(u) = -------- u0(1-u)3 = 1.u0(1-u)3 = (1 – u)3 0! . 3! 3! B13(u) = -------- u1(1-u)2 = 3.u1(1-u)2 = 3u.(1 – u)2 1! . 2! 3! B23(u) = -------- u2(1-u)1 = 3.u2(1-u)1 = 3u2(1 – u) 2! . 1! 3! B33(u) = -------- u3(1-u)0 = 1.u3(1-u)0 = u3 3! . 0!

120

Grafika Komputer Pertemuan Ke-10 Kita dapat melihat bahwa fungsi-fungsi ini sangat sederhana. Semuanya ini identik untuk semua belokan pada kurva bezier dengan p titik kontrol. Sekarang kita siap untuk menghitung pada point melengkung. Parameter u selalu mengalami perubahan dari 0 sampai dengan 1. u = 0 berkitan dengan titik awal lengkungan (titik kontrol pertama); u1 berkaitan dengan titik akhir lengkungan (titik kontrol terakhir). Kita hanya memutuskan pada jumlah langkah-langkah anara nilai 0 samapi 1, dan dari nilai untuk menghitung peningkatan Du, yang 1/ (jumlah langkah – 1). Makin besar (banyak) jumlah langkahlangkah yang dikerjakan kurva makin halus akan tetapi semakin lambat dalam proses perhitungan (menggambar). Pada contoh ini jumlah langkah yang harus dikerjakan sebanyak 6, maka du =1 / (6-1) = 1/5 = 0,2. 0,2 sebagi nilai steps yang bergerak dai 0.0, 0.2, 0.4 s/d 1. Dengan 6 langkah belokan (lengkung) akan memiliki 6 koordinat. Kordinat-kordinat yang dihasilkan akan digabung dengan segmen garis. Mari kita menghitung titik kontrol berdasarkan algoritma yang sederhana ini.

121

Grafika Komputer Pertemuan Ke-10

122

Grafika Komputer Pertemuan Ke-10

Modul Untuk Kurva Bezier Dengan VB Public Type POINTAPI X As Long Y As Long End Type Public Declare Function PolyBezier Lib "gdi32" (ByVal hdc As Long, lppt As POINTAPI, ByVal cPoints As Long) As Long Public P(0 To 3) As POINTAPI 'draws a single Bezier curve segment with 4 control points Function DrawBezierCurve(Canvas As PictureBox, P() As POINTAPI, Steps As Integer) Dim i As Integer Dim j As Integer Dim u As Single Dim B(0 To 3) As Single Dim Q() As POINTAPI 'calculate Bezier curve ' Steps = Form1.SlidNilaiU.Value ReDim Q(0 To Steps) For i = 0 To Steps u = i / Steps 'Bernstein cubic polynomials

123

Grafika Komputer Pertemuan Ke-10 B(0) B(1) B(2) B(3)

= = = =

(1 - u) ^ 3 3 * u * (1 - u) ^ 2 3 * u ^ 2 * (1 - u) u ^ 3

For j = 0 To 3 Q(i).X = Q(i).X + P(j).X * B(j) Q(i).Y = Q(i).Y + P(j).Y * B(j) Next j Form1.ListView2.ListItems.Add , , Format(u, "0.##") Form1.ListView2.ListItems(Form1.ListView2.ListItems.Count).SubItems(1) = Q(i).X Form1.ListView2.ListItems(Form1.ListView2.ListItems.Count).SubItems(2) = Q(i).Y Next i 'draw Bezier curve Canvas.CurrentX = Q(0).X Canvas.CurrentY = Q(0).Y For i = 0 To Steps Canvas.Line (Canvas.CurrentX, Canvas.CurrentY)-(Q(i).X, Q(i).Y) Next i End Function

LAMPIRAN PROGRAM MENGISI POLIGON Dengan Visual C #include #include //for random numbers rand(); #include <SDL/SDL.h> #include "QuickCG.h" #include "Q3Dmath.h" using namespace std; template inline T0 pow(T0 a, T1 b){return pow(a, T0(b));} //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// // PUT CODE BELOW HERE // //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// //the floodfill algorithms void floodFill4(int x, int y, Uint32 newColor, Uint32 oldColor); void floodFill8(int x, int y, Uint32 newColor, Uint32 oldColor); void floodFill4Stack(int x, int y, Uint32 newColor, Uint32 oldColor); void floodFill8Stack(int x, int y, Uint32 newColor, Uint32 oldColor); void floodFillScanline(int x, int y, Uint32 newColor, Uint32 oldColor); void floodFillScanlineStack(int x, int y, Uint32 newColor, Uint32 oldColor);

124

Grafika Komputer Pertemuan Ke-10 //the stack #define stackSize 16777216 int stack[stackSize]; int stackPointer; //the auxiliary functions bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB color); void clearScreenBuffer(ColorRGB color); //the graphics buffer #define screenW 256 #define screenH 256 Uint32 screenBuffer[screenW][screenH]; int main(int argc, char *argv[]) { screen(screenW, screenH, 0, "Flood Fill"); clearScreenBuffer(RGB_White); int mouseX, mouseY; int oldMouseX, oldMouseY; bool LMB, RMB; while(!done()) { oldMouseX = mouseX; oldMouseY = mouseY; getMouseState(mouseX, mouseY, LMB, RMB); //3 different mouse input actions if(LMB) paint_drawLine(oldMouseX, oldMouseY, mouseX, mouseY, RGB_Black); if(RMB) { Uint32 color = RGBtoINT(ColorRGB((mouseX % 3 + 1) * 64, (mouseY % 8) * 32, (mouseX + mouseY) % 256)); floodFillScanlineStack(mouseX, mouseY, color, screenBuffer[mouseX][mouseY]); } if(RMB && LMB) clearScreenBuffer(RGB_White); //benchmark readKeys(); if(inkeys[SDLK_SPACE]) { float startTime = getTime(); for(int i = 1; i <= 50; i++) floodFill4Stack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]); float endTime = getTime(); float startTime2 = getTime(); for(int i = 1; i <= 50; i++) floodFillScanlineStack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]); float endTime2 = getTime(); drawBuffer(screenBuffer[0]); fprint(endTime - startTime, 0, 0, 0, RGB_Black, 1, RGB_White);

125

Grafika Komputer Pertemuan Ke-10 fprint(endTime2 - startTime2, 0, 0, 8, RGB_Black, 1, RGB_White); redraw(); sleep(); } //redraw the screen each frame drawBuffer(screenBuffer[0]); redraw(); } return 0; } /////////////////////////////////////////////////////////////////////// //Stack Functions /////////////////////////////////////////////////////////////////////// bool pop(int &x, int &y) { if(stackPointer > 0) { int p = stack[stackPointer]; x = p / h; y = p % h; stackPointer--; return 1; } else { return 0; } } bool push(int x, int y) { if(stackPointer < stackSize - 1) { stackPointer++; stack[stackPointer] = h * x + y; return 1; } else { return 0; } } void emptyStack() { int x, y; while(pop(x, y)); }

/////////////////////////////////////////////////////////////////////// //Variants of the Floodfill Algorithm ///////////////////////////////////////////////////////////////////////

126

Grafika Komputer Pertemuan Ke-10 //Recursive 4-way floodfill, crashes if recursion stack is full void floodFill4(int x, int y, Uint32 newColor, Uint32 oldColor) { if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) { screenBuffer[x][y] = newColor; //set color before starting recursion! floodFill4(x + 1, y, floodFill4(x - 1, y, floodFill4(x, y + 1, floodFill4(x, y - 1,

newColor, newColor, newColor, newColor,

oldColor); oldColor); oldColor); oldColor);

} } //Recursive 8-way floodfill, crashes if recursion stack is full void floodFill8(int x, int y, Uint32 newColor, Uint32 oldColor) { if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) { screenBuffer[x][y] = newColor; //set color before starting recursion! floodFill8(x + floodFill8(x floodFill8(x, floodFill8(x, floodFill8(x + floodFill8(x floodFill8(x floodFill8(x +

1, y, 1, y, y + y 1, y + 1, y 1, y + 1, y -

1, 1, 1, 1, 1, 1,

newColor, newColor, newColor, newColor, newColor, newColor, newColor, newColor,

oldColor); oldColor); oldColor); oldColor); oldColor); oldColor); oldColor); oldColor);

} } //4-way floodfill using our own stack routines void floodFill4Stack(int x, int y, Uint32 newColor, Uint32 oldColor) { if(newColor == oldColor) return; //avoid infinite loop emptyStack(); if(!push(x, y)) return; while(pop(x, y)) { screenBuffer[x][y] = newColor; if(x + 1 < w && screenBuffer[x + 1][y] == oldColor) { if(!push(x + 1, y)) return; } if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor) { if(!push(x - 1, y)) return; } if(y + 1 < h && screenBuffer[x][y + 1] == oldColor) {

127

Grafika Komputer Pertemuan Ke-10 if(!push(x, y + 1)) return; } if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor) { if(!push(x, y - 1)) return; } } } //8-way floodfill using our own stack routines void floodFill8Stack(int x, int y, Uint32 newColor, Uint32 oldColor) { if(newColor == oldColor) return; //if you don't do this: infinite loop! emptyStack(); if(!push(x, y)) return; while(pop(x, y)) { screenBuffer[x][y] = newColor; if(x + 1 < w && screenBuffer[x + 1][y] == oldColor) { if(!push(x + 1, y)) return; } if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor) { if(!push(x - 1, y)) return; } if(y + 1 < h && screenBuffer[x][y + 1] == oldColor) { if(!push(x, y + 1)) return; } if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor) { if(!push(x, y - 1)) return; } if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor) { if(!push(x + 1, y + 1)) return; } if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor) { if(!push(x + 1, y - 1)) return; } if(x - 1 > 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor) { if(!push(x - 1, y + 1)) return; } if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor) { if(!push(x - 1, y - 1)) return; } }

128

Grafika Komputer Pertemuan Ke-10 } //stack friendly and fast floodfill algorithm void floodFillScanline(int x, int y, Uint32 newColor, Uint32 oldColor) { if(oldColor == newColor) return; if(screenBuffer[x][y] != oldColor) return; int y1; //draw current scanline from start position to the top y1 = y; while(screenBuffer[x][y1] == oldColor && y1 < h) { screenBuffer[x][y1] = newColor; y1++; } //draw current scanline from start position to the bottom y1 = y - 1; while(screenBuffer[x][y1] == oldColor && y1 >= 0) { screenBuffer[x][y1] = newColor; y1--; } //test for new scanlines to the left y1 = y; while(screenBuffer[x][y1] == newColor && y1 < h) { if(x > 0 && screenBuffer[x - 1][y1] == oldColor) { floodFillScanline(x - 1, y1, newColor, oldColor); } y1++; } y1 = y - 1; while(screenBuffer[x][y1] == newColor && y1 >= 0) { if(x > 0 && screenBuffer[x - 1][y1] == oldColor) { floodFillScanline(x - 1, y1, newColor, oldColor); } y1--; } //test for new scanlines to the right y1 = y; while(screenBuffer[x][y1] == newColor && y1 < h) { if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor) { floodFillScanline(x + 1, y1, newColor, oldColor); } y1++; } y1 = y - 1;

129

Grafika Komputer Pertemuan Ke-10 while(screenBuffer[x][y1] == newColor && y1 >= 0) { if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor) { floodFillScanline(x + 1, y1, newColor, oldColor); } y1--; } } //The scanline floodfill algorithm using our own stack routines, faster void floodFillScanlineStack(int x, int y, Uint32 newColor, Uint32 oldColor) { if(oldColor == newColor) return; emptyStack(); int y1; //note: if you use y here, we're working vertically. This goes much faster in this case, because reading and writing the buffer[x][y] goes faster if y is incremented/decremented bool spanLeft, spanRight; if(!push(x, y)) return; while(pop(x, y)) { y1 = y; while(screenBuffer[x][y1] == oldColor && y1 >= 0) y1--; y1++; spanLeft = spanRight = 0; while(screenBuffer[x][y1] == oldColor && y1 < h) { screenBuffer[x][y1] = newColor; if(!spanLeft && x > 0 && screenBuffer[x - 1][y1] == oldColor) { if(!push(x - 1, y1)) return; spanLeft = 1; } else if(spanLeft && x > 0 && screenBuffer[x - 1][y1] != oldColor) { spanLeft = 0; } if(!spanRight && x < w - 1 && screenBuffer[x + 1][y1] == oldColor) { if(!push(x + 1, y1)) return; spanRight = 1; } else if(spanRight && x < w - 1 && screenBuffer[x + 1][y1] != oldColor) { spanRight = 0; } y1++; }

130

Grafika Komputer Pertemuan Ke-10 } } /////////////////////////////////////////////////////////////////////// //Auxiliary Functions /////////////////////////////////////////////////////////////////////// void clearScreenBuffer(ColorRGB color) { for(int x = 0; x < w; x++) for(int y = 0; y < h; y++) { screenBuffer[x][y] = RGBtoINT(color); } } bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB color) { if(x1 < 0 || x1 > w - 1 || x2 < 0 || x2 > w - 1 || y1 < 0 || y1 > h - 1 || y2 < 0 || y2 > h - 1) return 0; int deltax = abs(x2 - x1); // The difference between the x's int deltay = abs(y2 - y1); // The difference between the y's int x = x1; // Start x off at the first pixel int y = y1; // Start y off at the first pixel int xinc1, xinc2, yinc1, yinc2, den, num, numadd, numpixels, curpixel; if (x2 >= x1) // The x-values are increasing { xinc1 = 1; xinc2 = 1; } else // The x-values are decreasing { xinc1 = -1; xinc2 = -1; } if (y2 >= y1) // The y-values are increasing { yinc1 = 1; yinc2 = 1; } else // The y-values are decreasing { yinc1 = -1; yinc2 = -1; } if (deltax >= deltay) // There is at least one x-value for every yvalue { xinc1 = 0; // Don't change the x when numerator >= denominator yinc2 = 0; // Don't change the y for every iteration den = deltax; num = deltax / 2; numadd = deltay; numpixels = deltax; // There are more x-values than y-values }

131

Grafika Komputer Pertemuan Ke-10 else // There is at least one y-value for every x-value { xinc2 = 0; // Don't change the x for every iteration yinc1 = 0; // Don't change the y when numerator >= denominator den = deltay; num = deltay / 2; numadd = deltax; numpixels = deltay; // There are more y-values than x-values } for (curpixel = 0; curpixel <= numpixels; curpixel++) { screenBuffer[x % w][y % h] = RGBtoINT(color); // Draw the current pixel num += numadd; // Increase the numerator by the top of the fraction if (num >= den) // Check if numerator >= denominator { num -= den; // Calculate the new numerator value x += xinc1; // Change the x as appropriate y += yinc1; // Change the y as appropriate } x += xinc2; // Change the x as appropriate y += yinc2; // Change the y as appropriate } return 1; }

132