(Bresenham dan Digital Differential Analyzer Algoritma

1. BRESENHAM ALGORITMA.

Bresenham algoritma adalah Sebuah algoritma efisien untuk membuat sebuah garis dengan piksel. Dimensi panjang bertambah untuk setiap pixel, dan lereng fraksi dikumpulkan. Konvensi umum bahwa peningkatan pixel koordinat dan kanan bawah arah dan bahwa pusat-pusat pixel koordinat bilangan bulat yang akan digunakan. Titik-titik ujung garis adalah piksel pada (x _0, y ₀₎ dan (x _1, y _1), di mana koordinat pertama dari pasangan adalah kolom dan baris kedua adalah.  Algoritma akan disajikan pada awalnya hanya untuk octant di mana segmen pergi ke bawah dan ke kanan (x ₀ ≤ x ₁ dan y ₀ ≤ y _1), dan proyeksi horisontal x ₁ - x ₀ berarti lebih besar dari proyeksi vertikal y ₁ - y ₀ (garis mempunyai kemiringan kurang dari 1 dan lebih besar dari 0.) Dalam octant ini, untuk setiap kolom x antara x ₀ dan x _1, ada tepat satu baris y (dihitung dengan algoritma) yang berisi piksel baris, sedangkan setiap baris antara y ₀ dan y ₁ dapat berisi beberapa rasterized piksel.

Algoritma Bresenham memilih y bilangan bulat yang sesuai dengan pusat pixel yang paling dekat dengan ideal (fraksional) y untuk x yang sama; pada kolom berturut-turut y dapat tetap sama atau meningkat sebesar 1. Umum persamaan garis melalui titik-titik ujung diberikan oleh:

Karena kita tahu kolom, x, pixel's baris, y, diberikan oleh pembulatan kuantitas ini ke integer terdekat:

Lereng (y ₁ - y ₀₎ / (x ₁ - x ₀₎ tergantung pada koordinat titik akhir hanya dan dapat precomputed, dan yang ideal berturut-turut integer y untuk nilai x dapat dihitung mulai dari y ₀ dan berulang-ulang menambahkan lereng .

Dalam prakteknya, algoritma dapat melacak, kemungkinan besar daripada nilai-nilai y, nilai sebuah kesalahan kecil antara -0,5 dan 0,5: jarak vertikal antara bulat dan nilai-nilai y yang tepat untuk saat ini x. Setiap kali x adalah meningkat, kesalahan meningkat oleh kemiringan; jika melebihi 0,5, y para rasterization meningkat sebesar 1 (garis berlanjut pada keesokan baris bawah raster) dan kesalahan decremented oleh 1.0.

Berikut pseudocode sampel plot(x,y) plot sebuah titik dan abs kembali nilai mutlak:

fungsi garis (x0, x1, y0, y1)

     int deltax := x1 - x0 int deltax: = x1 - x0

     int deltay := y1 - y0 int deltay: = y1 - y0

     error real: = 0

     real deltaerr := deltay / deltax    // Assume deltax != 0 (line is not vertical

  // note that this division needs to be done in a way that preserves the fractional part / /

int y: = y0

     for x from x0 to x1

         plot(x,y

         error := error + deltaerr

         if abs(error) ≥ 0.5 then j

             y := y + 1

             error := error - 1.0

Generalisasi

Versi di atas hanya menangani baris yang turun ke kanan. Kita tentu ingin bisa menarik semua baris. Kasus pertama adalah yang memungkinkan kita untuk menarik garis yang masih kemiringan ke bawah tetapi kepala di arah yang berlawanan. Ini adalah masalah sederhana menukar poin awal jika x0 > x1 Rumit adalah menentukan cara menggambar garis yang naik. Untuk melakukan hal ini, kita memeriksa apakah y ₀ ≥ y _1; jika demikian, langkah kita y dengan -1 bukan 1Terakhir, kita masih perlu untuk menggeneralisasi algoritma untuk menggambar garis ke segala arahSampai sekarang kita hanya bisa menggambar garis dengan kemiringan kurang dari satuUntuk dapat menggambar garis dengan kemiringan yang curam, kita mengambil keuntungan dari kenyataan bahwa garis yang curam dapat dicerminkan di garis y = x untuk memperoleh sebuah baris dengan kemiringan kecil. Efeknya adalah untuk mengaktifkan variabel x dan y di seluruh, termasuk mengganti parameter untuk merencanakan. Kode tampak seperti ini:

 fungsi garis (x0, x1, y0, y1)

     boolean steep := abs(y1 - y0) > abs(x1 - x0

     if steep

         swap(x0, y0)

         swap(x1, y1)

     if x0 > x1 then

         swap(x0, x1)

         swap(y0, y1)

     int deltax := x1 - x0

     int deltay := abs(y1 - y0)

     real error := 0

     real deltaerr := deltay / deltax

     int ystep

     int y := y0

     if y0 < y1 then ystep := 1 else ystep := -1

     for x from x0 to x1

         if steep then plot(y,x) else plot(x,y

         error := error + deltaerr

         if error ≥ 0.5 then j

             y := y + ystep

             error := error - 1.0

Sekarang fungsi menangani semua baris dan mengimplementasikan algoritma Bresenham lengkap.

Optimasi

Masalahnya dengan pendekatan ini adalah bahwa komputer beroperasi relatif lambat pada angka pecahan seperti error dan deltaerr selain itu, kesalahan dapat terakumulasi selama bertahun-floating-point tambahan. Bekerja dengan baik bilangan bulat akan lebih cepat dan lebih akurat. Trik yang kami gunakan adalah dengan mengalikan semua angka fraksional di atas oleh deltax yang memungkinkan kita untuk menyatakan mereka sebagai bilangan bulatSatu-satunya masalah yang tersisa adalah 0,5 konstan untuk menangani hal ini, kita mengubah inisialisasi dari variabel error dan invert itu untuk tambahan pengoptimalan kecil. Program baru terlihat seperti ini:

 function line(x0, x1, y0, y1

     boolean steep := abs(y1 - y0) > abs(x1 - x0

     if steep then

         swap(x0, y0)

         swap(x1, y1)

     if x0 > x1 then

         swap(x0, x1)

         swap(y0, y1)

     int deltax := x1 - x0

     int deltay := abs(y1 - y0)

     int error := deltax / 2

     int ystep

     int y := y0

     if y0 < y1 then ystep := 1 else ystep := -1

     for x from x0 to x1

         if steep then plot(y,x) else plot(x,y)

         error := error - deltay

         if error < 0 then

             y := y + ystep

             error := error + deltax

2.       Digital Differential Analyzer (DDA) Metode

Dasar dari metode DDA adalah untuk mengambil langkah-langkah di sepanjang satu unit mengkoordinasikan dan menghitung nilai-nilai yang sesuai sepanjang koordinat lain. Langkah-langkah unit selalu sepanjang koordinat perubahan terbesar, misalnya jika dx = 10 dan dy = 5, maka kami akan mengambil langkah-langkah unit sepanjang x dan menghitung langkah-langkah di sepanjang y. Mari kita asumsikan garis kemiringan positif dan menarik dari x1, y1 ke x2, y2.

{slope = m = dy/dx

if m <= 1.0

let x_step = 1 {dx = 1, dy = 0 or 1} 

else {m > 1.0}

let y_step = 1 {dy = 1, x_step = 0 or 1 

Ingat: selalu langkah sepanjang delta terpanjang.

{m <= 1.0} for x_step = 1, dy = m = yi+1 - yi -> yi+1 = yi + m

{m > 1} for y_step = 1 m = 1/dx => dx = 1/m => xi+1 = xi + 1/m (m> 1

If, instead, we draw from x2 , y2 to x1, y1 then:

a.       dx = -1 yi+1 = yi -m or

b.      dy = -1 xi+1 = xi - 1/m

Untuk sejalan dengan slopeslope <0,0 dan gambar dari x1, y1 ke x2, y2, yaitu, kiri ke kanan maka:

if |m| < 1 then 

let dx = 1 and yi+1 = yi + m 

else {|m| ³ 1} 

 let dy = -1 and xi+1 = xi -1/m 

if draw from x2, y2 to x1, y1 (right to left) then: 

 if |m| < 1 then let dx = -1 yi+1 = yi -m jika | m | <1 

else {|m| ³ 1} dy = 1 xi+1 = xi + 1/

Algoritma DDA lengkap :

procedure DDA( x1, y1, x2, y2: integer); 

var

  dx, dy, steps: integer; 

  x_inc, y_inc, x, y: real; 

begin 

  dx := x2 - x1; dy := y2 - y1;

  if abs(dx) > abs(dy) then

     steps := abs(dx); {steps is larger of dx, dy} 

  else 

     steps := abs(dy); 

  x_inc := dx/steps; y_inc := dy/steps; x_inc: = dx /

  {either x_inc or y_inc = 1.0, the other is the slope} 

  x:=x1; y:=y1; 

  set_pixel(round(x), round(y)); 

  for i := 1 to steps do for i:

    begin 

      x := x + x_inc; 

      y := y + y_inc; 

      set_pixel(round(x), round(y)); 

    end; 

end; {DDA}

DDA bekerja dengan menggunakan koordinat pixel dihitung terakhir dan lereng. From Dari  the previous section you can easily compute how far to move over (δx) or bagian sebelumnya Anda dapat dengan mudah menghitung berapa jauh untuk bergerak ke atas (δx) atau  how far to move up (δy) on the screen to draw your next point on the line. seberapa jauh untuk bergerak ke atas (δy) pada layar untuk menarik titik berikutnya di telepon.

δy = m * δx

Mengingat bahwa Anda sudah tahu Anda ingin memindahkan lebih dari (δx) atau atas (δy) tertentu  number of units (for computers these units equate to pixels on the screen) jumlah unit (untuk komputer unit-unit ini sama dengan piksel pada layar)  you then plug these values into one of the two equations along with the slope Anda kemudian plug nilai ini ke satu dari dua persamaan bersama dengan kemiringan  and solve. dan memecahkan.

DDA algoritma yang dapat kemudian dibagi ke dalam kasus-kasus berikut :

1.       Sebuah baris dengan kemiringan positif dan 0 ≤ m ≤ 1 maka anda dapat mengambil δx = 1 dan menghitung nilai-nilai y berturut-turut menggunakan..

^y  k+ = ^Y k +M

Catatan: ingat bahwa karena m adalah bilangan bulat belum tentu Anda harus  membulatkan hasi.l anda.

2.       Sebuah baris dengan kemiringan positif dan m> 1 maka anda menghitung x bukan  y  dan mengambil  δy = 1 dan menghitung berurutan x nilai menggunakan .

^Xk+1=^Xk+1/m

Hal yang sama berlaku di sini Anda harus bundar!

Kedua perhitungan ini dapat menggeneralisasi untuk baris dengan kemiringan negatif sehingga Anda  Kasus 1 dapat menggunakan ketika | m | ≤ 1 dan kasus 2 saat | m |> 1.