Algoritma Garis Bresenham
Algoritma garis
Bresenham adalah suatu algoritma yang menentukan untuk membentuk
pendekatan dekat dengan garis lurus antara dua poin yang diberikan .
Hal ini biasanya digunakan untuk menggambar garis pada layar komputer
, karena hanya menggunakan penambahan integer, pengurangan dan
pergeseran bit , yang semuanya beroperasi sangat murah dalam
arsitektur komputer standar. Ini adalah salah satu algoritma paling
awal dikembangkan di bidang komputer grafis . Sebuah ekstensi kecil
dengan algoritma asli juga berhubungan dengan lingkaran gambar
.Sedangkan algoritma seperti algoritma Wu juga sering digunakan dalam grafis komputer modern karena mereka dapat mendukung antialiasing , kecepatan dan kesederhanaan algoritma garis Bresenham berarti bahwa masih penting . Algoritma ini digunakan dalam perangkat keras seperti plotters dan dalam chip grafis dari kartu grafis modern . Hal ini juga dapat ditemukan di banyak perangkat lunak perpustakaan grafis . Karena algoritma ini sangat sederhana , sering dilaksanakan baik dalam firmware atau perangkat keras grafis dari kartu grafis modern .
Label " Bresenham " digunakan hari ini untuk seluruh keluarga algoritma memperluas atau memodifikasi algoritma Bresenham itu asli . Lihat referensi lebih lanjut di bawah ini.
A. History
Algoritma
ini dikembangkan oleh Jack Elton Bresenham pada tahun 1962 di IBM .
Pada tahun 2001 Bresenham menulis: [ 1 ]
Saya bekerja di lab komputasi di IBM San Jose pengembangan laboratorium . Sebuah plotter Calcomp telah dilampirkan ke IBM 1401 melalui 1407 mesin tik konsol . [ Algoritma ] telah digunakan produksi pada musim panas 1962 , mungkin satu bulan atau lebih sebelumnya . Program pada masa itu bebas dipertukarkan antara perusahaan sehingga Calcomp ( Jim Newland dan Calvin Hefte ) memiliki salinan . Ketika saya kembali ke Stanford pada musim gugur tahun 1962, saya menempatkan salinan di Stanford comp perpustakaan pusat . Penjelasan dari garis gambar rutin diterima untuk presentasi di 1963 ACM konvensi nasional di Denver , Colorado . Ini adalah tahun di mana tidak ada proses diterbitkan , hanya agenda speaker dan topik isu Komunikasi ACM . Seseorang dari IBM Systems Journal meminta saya setelah saya membuat presentasi saya jika mereka bisa menerbitkan kertas . Saya gembira menyetujui , dan mereka dicetak itu pada tahun 1965 .
Algoritma Bresenham yang kemudian dimodifikasi untuk menghasilkan lingkaran , algoritma yang dihasilkan yang kadang-kadang dikenal sebagai " lingkaran algoritma Bresenham " atau algoritma lingkaran titik tengah .
Saya bekerja di lab komputasi di IBM San Jose pengembangan laboratorium . Sebuah plotter Calcomp telah dilampirkan ke IBM 1401 melalui 1407 mesin tik konsol . [ Algoritma ] telah digunakan produksi pada musim panas 1962 , mungkin satu bulan atau lebih sebelumnya . Program pada masa itu bebas dipertukarkan antara perusahaan sehingga Calcomp ( Jim Newland dan Calvin Hefte ) memiliki salinan . Ketika saya kembali ke Stanford pada musim gugur tahun 1962, saya menempatkan salinan di Stanford comp perpustakaan pusat . Penjelasan dari garis gambar rutin diterima untuk presentasi di 1963 ACM konvensi nasional di Denver , Colorado . Ini adalah tahun di mana tidak ada proses diterbitkan , hanya agenda speaker dan topik isu Komunikasi ACM . Seseorang dari IBM Systems Journal meminta saya setelah saya membuat presentasi saya jika mereka bisa menerbitkan kertas . Saya gembira menyetujui , dan mereka dicetak itu pada tahun 1965 .
Algoritma Bresenham yang kemudian dimodifikasi untuk menghasilkan lingkaran , algoritma yang dihasilkan yang kadang-kadang dikenal sebagai " lingkaran algoritma Bresenham " atau algoritma lingkaran titik tengah .
Algoritma
Bresenham dapat diartikan sebagai sedikit dimodifikasi DDA
(menggunakan 0,5 sebagai ambang kesalahan bukan 0, yang diperlukan
untuk non-tumpang tindih poligon rasterizing).
Prinsip menggunakan kesalahan tambahan di tempat operasi divisi memiliki aplikasi lain di grafis. Hal ini dimungkinkan untuk menggunakan teknik ini untuk menghitung U, V koordinat selama raster scan tekstur poligon dipetakan [rujukan?]. The voxel heightmap mesin software-render terlihat di beberapa game PC juga digunakan prinsip ini.
Bresenham juga menerbitkan Run-slice (sebagai lawan Run-Length) algoritma komputasi. Perpanjangan dengan algoritma yang menangani garis tebal diciptakan oleh Alan Murphy di IBM.
Prinsip menggunakan kesalahan tambahan di tempat operasi divisi memiliki aplikasi lain di grafis. Hal ini dimungkinkan untuk menggunakan teknik ini untuk menghitung U, V koordinat selama raster scan tekstur poligon dipetakan [rujukan?]. The voxel heightmap mesin software-render terlihat di beberapa game PC juga digunakan prinsip ini.
Bresenham juga menerbitkan Run-slice (sebagai lawan Run-Length) algoritma komputasi. Perpanjangan dengan algoritma yang menangani garis tebal diciptakan oleh Alan Murphy di IBM.
 |
| Ilustrasi hasil algoritma garis Bresenham itu. (0,0) adalah di sudut kiri atas grid, (1,1) berada di ujung kiri atas baris dan (11, 5) berada di ujung kanan bawah garis. |
- Penurunan
Untuk mendapatkan
algoritma Bresenham, dua langkah yang harus ditempuh. Langkah pertama
adalah mengubah persamaan garis dari bentuk lereng-intercept khas
menjadi sesuatu yang berbeda, dan kemudian menggunakan persamaan ini
baru untuk garis untuk menarik garis berdasarkan gagasan akumulasi
kesalahan
Tidak ada komentar:
Posting Komentar