Mittelpunkt-Entscheidungsalgorithmus (Bresenham)

• Verwenden nur ganzzahlige Arithmetik
• Steigung liegt im Intervall $[0,1]$

Andere Steigungen: Übung.

treffen sukkzessive Entscheidungen: liegt nächstes Pixel im Osten (E) oder im Nordosten (NE) ?

untersuchen hierzu Mittelpunkt zwischen diesen beiden Pixel durch Einsetzen in die implizite Form

 
void RestrictedDrawLine(
  int x0, int y0,
  int x1, int y1,
  int color
) {
  int y(y0);

  for(int x(x0); x!=x1+1; x++) {
    SetPixel(x, y, color);
    if( F(x+1, y+0.5) > 0 ) {
      y = y+1;
    }
  }

}

Trick: Statt $F(x,y)$ immer wieder komplett zu berechnen, nutze bereits berechnete Werte aus vorhergehender Iteration!

Berechnen wir die Differenz zweier aufeinander folgender Iterationen:

Fall E:

$$\begin{eqnarray*} \lefteqn{F(x+2,y+0.5)-F(x+1,y+0.5)}\\ &=& (x+2-x_0)(y_1-y_0... ... \mbox{}-(x+1-x_0)(y_1-y_0)+(y+0.5-y_0)(x_1-x_0)\\ &=& y_1-y_0 \end{eqnarray*}$$

Fall NE:

$$\begin{eqnarray*} \lefteqn{F(x+2,y+1.5)-F(x+1,y+0.5)}\\ &=& (x+2-x_0)(y_1-y_0... ...1-x_0)(y_1-y_0)+(y+0.5-y_0)(x_1-x_0)\\ &=& (y_1-y_0)-(x_1-x_0) \end{eqnarray*}$$

Zu Beginn:

$$\begin{eqnarray*} \lefteqn{F(x_0+1,y_0+0.5)} \\ &=& (x_0+1-x_0)(y_1-y_0)+(y_0+0.5-y_0)(x_1-x_0)\\ &=& (y_1-y_0)-0.5\cdot(x_1-x_0) \end{eqnarray*}$$

Wir wollen zu Beginn nicht mit $0.5$ multiplizieren, also:

Trick: Multipliziere $F(x,y)$ mit 2, was beim Vergleich mit 0 nichts ausmacht!

 
void RestrictedDrawLine(
  int x0, int y0,
  int x1, int y1,
  int color
) {
  int y(y0);

  for(int x(x0); x!=x1+1; x++) {
    SetPixel(x, y, color);
    if( 2 * F(x+1, y+0.5) > 0 ) {
      y = y+1;
    }
  }

}

wir haben also:

$$\begin{eqnarray*} 2\cdot F(x_0+1,y_0+0.5) &=& 2\cdot (y_1-y_0)-(x_1-x_0) \\ 2... ...((y1-y0)-(x_1-x_0)) & \quad & \mbox{Fall NE} \end{array}\right. \end{eqnarray*}$$

d.h. insbesondere, dass das inkrementelle Aktualisieren von $F$ nicht von $x$ oder $y$ abhängt, was man bei einer Geraden auch intuitiv erwartet.

also ergibt sich der: