Definisi dan Cara kerja dari DDA(Digital Diferential Analyzer), Bresenham, Midpoint Circle

 

TUGAS M3 

                           Grafik Komputer 

NAMA                                        : Ajay Alfredo Almani

NPM                                           : 50420093

KELAS                                       : 3IA16

MATA KULIAH                        : Grafik Komputer 1**

DOSEN PENGAMPU               : DWI WIDIASTUTI., SKom., MMSI

TEKNIK INFORMATIKA UNIVERSITAS GUNADARMA
2022

SOAL TUGAS M3

Membuat blog mengenai definisi dan cara kerja dari DDA(Digital Diferential Analyzer), Bresenham, Midpoint Circle

JAWABAN TUGAS

DDA ( Digital Differential Analyzer ) 

Definisi dari Algoritma DDA (Digital Differential Analyzer) - Algoritma merupakan langkah - langkah untuk menyelesaikan masalah secara berurutan. Ada banyak model algoritma yang bisa diterapkan dalam menyelesaikan beberapa pekerjaan. Salah satunya adalah algoritma DDA atau yang biasa disingkat Digital Differential Analyzer.

 

Apa Sih Algoritma DDA?

Algoritma DDA adalah algoritma pembentukan garis yang menggunakan rumus dy = m.dx berdasarkan perhitungan dari dx dan juga dy. Garis yang terbentuk melalui titik koordinat diperoleh dari perhitungan yang kemudian di konversikan menjadi integer.

 

Algoritma DDA adalah garis yang membentak diantara 2 titik, yaitu P1 dan P2. Bentuk sudut dari kedua titik tersebut membentuk sudut yang besarnya beragam. Garis lurus yang membentang turunan dari x dan y merupakan konstanta.

 

Langkah - Langkah Pembentukan Garis Algoritma DDA

Ada beberapa langkah untuk pembentukan garis algoritma DDA, antara lain :

1. Pertama, dalam pembentukan garis tentukan dua titik yang akan dihubungkan terlebih dahulu.

2. Kemudian, tentukan titik awal dan titik akhir.

3. Hitung hasil perhitungan dari dx = x2 - x1 dan dy = y2 - y1.

4. Tentukan step, dengan syarat :

    Jika dx > dy maka step = dx

    Sebaliknya, jika dx < dy, maka step = dy

5. Hitung penambahan koordinat pixel dengan permasaan menggunakan :

    x_inc = dx / step

    y_inch = dy / step

6. Untuk koordinat selanjutnya yaitu x+x_inc, y+y_inch.

7. Hasil perhitungan nilai koordinat dibulatkan.

8. Untuk menentukan posisi pixel berikutnya, ikuti kembali langkah 6 dan 7.

 Metode DDA dapat diimplementasikan menggunakan aritmatika floating-point atau integer . Implementasi floating-point asli memerlukan satu operasi penambahan dan satu pembulatan per nilai interpolasi (misalnya koordinat x, y, kedalaman, komponen warna, dll.) dan hasil keluaran. Proses ini hanya efisien bila FPU dengan operasi penambahan dan pembulatan cepat akan tersedia.

 

Operasi bilangan bulat titik tetap memerlukan dua penambahan per siklus keluaran, dan dalam kasus bagian pecahan yang meluap, satu penambahan dan pengurangan tambahan. Probabilitas bagian pecahan yang meluap sebanding dengan rasio m dari nilai awal / akhir yang diinterpolasi. DDA sangat cocok untuk implementasi perangkat keras dan dapat disalurkan untuk throughput yang dimaksimalkan.

 

DDA linier dimulai dengan menghitung dy atau dx yang lebih kecil untuk kenaikan unit yang lain. Sebuah garis kemudian diambil sampelnya pada interval satuan dalam satu koordinat dan nilai bilangan bulat yang sesuai yang terdekat dengan jalur garis ditentukan untuk koordinat lainnya.

 

Mempertimbangkan garis dengan kemiringan positif, jika kemiringannya kurang dari atau sama dengan 1, kami mengambil sampel pada interval unit x (dx=1) dan menghitung nilai y berturut - turut sebagai

$${\displaystyle x_{k+1}=x_{k}+1}

Subskrip k mengambil nilai integer mulai dari 0, untuk titik pertama dan meningkat 1 hingga titik akhir tercapai. nilai y dibulatkan ke bilangan bulat terdekat agar sesuai dengan piksel layar.

 

Untuk garis dengan kemiringan lebih besar dari 1, kami membalikkan peran x dan y yaitu kami mengambil sampel pada dy=1 dan menghitung nilai x berturut - turut sebagai

$${\displaystyle y_{k+1}=y_{k}+1}

Perhitungan serupa dilakukan untuk menentukan posisi piksel di sepanjang garis dengan kemiringan negatif. Jadi, jika nilai mutlak kemiringan kurang dari 1, kita tetapkan dx=1 jika

yaitu titik ekstrim awal di sebelah kiri.

Bresenham Line Algortihm

Algoritma garis Bresenham adalah algoritma menggambar garis yang menentukan titik-titik raster n - dimensi yang harus dipilih untuk membentuk pendekatan yang dekat dengan garis lurus antara dua titik . Hal ini biasanya digunakan untuk menggambar garis primitif dalam gambar bitmap (misalnya pada layar komputer ), karena hanya menggunakan penambahan bilangan bulat, pengurangan dan pergeseran bit , yang semuanya merupakan operasi yang sangat murah di set instruksi komputer yang umum digunakan seperti x86_64 . Ini adalah algoritma kesalahan inkremental. Ini adalah salah satu algoritma paling awal yang dikembangkan di bidang grafik komputer . Perpanjangan ke algoritma asli dapat digunakan untuk menggambar lingkaran .

 

Sementara algoritme seperti algoritme Wu juga sering digunakan dalam grafik komputer modern karena dapat mendukung antialiasing , kecepatan dan kesederhanaan algoritme garis Bresenham membuatnya tetap penting. Algoritma ini digunakan dalam perangkat keras seperti plotter dan chip grafis dari kartu grafis modern . Hal ini juga dapat ditemukan di banyak perpustakaan perangkat lunak grafis . Karena algoritmenya sangat sederhana, ia sering diimplementasikan baik dalam firmware atau perangkat keras grafis kartu grafis modern. Label "Bresenham" digunakan saat ini untuk keluarga algoritme yang memperluas atau memodifikasi algoritme asli Bresenham.

 

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

        titik koordinat selanjutnya adalah (xk + 1, yk )

        dan Pk+1 = Pk + 2dy

    2. Jika sebaliknya, maka

        koordinat selanjutnya adalah (xk + 1, yk + 1)

        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.

Metode

Konvensi berikut akan digunakan :

- kiri atas adalah (0,0) sedemikian rupa sehingga koordinat piksel meningkat ke arah kanan dan bawah (misalnya piksel pada (7,4) tepat di atas piksel pada (7,5)), dan

- pusat piksel memiliki koordinat bilangan bulat.

Titik akhir garis adalah piksel di$${\displaystyle (x_{0},y_{0})}dan$${\displaystyle (x_{1},y_{1})}, di mana koordinat pertama pasangan adalah kolom dan yang kedua adalah baris.

Algoritma awalnya akan disajikan hanya untuk oktan di mana segmen turun dan ke kanan ($${\displaystyle x_{0}\leq x_{1}}dan$${\displaystyle y_{0}\leq y_{1}}), dan proyeksi horizontalnya$${\displaystyle x_{1}-x_{0}}lebih panjang dari proyeksi vertikal$${\displaystyle y_{1}-y_{0}}(garis memiliki kemiringan positif kurang dari 1). Dalam oktan ini, untuk setiap kolom x antara$${\displaystyle x_{0}}dan$${\displaystyle x_{1}}, ada tepat satu baris y (dihitung oleh algoritma) yang berisi piksel dari garis, sedangkan setiap baris di antara$${\displaystyle y_{0}}dan$${\displaystyle y_{1}}mungkin berisi beberapa piksel raster.

Algoritma Bresenham memilih bilangan bulat y yang sesuai dengan pusat piksel yang paling dekat dengan ideal (pecahan) y untuk x yang sama ; pada kolom-kolom yang berurutan y dapat tetap sama atau bertambah 1. Persamaan umum garis yang melalui titik-titik ujung diberikan oleh:

$${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} }.

Karena kita mengetahui kolom, x , baris piksel, y , diberikan dengan membulatkan kuantitas ini ke bilangan bulat terdekat:

$${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}.

lereng$${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}tergantung pada koordinat titik akhir saja dan dapat dihitung sebelumnya, dan y ideal untuk nilai bilangan bulat berturut-turut dari x dapat dihitung mulai dari$${\displaystyle y_{0}}dan berulang kali menambahkan kemiringan.

Dalam praktiknya, algoritme tidak melacak koordinat y, yang meningkat sebesar m = y/∆x setiap kali x bertambah satu; itu membuat kesalahan terikat pada setiap tahap, yang mewakili jarak negatif dari (a) titik di mana garis keluar dari piksel ke (b) tepi atas piksel. Nilai ini pertama kali disetel ke$${\displaystyle y_{0}-0.5}(karena menggunakan koordinat pusat piksel), dan bertambah m setiap kali koordinat x bertambah satu. Jika kesalahan menjadi lebih besar dari 0,5 , kita tahu bahwa garis telah bergerak ke atas satu piksel, dan bahwa kita harus menambah koordinat y kita dan menyesuaikan kembali kesalahan untuk mewakili jarak dari atas piksel baru – yang dilakukan dengan mengurangkan satu dari kesalahan.

Algoritma Lingkaran Midpoint

 

           Algoritma Lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45’ dari suatu lingkaran, yaitu oktan kedua dari x=0 ke x=R/Ö2, dan menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran. Dalam grafik komputer , algoritma lingkaran titik tengah adalah algoritma yang digunakan untuk menentukan titik-titik yang diperlukan untuk rasterisasi lingkaran . Algoritma lingkaran Bresenham diturunkan dari algoritma lingkaran titik tengah. Algoritma dapat digeneralisasi ke bagian kerucut .

Algoritma ini terkait dengan pekerjaan oleh Pitteway  dan Van Aken.

 Algoritma ini menarik semua delapan oktan secara bersamaan, mulai dari setiap arah mata angin (0 °, 90 °, 180 °, 270 °) dan meluas kedua cara untuk mencapai kelipatan terdekat dari 45 ° (45 °, 135 °, 225 °, 315 °). ). Itu dapat menentukan di mana harus berhenti karena ketika y = x, telah mencapai 45 °. Alasan menggunakan sudut-sudut ini ditunjukkan pada gambar di atas: Saat x bertambah, ia tidak melewatkan atau mengulangi nilai x apa pun hingga mencapai 45°. Jadi selama perulangan while, x bertambah 1 setiap iterasi, dan y berkurang 1 pada kesempatan, tidak pernah melebihi 1 dalam satu iterasi. Ini berubah pada 45 ° karena itu adalah titik di mana garis singgung naik = lari. Sedangkan rise>run before dan rise<run after.

 

Bagian kedua dari masalah, penentu, jauh lebih rumit. Ini menentukan kapan harus mengurangi y. Biasanya muncul setelah menggambar piksel di setiap iterasi, karena tidak pernah berada di bawah radius pada piksel pertama. Karena dalam fungsi kontinu, fungsi bola adalah fungsi lingkaran dengan jari-jari bergantung pada z (atau apa pun variabel ketiganya), dapat dipastikan bahwa algoritma untuk bola diskrit(voxel) juga bergantung pada algoritma lingkaran Midpoint ini. Tetapi ketika melihat sebuah bola, jari-jari bilangan bulat dari beberapa lingkaran yang berdekatan adalah sama, tetapi tidak diharapkan memiliki lingkaran yang sama persis yang berdekatan dengan dirinya sendiri di belahan bumi yang sama. Sebaliknya, lingkaran dengan jari-jari yang sama membutuhkan determinan yang berbeda, untuk memungkinkan kurva masuk sedikit lebih dekat ke pusat atau memanjang lebih jauh.

Langkah- langkah untuk membentuk lingkaran algoritma circle midpoint:

1. Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0) = (0,r)

2. Hitung nilai dari parameter P0 = 5/4 – r

3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut: Bila Pk < 0, maka titik selanjutnya adalah (xk+1 ,yk ) dan Parameter selanjutnya Pk+1 =Pk + 2xk+1 + 1 Bila tidak Pk > 0, maka selanjutnya adalah (xk+1 ,yk-1 )dan Parameter selanjutnya Pk+1=Pk + 2xk+1 + 1 – 2yk+1 Dimana 2xk+1 = 2xk + 2 dan 2yk+1 = 2yk – 2

4. Tentukan titik simetris pada ketujuh oktan yang lain

5. Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: Xk+1 = xk + 1 dan Yk+1 = yk , atau Yk+1 = yk -1

6. Ulangi langkah ke3 sampai 5, sehingga X >= y

Referensi :

https://www.anakblogger.com/2020/04/pengertian-algoritma-dda-digital.html?m=0

https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)

https://tambunan.staff.telkomuniversity.ac.id/mainan-2-grafcit-algoritma-dda-vs-bressenham/

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

https://hendroagungs.blogspot.com/2016/02/komputer-grafik.html

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm