Algoritma ( Tugas Grafika Komputer )

rGaris
Umumnya persamaan garis lurus pada koordinat kartesius diwujudkan dalam persamaan garis : y=m.x+b
jika dimisalkan pada dua titik(x0,y0 dan x1,y1) akan dibuat sebuah garis lurus, kita dapat menentukan nilai “m' dan “b” dengan persamaan berikut:

b = y1-­m.x1
algoritma untuk menggambar garis pada komputer didasarkan pada dua persamaan di atas. dimana m adalah gradien atau kemiringan garis tersebut.

Algoritma digital differential analyzer(DDA)

Prinsip algoritma ini adalah mengambil nilai integer terdekat dengan jalur garis
berdasarkan atas sebuah titik yang telah ditentukan sebelumnya(titik awal garis).
Algoritma pembentukan garis DDA:

1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
3. Hitung dx=x1­x0, dan dy= y1­y0.
4. Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai x maupun nilai y dengan cara:
   ­- Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut dari dx.
   ­- Bila tidak maka langkah= absolutdari dy
5. Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dan y_increment=dy/langkah
6. Koordinat selanjutnya (x+x_increment, y+y_increment)
7. Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x = x1 dan y = y1.

Contoh Prosedur DDA dalam pascal:

uses graph,crt;

{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1}

procedure drawLine(xstart,ystart,xend,yend:integer);

var

step,k:integer;

dx,dy:real;

x_inc,y_inc,x,y:real;

begin

dx:=xend-xstart;

dy:=yend-ystart;

x:=xstart;

y:=ystart;

if abs(dx) > abs(dy) then

step:=round(abs(dx))

else

step:=round(abs(dy));

x_inc:=dx/step;

y_inc:=dy/step;

putPixel(round(x),round(y),30);

for k:=1 to step do

begin

x:=x+x_inc;

y:=y+y_inc;

putPixel(round(x),round(y),30);

end;

end;

begin

init;

{menggambar garis dari titik 10,10 ke 500,10}

drawLine(10,10,500,10);

readkey;

destroy;

end.

Algoritma garis Bressenham

Tidak seperti Algoritma DDA, Algoritma Bressenham tidak membulatkan nilai posisi pixel setiap waktu. Algoritma Bressenham hanya menggunakan penambahan nilai integer yang juga dapat diadaptasi untuk menggambar lingkaran.
Berikut ini langkah langkah untuk membentuk garis menurut algoritma Bressenham:

1. Tentukan dua titik yang akan dihubungkan
2. Tentukan salah satu titik di sebelah kiri sebagai titik awal yaitu(x0,y0) dan titik lainnya sebagai titik akhir(x1,y1).
3. Hitung dx,dy,2dx dan 2dy­2dx.
4. Hitung parameter p0=2dy­dx
5. Untuk setiap xk sepanjang jalur garis, dimulai dengan k=0,
   ­ - Bila pk < 0, maka titik 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­
6. Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, samapai x=x1 dan y=y1. 

Contoh Prosedur algoritma Bressenham untuk menggambar garis dari titik (10,10) ke (500,10).

uses graph,crt; 

{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1} 

procedure DrawBressLine(xa,ya,xb,yb:integer); 

var 

dx,p,dy,xEnd:integer; 

x,y:real; 

begin 

dx:= abs(xb-xa); 

dy:= abs(yb-ya); 

p:=2*dy-dx; 

if xa > xb then

begin

x:=xb;

y:=yb;

xEnd:=xa;

end

else

begin

x:=xa;

y:=ya;

xEnd:=xb;

end;

putPixel(round(x),round(y),30);

while x < xEnd do

begin

x:=x+1;

if p < 0 then

p:=p+(2*dy)

else

begin

y:=y+1;

p:=p+(2*(dy-dx));

end;

putPixel(round(x),round(y),30);

end;

end;

begin

init;

DrawBressLine(10,10,500,10);

readkey;

destroy;

end.