Comment tracer une ligne droite entre deux points dans une image bitmap?

Je joue avec des cartes de hauteur (bitmaps), j'essaie de créer certaines des miennes dans mon jeu, et pour cela, je dois implémenter quelques méthodes de dessin de base. J'ai rapidement réalisé que dessiner des lignes droites n'était pas aussi basique que je le pensais.

C'est simple si vos points partagent une coordonnée X ou Y, ou s'ils sont alignés afin que vous puissiez dessiner une ligne parfaitement diagonale. Mais dans tous les autres cas, c'est plus délicat.

Quel algorithme utilisez-vous pour déterminer quels pixels doivent être colorés pour qu'il devienne une ligne "droite"?

Je pense que ce dont vous avez besoin est l' algorithme de ligne de Bresenham .

D'après ce dont je me souviens, il est utilisé pour déterminer quel point doit être coloré, pas combien chaque point doit être coloré.

L'algorithme de ligne de Bresenham peut être utilisé pour déterminer les points d'une grille raster à tracer afin d'obtenir une approximation visuelle appropriée d'un segment de ligne.

L'algorithme couvre la pixellisation d'une ligne définie par l'origine et les extrémités dans un espace de coordonnées où l'origine est en haut à gauche. Les coordonnées entières sont supposées correspondre aux centres des pixels. Notamment, la forme de base de l'algorithme ne couvre qu'un octant du cercle: celui où la ligne a des coordonnées X et Y croissantes mais une pente négative avec une valeur absolue inférieure à 1. Tous les autres octants peuvent être dérivés comme de simples transformations de ce octant de base.

En psuedocode, ce formulaire de base ressemble à:

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

Le site Web de Rosetta Code contient une collection d'implémentations concrètes dans une variété de langues .

Vous pouvez également être intéressé par l'algorithme de ligne de Wu , qui permet l'anti-aliasing.

Voici une manière extrêmement simple de dessiner des lignes. La fonction peut facilement être modifiée pour être utilisée dans des projets.

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