Algoritma DDA (Digital Diferential Analyzer), Bresenham & Midpoint Circle
A. Simple Digital Differential Analyzer (DDA)
Algoritma DDA adalah suatu algoritma pengkonversian suatu himpunan pixel–pixel menjadi suatu garis yang didasari atas perhitungan delta(x) dan delta(y);
Algoritma pembuatan garis DDA :
- Garis yang membentang membentang antara 2 titik, P1 dan P2 , selalu membentuk membentuk sudut yang besarnya sangat bervariasi.
- Sudut yang terbentuk menentukan kemiringan suatu garis atau disebut gradient/ slop atau disimbolkan dengan parameter m. Jika titik-titik yang membetuk garis adalah : (x1,y1) dan (x2,y2) maka
- Algoritma DDA bekerja atas dasar penambahan nilai x dan nilai y.
- Pada garis lurus, turunan pertama dari x dan y adalah konstanta.
- Sehingga untuk memperoleh suatu tampilan dengan ketelitian tinggi, suatu garis dapat dibangkitkan dengan menambah nilai x dan y masing-masing sebesar ∆x dan ∆y.
- Kondisi ideal ini sukar dicapai, karenanya pendekatan yang mungkin dilakukan adalah berdasarkan piksel-piksel yang bisa dialamati/dicapai atau melalui penambahan penambahan atau pengurangan pengurangan nilai x dan y dengan suatu besaran besaran dan membulatkannya ke nilai integer terdekat.
Contoh Soal:
Untuk menggambarkan algoritma DDA dalam pembentukan
suatu garis yang menghubungkan titik (10,10) dan (17,16), pertama-tama
ditentukan dx dan dy, kemudian dicari step untuk mendapatkan x_increment dan
y_increment.
Δx = x1 — x 0 = 17–10 = 7
Δy = y1 — y0 = 16 -10 = 6
selanjutnya hitung dan bandingkan nilai absolutnya.
|Δx| = 7
|Δy| = 6
karena |Δx| > |Δy|, maka step = |Δx| = 7, maka diperoleh
:
x_inc = 7/7= 1
y_inc = 6/7 = 0,86
B. ALGORITMA BRESENHAM
Algoritma Bresenham merupakan suatu algoritma yang dibuat oleh Bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya.
Menggambar Garis Algoritma Bresenham :
- Algoritma Bresenham memilih titik terdekat dari actual path
- Setiap sampling akan diinkremen menjadi 1 atau 0.
- Kondisi awal :Jika m < 1, maka m bernilai positif
- Bresenham melakukan inkremen 1 untuk x dan 0 atau 1 untuk y.
- Jika current pixel (xk, yk)
- Dimanakah pixel berikutnya akan di-plot, apakah di (xk+1, yk+1), (xk+1, yk), atau (xk, yk+1)?
- Parameter ke putusan, pk:
Algoritma Algoritma Bresenham Bresenham untuk |m| < 1:
- Input 2 endpoints, simpan endpoints kiri sebagai (x0, y0).
- Panggil Panggil frame buffer (plot frame buffer (plot titik pertama pertama )
- Hitung konstanta ∆ x, ∆y, 2 ∆y, 2 ∆y–2 ∆ xdan nilai awal parameter keputusan p0= 2 ∆y – ∆ x
- Pada setiap xk sepanjang sepanjang garis, dimulai dimulai dari k=0 ,
- ujilah : Jika pk< 0, maka plot(xk+1, yk)
- dan pk+1 = pk+ 2 ∆y
- Jika tidak maka plot (xk+1, yk+1) dan pk+1= pk+ 2 ∆y -2 ∆x
- Ulangi tahap 4 ∆ xkali
Algoritma MidPoint (Lingkaran)
- Algoritma ini diawali dengan menentukan jari jari r dan titik pusat di (xk,yk)
- Algoritma ini mengenerate pixel ke 8 arah dari 4 titik lurus (0°, 90°, 180°, 270°) , ke 4 titik ini memiliki masing masing 2arah generate pixel yang ditentukan oleh algoritma lalu loop berhenti pada saat sudut terdekat kelipatan 45° (45°, 135°, 225°, 315°) atau kondisi ini sama dengan nilai x=y
Langkah- langkah untuk membentuk lingkaran algoritma circle
midpoint:
- Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0) = (0,r)
- Hitung nilai dari parameter P0 = 5/4 – r
- 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
- Tentukan titik simetris pada ketujuh oktan yang lain
- 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
- Ulangi langkah ke3 sampai 5, sehingga X >= y
Komentar
Posting Komentar