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). Langkah-langkah menentukan garis dengan algoritma DDA sebagai berikut :
Prinsip algoritma ini adalah mengambil nilai integer terdekat dengan jalur garis berdasarkan atas sebuah titik yang telah ditentukan sebelumnya(titik awal garis). Langkah-langkah menentukan garis dengan algoritma DDA sebagai berikut :
- Tentukan 2 buah titik
- Tentukan yang menjadi titik awal (X0, Y0) dan titik akhir (X1, Y1)
- Hitung Δx dan Δy Δx = X1 – X0 dan Δy = Y1 – Y0
- Bandingkan absolut (Δx) dan absolut (Δy)
Jika absolute (Δx) > absolut (Δy), maka Steps = absolute (Δx)
bila tidak, steps = absolut (Δy)
- Hitung penambahan koordinat pixel, yaitu:
X_increment = Δx/Steps
Y_increment = Δy/Step
- Koordinat selanjutnya yaitu:
X = X + X_increment
Y = Y + Y_increment
- Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut
- Ulangi langkah diatas untuk posisi selanjutnya sampai X = X1, Y= Y1
Algoritma Midpoint
Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yang lebih sedikit dibandingkan dengan algoritma yang menggunakan operasi bilangan riel.
Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yang lebih sedikit dibandingkan dengan algoritma yang menggunakan operasi bilangan riel.
Implementasi ke dalam bahasa pemrograman C dari kedua macam algoritma diatas, menunjukkan bahwa waktu komputasi algoritma midpoint lebih cepat sebesar 8 kali pada pembuatan garis lurus, dan lebih cepat sebesar 15 kali pada penggambaran lingkaran, dibandingkan dengan waktu komputasi algoritma yang menggunakan dasar operasi bilangan riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi algoritma yang Breserham telah menggunakan dasar operai bilangan integer juga.
Persamaan garis lurus yang telah dinyatakan dalam persamaan (1) dapat dinyatakan dalam fungsi x,y berikut.
f(x, y) = ax + by + c = 0 (4)
Fungsi f(x,y) dalam persamaan (4), akan memberikan nilai 0 pada setiap titik yang terletak pada garis, dan bernilai positip pada setiap titik yang terletak dibawah garis, dan bernilai negatif pada setiap titik yang terletak diatas garis.
Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q, sebaliknya piksel berikutnya adalah P.
Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q, sebaliknya piksel berikutnya adalah P.
g(x, y) = f(xn + 1, yn + 1/2) (5)
Fungsi g(x,y) persamaan (5) merupakan variabel penentu, dengan mengevaluasi g (x, y) dapat ditentukan piksel berikutnya yang mana berdasarkan tanda plus atau minus dari hasil fungsi g(x,y).
Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai sebelumnya. Untuk setiap piksel, increment sederhana (ΔG) dipakai sebagai variabel penentu. Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan menggunakan persamaan 4 dan persamaan 5.
ΔG = a * ΔX + b * ΔY (6)
Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai sebelumnya. Untuk setiap piksel, increment sederhana (ΔG) dipakai sebagai variabel penentu. Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan menggunakan persamaan 4 dan persamaan 5.
ΔG = a * ΔX + b * ΔY (6)
Dimana ΔX dan ΔY adalah increment yang dipakai pada x dan y, yang bernilai 0 atau 1. Bila bergeser 1 piksel ke kanan :
ΔG1 = a (7)
Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.
Δ2 = a + b (8)
Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a) atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan langkah-langkah sebagai-berikut:
ΔG1 = a (7)
Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.
Δ2 = a + b (8)
Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a) atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan langkah-langkah sebagai-berikut:
- Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
- Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a) pada variabel penentu.
- Plot piksel pada posisi (x, y).
- Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).
Algoritma Xiaolin Wu
Algoritma Xialin Wu diperkenalkan dalam sebuah artikel An Efficient Antialising Technique pada July 1991. Algoritma Bressenham sangat cepat dalam menggambar bentuk garis, tetapi tidak melakukan anti-aliasing (proses menghilangkan atau mengurangi distorsi bergerigi di kurva).
Efek samping yang dihasilkan oleh penggunaan alat display digital untuk penggambaran garis dan kurva adalah objek-objek ini cenderung menjadi kelihatan bergerigi atau seperti tangga (disebut juga ‘jaggies’). Penyimpangan ini disebut dengan aliasing, istilah ini diambil dari teori sampling yang awalnya bertitik berat pada sampling sinyal elektronik seperti gelombang radio, sedangkan proses untuk menghilangkan fenomena demikian disebut antialiasing. Salah satu cara untuk menaikkan sampling rate pada raster system secara sederhana dilakukan dengan menampilkan objek pada resolusi tinggi, akan tetapi walaupun resolusi yang digunakan paling tinggi degnan Teknologi saat ini bentuk gerigi akan tetap kelihatan.
Dengan raster system yang mampu menampilkan lebih dari dua tingkat intensitas atau grayscale, metode antialiasing dapat digunakan untuk modifikasi intensitas pixel. Penyesuaian intensitas dari pixel sepanjang batas primitive dapat menghasilkan batas yang halus dan mengurangi tampilan bergerigi. Teknik sampling pada objek dengan resolusi tinggi dan menampilkannya pada resolusi rendah disebut supersampling. Alternative lain dari supersampling adalah menentukan intensitas pixel dengan menghitung area yang overlap setiap pixel dari suatu objek. Antialiasing dengan menghitung overlap area disebut area sampling.
Sumber :
Tidak ada komentar:
Posting Komentar