Mainan ini khusus untuk mahasiswa yang mengambil mata kuliah Grafika dan Citra Komputer pada kelas TFN.

Anda disarankan untuk membaca beberapa referensi berikut ini (atau bisa mencari referensi lain yang sejenis),

• https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)
• https://www.tutorialspoint.com/computer_graphics/line_generation_algorithm.htm
• https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
• https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

Beberapa referensi penjelasan mengenai teknik pembuatan garis ini juga bisa Anda dapatkan di Youtube.

Simple Digital Differential Analyzer (DDA)

Secara sederhana garis akan dibentuk dari adanya dua endpoint yang terdiri dari koordinat awal dan koordinat akhir.

Pembentukan garis ini sangat bergantung pada perhitungan nilai increment yang dihasilkan pada masing-masing sumbu koordinat, berdasarkan perhitungan titik awal dan akhir. Berikut ini langkah-langkah penyelesaian untuk penentuan koordinat pembentukan garis dengan DDA,

1. Tentukan koordinat awal dan koordinat akhir, titik awal sebagai (x1,y1) dan titik akhir sebagai (x2,y2)
2. Kemudian hitung nilai dx = x2 – x1, dan nilai dy = y2 – y1.
3. Selanjutnya lakukan penetuan jumlah step dari proses increment pembuatan garis yang akan Anda lakukan. Caranya adalah dengan membandingkan nilai dari |dx| dan |dy|
4. jika |dy| > |dx|, maka jumlah nilai step yang diambil sama dengan nilai |dy|,
5. sebaliknya, bila |dx| > |dy|, maka nilai step = |dx|
6. Hitung penambahan koordinat (increment) pada setiap sumbu berdasarkan nilai perbandingan terhadap jumlah step. Misal nilai increment_x = dx/step,  dan nilai increment_y = dy/step.
7. penentuan koordinat selanjutnya untuk masing-masing sumbu ditentukan dari nilai x sebelumnya ditambah nilai increment_x, dan nilai y sebelumnya ditambah nilai increment_y.
8. Pada proses penentuan koordinat ini, berlaku sistem pembulatan integer untuk hasil titik selanjutnya.

Contoh Kasus:

Pada pembentukan garis untuk koordinat awal (10,10) dan koordinat akhir (17,16) maka didapatkan hasil titik koordinat sebagai berikut,

iterasi	x	y	koordinat (x,y)
0	10	10	(10,10)
1	11	10,86	(11,11)
2	12	11,72	(12,12)
3	13	12,58	(13,13)
4	14	13,44	(14,13)
5	15	14,3	(15,14)
6	16	15,16	(16,15)
7	17	16,02	(17,16)

Silahkan Anda ilustrasikan bentuk garis yang dihasilkan dari koordinat tersebut dalam bentuk gambar.

Berikut ini beberapa kelemahan dan masalah yang biasanya dihadapi pada penggunaan DDA,

• Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y ke bilangan integer memerlukan waktu.
• Variabel x, y maupun m memerlukan bilangan real, padahal penentuan kemiringan merupakan nilai pecahan.

Anda bisa mencoba teknik DDA ini pada pembentukan Garis untuk beberapa koordinat berikut ini,

1. (6,4) to (2,1)

2. (4,3) to (8,-2)

3. (1,2) to (-5,5)

 

Bresenham Line Algortihm

Algoritma ini digunakan untuk pembentukan garis menggunakan bilangan integer, sehingga tidak diperlukan adanya proses pembulatan bilangan pada setiap iterasinya. Algoritma Bresenham ini juga dikenal dengan istilah Midpoint Line Algorithm (teknik ini juga digunakan pada penggambaran lingkaran).

Pada proses pembentukan garis ini setiap titik dibuat melalui iterasi tanpa ada pembulatan dari hasil perhitungan pecahan. Sehingga algoritma ini diklaim lebih baik dalam hal pemrosesan titik koordinat. Berikut ini adalah langkah-langkah penerapan Bresenham Line Algorithm;

1. Tentukan koordinat awal garis dan koordinat akhir. A(x1, y1) dan B(x2, y2)
2. Hitung nilai dx, dari perhitungan (x2 – x1), kemudian nilai dy dari perhitungan (y2 – y1)
3. kemudian hitung nilai Parameter, P0 = 2dy – dx
4. pastikan iterasi setiap titik pada garis tersebut berawal dari k = 0.
5. Cek ketentuan untuk proses iterasi yang digunakan
   1. Jika Pk < 0 , maka
      1. titik koordinat selanjutnya adalah (xk + 1, yk )
      2. dan Pk+1 = Pk + 2dy
   2. Jika sebaliknya, maka
      1. koordinat selanjutnya adalah (xk + 1, yk + 1)
      2. dan Pk+1 = Pk + 2dy – 2dx
6. ulangi kembali proses pada step ke-5 diatas pada setiap iterasi titik berikutnya, sampai bertemu dengan titik koordinat akhir dari garis

Proses iterasi akan berhenti pada posisi titik akhir garis, dan tidak ada proses pembulatan hasil.

 

Contoh Kasus:

Pada pembentukan garis untuk koordinat awal (10,10) dan koordinat akhir (17,16) maka didapatkan hasil titik koordinat dengan algoritma Bresenham sebagai berikut,

K	Pk	Xk+1	Yk+1
–	–	10	10
0	5	11	11
1	3	12	12
2	1	13	13
3	-1	14	13
4	11	15	14
5	9	16	15
6	7	17	16

Silahkan Anda ilustrasikan bentuk garis yang dihasilkan dari koordinat tersebut dalam bentuk gambar.

 

 

Selamat Mencoba..