Document

Report
KOMPUTER GRAFIK
Algoritma Garis Naïve dan DDA
Garis
 Dinyatakan dengan 4 nilai : x1,y1,x2,y2
 Koordinat / titik awal (x1,y1)
 Koordinat / titik akhir (x2,y2)
m = gradien / kemiringan garis
 Persamaan garis lurus :Y = mx + c
 M : gradien
 C : konstanta
 Garis dikelompokkan ke dalam 3 bentuk : cenderung
tegak (m>1), miring 45 derajat (m=1) dan cenderung
mendatar (0<m<1)
Naïve Idea
 Menentukan titik-titik garis penghubung koordinat
awal dan akhir
 Dimulai dari (x, y), untuk menentukan titik
selanjutnya, koordinat x diincrement sebanyak 1 dan
koordinat y dihitung sebagai y=m*x+c
 Kelemahan : Komputasi tinggi, tidak efisien
for x from x0 to xend
Compute y=mx+b
Draw_fn(x, round(y))
Naive Idea
void NaiveLine(int x0,int y0,int xend,int yend,int color)

int x;
float y, m, b;
m=(yend-y0)/(xend-x0);
b = y0 – m*x0;
for (x=x0; xxend; x++)
 drawpixel (x, int(y+0.5), color);
Costly floating point
y=m*x+b;
computations !!
Multiplications, additions,

roundings

DDA (Digital Differential
Analyzer) Algorithm
 Increment
yi 1  m xi 1  b
 m( xi  x)  b
 m xi  b  mx
 yi  mx
 Jika m<1 (garis cenderung mendatar pada kuadran
1 ,oktan 1) maka x sebagai iterator.
 For x  1 yi 1  yi  m
 Dimulai dari x=x0 and y=y0, setiap posisi (x,y) dihitung
dengan melakukan increment x sebanyak 1 dan y
sebanyak m -> x sebagai iterator
Example:draw segment, octant 1
P0 (0, 0)  Pend (5, 2)
x
0
1
2
3
4
5
y
0
0+0.4
0.4+0.4
0.8+0.4
1.2+0.4
1.6+0.4
int(y+0.5)
0
0
1
1
2
2
round
Line: P0(0, 0)-- P1(5, 2)
3
2
1
0
1
2
3
4
5
Draw segment, octant 2
 Jika m> 1, garis cenderung tegak pada kuadran 1, oktan
2, maka yang jadi iteratornya adalah y
 y di-incremet 1 dan x di-increment 1/m
 Bagaimana mengimplementasikan pada program?
DDA (Digital Differential Analyzer) Algorithm
Berikut ini adalah algoritma DDA untuk kuadran 1, oktan 1 dan 2
 Tentukan 2 buah titik.
 Tentukan yang menjadi titik awal (X0,Y0) dan titik akhir (X1,Y1).
 Hitung Dx dan Dy dimana Dx= X1-X0 dan Dy= Y1–Y0
 Bandingkan Abs(Dx) dan Abs(Dy). Jika Abs(Dx) > Abs(Dy) maka
Steps = Abs(Dx) bila tidak Steps = Abs(Dy)
 Hitung penambahan koordinat pixel, yaitu: X_increment =
dx/steps, dan Y_increment = dy/steps.
 Koordinat selanjutnya, yaitu X+X_increment dan Y+Y_increment
 Posisi pixel ditentukan dengan pembulatan nilai koordinat
tersebut.
 Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X1, Y
= Y1
 •Hasil dari fungsi : bilangan riil
 •Koordinat pixel : integer
 •Harus dibulatkan ke dalam integer terdekat
Contoh
Diketahui 2 buah titik A(10,10) dan titik
B(17,16), bila titik A sebagai titik awal dan
titik B sebagai titik akhir maka buatlah garis
yang menghubungkan titik tersebut dengan
menggunakan algoritma DDA.
Jawab







Titik awal = A(10,10)
Titik akhir = B(17,16)
Dx= X1-X0 = 17 –10 = 7
Dy= Y1-Y0 = 16 –10 = 6
Absolut(Dx) = 7
Absolut(Dy) = 6
Absolut (Dx) > absolute (Dy) maka steps =
Absolut(Dx) = 7
 X_increment= =7/7 = 1
 Y_increment= = 6/7 = 0,86
X1 = X + X_increment= 10 + 1 =11
Y1 = Y + Y_increment= 10 + 0,857 = 10,857 =11









K
1
2
3
4
5
6
7
X
11
12
13
14
15
16
17
Y
10,86
11,71
12,57
13,43
14,29
15,14
16
X_inc Y_in
10
10
11
11
12
12
13
13
14
13
15
14
16
15
17
16
Contoh
Diketahui 2 buah titik A(10,10) dan titik
B(16,17), bila titik A sebagai titik awal dan
titik B sebagai titik akhir maka buatlah garis
yang menghubungkan titik tersebut dengan
menggunakan algoritma DDA.
Jawab







Titik awal = A(10,10)
Titik akhir = B(16,17)
Dx= X1-X0 = 16–10 = 6
Dy= Y1-Y0 = 17 –10 = 7
Absolut(Dx) = 6
Absolut(Dy) = 7
Absolut (Dy) > absolute (Dx) maka steps =
Absolut(Dy) = 7
 X_increment= 6/7 = 0,86
 Y_increment= 7/7 = 1
Y1 = Y + Y_increment= 10 + 1 =11
X1 = X + X_increment= 10 + 0,857 = 10,857 =11









K
1
2
3
4
5
6
7
X
10,86
11,71
12,57
13,43
14,29
15,14
16
Y
11
12
13
14
15
16
17
X_inc Y_in
10
10
10
11
11
12
13
13
13
14
14
15
15
16
16
17
Kelemahan
 Hanya dapat digunakan untuk nilai x1<x2 dan y1<y2
(kuadran I)
 Menggunakan pembagian serta pembulatan sehingga
kurang akurat
Membuat titik
 #include<GL/glut.h>
 #include<stdlib.h>
 #include<math.h>
 void setPixel(int px, int py)
 {



glBegin(GL_POINTS);
glVertex2i(px, py);
glEnd();
 }
 void display()
 {





glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0,0.0,0.0);
glPointSize(4.0);
// Draws points (100,100) and (200,200).
setPixel(100, 100);
setPixel(200, 200);

 }
glFlush();


























void init(void)
{
//set display-window background color to white
glClearColor(1.0,1.0,1.0,0.0);
//set projection paramaters
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0,300.0,0.0,300.0);
}
main(int argc, char**argv)
{
//initialize GLUT
glutInit(&argc,argv);
//initialize display mode
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
//set display-window width & height
glutInitWindowSize(500,500);
//set display-window upper-left position
glutInitWindowPosition(0,0);
//create display-window with a title
glutCreateWindow("Digital Differential Analyzer Algorithm: Programmed by Salha");
//initialze OpenGL
init();
//call graphics to be displayed on the window
glutDisplayFunc(display);
//display everything and wait
glutMainLoop();
Latihan 1
 Modifikasilah program titik di atas sesuai dengan
algoritma DDA sehingga program bisa menggambar
beberapa titik membentuk garis dari suatu koordinat
awal dan akhir. Untuk membulatkan gunakan fungsi
berikut
 int round (float a)
{

return int (a+0.5);
}
Latihan 2
 Modifikasilah program di atas sesuai dengan algoritma
Naive sehingga program bisa menggambar beberapa
titik membentuk garis dari suatu koordinat awal dan
akhir. Untuk membulatkan gunakan fungsi berikut

similar documents