1 Rastergrafik Algorithmen

1.3 Darstellung solider Dreiecke

Gebiet Computergrafik Algorithmen
Thema Rastergrafik, Darstellung solider Dreiecke
Autor Holger Förterer
Datum April 1995
Letzte Änderung 23. November 2005
Version 0.22

Inhalt


1.3 Dreiecke

Der Einfachheit halber bezeichnen wir die Punkte eines Dreiecks im Folgenden (von oben nach unten) mit A, B und C, die Koordinaten der Punkte seien (ax,ay), (bx,by) und (cx,cy) (nicht verwechseln mit 'a mal x' etc.).


1.3.1 Das Grundprinzip

Ein Dreieck wird durch die Scanzeilen in Linien zerlegt. Für jede Zeile benötigen wir also einen Anfangs- und Endpunkt (in Abb. 1 durch kleine Kugeln gekennzeichnet), die wir durch eine Linie verbinden.

Dreieck durch Scanzeilen zerlegt

Abb. 1


1.3.2 Die Realisierung

Für jede Seitenbegrenzung a, b und c können wir einen vereinfachten Linienalgorithmus verwenden, da wir keine geschlossene Pixelreihe erzeugen müßen, sondern linke und rechte Begrenzung des Dreiecks auf einer Scanzeile ausreichen (Abb. 2).

Linie vs. linke Grenze eines Dreiecks

Abb 2

Nun zur eigentlichen Vorgehensweise. Wir zeichnen das Dreieck in zwei Teilschritten. Zuerst die Teilfläche, die vertikal von ay bis by-1 geht, und dann diejenige, die von by bis cy reicht. Den Punkt zwischen A und C auf Höhe by bezeichnen wir als H (Abb. 3).

Teilbereiche des Dreiecks

Abb. 3

Jetzt müssen wir einfach den angepaßten Linienalgorithmus für A->B und A->H parallel laufen lassen, die errechneten Punkte nach jedem y-Schritt verbinden und bei by-1 abbrechen. Dasselbe wiederholen wir für den zweiten Teil mit B->C und H->C.

Zu einer weiteren erfreulichen Vereinfachung: H muß nicht einmal berechnet werden. Der Scanline-algorithmus A->C verwendet ja einen Zähler, der den x-Wert selbständig erhöht, also arbeiten wir bei der zweiten Teilfläche mit den vorhandenen Werten weiter.


1.3.3 Beispielroutinen

Vielleicht wird dies duch eine auf ay < by < cy eingeschränkte Prozedur leichter verständlich. Grundlage für den Linienalgorithmus war hier Line2 aus Kapitel 1.1:


Procedure Triangle(ax, ay, bx, by, cx, cy, color: integer);
var
  y             : integer;       { Schleifenvariable für die Scanzeile  }
  x1,x2,x3      : real;          { x-Werte für Scanline-Algorithmus     }
  m1,m2,m3      : real;          { Increments für die x-Werte           }
begin
  x1  := ax;                                    { x-Wert Linie A -> B   }
  x2  := bx;                                    { x-Wert Linie B -> C   }
  x3  := ax;                                    { x-Wert Linie A -> C   }

  m1 := (bx-ax) / (by-ay);                      { Increments   A -> B   }
  m2 := (bx-cx) / (by-cy);                      { Increments   B -> C   }
  m3 := (cx-ax) / (cy-ay);                      { Increments   A -> C   }

  for y := ay to by-1 do                        { erste Teilfläche      }
    begin
      Line (round(x1), y, round(x3), y, color); { horiz. Linie          }
      x1 := x1 + m1;
      x3 := x3 + m3
    end;

  for y := by to cy do                          { zweite Teilfläche     }
    begin
      Line (round(x2), y, round(x3), y, color); { horiz. Linie          }
      x2 := x2 + m2;
      x3 := x3 + m3
    end
end;

Ich denke, das Prinzip ist ersichtlich. Es fehlen die Sortierung der Punkte und die Fallunterscheidungen für eventuell gleiche y-Werte (sonst ergeben sich oben Divisionen durch Null!).

Ganz einfach - aber nicht effizient - könnte man die Punkte so sortieren:

  h: Integer;
...
if (ay>by) then
begin
h := ay; ay := by; by := h; { vertausche A und B }
h := ax; ax := bx; bx := h
end;
if (by>cy) then
begin
h := by; by := cy; cy := h; { vertausche B und C }
h := bx; bx := cx; cx := h
end;
if (ay>by) then
begin
h := ay; ay := by; by := h; { vertausche A und B }
h := ax; ax := bx; bx := h
end;

Eine Methode, die Fallunterscheidung durchzuführen, besteht darin, die m-Werte bei einem Null-Divisor einfach auf 0 zu setzen. Ist ay = cy, so braucht man eigentlich eine Information über die Tiefe der Punkte, um das Dreieck noch korrekt zu zeichnen. Da wir diese Informationen im vorliegenden Fall aber nicht haben, ziehen wir einfach die Linie zwischen kleinstem und größtem x der Punkte (oder auch einfach die Linien A->B und B->C).


1.3.4 Vorschläge zur selbständigen Programmierung


1.3.5 Anmerkungen

Für alle Arten von Kommentaren bin ich äußerst dankbar. Fragen beantworte ich gerne.


1.3.6 Literatur

[FOLEY92]



James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes
"Computer Graphics: Priniples and Practice" - 2nd ed.
Addison-Wesley Publishing Company, Reading, Massachusetts, 1992
ISBN 0-201-12110-7
[WATT89]




Alan H. Watt
"Fundamentals of Three-Dimensional Computer-Graphics"
Addison-Wesley Publishing Company, Reading, Massachusetts, 1989
ISBN 0-201-15442-0
(there is a second edition but I don't have it)

Linien | Dreiecke | Volumendarstellung | Iteratives 3D Füllen

home