Bagaimana Anda menggambar garis lurus antara dua titik dalam bitmap?

17

Saya bermain-main dengan peta ketinggian (bitmap), mencoba membuat beberapa milik saya sendiri dalam permainan saya, dan untuk itu saya perlu menerapkan beberapa metode menggambar dasar. Saya dengan cepat menyadari bahwa menggambar garis lurus tidak se dasar yang saya kira.

Ini sederhana jika poin Anda berbagi koordinat X atau Y, atau jika mereka sejajar sehingga Anda dapat menggambar garis diagonal sempurna. Tetapi dalam semua kasus lain itu lebih sulit.

Algoritma apa yang Anda gunakan untuk menentukan piksel apa yang perlu diwarnai agar menjadi garis "lurus"?

c++ rasterization Fredrik Boston Westman
sumber

Jawaban:

25

Saya pikir yang Anda butuhkan adalah algoritma garis Bresenham .

Dari apa yang saya ingat itu digunakan untuk menentukan apa yang hal harus berwarna, tidak berapa banyak setiap titik harus berwarna.

Vaillancourt
sumber
21

Algoritma garis Bresenham dapat digunakan untuk menentukan titik mana dalam raster grid untuk plot untuk mencapai pendekatan visual yang sesuai dari segmen garis.

Algoritma ini mencakup rasterisasi garis yang ditentukan oleh titik asal dan titik akhir dalam ruang koordinat di mana titik asal berada di kiri atas. Koordinat integer dianggap memetakan ke pusat piksel. Khususnya, bentuk dasar dari algoritma hanya mencakup satu oktan dari lingkaran: yang mana garis memiliki peningkatan koordinat X dan Y tetapi kemiringan negatif dengan nilai absolut kurang dari 1. Semua oktan lainnya dapat diturunkan sebagai transformasi sederhana dari ini oktan dasar.

Dalam psuedocode, bentuk dasar ini terlihat seperti:

void DrawLine(Point origin, Point endpoint, Bitmap surface) {
    deltaX = endpoint.X - origin.X
    deltaY = endpoint.Y - origin.Y
    error = 0

    // Note the below fails for completely vertical lines.
    deltaError = absoluteValue(deltaY / deltaX)

    Y = origin.Y
    for (X from origin.X to endpoint.X) {
        surface.PlotPixel(X, Y)
        error = error + deltaError 
        if (error >= 0.5) {
            ++Y;
            error -= 1.0
        }
    }
}

Situs web Kode Rosetta memiliki koleksi implementasi konkret dalam berbagai bahasa .

Anda juga mungkin tertarik pada algoritma garis Wu , yang memungkinkan untuk anti-aliasing.

Ken Williams
sumber
3
Hanya ingin memperingatkan orang yang lewat untuk tidak mengambil pseudocode yang disertakan di luar konteks, karena tidak akan berfungsi di luar kotak. Ini hanya berfungsi untuk oktan tertentu (baca sisa jawabannya). Jika Anda mencari kode untuk disalin / ditempel, coba tautan ke situs web Kode Rosetta.
congusbongus
1
Bagi siapa pun yang ingin melihat versi c dari algoritma garis Wu, saya ingin memperingatkan Anda bahwa itu tidak lengkap. Dalam _dla_changebrightness ketika Anda mengubah kecerahan Anda perlu mengubah dari: to->red = br * (float)from->red;ke berikut ini: to->red = (br * (float)from->red) + ((1-br) * (float) to->red);. Lakukan hal yang sama untuk hijau dan biru dengan hormat
Fredrik Boston Westman
2

Berikut ini cara menggambar garis yang sangat sederhana. Fungsi dapat dengan mudah diubah untuk digunakan dalam proyek.

void draw_line(float x0, float y0, const float& x1, const float& y1)
{
    float x{x1 - x0}, y{y1 - y0};
    const float max{std::max(std::fabs(x), std::fabs(y))};
    x /= max; y /= max;
    for (float n{0}; n < max; ++n)
    {
        // draw pixel at ( x0, y0 )
        x0 += x; y0 += y;
    }
}
cppxor2arr
sumber