Grafika Komputer Output Primitive : Titik, Garis DDA dan Bresenham

     Grafika komputer merupakan bagian ilmu multimedia yang juga di pelajari di teknik informatika, bidang ini mempelajari bagaimana kita membuat sebuah grafis atau gambar dengan komputer atau program komputer pencipta grafis. Tapi, maksud dari menggambar disini adalah kita bukan mengedit gambar, melainkan sebagai pembuat software/aplikasi pengedit gambarnya. Semisal ada aplikasi Photoshop/Freehand,CorelDraw,AdobePremiere,Ulead,dll. Nah dengan kita belajar grafika komputer ini kita diharapkan bisa membuat sebuah aplikasi sederhana yang semacam itu(editor gambar/grafis). 

        Gafika komputer ini tidak hanya dipakai dalam editing desain saja, tetapi digunakan juga di bidang medis kedokteran sebagai alat pencipta gambar dari hasil scanner & pengolah foto rontegen. Di bidang militer digunakan untuk pembuatan monitor koordinat pesawat tempur dan masih banyak lagi kegunaan lainnya. Grafika komputer memiliki peran yang penting dan amat dibutuhkan dewasa ini, baru-baru ini penerapan yang sudah real nya adalah di sistem informasi geografis mapping (SIG), contohnya adalah : Google MAP & GPS MAP. Mungkin demikian sekilas pengetahuan aku tentang grafika komputer. Sekarang kita coba masuk ke pelajaran & perhitungannya, bahkan mungkin kalo aku ada waktu akan ku implementasikan dengan buat sebuah program grafis.

Memahami konsep primitif geometri titik dan garis
• memahami dan membedakan algoritma pembuatan garis
• Menganalisis algoritma pembuatan garis baik DDA
maupun bresenham
• Mengimplementasikan algoritma pembuatan garis dalam

program

Grafis Output primitif
- Fungsi digunakan untuk menggambarkan berbagai komponen gambar
- Contoh: mobil, rumah, bunga, ...

 Geometris Primitif
- Fungsi digunakan untuk menggambarkan titik, garis, segitiga, lingkaran, prisma ...

Dalam pembuatan titik dan garis, grafika komputer memiliki 3 metode Algoritma :

a.Algoritma Penggambaran Garis

b.Algoritma Digital Diferential Analyzer (DDA)

c.Algoritma Bresenham 

  

A.  Algoritma Penggambaran Garis:

Rumus Pers.Garis   y = m . x + b

Jika diketahui dua titik (x1,y1) dan (x2,y2) maka pers.garis dapat dihitung :

m = dy/dx  atau  m = y2 - y1 / x2 - x1

Contoh :

B. Algoritma Digital Diferential Analyzer (DDA) adalah scan convertion algorithm yang didasari oleh perhitungan berikut :

Scan Convertion
dy = m . dx      dan     dx = dy/ m

Basic DDA Algorithm
y = m . x + c (konstanta) 

m = dy/dx
                                                               

Syarat:
1. Jika 0<m<1  maka,
yk+1 = yk + m
xk+1 = xk + 1

2. Jika m >1  maka,
xk+1 = xk + 1/m
yk+1 = yk + 1


 Algoritma dlm pembuatan garis DDA



                                  











Langkah mengerjakan Algoritma DDA :
1.Inputkan titik awal (x1,y1) dan titik akhir (x2,y2)
2.Hitung dx dan dy dimana, dx = x2 - x1  dan  dy = y2 - y1
3.Jika absolut/abs |dx| > |dy| maka, |dx| = steps/ S, selain itu S = |dy|
4.Hitung berapa nilai dari abs |dx|= ? dan abs |dy|=? , serta steps
5.Hitung x_Incrementnya = dx/s   dan y_Incrementnya = dy/s
6.Hitung x1 = x + x_increment dan  y1 = y + y_increment
7.Ulang langkah 5 dan 6, sampai x > y

Contoh :
1. Misal buatlah sebuah garis dg titik awal (2,3) dan titik akhirr (12,8)
2. Berapa nilai dari tiap variabel-variabel x dan y pada setiap kali langkah, hingga mencapai batas yang ditentukan?

Penyelesaian:
Diket : 
Ttitik awal (2,3) dan titik akhir (12,8)
dx = x2 - x1 = 12 - 2 = 10
dy = y2 - y1 = 8 - 3 = 5
jika |dx| > |dy| maka,  S = |dx| = 10  dan  
|dy| = 5

X_inc = dx/s 
           = 10/10 = 1  (kenaikan nilai X sebelumnya)

Y_inc = dy/s
           = 5/10 = 1/2 atau  0.5 (kenaikan nilai Y sebelumnya)


Untuk lebih mudahnya kita buat tabel dari variabel titik diatas!

K	X	Y	X_Inc	Y_Inc (pembulatan bil riil)
0	2	3	2	3
1	3	3,5	3	4
2	4	4	4	4
3	5	4,5	5	5
4	6	5	6	5
5	7	5,5	7	6
6	8	6	8	6
7	9	6,5	9	7
8	10	7	10	7
9	11	7,5	11	8
10	12	8	12	8

Proses pembacaan dan perhitungannya :
  
K=0
x = 2 ; y = 3;

K=1
xk+1 = x + x_inc
         = 2 + 1 = 3
yk+1 = y + y_inc
         = 3 + 0,5 = 3,5

K=2
xk+1 = x + x_inc
         = 3 + 1 = 4
yk+1 = y + y_inc
         = 3,5 + 0,5 = 4  
(dst.. lanjutin ya :p , klo msh bingung koment ja dibawah! ).

Kesimpulan : 
Pembuatan garis dengan Algoritma DDA terbilang sangat sederhana dan belum cukup sempurna hasilnya, karena nilai yang dihasilkan dari perhitungan algoritma masih berupa bilangan riil (float), sehingga output gambar garis yang akan dihasilkan oleh program pun kurang jelas jika di zoom. Jika dianalogikan misal: sebuah titik pada grafik/kurva bernilai riil  x = 3 dan y = 3,5 maka akan ada plot yg tdk terisi/space sebesar 0,5 :   ___  ___  ___    garis setengah sempurna berupa putus-putus/dash.

C. Algoritma Bresenham (Bresenham Algorithm)

a. Sumbu vertikal memperlihatkan posisi scan line.

b. Sumbu horizontal memperlihatkan kolom pixel

c. 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.

Langkah-langkah mengerjakan Algoritma Bresenham :
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis
2. Tentukan salah satu sebagai titik awal (x0,y0) dan titik akhir (x1,y1) 
3. Hitung  dy = y1 - y0 dan dx = x1 - x0 , 2*dy , 2*dx
4. Hitung  Hitung parameter Po = 2dy - dx
5. Untuk setiap xk sepanjang jalur garis, dimulai dengan K = 0

•  Bila  Pk < 0  maka, titik selanjutnya adalah : 

         ( xk+1,  yk/nilai yk tetap ) dan  Pk+1 = Pk + 2 . dy

• Bila tidak, titik selanjutnya adalah : 

         ( xk+1,  yk+1 )  dan Pk+1 = Pk + 2dy - 2dx

6. Ulang langkah nomor 5 untuk menentukan posisi pixel berikutnya,

hinngga  x0 = x1  dan/atau  y0 = y1 .

 

Contoh:

Diketahui 2 buah titik A (10,10) dan titik B (17,16), bila titik awal adalah A dan titik akhir adalah B, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma bresenham!

Penyelesaian :

titik awal A (10,10)

titik akhir B (17,16)

dx = x1  - x0 =  17 - 10 = 7

dy = y1  - y0 = 16 - 10 = 6

2*dy = 2*6 = 12

2*dx = 2*7 = 14

Po/pk_awal = 2dy - dx 

                    = 12 - 7 =  5   (positive)

Periksa x0 & x1;

jika x0 < x1 , 

input  x0 = 10 dan y0 = 10 (sebagai plot awal x,y)

hingga  x0 = x1 dan y0 = y1, x_end = x1

Ulangi selama x0  <  x_end

K	PK	( xk + 1, yk + 1)
-	-	10,10
0	3	11,11
1	1	12,12
2	-1	13,13
3	11	14,13
4	9	15,14
5	7	16,15
6	5	17,16

Proses pembacaan dan perhitungannya :

Ingat slalu langkah dan aturan mengerjakan bresenham diatas!

diperoleh  pk_awal  = 5

periksa pk, karena  Pk > 0 maka, titik selanjutnya a/ pake rumus berikut :

( xk+1,  yk+1 )  dan  Pk+1 = Pk + 2dy - 2dx

K=0 

xk+1=  x + 1 = 10 + 1= 11

yk+1=  y + 1 = 10 + 1= 11

pk+1 = pk + 2dy - 2dx

          = 5 + 12 - 14 =  3

K=1

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk = 3,  Pk > 0

xk+1=  x + 1 = 11 + 1= 12

yk+1=  y + 1 = 11 + 1= 12

pk+1 = pk + 2dy - 2dx

         = 3   +  12 - 14 =  1

K=2

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk = 1,  Pk > 0

xk+1=  x + 1 = 12 + 1= 13

yk+1=  y + 1 = 12 + 1= 13

pk+1 = pk + 2dy - 2dx

         =  1 + 12 - 14 =  -1  (negative)

K=3

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk = -1, 

karena  Pk < 0 maka, titik selanjutnya a/ pake rumus berikut :

( xk+1 /nilai x bertambah 1,   yk / nilai y tetap ) dan  Pk+1 = Pk + 2 . dy

xk+1 = x + 1 = 13 + 1 = 14

yk (nilai y tetap, yaitu y) = 13  

pk+1 = pk + 2 . dy

         =  -1  + 12 =  11

K=4

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk =  11,  Pk > 0

xk+1 = x + 1 = 14 + 1 = 15

yk+1 = y + 1 = 13 + 1 = 14

pk+1 = pk + 2dy - 2dx

         =  11 + 12 - 14 = 9

K=5

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk =  9,  Pk > 0

xk+1 = x + 1 = 15 + 1 = 16

yk+1 = y + 1 = 14 + 1 = 15

pk+1 = pk + 2dy - 2dx

         =  9 + 12 - 14 = 7

K=6

periksa nilai pk ato hasil dr pk sebelumnya, dimana pk =  7,  Pk > 0

xk+1 = x + 1 = 16 + 1 = 17

yk+1 = y + 1 = 15 + 1 = 16

pk+1 = pk + 2dy - 2dx

         =  7 + 12 - 14 = 5

Proses Loop(perulangan) dan perhitungan berhenti, karena sudah memenuhi x0=x1  dan/atau  y0=y1

Proses Done..  =)

Untuk implementasi, cobalah code program garis DDA berikut :
/* * DDA_Line_Grafika_Komputer * Compiler : Turbo C++ 3.0 + DosBox 0.74 * @adi_ahmad_m_(0610u020) */ #include <graphics.h> #include <stdio.h> #include <conio.h> #include <math.h> void main() { int gd = DETECT, gm = DETECT, s, dx, dy, m, x1, y1, x2, y2; float xi, yi, x, y; printf("Enter the sarting point x1 & y1\n"); scanf("%d%d", &x1, &y1); printf("Enter the end point x2 & y2\n"); scanf("%d%d", &x2, &y2); initgraph(&gd, &gm, "c:\\tc\\bgi"); cleardevice(); dx = x2 - x1; dy = y2 - y1; if (abs(dx) > abs(dy)) s = abs(dx); else s = abs(dy); xi = dx / (float) s; yi = dy / (float) s; x = x1; y = y1; putpixel(x1, y1, 4); for (m = 0; m < s; m++) { x += xi; y += yi; putpixel(x, y, 4); } getch(); }
Output :

 Dan  sebagai latihan cobalah buat program garis bresenham, cari sumber di internet ("ambalayahh...")!
Contoh Output Bresenham :

Diatas adalah versi yg saya buat dengan Microsoft Visual Studio 2008 (vb.net 2008), selamat belajar.. Good luck!