Gambar garis cepat antialiased

11

Algoritma garis Bresenham adalah cara menggambar garis lurus hanya menggunakan operasi integer cepat (penjumlahan, pengurangan, dan perkalian dengan 2). Namun, itu menghasilkan garis alias. Apakah ada cara cepat yang sama untuk menggambar garis antialiased?

antialiasing pixel-graphics line-drawing Menandai
sumber
1
Beberapa pertanyaan ... apakah Anda melakukan logika menggambar pada CPU atau GPU? Juga, apakah Anda mencari algoritma berbasis integer atau floating point?
Alan Wolfe
5
@AlanWolfe, algoritma integer pada CPU - lingkungan yang sama dengan algoritma Bresenham dirancang untuk.
Markus
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm adalah yang klasik, meskipun halaman wikipedia setengah matang dan saya tidak memiliki akses ke kertas. Ini terasa seperti pertanyaan malas, karena cukup mudah untuk menemukan ini dengan melakukan beberapa googling dasar.
yuriks
2
Hanya berpikir keras, saya pikir itu harus mudah untuk beradaptasi Bresenham untuk menggambar garis multi-pixel-tebal. Kemudian Anda dapat melakukan antialiasing dengan menghitung jarak setiap pusat piksel dari garis ideal matematika, dan menerapkan beberapa fungsi falloff.
Nathan Reed
2
Saya tidak dapat menandai komentar sebagai benar.
Tandai

Jawaban:

9

Apakah ada cara cepat yang sama untuk menggambar garis antialiased?

Tidak, karena menurut definisi, garis anti-alias menyentuh lebih banyak piksel. Algoritma seperti itu akan lebih lambat.

Dalam rasterizer perangkat lunak, cara di mana-mana untuk menggambar garis anti-alias adalah algoritma garis Xiaolin Wu . Ini tidak sulit untuk diterapkan, dan lagi pula ada pseudocode berkualitas tinggi yang luar biasa pada tautan itu.

Dalam pipa raster perangkat keras, garis primitif diperluas ke quad-layar-ruang secara default (atau disediakan pengguna) geometri shader, dan kemudian digambar sebagai dua segitiga, yang kemudian dapat anti-alias dengan cara biasa.

Dalam sebuah raytracer, ada berbagai opsi. Ada baiknya memikirkan bagaimana Anda benar-benar ingin menggambar objek 1D. Mungkin sebagai silinder (woo shadows!). Perhatikan bahwa ini memperkenalkan masalah perspektif / foreshortening yang mungkin (atau mungkin tidak) menjadi apa yang Anda inginkan. Tidak ada generalisasi yang jelas. Kemudian, jelas, apa pun yang Anda lakukan, Anda hanya mengunggahnya.

Imallett
sumber
"Dan lagi pula ada pseudocode berkualitas tinggi yang luar biasa pada tautan itu", saya tidak setuju. Kode pseudo itu kemungkinan bukan implementasi yang tepat dari algoritma Wu meskipun tampaknya apa yang digunakan di tempat yang tak terhitung jumlahnya di web. Algoritma asli Wu menarik dari kedua ujung ke dalam ke arah pusat dan sebenarnya lebih cepat daripada Bresenham karena melakukan sekitar setengah operasi sebanyak walaupun menulis ke lebih banyak piksel. Saya berbicara tentang algoritma aktual Wu, bukan yang diposting di artikel wikipedia tertaut.
Octopus
@Octopus [Mengungkapkan skeptisisme yang samar-samar, terutama pada bit yang lebih cepat, tetapi tidak memiliki konteks untuk membantah atau mengkonfirmasi — jika demikian, sumber, koreksi, dan pengeditan tentu saja diterima.]
imallett
Tergantung pada apa yang Anda hitung. Jika Anda menggambar dari kedua ujung ke dalam, maka algoritma Wu melakukan setengah perhitungan tetapi dua kali lebih banyak pixel yang menulis. Lihat Tabel 1 di kertas Wu, ditautkan di Wikipedia. Jadi jika penulisan pixel mahal, seperti halnya ketika menulis ke TFT pada koneksi serial, maka algoritma Wu lebih mahal daripada Bresenham. (Harus saya akui saya tidak mengerti mengapa algoritma Bresenham tidak dapat menggunakan simetri juga.)
Jan-Åke Larsson
1
Tapi saya setuju dengan @Octopus, bahkan menerima "menggambar dari satu ujung ke ujung yang lain", kodesemu adalah algoritma Wu hanya jika bilangan bulat aritmatika digunakan di seluruh. Kode yang saya lihat online menggunakan aritmatika floating-point, yang merupakan perubahan signifikan. Dalam makalah Wu, algoritme hanya menggunakan aritmatika integer (atau aritmatika titik tetap).
Jan-Åke Larsson