Gebiet | Computergrafik Algorithmen | |
Thema | Rastergrafik, Darstellung solider Dreiecke | |
Autor | Holger Förterer | |
Datum | April 1995 | |
Letzte Änderung | 23. November 2005 | |
Version | 0.22 | |
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.).
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
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
bisby
-1 geht, und dann diejenige, die vonby
biscy
reicht. Den Punkt zwischen A und C auf Höheby
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.
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. Istay
=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).
- Programmiere eine Dreiecksroutine, die die Punkte vorher sortiert und eine korrekte Fallunterscheidung durchführt.
- Wende den Bresenham-Algorithmus aus Kapitel 1.1 (Procedure Line4) an.
Für alle Arten von Kommentaren bin ich äußerst dankbar. Fragen beantworte ich gerne.
[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