Wie wird Bresenhams Linienzeichnungsalgorithmus mit Clipping verwendet?

Question

Wenn Sie eine Linie mit Bresenham line drawing algorithm, zeichnen, bei der die Linie nicht innerhalb der Grenzen der zu schreibenden Bitmap liegt, wäre es sinnvoll, die Ergebnisse so zu beschneiden, dass sie in die achsgerechten Grenzen des zu schreibenden Bildes passen.

Während es möglich ist, zuerst die Linie an das Rechteck zu befestigen, zeichnen Sie dann die Linie. Dies ist nicht ideal, da es oft eine leicht abweichende Neigung zu der Linie (unter der Annahme, dass int-Coords verwendet werden) gibt.

Da dies eine so primitive Operation ist, gibt es Methoden, um die Linie zu beschneiden und gleichzeitig die gleiche Form beizubehalten?

Falls es hilft, here is a reference implementation of the algorithm - es verwendet Int-Coords, die Int/Float-Konvertierung beim Zeichnen der Linie vermeidet.

---

ich einige Zeit damit verbracht in diese suchen:

• Problem im Detail auf virtual-dub's web page beschrieben.
• Possible solution from Alan Tiedemann
  ... obwohl ich Code basierend auf dem Text implementieren müsste - um zu sehen, wie gut es funktioniert.
• Bresenham's Line Generation Algorithm with Built-in Clipping
  (Papier von 1995, konnte nicht das gesamte Dokument finden? - PDF ist eine einzelne Seite ohne den C-Code verweist es, sieht aus wie seine Pay-Walled).

Answer 1

Lassen Sie uns das Problem reframe so können wir sehen, wie Bresenham-Algorithmus wirklich funktioniert ...

Lässt Sie sagen eine meist horizontale Linie zeichnen (die Methode die gleiche für meist vertikal ist, aber mit den Achsen geschaltet) (x0,y0)-(x1,y1):

y = y0 + round((x-x0) * (y1-y0)/(x1-x0)) 

:

Die durchgezogene Linie kann in Abhängigkeit von y in Bezug auf x (alle ganzen Zahlen) beschrieben werden

Dies beschreibt genau jedes Pixel, das Sie beim Zeichnen der vollen Linie malen, und wenn Sie die Linie konsistent schneiden, beschreibt immer noch genau jedes Pixel, das Sie malen werden - Sie wenden es nur auf einen kleineren Bereich von x Werten an.

Wir können diese Funktion mit allen Integer-Mathe berechnen, indem Sie den Divisor und den Rest separat berechnen. Für x1 >= x0 und y1 >= y0 (tut die normalen Transformationen anders):

let dx = (x1-x0); 
let dy = (y1-y0); 
let remlimit = (dx+1)/2; //round up 

rem = (x-x0) * dy % dx; 
y = y0 + (x-x0) * dy/dx; 
if (rem >= remlimit) 
{ 
    rem-=dx; 
    y+=1; 
} 

Bresenham-Algorithmus eine nur eine schnelle Art und Weise ist das Ergebnis dieser Formel inkrementell zu aktualisieren, wie Sie x aktualisieren.

Hier ist, wie wir die Verwendung von inkrementellen Updates machen können von x = xs den Teil der gleichen Linie zu zeichnen x = xe:

let dx = (x1-x0); 
let dy = (y1-y0); 
let remlimit = (dx+1)/2; //round up 

x=xs; 
rem = (x-x0) * dy % dx; 
y = y0 + (x-x0) * dy/dx; 
if (rem >= remlimit) 
{ 
    rem-=dx; 
    y+=1; 
} 
paint(x,y); 
while(x < xe) 
{ 
    x+=1; 
    rem+=dy; 
    if (rem >= remlimit) 
    { 
     rem-=dx; 
     y+=1; 
    } 
    paint(x,y); 
} 

Wenn Sie gegen 0 zu Ihren Rest Vergleiche tun möchten, können Sie versetzt es gerade am Anfang kann:

let dx = (x1-x0); 
let dy = (y1-y0); 
let remlimit = (dx+1)/2; //round up 

x=xs; 
rem = ((x-x0) * dy % dx) - remlimit; 
y = y0 + (x-x0) * dy/dx; 
if (rem >= 0) 
{ 
    rem-=dx; 
    y+=1; 
} 
paint(x,y); 
while(x < xe) 
{ 
    x+=1; 
    rem+=dy; 
    if (rem >= 0) 
    { 
     rem-=dx; 
     y+=1; 
    } 
    paint(x,y); 
} 

Answer 2

kann Bresenham-Algorithmus verwendet werden, wobei Werte berücksichtigt Clipping, basierend auf dem Papier durch Kuzmin & Jewgeni P:

Der Vollständigkeit halber ist hier eine funktionierende Version des Algorithmus aufgeführt, eine einzelne Python-Funktion, obwohl sie nur ganzzahlige Arithmetik verwendet - also leicht in andere Sprachen portiert werden kann.

def plot_line_v2v2i(
    p1, p2, callback, 
    clip_xmin, clip_ymin, 
    clip_xmax, clip_ymax, 
): 
    x1, y1 = p1 
    x2, y2 = p2 

    del p1, p2 

    # Vertical line 
    if x1 == x2: 
     if x1 < clip_xmin or x1 > clip_xmax: 
      return 

     if y1 <= y2: 
      if y2 < clip_ymin or y1 > clip_ymax: 
       return 
      y1 = max(y1, clip_ymin) 
      y2 = min(y2, clip_ymax) 
      for y in range(y1, y2 + 1): 
       callback(x1, y) 
     else: 
      if y1 < clip_ymin or y2 > clip_ymax: 
       return 
      y2 = max(y2, clip_ymin) 
      y1 = min(y1, clip_ymax) 
      for y in range(y1, y2 - 1, -1): 
       callback(x1, y) 
     return 

    # Horizontal line 
    if y1 == y2: 
     if y1 < clip_ymin or y1 > clip_ymax: 
      return 

     if x1 <= x2: 
      if x2 < clip_xmin or x1 > clip_xmax: 
       return 
      x1 = max(x1, clip_xmin) 
      x2 = min(x2, clip_xmax) 
      for x in range(x1, x2 + 1): 
       callback(x, y1) 
     else: 
      if x1 < clip_xmin or x2 > clip_xmax: 
       return 
      x2 = max(x2, clip_xmin) 
      x1 = min(x1, clip_xmax) 
      for x in range(x1, x2 - 1, -1): 
       callback(x, y1) 
     return 

    # Now simple cases are handled, perform clipping checks. 
    if x1 < x2: 
     if x1 > clip_xmax or x2 < clip_xmin: 
      return 
     sign_x = 1 
    else: 
     if x2 > clip_xmax or x1 < clip_xmin: 
      return 
     sign_x = -1 

     # Invert sign, invert again right before plotting. 
     x1 = -x1 
     x2 = -x2 
     clip_xmin, clip_xmax = -clip_xmax, -clip_xmin 

    if y1 < y2: 
     if y1 > clip_ymax or y2 < clip_ymin: 
      return 
     sign_y = 1 
    else: 
     if y2 > clip_ymax or y1 < clip_ymin: 
      return 
     sign_y = -1 

     # Invert sign, invert again right before plotting. 
     y1 = -y1 
     y2 = -y2 
     clip_ymin, clip_ymax = -clip_ymax, -clip_ymin 

    delta_x = x2 - x1 
    delta_y = y2 - y1 

    delta_x_step = 2 * delta_x 
    delta_y_step = 2 * delta_y 

    # Plotting values 
    x_pos = x1 
    y_pos = y1 

    if delta_x >= delta_y: 
     error = delta_y_step - delta_x 
     set_exit = False 

     # Line starts below the clip window. 
     if y1 < clip_ymin: 
      temp = (2 * (clip_ymin - y1) - 1) * delta_x 
      msd = temp // delta_y_step 
      x_pos += msd 

      # Line misses the clip window entirely. 
      if x_pos > clip_xmax: 
       return 

      # Line starts. 
      if x_pos >= clip_xmin: 
       rem = temp - msd * delta_y_step 

       y_pos = clip_ymin 
       error -= rem + delta_x 

       if rem > 0: 
        x_pos += 1 
        error += delta_y_step 
       set_exit = True 

     # Line starts left of the clip window. 
     if not set_exit and x1 < clip_xmin: 
      temp = delta_y_step * (clip_xmin - x1) 
      msd = temp // delta_x_step 
      y_pos += msd 
      rem = temp % delta_x_step 

      # Line misses clip window entirely. 
      if y_pos > clip_ymax or (y_pos == clip_ymax and rem >= delta_x): 
       return 

      x_pos = clip_xmin 
      error += rem 

      if rem >= delta_x: 
       y_pos += 1 
       error -= delta_x_step 

     x_pos_end = x2 

     if y2 > clip_ymax: 
      temp = delta_x_step * (clip_ymax - y1) + delta_x 
      msd = temp // delta_y_step 
      x_pos_end = x1 + msd 

      if (temp - msd * delta_y_step) == 0: 
       x_pos_end -= 1 

     x_pos_end = min(x_pos_end, clip_xmax) + 1 
     if sign_y == -1: 
      y_pos = -y_pos 
     if sign_x == -1: 
      x_pos = -x_pos 
      x_pos_end = -x_pos_end 
     delta_x_step -= delta_y_step 

     while x_pos != x_pos_end: 
      callback(x_pos, y_pos) 

      if error >= 0: 
       y_pos += sign_y 
       error -= delta_x_step 
      else: 
       error += delta_y_step 

      x_pos += sign_x 
    else: 
     # Line is steep '/' (delta_x < delta_y). 
     # Same as previous block of code with swapped x/y axis. 

     error = delta_x_step - delta_y 
     set_exit = False 

     # Line starts left of the clip window. 
     if x1 < clip_xmin: 
      temp = (2 * (clip_xmin - x1) - 1) * delta_y 
      msd = temp // delta_x_step 
      y_pos += msd 

      # Line misses the clip window entirely. 
      if y_pos > clip_ymax: 
       return 

      # Line starts. 
      if y_pos >= clip_ymin: 
       rem = temp - msd * delta_x_step 

       x_pos = clip_xmin 
       error -= rem + delta_y 

       if rem > 0: 
        y_pos += 1 
        error += delta_x_step 
       set_exit = True 

     # Line starts below the clip window. 
     if not set_exit and y1 < clip_ymin: 
      temp = delta_x_step * (clip_ymin - y1) 
      msd = temp // delta_y_step 
      x_pos += msd 
      rem = temp % delta_y_step 

      # Line misses clip window entirely. 
      if x_pos > clip_xmax or (x_pos == clip_xmax and rem >= delta_y): 
       return 

      y_pos = clip_ymin 
      error += rem 

      if rem >= delta_y: 
       x_pos += 1 
       error -= delta_y_step 

     y_pos_end = y2 

     if x2 > clip_xmax: 
      temp = delta_y_step * (clip_xmax - x1) + delta_y 
      msd = temp // delta_x_step 
      y_pos_end = y1 + msd 

      if (temp - msd * delta_x_step) == 0: 
       y_pos_end -= 1 

     y_pos_end = min(y_pos_end, clip_ymax) + 1 
     if sign_x == -1: 
      x_pos = -x_pos 
     if sign_y == -1: 
      y_pos = -y_pos 
      y_pos_end = -y_pos_end 
     delta_y_step -= delta_x_step 

     while y_pos != y_pos_end: 
      callback(x_pos, y_pos) 

      if error >= 0: 
       x_pos += sign_x 
       error -= delta_y_step 
      else: 
       error += delta_x_step 

      y_pos += sign_y 

Beispiel für die Verwendung:

plot_line_v2v2i(
    # two points 
    (10, 2), 
    (90, 88), 
    # callback 
    lambda x, y: print(x, y), 
    # xy min 
    25, 25, 
    # xy max 
    75, 75, 
) 

Hinweise:

• Clipping min/max Werte sind inklusive
  (so max Werte image_width - 1 sein sollte, image_height - 1)
• Ganzahldivision // ist überall benutzt.
• Viele Sprachen (z. B. C/C++) verwenden Floored-Runden auf Division.
  Siehe Fast floor of a signed integer division in C/C++, um leicht verzerrte Ergebnisse mit diesen Sprachen zu vermeiden.

Es gibt einige Verbesserungen gegenüber dem Code in dem Papier zur Verfügung gestellt:

• Die Linie wird immer in Richtung des Grundstückes definiert (von p1 bis p2).
• Es gab manchmal einen feinen Unterschied im Liniengefälle, so dass das Drehen der Punkte, das Berechnen der Linie und das anschließende Zurückdrehen etwas andere Ergebnisse liefern würde. Die Asymmetrie wurde verursacht, indem der Code die X- und Y-Achse vertauschte, um eine Code-Duplizierung zu vermeiden.

---

Für Tests und Beispiel Verwendung finden:

• The Python repository.
• Rust version.