Perkembangan kemampuan komputasi prosesor yang pesat telah membuat komputer desktop mempunyai kemampuan komputasi yang besar. Hal ini mendorong perkembangan program aplikasi yang memerlukan komputasi yang besar seperti program aplikasi yang menggunakan grafik 3 dimensi. Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yang sarat komputasi, perlu dibarengi peningkatan efisiensi algoritma, sehingga pembuatan grafik garis dan kurva yang merupakan dasar pembuatan grafik dapat memberikan hasil yang optimal.
Algoritma midpoint merupakan algoritma pembuatan garis dan kurva dengan dasar operasi bilangan integer yang menonjolkan ciri kecepatan. Sehingga algoritma ini dapat dipakai sebagai algoritma pembuatan grafik yang menuntut kecepatan sebagai hal yang diutamakan. Pembahasan algoritma Midpoint dilakukan dengan mengasumsikan garis lurus dari kiri ke kanan, dan gadient antara 0 dan 1, sedangkan untuk lingkaran dengan mengasumsikan hanya sebagian lingkaran dengan sudut sebesar 45° , hal ini dilakukan untuk mempermudah penjelasan, sedangkan untuk kondisi yang lain dapat diderivasi dengan cara yang serupa. Untuk mendapatkan kinerja algoritma midpoint, dilakukan uji kecepatan komputasi dengan cara mengimplementasikan kedalam bahasa pemrograman C, dan melakukan perbandingan waktu komputasi dengan algoritma yang menggunakan dasar komputasi bilangan riel, maupun algoritma lain yang telah banyak dikenal seperti algoritma dda dan algoritma bressenham.
GARIS LURUS
Garis lurus dinyatakan dinyatakan dalam persamaan :
y = mx + c (1)
dimana : m : gradient dan
c : konstanta.
Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan riel, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat.
Penggambaran garis lurus dengan metode diatas dimulai dengan operasi bilangan riel untuk menghitung gradient m dan konstanta c.
m = (y2 - y1 ) / (x2-x1) (2)
c = y1 – m* x1 (3)
Operasi bilangan riel berikutnya adalah menghitung nilai y dengan persamaan (1) untuk mendapatkan koordinat piksel (x,y), untuk setiap nilai x, dari =x1 sampai x=x2, operasi inilah yang perlu dihindari, karena operasi ini memerlukan waktu operasi yang besar.
Algoritma Bresenham
Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan riel perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Algoritma Midpoint untuk Penggambaran Garis
Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar 1, titik abu-abu menyatakan posisi piksel, titik hitam menyatakan posisi piksel yang telah digambar. Berdasarkan piksel ke n yang telah digambar, diperlukan metode untuk menentukan piksel berikut yang akan digambar, karena penggambaran dilakukan dari kiri ke kanan, maka piksel berikutnya harus pada kolom n+1. Karena gradien diantara 0 dan 1, maka piksel berikutnya adalah pada posisi titik p atau titik q.
gambar garis lurus
Persamaan garis lurus yang telah dinyatakan dalam persamaan (1) dapat dinyatakan dalam fungsi x,y berikut.
f(x, y) = ax + by + c = 0 (4)
Fungsi f(x,y) dalam persamaan (4), akan memberikan nilai 0 pada setiap titik yang terletak pada garis, dan bernilai positip pada setiap titik yang terletak dibawah garis, dan bernilai negatif pada setiap titik yang terletak diatas garis.
Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q, sebaliknya piksel berikutnya adalah P.
g(x, y) = f(xn + 1, yn + 1/2) (5)
Fungsi g(x,y) persamaan (5) merupakan variabel penentu, dengan mengevaluasi g (x, y) dapat ditentukan piksel berikutnya yang mana berdasarkan tanda plus atau minus dari hasil fungsi g(x,y).
Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai sebelumnya. Untuk setiap piksel, increment sederhana (DeltaG) dipakai sebagai variabel penentu. Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan menggunakan persamaan 4 dan persamaan 5.
DeltaG = a * DeltaX + b * DeltaY (6)
Dimana DeltaX dan DeltaY adalah increment yang dipakai pada x dan y, yang bernilai 0 atau 1. Bila bergeser 1 piksel ke kanan :
DeltaG1 = a (7)
Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.
DeltaG2 = a + b (8)
Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a) atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan langkah-langkah sebagai-berikut:
Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a) pada variabel penentu.
Plot piksel pada posisi (x, y).
Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).
LINGKARAN
Kurva lingkaran dinyatakan dinyatakan dalam persamaan :
(x-xc) 2 + (y-yc) 2 = r 2 (9)
dimana : (xc,yc) : koordinat titik pusat lingkaran
r : jari-jari lingkaran
Untuk menggambarkan piksel-piksel dalam kurva lingkaran, dapat digunakan sumbu x dari x = (xc-r) sampai x = (xc+r) sebagai parameter dan sumbu y sebagai hasil dari persamaan (10)
y = yc +- sqrt(r 2 - (x-xc) 2 (10)
Algoritma ini memerlukan waktu operasi yang besar, karena mengandung operasi bilangan riel perkalian maupun eksponential, dan menghasilkan posisi koordinat piksel yang tidak merata, karena terjadinya gaps yang disebabkan adanya perubahan gradient.
Untuk menghindari posisi koordinat piksel yang tidak merata, koordinat piksel (x,y) dinyatakan dengan menggunakan koordinat polar dalama persamaan (11)
x = xc + r cos q (11a)
y = yc + r sin q (11b)
Persamaan (11) diatas mengandung operasi bilangan riel perkalian untuk mendapatkan koordinat piksel (x,y), untuk setiap nilai x, dari x = (xc-r) sampai x = (xc+r), operasi inilah yang perlu dihindari, karena operasi ini memerlukan waktu operasi yang besar.
Algoritma Midpoint
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. Sebagai contoh, digambarkan bagian dari lingkaran dari sudut 90° sampai 45° .
Seperti pada algoritma midpoint untuk garis lurus, maka pada setiap tahapan, terdapat 2 koordinat piksel yang harus dipilih yaitu (x+1, y) atau (x+1, y-1).
kurva lingkaran
Langkah berikutnya, adalah menyatakan persamaan lingkaran dan fungsi untuk menentukan variabel penentu. Persamaan lingkaran dengan pusat (0,0) dinyatakan dalam persamaan (12).
f(x, y) = x*x + y+y - r*r = 0 (12)
Fungsi f(x, y) persamaan (12) akan bernilai positif jika titik (x,y) diluar lingkaran, dan bernilai negatif jika titik (x,y) didalam lingkaran. Fungsi untuk variabel penentu dan increment dinyyatakan dalam persamaan (13), (14), dan (15).
g(x, y) = (x + 1)*(x + 1) + (y - 1/2)*(y - 1/2) - r*r (13)
DeltaG1 = 2x + 3 (14)
DeltaG2 = 2x - 2y + 5 (15)
Berbeda dengan nilai dari increment pada algoritma garis lurus yang bernilai konstan, pada kurva lingkaran, increment tidak konstan. Terlihat bahwa komputasi increment memerlukan operasi perkalian, tetapi operasi perkalian dapat diubah dengan cara komputasi nilai increment secara increment pula, sehingga diperlukan 2 komputasi increment dalam setiap piksel yang diproses. Secara umum, kurva polinomial orde n memerlukan n level increment. Pada titik awal (x1,y1), komputasi variabel penentu mempunyai bagian bilangan riel, sehingga operasi bilangan integer tidak dapat digunakan secara langsung. Dalam praktek hal ini diselesaikan dengan cara menambahkan nilai 1/4 pada variable penentu. Hal ini tidak mempengaruhi perubahan tanda bilangan, karena operasi yang dilakukan adalah operasi bilangan integer, sehingga menghasilkan operasi yang lebih cepat.
IMPLEMENTASI PERANGKAT LUNAK
Untuk mendapatkan hasil kerja dari suatu algoritma, maka algoritma pembuatan grafik garis lurus dan kurva lingkaran perlu diimplementasikan kedalam bahasa pemrograman dan dilakukan pengukuran waktu komputasi. Pada penulisan ini algoritma pembuatan grafik diimplementasikan kedalam bahasa pemrograman C, dengan menggunakan compiler Turbo C++. Listing lengkap (source code) dari program ini dapat
di download disini .
KESIMPULAN
Panjang garis atau banyak piksel dalam garis lurus sangat berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini disebabkan adanya perbedaan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya.
Panjang jari-jari dalam lingkaran tidak berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini menunjukkan perbandingan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya berimbang.
Algoritma dengan dasar operasi bilangan integer memberikan waktu operasi yang lebih cepat dibandingkan dengan algoritma dengan dasar operasi bilangan riel, hal ini ditunjukkan dengan waktu komputasi algoritma DDA, algoritma Bresenham dan algoritma Midpoint yang lebih cepat, baik pada pembuatan garis lurus maupun lingkaran dibandingan waktu komputasi dengan algoritma yang menggunakan dasar operasi bilangan riel.
Algoritma midpoint memberikan waktu operasi tercepat diantara algoritma penggambaran garis lurus yang telah menggunakan dasar operasi bilangan integer, seperti algoritma DDA, algoritma Bresenham. Jadi algoritma Midpoint merupakan algoritma yang cocok untuk penggambaran grafik yang menuntut kecepatan sebagai hal yang diutamakan.
Source Code
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <math.h>
int line_mat(int x1,int y1,int x2,int y2,int color);
int line_dda(int x1,int y1,int x2,int y2,int color);
int line_bre(int x1,int y1,int x2,int y2,int color);
int line_mid(int x1,int y1,int x2,int y2,int color);
int circ_mat(int xc,int yc,int r,int color);
int circ_bre(int xc,int yc,int r,int color);
int circ_mid(int xc,int yc,int r,int color);
int main(void)
{
int elapse;
struct time t1,t2;
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
int xmax, ymax;
/* initialize graphics and local variables */
initgraph(&gdriver, &gmode, "");
/* read result of initialization */
errorcode = graphresult();
/* an error occurred */
if (errorcode != grOk)
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1);
}
setcolor(getmaxcolor());
xmax = getmaxx();
ymax = getmaxy();
// get start time
gettime(&t1);
printf("The Start time is: %2d:%02d:%02d.%02d\n",
t1.ti_hour, t1.ti_min, t1.ti_sec, t1.ti_hund);
// draw line graphics
// line_mat(0,0,xmax*1,ymax*1,1);
// line_dda(0,0,xmax*1,ymax*1,1);
// line_bre(0,0,xmax*1,ymax*1,1);
// line_mid(0,0,xmax*1,ymax*1,1);
// draw circle graphics
// circ_mat(320,240,480*50,1);
// circ_bre(320,240,480*50,1);
// circ_mid(320,240,480*50,1);
// get finish time
gettime(&t2);
printf("The Finish time is: %2d:%02d:%02d.%02d\n",
t2.ti_hour, t2.ti_min, t2.ti_sec, t2.ti_hund);
// elapse time
elapse = (t2.ti_hour*60*60*100+t2.ti_min*60*100+t2.ti_sec*100+t2.ti_hund)- \
(t1.ti_hour*60*60*100+t1.ti_min*60*100+t1.ti_sec*100+t1.ti_hund);
printf("The Elapse time is: %d x 1/100 second \n",elapse);
/* clean up */
getch();
closegraph();
return 0;
}
int line_mat(int x1,int y1,int x2,int y2,int color)
// Algorithm y = m * x + b
// It is assumed that x1 < x2 and the gradient is less than 1.
{ float m = ((float) (y2 - y1)) / ((float) (x2 - x1));
float c = y1 - m * x1;
for ( int x = x1; x <= x2; x++)
{ float fy = m * x + c;
int y = fy + 0.5;
putpixel(x,y,color);
}
return(0);
}
int line_dda(int x1,int y1,int x2,int y2,int color)
// Algorithm digital differential analyzer
{ int dx,dy,step,k;
float x_increment,y_increment,x,y;
dx = x2-x1; dy = y2-y1;
// determine maximum step
if (abs(dx) > abs(dy)) step=abs(dx); else step=abs(dy);
x_increment = float(dx) / float(step);
y_increment = float(dy) / float(step);
x = x1; y = y1;
putpixel(int (x+0.5),int(y+0.5),color);
for (k=1;k<=step;k++)
{ x = x+x_increment;
y = y+y_increment;
putpixel(int(x+0.5),int(y+0.5),color);
}
return(0);
}
int line_bre(int x1,int y1,int x2,int y2,int color)
// Algorithm Bresenham
{ int dx,dy,x,y,x_end;
int p,const1,const2;
dx = x2-x1; dy = y2-y1;
p = 2*dy-dx; y = y1;
const1 = 2*dy; const2 = 2*(dy-dx);
// determine which point to use as start, which as end
if (x1 > x2)
{ x = x2; y = y2; x_end = x1; }
else
{ x = x1; y = y1; x_end = x2; }
putpixel(x,int(y+0.5),color);
while ( x < x_end )
{ x++;
if ( p < 0 )
p = p+const1;
else
{ y = y+1;
p = p+const2;
}
putpixel(x,int(y+0.5),color);
}
return(0);
}
int line_mid(int x1,int y1,int x2,int y2,int color)
// Algorith midpoint
// It is assumed that x1 < x2 and the gradient is less than 1.
{ int x,y=y1;
int a = y2 - y1;
int b = x2 - x1;
int G = 2 * a - b; // Decision variable
int DeltaG1 = 2 * (a - b);
int DeltaG2 = 2 * a;
for (x = x1; x <= x2; x++)
{ if (G > 0)
{ G += DeltaG1;
y++; ; // Next column and row.
putpixel(x,y,color);
}
else
{ G += DeltaG2;
// y not changed // Next column.
putpixel(x,y,color);
}
}
return (0);
}
int circ_mat(int xc,int yc,int r,int color)
// Algorithm y = yc +/- sqrt(r^2-(x-xc)^2)
// It is assumed that theta 45 degrees
{ int x, y, dy;
for ( x = xc; x <= xc+int (r/2); x++)
{ dy = int( sqrt( double(r)*double(r)- double ((x-xc)*(x-xc))) + 0.5);
putpixel(x,yc+dy,color);
}
return(0);
}
int circ_bre(int xc,int yc,int r,int color)
// Algorithm y = yc +/- sqrt(r^2-(x-xc)^2)
// It is assumed that theta 45 degrees
{ int x, y, p;
x = 0; y = r; p = 3 - 2 * r;
while ( x < y )
{ putpixel(xc+x,yc+y,color);
if ( p < 0 ) p = p + 4 * x + 6;
else
{ p = p + 4 * ( x-y) + 10;
y = y -1;
}
x++;
}
return (0);
}
int circ_mid(int xc,int yc,int r,int color)
/* Draw the second octant of a circle centred on the top
left corner of the screen. This particular algorithm will only draw
an arc whose inclination is between 0 and 45 degrees.
*/
{ int x, y, G, DeltaG1, DeltaG2;
x = 0; y = r;
G = 1 - r;
DeltaG1 = 3; DeltaG2 = -2 * r + 5;
while (x < y)
{ if (G < 0)
{ G += DeltaG1;
DeltaG1 += 2;
DeltaG2 = DeltaG2 + 2;
}
else
{ G += DeltaG2;
DeltaG1 += 2;
DeltaG2 += 4;
y--;
}
x++;
putpixel(xc+x,yc+y,color);
}
return(0);
}
DAFTAR PUSTAKA
- Donald Hearn and M.Pauline Baker, Computer graphics, NJ : Prentice-Hall, 1992.
- Borland International, Inc., Turbo C++ Reference Guide, 1990.
- http://www.geocities.com/Broadway/4574/ midpoint/index.htm
- http://hops.cs.jhu.edu/~stevec/graphics/ midpoint.htm
