ALGORITMA BRESENHAM
Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan, dengan cara menggantikan operasi bilangan riel perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Cara menentukan garis dengan algoritma bresenham :
1. Tentukan koordinat awal garis (x0,y0)
2. tentukan koordinat akhir garis (x1,y1)
3. Hitung jarak mendatar ke 2 titik (dx)
Dx=x1-x0
4. Hitung jarak mendatar ke 2 titik (dx)
Dy=y1-y0
5. Tentukan faktor pembagi (mencari yg lebih panjang)
Apakah dx>dy,bila ya
Step=dx
Bila tidak
Step=dy
6. Hitung faktor penambah ke koordinat mendatar dan vertikal titik berikut (x_tambah,y_tambah)
X_tambah=dx/step
Y_tambah=dy/step
7. Buat loop mulai titik ke 1 sampai titik ke step
For k=1 to step
8. Hitung koodinat titik berikutnya
X=x+x_tambah
Y=y+y_tambah
9. gambar pikxel pada koordinat (x,y)
Catatan : koordinat x,y harus bulat (integer), sehingga hasil dari perhitungan diatas harus diinteger-kan
10. Ulangi langkah ke 7, dan setetrrsnya sampai titik ke step
Berikut pseudocode untuk algoritma bresenham
x0=10;y0=10;
x1=100;y1=200;
dx=x1-x0;
dy=y1-y0;
x=float(x0);y=float(y0);
if (dx>dy)
step=dx;
else
step=dy;
x_tambah=(float) dx/step;
y_tambah=(float) dy/step ;
int xx,yy;
for (k=0;k
{
x+=x_tambah;
y+=y_tambah;
Canvas->Pixels[int(x)][int(y)]=clRed;
}
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
DDA (Digital Defferential Analyzer)
Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritam yang umum adalah DDA dan Bresenham.
Berikur ini adalah algoritma DDA
1. Tentukan 2 buah titik.
2. Tentukan yang menjadi titik awal (X0,Y0) dan titik akhir (X1,Y1).
3. Hitung Dx dan DyDx = X1-X0 dan Dy = Y1 – Y0
4. Bandingkan Abs(Dx) dan Abs(Dy)Jika Abs(Dx) > Abs(Dy) makaSteps = Abs(Dx) bila tidak Steps = Abs(Dy)
5. Hitung penambahan koordinat pixel, yaitu:X_increment = dx/steps, danY_increment = dy/steps.
6. Koordint selanjutnya, yaituX+X_incrementY+Y_increment
7. Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X1, Y = Y1
IMPLEMENTASI DDA dan BRESENHAM
UNTUK ANTI-ALIASING
APA ITU ANTI-ALIASING
Seperti teori diatas bahwa garis merupakan kumpulan titik yang saling terhubung. Pada pembahasan sebelumnya kelompok kami menceritakan sebuah efek yang bernama Tessellation yang digunakan untuk membuat gambar detail menjadi semakin realistik. Kali ini kelompok kami akan sedikit menjelaskan teknologi yang pada umumnya sering dipakai dalam dunia games yaitu Implementasi Dari DDA dan Bresenham.
Selain adanya tesselltion yang digunakan untuk membuat gambar menjadi lebih realistik ada juga yang namanya anti aliasing yaitu memperhalus tampilan gambar dengan membuat sejumlah titik yang membentuk garis seperti yang ada pada gambar diatas sehingga bisa mengurangi jaggies pada sebuah games.
Konsep DDA & Bresenham dipakai untuk menghilangkan Jaggies dalam sebuah games. Terkadang merasa kurang nyaman jika menonton film layar lebar atau bermain games tanpa anti aliasing karena adanya belahan atau jaggies ( sejumlah titik garis yang tidak terdistribusi dengan wajar).
Lihat gambar dibawah ini perbedaan penggunaan anti aliasing dan non anti aliasing :
Gambar sebelah kiri memperlihatkan banyaknya jaggies dan disebelah kanan memperlihatkan berkurangnya jaggies karena dibantu oleh teknologi Anti Aliasing yang diterapkan melalui konsep DDA Bresenham.
CARA KERJA DDA & BRESENHAM
UNTUK ANTI ALIASING
Seperti biasanya sesuai dengan konsep DDA bahwa garis adalah kumpulan titik maka untuk mengubahnya juga harus dilakukan pembentukan garis oleh banyaknya titik dan kembali kepada pembuatnya ada yang dihubungkan dengan konsep fisika mekanika ada yang secara matematis. Gambar diatas hanyalah contoh pembentukan garis secara sederhana saja. Setelah titik-titik terbuat maka akan dilanjutkan kedalam tahap penarikan garis dan lihat gambar dibawah ini :
Untuk membentuk sebuah anti aliasing DDA di convert menjadi dua bagian teknis yaitu Sebut saja namanya (Wave area dan Frequency Area) pertama setelah sebuag titik dibentuk dan dihubungkan sehingga membentuk garis maka ada yang namanya sampling image untuk dirender yang kemudian diberikan ke daerah Frequency untuk diubah menjadi algoritma diskrit.
Setelah diubah menjadi algoritma diskrit maka akan dibentuk garis lingkar untuk menghitung seberapa besar jaggies yang akan dipersempit yang intinya bagaimana sejumlah titik sembarang membentuk garis baru untuk memperhalus tampilannya.
Setelah dihitung lingkar jaggiesnya maka akan transformasikan menjadi sebuah titik pixel yang membentuk resolusi baru yang akan diberikan kembali untuk menimpa jaggies yang lama sehingga garisnya lebih sempurna sehingga akan dikembalikan lagi ke daerah wave denganukuran sampling yang lebih kecil lagi sehingga efek jaggiesnya berkurang karena sampling kecil yang baru menutupi sampling besar dengan jumlah yang banyak sehingga gambar terlihat lebih halus dan jernih.
Sekian materi yang kami sampaikan semoga bermanfaat sampai bertemu di episode menarik selanjutnya.
http://www.patentstorm.us/patents/5570463/description.html
http://slidefinder.net/s/scan_conversion_dda_line_drawing/12090680
http://www.pantherproducts.co.uk/Articles/Graphics/anti_aliasing.shtml
Tidak ada komentar:
Posting Komentar