Rasterung von Flächen

Die reellwertigen Koordinaten der Objekte im DC am Ende der Transformationspipeline müssen in ganzzahlige Pixelkoordinaten gerundet werden. Die Rasterung von Flächen kann mit Hilfe des Scanline-Verfahrens auf die von Linien zurückgeführt werden. In einem zweistufigen Algorithmus wird die Fläche zunächst in eine Menge horizontaler Linien, die sogenannten Spans, zerlegt. Die Eckpunkte dieser Spans ergeben sich durch Rasterung der Kanten nach dem vorgestellten Verfahren. In der zweiten Stufe wird dann jeder der Spans gerastert.

Das Scanline-Verfahren wird zur Vereinfachung und Beschleunigung des Rendering-Programms nur auf Dreiecke angewandt, denn Dreiecke sind die einfachsten Polygone. Gegenüber allgemeinen Polygonen bieten sie den Vorteil, daß sie planar und konvex sind. Für das Scanline-Verfahren eignen sie sich ausgezeichnet, da für jede Bildschirmzeile (Scanline) maximal zwei Schnittpunkte mit den Dreieckskanten auftreten.

Ein konvexes Polygon läßt sich gemäß der Abbildung triangulisieren, indem von einem beliebigen Eckpunkt aus zu allen nicht benachbarten Eckpunkten Diagonalen gezogen werden.

Abbildung 17.1: Triangulisierung eines konvexen Polygons

Unter Rasterung wird hier nicht nur das Füllen der Fläche in der Objektfarbe verstanden. Beim Einsatz des z-Buffers müssen neben den Pixelkoordinaten auch die $z$-Werte der Polygonpunkte interpoliert werden, um mit Hilfe dieser Tiefeninformation verdeckte Flächen zu unterdrücken.

Abbildung 17.2: Scanline-Verfahren zur Rasterung von Dreiecken

Dabei ist zu beachten, daß die Anfangs- und Endpunkte der Spans sich mit einem von Swanson und Thayer 1986 entwickelten Algorithmus berechnen lassen, der dem Bresenham-Algorithmus für Linien ähnlich ist. Er kommt auch ausschließlich mit Ganzzahlarithmetik aus, setzt aber pro Scanline nur genau zwei Punkte und damit weniger als der Bresenham-Algorithmus.

public void drawSpanStartPoints(int xa, int xe, int ya, int ye) {
  int dx, dy, x, y, error, mi, mf, schritt;

  dx = xe-xa;
  dy = ye-ya;

  error = -dy;
  mi = dx / dy;
  mf = 2*(dx%dy);
  schritt = -2*dy;

  for(y=ya; y<ye; y++) {
    setPixel(x, y);
    x += mi;
    error += mf;
    if(error > 0) {
      x++;
      error += schritt;
    }
  }
}

Außerdem sind je nach Schattierungs-Verfahren auch die Farbwerte bzw. die Normalenvektoren, die in den Eckpunkten gegeben sind, über die Fläche zu interpolieren. Verschiedene Farbwerte auf den Objektflächen ergeben sich durch die individuelle Beleuchtung der Punkte. Die Interpolation der Normalen simuliert dabei einen gekrümmten Flächenverlauf. Grundlegend für die Schattierungs-Verfahren ist die Beleuchtung einer Szene mit Hilfe von unterschiedlichen Lichtmodellen.