Komputer Grafik
Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yang lebih sedikit dibandingkan dengan algoritma yang menggunakan operasi bilangan real. Implementasi ke dalam bahasa pemrograman C dari kedua macam algoritma diatas, menunjukkan bahwa waktu komputasi algoritma midpoint lebih cepat sebesar 8 kali pada pembuatan garis lurus, dan lebih cepat sebesar 15 kali pada penggambaran lingkaran, dibandingkan dengan waktu komputasi algoritma yang menggunakan dasar operasi bilangan
riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi algoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.
Algoritma DDA
1. Start at first endpoint.
2. Draw pixel.
3. Step right by one pixel and up by m*change_in_x
1. (But change_in_x is 1 pixel!
2. so just step up by m pixels)
4. Draw pixel.
5. Repeat from step 3, until we reach second endpoint
Pseudo code:
1. Let x = x1; y = y1; m = (y2-y1)/(x2- x1);
2. Draw pixel (x, y)
3. WHILE (x < x2) //i.e. we reached the second endpoint
{
x = x + 1; //step right by one pixel
y = y + m; //step up by m pixels
Draw pixel (ROUND(x), ROUND(y));
}
Banyak yang menganggap bahwa algoritma DDA sangat lambat didalam menggambarkan suatu titik, garis maupun kurva. Berikut ini adalah function untuk menggambar garis dengan algoritma DDA
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);
}
Garis lurus dinyatakan dinyatakan dalam persamaan :
y = mx + c (1)
dimana : m : gradient dan c : konstanta.
Untuk menggambarkan pixel-pixel 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 pixel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, 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 real untuk menghitung gradient m dan konstanta c.
m = (y2 - y1 ) / (x2-x1) (2)
c = y1 – m* x1 (3)
Operasi bilangan real 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 real
dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan real, terutama pada penambahan dan pengurangan.
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);
}
riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi algoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.
Algoritma DDA
1. Start at first endpoint.
2. Draw pixel.
3. Step right by one pixel and up by m*change_in_x
1. (But change_in_x is 1 pixel!
2. so just step up by m pixels)
4. Draw pixel.
5. Repeat from step 3, until we reach second endpoint
Pseudo code:
1. Let x = x1; y = y1; m = (y2-y1)/(x2- x1);
2. Draw pixel (x, y)
3. WHILE (x < x2) //i.e. we reached the second endpoint
{
x = x + 1; //step right by one pixel
y = y + m; //step up by m pixels
Draw pixel (ROUND(x), ROUND(y));
}
Banyak yang menganggap bahwa algoritma DDA sangat lambat didalam menggambarkan suatu titik, garis maupun kurva. Berikut ini adalah function untuk menggambar garis dengan algoritma DDA
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);
}
Garis lurus dinyatakan dinyatakan dalam persamaan :
y = mx + c (1)
dimana : m : gradient dan c : konstanta.
Untuk menggambarkan pixel-pixel 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 pixel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, 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 real untuk menghitung gradient m dan konstanta c.
m = (y2 - y1 ) / (x2-x1) (2)
c = y1 – m* x1 (3)
Operasi bilangan real 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 real
dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan real, terutama pada penambahan dan pengurangan.
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);
}
