Garis dibuat dengan menentukan
dua endpoint atau posisi awal dan posisi akhir dari suatu garis. Kmeudian
peralatan output membuat garis sesuai posisi titik titik tersebut. Untuk
peralatan analog seperti plotter an random-scan display garis lurus dapat
dihasilkan dengan halus.
Garis adalah penghubung antara
dua buah titik (titik awal dan titik akhir). Seperti yang kita tahu, bahwa
persamaan garis lurus dinyatakan dalam rumus: y=mx+c. Dimana m adalah gradien
yang didapatkan dari hasil pembagian deltaY dengan deltaX dan c adalah sebuah
konstanta. Berangkat dari sini kita coba mulai untuk membahas algortima apa
saja yang digunakan dalam pembuatan garis lurus.
1. ALGORITMA DDA
A. PENGERTIAN ALGORITMA DDA
Algoritma DDA adalah algoritma
pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus
dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan
kemudian dikonversikan menjadi nilai integer.
DDA ( Digital Differential
Analyzer) adalah garis yang membentang antara 2 titik, P1 dan P2. Dimana ke-2
titik ini membentuk sudut yang besarnya sangat bervariasi. Bekerja atas dasar
penambahan nilai x dan nilai y. Dimana pada garis lurus, turunan pertama dari x
dan y adalah kostanta.
B. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA
1. Tentukan
dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan
salah satu sebagai titik awal (x1, y1) dan titik akhir (x2, y2).
3. Hitung
dx = x2 – x1 dan dy = y2 – y1
4. Tentukan
step, yaitu jarak maksimum jumlah penambahan nilai x atau nilai y, dengan
ketentuan:
a.
bila |dx| > |dy| maka step = |dx|
b.
bila tidak, maka step = |dy|
5.
Hitung penambahan koordinat pixel dengan
persamaan:
x_inc = dx / step
y_inc = dy / step
6.
Koordinat selanjutnya (x+x_inc, y+y_inc)
7.
Plot pixel pada layar, nilai koordinat hasil
perhitungan dibulatkan
8.
Ulangi step nomor 6 dan 7 untuk menentukan
posisi pixel berikutnya sampai x = x1 atau y = y1.
C. KEUNTUNGAN DAN KERUGIAN ALGORITMA DDA
Keuntungan dari
algoritma Digital Differential
Analyzer (DDA) adalah tidak perlu
menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan metode off
set)
Kerugiannya dari algoritma Digital
Differential Analyzer (DDA) adalah adanya akumulasi Round-off
errors, sehingga garis akan melenceng dari garis lurus, selain itu operasi
round-off juga menghabiskan waktu.
D. PENERAPAN ALGORITMA DDA
#define BLACK
0 #include
#include
using namespace std;
void draw_pixel(int ix, int
iy, int value)
{
glBegin(GL_POINTS);
glVertex2i( ix, iy);
glEnd();
}
int bres(int x1,int y1,int
x2,int y2)
{
int dx, dy, i, e;
int incx, incy, inc1, inc2;
int x,y;
dx = x2 - x1;
dy = y2 - y1;
if(dx < 0) dx = -dx;
if(dy < 0) dy = -dy;
incx = 1;
if(x2 < x1) incx = -1;
incy = 1;
if(y2 < y1) incy = -1;
x=x1;
y=y1;
if(dx > dy)
{
draw_pixel(x,y, BLACK);
e = 2*dy - dx;
inc1 = 2*( dy -dx);
inc2 = 2*dy;
for(i = 0; i < dx; i++)
{
if(e >= 0)
{
y += incy;
e += inc1;
}
else e += inc2;
x += incx;
draw_pixel(x,y, BLACK);
}
}
else
{
draw_pixel(x,y, BLACK);
e = 2*dx - dy;
inc1 = 2*( dx - dy);
inc2 = 2*dx;
for(i = 0; i < dy; i++)
{
if(e >= 0)
{
x += incx;
e += inc1;
}
else e += inc2;
y += incy;
draw_pixel(x,y, BLACK);
}
}
}
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
bres(200, 200, 100, 50);
glFlush();
}
void myinit()
{
glClearColor(1.0, 1.0, 1.0,
1.0);
glColor3f(1.0, 0.0, 0.0);
glPointSize(1.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, 499.0, 0.0,
499.0);
}
int main(int argc, char**
argv)
{
glutInit(&argc;,argv);
glutInitDisplayMode
(GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(500,500);
glutInitWindowPosition(0,0);
glutCreateWindow("Bresenham's
Algorithm");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
2. ALGORITMA
BRESENHAM
A.PENGERTIAN ALGORITMA BRESENHAM
Algoritma bresenham merupakan
suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah
akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian
pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan
nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan
dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita.
Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan
proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1.
Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada
unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan,
kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot
pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan
line-path.
B. ATURAN BRESENHAM
·
Jika Pk bernilai positif (+), maka tambahkan
hasilnya dengan B dan nilai x dan y ditambah 1.
·
Jika Pk bernilai negatif (-), maka tambahkan
hasilnya dengan A dan nilai x ditambah 1, sedangkan y ditambah 0 (tetap).
·
Putaran dihentikan jika koordinat x dan y sudah
mencapai batas akhir.
C. PRINSIP DARI ALGORITMA BRESENHAM
1. Sumbu
vertikal memperlihatkan posisi scan line.
2. Sumbu
horizontal memperlihatkan kolom pixel
3. Pada
tiap langkah, penentuan pixel selanjutnya didasari oleh parameter integer yang
nilainya proporsional dengan pengurangan antara vertical separations dari dua
posisi piksel dari nilai actual.
Garis lurus dinyatakan
dinyatakan dalam persamaan :
y = mx + c รจ Persamaan(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 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 operasibilangan 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 setiapnilai x, dari =x1 sampai x=x2, operasi inilah yang
perlu dihindari,karena operasi ini memerlukan waktu operasi yang besar.
D. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA
1.
Tentukan 2 titik yang akan dihubungkan dalam
pembentuk garis.
2.
Tentukan salah satu titik disebelah kiri sebagai
titik awal, yaitu (X0,Y0) dan titik lainnya sebagai titik akhir (X1, Y1)
3.
hitung Dx, Dy, 2DX dan 2Dy-2Dy
4.
Hitung parameter P0= 2Dy – 2Dx
5.
Untuk setiap X1 sepanjang jalur garis, dimulai
dengan k=0,
·
bila pk<0, makatitik selanjutnya adalah (Xk +
1, Yk) dan Pk+1 = Pk +2Dy
·
bila tidak, maka titik selanjutnya adalah (Xk +
1, Yk +1) dan Pk+1 = Pk +2Dy – 2Dx
6.
Ulangi langkah no. 5 untuk menentukan posisi
selanjutnya, sampai X=X1 dan Y=Y1
E. PENERAPAN ALGORITMA BRESENHAM
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
int main()
{
int gd = DETECT, gm;
int dx, dy, p, xakhir;
float x0, x1, y0, y1, x, y;
initgraph(&gd,
&gm,0);
printf("Masukkan Nilai
X0: ");
scanf("%f",
&x0);
printf("Masukkan Nilai
Y0: ");
scanf("%f",
&y0);
printf("Masukkan Nilai
X1: ");
scanf("%f",
&x1);
printf("Masukkan Nilai
Y1: ");
scanf("%f",
&y1);
dx = abs(x1 - x0);
dy = abs(y1 - y0);
p = 2 * dy - dx;
if(x0 > x1)
{
x = x1;
y = y1;
xakhir = x0;
}
else
{
x = x0;
y = y0;
xakhir = x1;
}
while(x < xakhir)
{
x = x + 1;
if(p < 0)
{
p = p + 2 * dy;
}
else
{
y = y + 1;
p = p + 2 * (dy - dx);
}
putpixel(x, y, WHITE);
}
getch();
closegraph();
}
This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.
ConversionConversion EmoticonEmoticon