Wie zeichnet man eine gerade Linie zwischen zwei Punkten in einer Bitmap?

17

Ich spiele mit Höhenkarten (Bitmaps) herum und versuche, einige meiner eigenen in meinem Spiel zu erstellen. Dazu muss ich einige grundlegende Zeichenmethoden implementieren. Ich habe schnell gemerkt, dass das Zeichnen von geraden Linien nicht so einfach ist, wie ich dachte.

Es ist ganz einfach, wenn Ihre Punkte eine X- oder Y-Koordinate haben oder wenn sie so ausgerichtet sind, dass Sie eine perfekt diagonale Linie zeichnen können. Aber in allen anderen Fällen ist es schwieriger.

Mit welchem ​​Algorithmus bestimmen Sie, welche Pixel gefärbt werden müssen, damit eine "gerade" Linie entsteht?

Fredrik Boston Westman
quelle

Antworten:

25

Ich denke, was Sie brauchen, ist Bresenhams Linienalgorithmus .

Soweit ich mich erinnere, wird es verwendet, um zu bestimmen, welcher Punkt gefärbt werden soll, und nicht, wie viel jeder Punkt gefärbt werden soll.

Vaillancourt
quelle
21

Mit dem Linienalgorithmus von Bresenham können Sie bestimmen, welche Punkte in einem Rastergitter geplottet werden sollen, um eine angemessene visuelle Approximation eines Liniensegments zu erzielen.

Der Algorithmus deckt die Rasterung einer Linie ab, die durch den Ursprung und die Endpunkte in einem Koordinatenraum definiert ist, in dem sich der Ursprung oben links befindet. Es wird angenommen, dass Ganzzahlkoordinaten auf Pixelmitten abgebildet werden. Insbesondere deckt die Grundform des Algorithmus nur einen Oktanten des Kreises ab: denjenigen, bei dem die Linie zunehmende X- und Y-Koordinaten aufweist, aber eine negative Steigung mit einem Absolutwert von weniger als 1. Alle anderen Oktanten können als einfache Transformationen davon abgeleitet werden Grundoktant.

Im Pseudocode sieht diese Grundform so aus:

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
        }
    }
}

Die Rosetta Code-Website enthält eine Sammlung konkreter Implementierungen in verschiedenen Sprachen .

Sie könnten auch an Wus Linienalgorithmus interessiert sein , der Anti-Aliasing ermöglicht.

Ken Williams
quelle
3
Ich möchte nur Passanten warnen, den enthaltenen Pseudocode nicht aus dem Kontext zu nehmen, da er nicht sofort funktioniert. Es funktioniert nur für einen bestimmten Oktanten (lesen Sie den Rest der Antwort). Wenn Sie Code zum Kopieren / Einfügen suchen, klicken Sie auf den Link zur Rosetta Code-Website.
Congusbongus
1
Für alle, die die c-Version von Wus Zeilenalgorithmus ausprobieren möchten, möchte ich Sie warnen, dass er unvollständig ist. Im _dla_changebrightness wenn Sie die Helligkeit ändern Sie es ändern müssen aus: to->red = br * (float)from->red;auf diese folgendes: to->red = (br * (float)from->red) + ((1-br) * (float) to->red);. Machen Sie dasselbe für Grün und Blau
Fredrik Boston Westman
2

Hier finden Sie eine äußerst einfache Methode zum Zeichnen von Linien. Die Funktion kann leicht geändert werden, um in Projekten verwendet zu werden.

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
quelle