Bilderspiele - Vierter Teil
Am Ende der letzten Folge wurde es dreidimensional. Zumindest in der Mathematik. Hier soll die Mathe Routinensammlung noch ein wenig erweitert und dann auch verwendet werden. Neben den einfacheren Problemen wie der Projektion dreidimensionaler Körper auf den flachen Bildschirm steht auch noch die 3D-Clipping-Routine grau und unheimlich im Hintergrund.
Mathematik
Zunächst einmal noch etwas Mathematik. Es fehlen noch diverse Dinge, die man mit Vektoren tun kann und die in der Clipping-Routine auch getan werden müssen.
In Bild 1 finden Sie eine Erläuterung zur Addition und Subtraktion von Vektoren. Das Prinzip ist einfach: Vektoren werden komponentenweise addiert bzw. subtrahiert. Wir benötigen nur die Subtraktion, deren Implementierung Sie in Listing 1 sehen.
Das Produkt von zwei Vektoren ist schon etwas schwieriger. Da gibt es nämlich gleich zwei, das sogenannte Skalarprodukt und das Kreuzprodukt.
Zuerst einmal zum Skalarprodukt. Dieses ist im Prinzip nichts anderes als die Übertragung des Cosinussatzes, mit dessen Hilfe man Seitenlängen von Dreiecken berechnen kann, in den Bereich der Vektor-Mathe-matik. In Bild 2 finden Sie eine nähere Erklärung. Das Skalarprodukt zweier Vektoren ist, wie Sie dort sehen, kein Vektor, sondern ein Skalar. Besonders praktisch ist die Eigenschaft des Skalarproduktes, genau dann 0 zu sein, wenn die beiden Vektoren senkrecht aufeinander stehen, also im Winkel von 90 Grad (natürlich nur dann gültig, wenn keiner der Ursprungsvek-toren der Nullvektor ist). Damit ist das Skalarprodukt eine einfache Möglichkeit, genau diese häufig gestellte Frage zu klären. Diese Methode wird in der Clipping-Routine verwendet, um Linien, die parallel zu einer der Clipping-Ebenen sind, als unsichtbar zu entlarven. In Listing 1 finden Sie die Implementierung.
procedure sub_vec(v1, v2: vec3dh; var v3: vec3dh);
begin
v3[1] := v2[1] - v1[1];
v3[2] := v2[2] - v1[2];
v3[3] := v2[3] - v1[3];
end;
function skal_prod(vl, v2: vec3dh) : real;
begin
skal_prod := vl[l]*v2[l] + vl[2)*v2[2] + vl[3]*v2[3];
end;
procedure kreuz_prod(v1, v2: vec2dh; var v3: vec3dh);
begin
v3[1] := v1[2]*v2[3) - v2[2]*vl[3];
v3[2] := v1[3]*v2[1] - v2[3]*vl[1];
v3[3] := v1[1]*v2[2] - v2[1]*vl[2];
end;
function normalize(var n: vec3dh) : real;
var
l : real;
begin
l := sqrt (n[l] *n [1] + n[2]*n[2] + n[3]*n[3]);
n[1] := n[1]/l;
n[2] := n[2]/l;
n[3] := n[3]/l;
normalize := l;
end;
Listing 1
Das Kreuzprodukt ist noch etwas komplizierter - es ist ein Vektor, der auf der von den beiden Vektoren aufgespannten Ebene senkrecht steht. Bild 3 hilft hoffentlich Ihrem Verständnis. Das Kreuzprodukt ist genau dann der Nullvektor, wenn
- keiner der Ausgangsvektoren der Nullvektor ist und
- die beiden Vektoren parallel sind.
Sehr praktisch. Siehe auch Listing 1.
Eine häufig benötigte Größe ist die sogenannte Ebenennormale. Das ist ein Vektor, der senkrecht auf der Ebene steht und die Länge 1 hat. Länge eines Vektors ? Wie Sie in Bild 4 sehen, ist das ganz einfach. Ein Ebenennormalenvektor (schönes Wort, nicht?) läßt sich ganz einfach mit dem Kreuzprodukt zweier in der Ebene liegender, nicht paralleler Vektoren bestimmen. Aber Vorsicht! Dieses Kreuzprodukt wird im allgemeinen nicht die Länge 1 haben. Also basteln wir uns eine Normalisierungs-Funktion (siehe Listing 1, Funktion normalize), die den übergebenen Vektor komponentenweise durch seine Länge teilt und
außerdem die Länge (natürlich vor der Normalisierung) zurückgibt.
Apropos Ebene. Die Gleichung für Gerader ist ja schon lange bekannt. Spätestens seil dem zweiten Teil dieser Serie. Heute soll auch die Steigerung von ‘Gerade’, nämlich die ‘Ebene’, vorgestellt werden. Schauer Sie dazu am besten auf Bild 5.
Wofür diese ganze Mathematik gebrauch! wird, sehen Sie später. Zuerst einmal soll es um die Änderungen im display-Vorgang gehen.
Der Darstellungsprozeß in drei Dimensionen
Der Ablauf bleibt in einem einfachen 3D-System gegenüber dem 2D-System aus dem letzten Heft fast unverändert:
Zuerst wird jedes Objekt mit der transform_objekt-Routine transformiert, um es in die gewünschte Lage zu bringen
Danach wird Linie für Linie durch die Clipping-Routine geschickt. Wenn die Linie ganz oder teilweise sichtbar ist, muß sie auf zwei Dimensionen reduziert werden. Dies geschieht durch die Routine do_project, die eine Linie auf die xy-Ebene projiziert. Dazu wird eine perspektivische Projektion mit einem Zentralpunkt auf der z-Achse verwendet. Das dabei entstehe ende zweidimensionale Bild wird wie gehabt mit wvp_transform in einen Viewport transformiert und mit view_transform in Gerätekoordinaten umgesetzt und angezeigt.
Das Struktogramm aus dem letzten Heft muß also nur um die Routine zur Durchführung der Projektion erweitert ..erden (siehe Bild 14).
Projektionen
Bevor wir näher auf die Möglichkeiten und Voraussetzungen des Systems in dieser Form eingehen, sollte man sich zuerst mit dem Vorgang der Projektion eines Punktes m Raum auf eine Bildebene befassen. Das erleichtert die Diskussion des Systems.
In Bild 6 sehen Sie zwei verschiedene Arten der Projektion. Es gibt v erschiedene Techniken der Projektion, die sich darin unterscheiden, ob sie ein Objekt so zeigen, wie es erscheint (also perspektivisch verzerrt), oder so, wie es tatsächlich aussieht. Leider lassen sich nicht alle Forderungen, die Ingenieure und Künstler an Projektionen stellen, mit einer Projektion erfüllen. Man muß sich also entscheiden. Die gebräuchlichsten Projektionen sind die Parallel- und die Zentralprojektion. Wie man im Bild sieht, entsteht die Zentralprojektion dadurch, daß jeder Punkt des Objektes auf den Schnittpunkt einer Linie zwischen dem Punkt und dem Zentral- (Aug-) punkt der Projektion mit der Bildebene abgebildet wird. Bei der Parallelprojektion werden statt dessen parallele Strahlen verwendet. Das vorgestellte System benutzt eine Zentralprojektion, weil sie wohl den meisten Anwendungen entgegenkommt und auch die schönsten Demo-Effekte erzeugt. Wenn Sie eine Parallelprojektion haben möchten, sollte Ihnen die Implementierung keine Schwierigkeiten machen, wenn Sie die Berechnung der Zentralprojektion verstanden haben. Diese finden Sie übrigens in Bild 7. Die Berechnung ist so einfach, weil als Bildebene die xy-Ebene verwendet wird und der Zentralpunkt auf der z-Achse liegt. Diese Einschränkungen sind auch insofern sinnvoll, als die Bildebene senkrecht auf der Geraden, die durch den Zentralpunkt und den Fenstermittelpunkt geht, liegen sollte. Das eigentliche Problem eines 3D-Systems, nämlich die Projektion auf zwei Koordinaten, hat sich damit als sehr einfach lösbar herausgestellt, zumindest wenn man die xy-Ebene als Bildebene verwendet und den Zentralpunkt auf die z-Achse legt. Diese Voraussetzung macht nicht nur die Projektion einfacher, sondern auch das 3D-Clipping, allerdings wird das System dadurch auch weniger universell. Dieses Problem läßt sich aber lösen.
Also wieder der Reihe nach. Wie dreidimensionale Objekttransformationen funktionieren, wissen Sie aus dem letzten Heft. Sie können die Editier-Routinen für die verschiedenen Transformationen leicht selbst (Sie sollen auch etwas tun - ist aber ganz einfach !) auf drei Dimensionen erweitern. Ein Beispiel finden Sie in Listing 2.
procedure edit_transform ;
var
endit : Boolean; i : integer;
o : objekttype;
procedure set_scale(i: integer);
{Eingabe eines Skalierungswetes; dann Berechnung von t}
var
x, y, s, z : real;
m : mat3dh;
begin
writeln('Objekt i) ;
ident_mat(m);
write('scale x:');
readln(x);
m[1][1] := ra[1][1]*x;
write('scale y:');
readln(y);
m[2][2] := m[2][2]*y;
write('scale z:');
readln(z);
m[3][3] := m[3][3]*y;
write('scale global:');
readln(s);
m[4][4] := m[4][4]*s;
matmul3dh(o.t, m, o.t);
end;
procedure set_shear(i: integer);
{Hier neue Verzerrungseingabe einsetzten}
procedure set_trans(i: integer);
{Verschiebungseingabe und Berechnung von t}
var
m : mat3dh;
x, y, z : real;
begin
writeln('Objekt ', i);
ident_mat(m);
write('trans. x:');
readln(x);
m[4][1] := m[4][1] + x;
write('trans. y:');
readln(y);
m[4][2] := m[4][2] + y;
write('trans. z:');
readln(z);
m[4] [3] := ra[4] [3] + z;
matmul3dh(o.t, m, o.t);
end;
procedure set_rot(k: integer);
{Hier neue Rotationsroutine einsetzen)
begin
{Ablaufteil gegenüber der letzten Version unverändert}
end;
Listing 2
3D-Clipping
Der nächste Schritt ist das Clipping. Da dreidimensionales Clipping verwendet werden soll, genügt es nicht, ein Clipping-Fenster anzugeben, es wird ein Clipping-Volumen benötigt (siehe Bild 8). Jede Linie muß nun mit dem Clipping-Volumen verglichen werden. Das grundsätzliche Verfahren wurde bereits im letzten Heft vorgestellt. Leider ist das Ganze im Detail recht kompliziert, so daß die Clipping-Rou-tine die bisher bei weitem aufwendigste des ganzen Systems ist. Im Gegensatz zum zweidimensionalen Verfahren müssen bei teilweise sichtbaren Linien jetzt nicht Schnittpunkte von zwei Linien, sondern von einer Linie und einer Ebene (die Begrenzungen des Clipping-Volumens sind ja Ebenen) berechnet werden. Auch die Entscheidung, ob eine Linie innerhalb des Volumens liegt, wird durch die unpraktische Form des Clipping-Volumens bei der Zentralprojektion um einiges aufwendiger. Glücklicherweise haben wir aber bereits bei der Projektion einige Einschränkungen in Bezug auf die Lage der Projektionsebene und des Zentralpunktes gemacht, was die Berechnungen wieder etwas erleichtert.
Das ganze Verfahren erfordert allerdings für alle Objekte, daß sie vor dem Zentralpunkt liegen, sonst könnte es Fehler geben. Das gleiche gilt im übrigen auch für die Zentralprojektion. (Warum wohl ?). Das Clipping-Verfahren (das sich nach seinen Erfindern Cohen-Sutherland-Clip-ping nennt) im einzelnen: Zuerst wird für jeden Punkt einer Linie festgestellt, ob er rechts, links, ober- oder unterhalb, vor oder hinter dem Clipping-Volumen liegt (siehe Bild 9). Dabei werden jedem Punkt sechs Flags zugeordnet. Wenn ein Punkt innerhalb liegt, sind alle Flags Null. Für jedes festgestellte ‘Außerhalb' wird das jeweilige Flag auf 1 gesetzt, so daß maximal 3 Flags 1 sein können (Wenn ein Punkt zum Beispiel vorne, unten und links des Clipping-Volumens liegt). Welcher Teil einer Linie nun sichtbar oder unsichtbar ist, läßt sich einfach entscheiden: Eine Linie is: vollständig sichtbar, wenn die Summe de: Flags beider Punkte Null ist, also beide Punkte innerhalb des Volumens liegen. Genauso ist eine Linie vollständig unsichtbar, wenn beide Punkte auf der gleichen Seite einer Begrenzungsebene des Clipping-Vo-lumens liegen. Das ist immer dann der Fall wenn nicht beide Flag-Summen Null sind, aber nicht die gleichen Flags Eins sind Wenn es die gleichen Flags sind, dann liegen die Punkte auf der gleichen Seite der Ebene, also ist die Linie unsichtbar. Wenn auch nur ein Flagpaar ungleich ist, ist der Fall weniger trivial. Dann könnte die Linie teilweise sichtbar sein (Zur Illustration Bild 10). Was nun ?
Mindestens ein Punkt einer Linie, die teilweise sichtbar ist, liegt außerhalb des Fensters. Als erstes stellt die Routine fest, welcher der Punkte dies ist. Besser gesagt: Die Routine stellt fest, ob Punkt eins außerhalb des Fensters liegt. Wenn nicht, werden die Punkte vertauscht. Auf diese Weise ‘weiß’ der Clipping-Algorithmus immer, daß ein Punkt der zu clippenden Linie außerhalb des Fensters liegt, und zwar der Punkt, der nach dem Vertauschen der erste Punkt der Linie ist.
Der sichtbare Teil einer teilweise sichtbaren Linie endet mit Sicherheit an den Fenstergrenzen. Also wäre es doch eine Idee, die Linie mit den Begrenzungsebenen des Fensters zu schneiden. Wie das funktioniert, sehen Sie in Bild 5. Wenn Sie den Wert für t, den Sie mit der Formel aus Bild 5 erhalten, in die Gleichung der Geraden zwischen den beiden Linienendpunkten einsetzen, erhalten Sie die Koordinaten des Schnittpunkts, vorausgesetzt N*(L2-L1) ist ungleich Null (denn dann wären Ebene und Gerade parallel, schnittpunktlos und außerdem die Formel Undefiniert).
Für jedes Flag, das den Wert Eins hat, wird ein Schnittpunkt berechnet. Danach werden wieder die Endpunktcodes berechnet. Liegt der Schnittpunkt mit der Ebene im Fenster, sind die Endpunktcodes und ihre Summe Null. Wenn nicht, werden weitere Schnittpunkte berechnet, bis alle (maximal drei) Schnittpunkte bekannt sind. Jetzt wird der ganze Prozeß mit dem anderen Punkt wiederholt, falls dieser außerhalb des Fensters liegt. Wenn nach dem gesamten Prozeß die Linie (oder was von ihr übrig ist) vollständig sichtbar ist, übergibt die Clipping-Routine den folgenden Routinen den Wert ‘True’ und dieser Linienteil wird weiterbearbeitet. Andernfalls ist das Ergebnis "False" und es geht mit der nächsten Linie weiter. In Bild 11 finden Sie ein zweidimensionales Beispiel zur Erklärung.
Betrachtungstransformationen
Der Clipping-Algorithmus in der hier vorgestellten Form hat zwei Nachteile. Der erste ist. daß die Testfunktionen für die Ebenen aus der Endpunktcode-Berechnung nur funktionieren, wenn der Zentralpunkt der Projektion und der Fenstermittelpunkt auf der z-Achse liegen. Das läßt sich, wie bereits bei der Projektion erwähnt, leicht umgehen, indem man vor der Clipping-Routine eine zusätzliche Transformation einfügt, die den Zentralpunkt, oder besser die Achse vom Zentralpunkt zur Mitte des Clipping-Volumens auf die z-Achse transformiert. Dieses Problem ist nicht neu (siehe: Rotation um eine beliebige Achse, letzte Folge), es ist lediglich eine Rotation des Koordinatensystems, so daß die Achse vom Zentralpunkt zum Fenstermittelpunkt auf der z-Achse liegt. Das ist nicht besonders schwierig, es müssen lediglich die Winkel für Rotationen um die x- und y-Achse aus der Lage des Zentralpunktes berechnet werden. Natürlich muß vorher das ganze noch so zurechtgeschoben werden. daß der Fenstermittelpunkt auf der z-Achse liegt.
Man kann das Ganze noch verfeinern, indem man einen Vektor definiert, der eine Richtung angibt, die ‘oben’ bedeutet. Man kann jetzt noch um die z-Achse drehen, bis dieser Vektor auf der y-Achse liegt. Dann entspricht das System einer Art künstlicher Kamera, mit der man die Szene betrachtet: Position und Abstand der Kamera werden durch den Zentralpunkt angegeben. In welcher Richtung ‘oben’ ist, gibt der zusätzliche Vektor an. Damit ist es möglich, die Kamera um die Sichtrichtung rotieren zu lassen. Mit etwas zusätzlichem Rechenaufwand wäre es auch möglich, die Kameraentfernung von der Bildebene anzugeben, und daraus und aus der Lage der Sichtachse die Zentralpunktkoordinaten zu berechnen. Damit kann man an die Bildebene her-anzoomen (Siehe Bild 12).
Diese Transformation soll aber nicht an dieser Stelle besprochen werden.
Der zweite und wesentliche Nachteil dieses Clipping-Algorithmus ist die Tatsache, daß das Verfahren nur für das Clippen von Linien geeignet ist. Wenn (auszufüllende) Flächen geclippt werden sollen, müssen einige zusätzliche Probleme berücksichtigt werden (siehe Bild 13). Wenn Hidden-Surface-Routinen zum Einsatz kommen sollen, also Routinen, die nur die Oberflächen zeigen, die vom Standpunkt des Beobachters auch tatsächlich sichtbar sind, kann man diese Probleme nicht ignorieren. Das soll aber nicht an dieser Stelle behandelt werden.
Denken Sie doch selbst einmal über beides nach! Wenn Sie den bisherigen Stoff verstanden haben, sollten Sie in der Lage sein, eine Lösung zu finden. Nur ein Tip noch zur Transformation: Sie können die entstehende Rotationsmatrix in die Transformationsmatrix jedes Objektes hineinmultiplizieren. Dadurch sparen Sie einiges an Rechenzeit.
Effizienz
Wie Sie an der Implementierung des 3D-Clipping sehen, ist dieses Verfahren sehr aufwendig und rechenintensiv, obwohl der Algorithmus sehr effizient ist. Man wird also nur in Systemen, bei denen die Fähigkeit, ein dreidimensionales Fenster zu verwenden, unabdingbar ist (z.B. Architektur- oder Konstruktionssysteme), 2D-Clipping verwenden, weil 2D-Clipping erheblich effizienter, oft sogar (wie z.B. in allen modernen Grafikprozessoren) als Hardware zu implementieren ist. Systeme mit 3D-Clipping werden im allgemeinen Volumenmodelle verwenden, also Objekte tatsächlich als Körper, nicht nur als Flächen darstellen. Dann ist es nämlich sehr sinnvoll, einen Teil des Bildes abzuschneiden, um eine Rißzeichnung durch z.B. ein Getriebe zu erhalten.
Nur wenn die Clippingroutine den Wert ‘True’ zurückgibt, werden die Linien von der do_project-Routine weiterverarbeitet. Das daraus entstehende 2D-Bild wird wie gehabt von der Window/Viewport-Transformation in einen Viewport transformiert. Vorsicht: Achten Sie darauf, symmetrische Fenstergrößen in x- und y-Richtung zu verwenden. Wie gesagt, ohne die zusätzliche Kamera-Transformation ergeben sonst sowohl Clipping- wie Projektions- und Window/Viewporttransformation fehlerhafte Bilder.
Der Viewport schließlich wird durch view_transform in Gerätekoordinaten übersetzt. Die Routine wurde etwas geändert: Die Routinen zum Linienzeichnen wurden der Einfachheit halber jetzt in diese Prozedur integriert. Außerdem wurde mit Hilfe der Bildschirmkonstanten der Nullpunkt aus der linken unteren Ecke in die Bildschirmmitte verlegt. Das hat den Vorteil, daß man Rotationen besser beobachten kann, die sich ja fast alle auf den Koordinatennullpunkt beziehen.
Das können Sie bei der Kamera-Transformation berücksichtigen: Wenn Sie Ihre Welt so definieren, daß die Objekte geeignet zum Nullpunkt liegen, können Sie sie leichter modifizieren. Die Kamera-Transformation kann dann die Arbeit erledigen, die Objekte
- hinter die Bildebene (in positiver z-Richtung) und
- richtig zur Sichtachse auszurichten.
Nun zur Implementierung:
Der ganze Ablauf ist, übersichtlich als Struktogramm, in Bild 14 zu sehen. Im einzelnen:
Zuerst einmal mußten natürlich die Datentypen für Vektoren und Matrizen auf 3 Dimensionen erweitert werden.
Den gesamten Deklarationsteil für das Programm finden Sie vollständig in Listing 3. Die Mathematik-Routinen wurden angepaßt. Hier können Sie eine Beschleunigung erreichen, wenn Sie bei jedem Aufruf einen Index übergeben, der die notwendige Rechengröße bestimmt. Die Window/ Viewport-Transformation zum Beispiel findet ja im Zweidimensionalen statt, es müssen also nicht mehr alle Komponenten der Vektoren mit verrechnet werden (immerhin mindestens 25% weniger Rechnerei). Die Matrixroutinen können beschleunigt werden, wenn alle Elemente, die Null sind, von vomeherein aus der Rechnung ausgeschlossen werden; ein Vergleich braucht weniger Zeit als eine Multiplikation, und das Ergebnis einer Multiplikation mit Null ist nun mal immer Null. Dies aber nur nebenbei; optimierbar ist das System an vielen Punkten.
Denken Sie daran, daß alle Routinen, auch die, die jetzt nicht in geänderter Form im Listing erscheinen, an die geänderten Datentypen und Mathemetikroutinen angepaßt werden müssen. Am einfachsten ist es, wenn Sie die Namen der Typen und Routinen nicht ändern, sondern nur ihren Inhalt. Wenn ihr Texteditor vernünftige ‘ Suchen & Ersetzen’-Funktionen besitzt, ist auch die Änderung aller Namen, z.B. von vec2dh in vec3dh, kein Problem.
const
xmax = 639;
ymax = 399;
xstart = 320; {Diese Werte legen den Nullpunkt in}
ystart = 200; {die Bildschirmmitte}
maxobjekt = 10; {Maximale Anzahl der Objekte}
maxpunkte = 20; {Maximale Punktanzahl pro Objekt}
maxlinien = 20; {Maximale Linienanzahl pro Objekt}
type
mat3dh = array [1..4] of array [1..4] of real;
vec3dh = array [1..4] of real;
punkttype = array [1..maxpunkte] of vec3dh;
linie = record
P1 : integer; {Zeiger in Punktliste}
P2 : integer;
end;
linientype = array [1..maxlinien} of linie;
linienbuffer = record
p1 : vec3dh;
p2 : vec3dh;
end;
objekttype = record
p : punkttype;
l : linientype;
t : mat3dh; {Transformationsmatrix fuer jedes Objekt}
onoff : Boolean; {An-Ausschalter fuer Objekt}
nrp : integer; {Anzahl der definierten Punkte}
nrl : integer; {Anzahl der definierten Linien}
end;
welttype = array [1..maxobjekt] of objekttype;
wtype = record
xlu, ylu, xro, yro, zv, zh : real;
end;
clipvoltype = record
normall, normalr, normalu, normald : vec3dh;
end;
{Vier Ebenennormalen für die Seiten des}
{Clippingvolumens}
var
nro : integer;
{Anzahl der Objekte in der 'weit'}
welt : welttype;
w : wtype; vp : wtype;
clipvolume : clipvoltype; tview2dh : mat3dh;
cop : vec3dh; {Zentrum der Projektion}
g : char;
ende : Boolean;
a1, a2, b1, b2, c1, c2, d1, d2 : real; {Parameter }
{für die Clippingroutine}
Listing 3
Die ‘init’-Routine muß um einige Befehle erweitert werden; Sie finden sie, wie Änderungen an den übrigen Routinen, in Listing 4. Die Befehle dienen dazu, Anfangswerte für Fenster, Viewport und Zentralpunkt einzustellen. Außerdem müssen einige Parameter berechnet werden, wozu die Routinen calc_wvp, calc_cprm und calc_clipnorm aufgerufen werden (siehe unten).
Eine neue ‘init_welt’-Routine muß für dreidimensionale Objekte geschrieben werden. Die hier beschriebene definiert einen Würfel und ein Achsenkreuz. Sie können aber beliebige Objekte selbst eingeben. Viel Arbeit! Deshalb: Schreiben Sie sich doch einen Objekteditor. Der Editor muß Punkte und Linien in die Objekt-Datenstruktureinfügen. Wenn Ihr Objekt groß ist, denken Sie daran, daß die Fensterkoordinaten am Anfang auf (-0.5/-0.5) und (0.5/ 0.5) gesetzt wurden. Ändern Sie dies nach Bedarf (in der init-Routine).
An der ‘transform_objekt’-Prozedur hat sich wenig geändert; Es müssen nur die 3D-Mathematikroutinen statt der 2D-Ver-sionen aufgerufen werden. Außerdem muß natürlich die Flomogenisierung nach der Transformation, der veränderten Matrix-Dimensionen wegen, jetzt mit dem Matrixelement (4,4) statt (3,3) erfolgen. Die Editierung der Transformation wurde leicht verändert (siehe oben, Listing 2).
Parameter-Perechnungen
Die Routine für Fenster- und Viewport-Editierung muß ebenfalls leicht verändert werden: Zwei neue Variablen für die vordere und hintere Grenze des Clippingvo-lumens müssen eingegeben werden. Wie in der Init-Routine müssen dann auch wieder die Parameter-Berechnungsprozeduren aufgerufen werden:
calc_wvp hat sich nicht verändert. Schließlich geschieht die wvp_Transfor-mation erst nach der Projektion. calc_cprm berechnet eine Reihe von Parametern, die für den effizienten Vergleich eines Punktes mit einer Ebene benötigt werden (siehe oben). Diese Parameter werden in einer speziellen Routine berechnet und in globalen Variablen gespeichert, damit die Berechnung nicht für jeden Punkt wiederholt werden muß. calc_clipnorm hat den gleichen Zweck; Es werden hier die Ebenen-Normalenvektoren der rechten, linken, oberen und unteren Clipping-Ebene berechnet. Auch dies muß nur einmal durchgeführt werden, solange sich die Fensterkoordinaten nicht ändern. Das Prinzip ist einfach: Für jede der Ebenen sind mehrere Punkte bekannt: Der Zentralpunkt der Projektion liegt auf jeder der Ebenen, zwei der Fenster-Eckpunkte liegen ebenfalls auf jeder Ebene. Aus drei Punkten lassen sich zwei Vektoren konstruieren, die in der Ebene liegen: z.B. Zentralpunkt-rechte obere Fensterecke und Zentralpunktrechte untere Fensterecke. Der Normalenvektor ist dann das Kreuzprodukt dieser beiden Vektoren, komponentenweise dividiert durch seinen Betrag, was die Funktion ‘normalize’ erledigt.
Für die vordere und hintere Clippingebene ist die Berechnung von Schnittpunkten so einfach (weil sie ja immer parallel zur Bildebene liegen), daß man auf die Normalenvektoren verzichten kann.
Do_clip3D
Die Clipping-Routine selbst wurde, mit Rücksichtnahme auf die Nicht-Pascal-Pro-grammierer, etwas unelegant programmiert. Statt für die Endpunktcodes den dafür idealen Datentyp ‘Menge’, der sich in den meisten Programmiersprachen nicht ohne weiteres simulieren läßt, zu verwenden, werden die 6 Codes in einem Array mit jeweils 6 Integer-Zellen für jeden Punkt gespeichert. Dadurch wird das Ganze etwas aufwendiger. Die Summe der Codes wird ebenfalls gespeichert.
Zuerst werden die Punkte der Linie in einem Array zwischengespeichert (Ablaufteil). Dann wird die Funktion ‘sichtbar’ aufgerufen, deren Ergebnis ein Flag ist, das den Wert ‘ja’ (Linie sichtbar), ‘nein’ (Linie unsichtbar) oder ‘teilweise’ erhalten kann. Die Funktion arbeitet folgendermaßen: Zuerst wird die Prozedur calc_endcode, die die Endcodes für einen Punkt berechnet, aufgerufen. Nach den oben erklärten Verfahren entscheidet ‘sichtbar-, ob die Linie (teilweise) sichtbar ist oder nicht. Die dafür notwendige logische ‘UND’-Verknüpfung der Endpunktcodes beider Punkte erledigt die Funktion ‘intersect’. Auch diese Funktionen könnten unter Verwendung z.B. der bitweisen Logikoperationen von ST-Pascal eleganter implementiert werden, weshalb hier darauf verzichtet wurde. Wenn eine Linie teilweise sichtbar ist, muß noch geprüft werden, ob Punkt 1 außerhalb des Fensters liegt. Wenn nicht, werden Punkt 1 und 2 mit Hilfe der Prozedur ‘Swap’ vertauscht. Dies ist notwendig, weil die nachfolgende Schnittpunktberechnung immer davon ausgeht, daß Punkt 1 außerhalb liegt (Bei teilweise sichtbaren Linien muß ja zumindest ein Punkt außerhalb liegen).
Wenn 'sichtbar’ nicht den Wert teilweise zurückgibt, muß Clip3D je nach dem Rückgabewert Wahr oder Falsch werden. Ist die Linie sichtbar, müssen außerdem die gepufferten Punkte wieder in ihre ursprüngliche Variable zurückgespeichert werden.
Ansonsten muß der sichtbare Teil der Linie berechnet werden. Dazu wird für jeden auf 1 gesetzten Endpunktwert der Schnittpunkt der Linie mit der entsprechenden Fensterseite i berechnet. Das geschieht in der Prozedur calc_s. Dabei wird erst geprüft, ob Linie und Ebene parallel sind; dann kann es keinen Schnittpunkt geben. Danach wird wieder auf Sichtbarkeit geprüft. Wenn alle auf 1 gesetzten Endpunktcodes bearbeitet worden sind, kann endgültig entschieden werden, ob ein, und wenn ja welcher, Teil einer Linie sichtbar ist. Je nachdem wird dann, wie oben erwähnt, der Rückgabewert von do_clip3D gesetzt.
Noch eine Bemerkung zu der Endcode-Berechnung: Eigentlich müßte in den Vergleichen in dieser Routine immer mit dem Wert 0 verglichen werden. Hier spielt uns aber die Rechen-Ungenauigkeit des verwendeten Pascal-Systems einen Streich: Die Rechnung ergibt in manchen Fällen einen Wert, der zwar nahe Null, aber nicht gleich Null ist. Das führt dann, ganz nach dem Motto knapp daneben ist auch vorbei, zu falschen Endcodes. Deshalb wird hier anstatt der Null ein Wert verwendet, der weit genug von den Rechenfehlern des Computers entfernt ist und somit korrekte Ergebnisse liefert. Bei anderen Compilern oder Interpretern kann man möglicherweise auf diese Korrektur verzichten.
Die Routine do_project berechnet die Bildpunkte aus den geclippten Linien. Nochmal: Das funktioniert so (ohne zusätzliche Viewing-Transformation) nur mit nullpunkt-symmetrischen Fenstern. Wie Sie im Listing sehen, ist die Implementierung trivial.
Die View_trans-Routine wurde insofern geändert, als sie jetzt den Aufruf der Linienzeichenroutine enthält.
Schließlich finden Sie im Listing der Vollständigkeit halber noch die do_dis-play-Routine und den Ablaufteil des Hauptprogramms.
Das war’s für diesmal. In Bild 15 sehen Sie noch ein Beispiel für ein mit dem Demo-Programm erzeugtes Bild. Dazu wurde der Würfel um einen Winkel gedreht und nach oben geschoben. Die Fensterkoordinaten reichen von (-0.5/-0.5) bis (0.5/0.5), der Viewport hat die Koordinaten (0.1/0.1) bis (0.9/0.9). Am oberen Bildrand reicht der Würfel nach der Verschiebung über den Fensterrand hinaus und wurde geclippt.
C. Schorrmann
Erweiterungen an der init-Routine:
ident_mat(tview3dh);
w.xlu := -0.5;
w.xro 0.5;
w.ylu := -0.5;
w.yro := 0.5;
w.zh := 2;
w.zv := 0;
vp.xlu := 0.1;
vp.ylu := 0.1;
vp.xro := 0.9;
vp.yro ;= 0.9;
cop[1] := 0;
cop[2] := 0;
cop [3] : = -1;
cop [4] : = 1;
calc_clipnorm ;
calc_wvp ;
calc_cprm ;
Neue init_welt-Routine:
procedure init_welt ;
{3D-Fassung für init_welt}
{Definition eines Würfels und eines Achsenkreuzes}
var
i, j : integer;
dummy ; vec3dh;
begin
{Initialisierung}
for i := 1 to maxobjekt do begin
for j := 1 to maxlinien do begin
welt [i].l[j].P1 := 0;
welt [i].l[j].P2 := 0;
end;
dummy[1] := 0;
dummy[2] : = 0;
dummy[3] := 0;
dummy[4] := 1;
for j := 1 to maxpunkte do begin
welt[i].p[j] := dummy;
end;
ident_mat(welt[i].t);
welt[i].onoff := true;
end;
{Objektedef' s}
nro := 2;
with welt[1] do begin
{Erstes Objekt: Würfel mit einem}
{Häkchen zur Identifizierung der Vorderseite}
for i := 1 to 2 do begin
{Punktliste für Vorder- und Rückseite}
dummy[1] := -0.3;
dummy[2] := -0.3;
dummy [3] := 0 + (i - 1) *0.6;
p[1 + (i - 1)*7] := dummy;
dummy[1] := -0.3;
dummy[2] := 0.3;
p[2 + (i - 1)*7] := dummy;
dummy[1] := 0.3;
dummy[2] := 0.3;
p[3 + (i - 1)*7] := dummy;
dummy[1] := 0.3;
dummy[2] := -0.3;
p[4 + (i - 1)*7] := dummy;
end;
{Punktliste Häkchen}
dummy[1] := -0.3;
dummy[2] := 0;
dummy[3] := 0;
p[5] := dummy;
dummy[1] := 0;
dummy[2] := -0.3;
p[6] := dummy;
dummy[1] := 0;
dummy[2] := 0;
p[7] := dummy;
{Linienliste Würfel}
l[1].P1 := 1;
l[1].P2 := 2;
l[2].P1 := 2;
l[2].P2 := 3;
l[3].P1 := 3;
l[3].P2 := 4;
l[4].P1 := 4;
l[4].P2 := 1;
l[5].P1 : = 5;
l[5].P2 := 6;
l[6].P1 := 6;
l[6].P2 := 7;
l[7].P1 := 8;
l[7].P2 := 9;
l[8].P1 := 9;
l[8].P2 := 10;
l[9].P1 := 10;
l[9].P2 := 11;
l[10].P1 := 11;
l[10].P2 : = 8;
l[11].P1 := 1;
l[11].P2 := 8;
l[12].P1 := 2;
l[12].P2 := 9;
l[13].P1 := 3;
l[13].P2:=10;
l[14].P1 := 4;
l[14].P2 := 11;
nrl : = 14;
nrp := 11;
onoff := true;
end;
{Achsenkreuz xy, z=0}
with weit[2] do begin
{Punktliste}
p[1][1] := -1;
p[1][2] := 0;
p[1][3] := 0;
p[1] [4] := 1;
p[2][1] := 1;
p[2] [2] := 0;
p[2] [3] := 0;
p[2] [4] := 1;
p[3][2] := -1;
p[3][1] := 0;
p[3][3] := 0;
p[3][4] := 1;
p[4][2] := 1;
p[4][1] := 0;
p[4][3] := 0;
p[4][4] := 1;
{Linienliste}
l[1] .P1 := 1;
l[1] .P2 := 2;
l[2].P1 := 3;
l[2].P2 := 4;
nr1 := 2;
nrp ;= 4;
onoff := true;
end;
end;
Erweiterte edit_wvp-Routine
procedure edit_wvp ;
begin
writeln('Geben Sie Window xlu, ylu, xro, yro, zv, zh ein:');
readln(w.xlu, w.ylu, w.xro, w.yro, w.zv,w.zh);
{Erweitert um z-Werte für vordere und hintere}
{Clipping-Ebene}
writeln('Geben Sie Viewport xlu, ylu, xro, yro ein:');
readln(vp.xlu, vp.ylu, vp.xro, vp.yro);
calc_wvp ;
{Neue Parameter-Berechnungen:}
calc_cprm ;
calc_clipnorm ;
end;
Neue Parameterberechnungen:
procedure calc_cprm ;
{Berechnung der Parameter für den Punkt-Ebenen-Vergleich}
begin
a1 := w.xro/(w.zv - cop[3]);
a2 := -a1*cop[3];
b1 := w.xlu/(w.zv - cop[3]);
b2 := -b1*cop[3];
c1 := w.yro/(w.zv -'cop[3]);
c2 := -cl*cop[3];
d1 := w.ylu/(w.zv - cop[3]);
d2 := -d1*cop[3];
end;
procedure calc_clipnorm ;
{Berechnung der Ebenennormalen der 'schwierigen'}
{Clippingebenen}
var
p1, p2 : vec3dh;
l : real;
begin
with clipvolume do begin
null_vec(normall);
null_vec(normalr);
null_vec(normalu);
null_vec(normald);
end;
with clipvolume do begin
p1[1] := w.xlu - cop[1];
p1[2] := w.ylu - cop[2];
pl[3] := w.zv - cop[3];
p2[1] := w.xlu - cop[1];
p2[2] := w.yro - cop[2];
p2[3] := w.zv - cop[3];
{Links}
kreuz_prod(p1, p2, normal1);
l := normalize(normall);
pl[1] := w.xro - cop[1];
pl[2] := w.ylu - cop[2];
pl[3] := w.zv - cop[3];
p2[1] := w.xro - cop[1];
p2[2] := w.yro - cop[2];
p2[3] := w.zv - cop[3];
{rechts}
kreuz_prod(p1, p2, normalr);
l := normalize(normalr);
pl[l] := w.xlu - cop[1];
pl[2] := w.yro - cop[2];
pl[3] := w.zv - cop[3];
p2[1] := w.xro - cop[1];
p2[2] := w.yro - cop[2];
p2[3] := w.zv - cop[3];
{oben}
kreuz_prod(p1, p2, normalu);
l := normalize(normalu);
pl[1] := w.xro - cop[1];
pl[2] := w.ylu - cop[2];
pl[3] := w.zv - cop[3];
p2[1] := w.xlu - cop[1];
p2[2] := w.ylu - cop[2];
p2[3] := w.zv - cop[3];
{unten}
kreuz_prod(p1, p2, normald);
1 := normalize(normald);
end;
end;
Neue 'Arbeits'-Routinen
procedure transform_objekt(var o: objekttype);
{Multipliziert die Punkte des Originals mit der}
{Transformationsmatrix t}
var
i, j : integer; begin
for i := 1 to o.nrp do begin
vecmat3dh(o.p[i], o.t, o.p[i]);
for j := 1 to 3 do begin
o.p[i][j] := o.p[i][j]/o.p[i][4];
{Diese for-Schleife dient der erneuten Normalisierung}
{der homogenen Koordinaten}
end;
end;
end;
function do_clip3D(var l: linienbuffer) :Boolean;
type sicht = (ja, nein, teilweise);
var
i, j : integer;
e : array [1..2] of array [1..6] of integer;
s : array [1..2] of integer;
inter : integer;
point : array [1..2] of vec3dh;
p2, pl : vec3dh;
f : sicht;
procedure calc_endcode(p: vec3dh; i: integer);
{Berechnung der Punkt-Endcodes}
var
j : integer;
begin
{Jener ominöse Wert von 1.999999*E-16 ist eine }
{Korrektur der Rechenungenauigkeit, die sonst }
{unter Umständen zu falschen Ergebnissen führt }
if (p[l] - p[3]*b1) - b2 < -1.999999e-16 then begin
e[i][6] := 1;
end else begin
e[i][6] := 0;
end;
if (p[1] - p[3]*a1) - a2 > 1.999999e-16 then begin
e[i][5} := 1;
end else begin
e[i][5] := 0;
end;
if p[2} - p[33*dl - d2 < -1.999999e-16 then begin
e[i][4] := 1;
end else begin
e[i][4] : = 0;
end;
if p[2] - p[3]*c1 - c2 > 1.999999e-16 then begin
e[i][3] := 1;
end else begin
e[i][3] := 0;
end;
if p[3] - w.zv < 0 then begin
e[ i] [2] : = 1;
end else begin
e[i] [2] := 0;
end;
if p[3] - w.zh > 0 then begin
e[i][1] := 1;
end else begin
e[i] [1] := 0;
end;
{Berechnung der Summen der Endpunktcodes}
s [i] : = 0;
for j := 1 to 6 do begin
s[i] := s[i] + e[i][j];
end;
end;
procedure calc_s(i: integer; var p: vec3dh);
{Berechnet Linien-Ebenen-Schnittpunkt}
{Ergebnis in p}
var ts : real;
pflag : Boolean;
begin
pflag := false;
sub_vec(cop, point[1}, p1);
sub_vec(point[1], point[2), p2);
case i of
6: begin
if skal_prcd(clipvolume.normall, p2) <> 0
then begin
ts := skal_prod(clipvolume.normall, p1)/ skal_prod(clipvolume.normall, p2);
end else begin pflag := true;
end;
end;
5: begin
if skal_prod(clipvolume.normalr, p2) <> 0 then begin
ts := skal_prod(clipvolume.normalr, pl)/ skal_prcd iclicvoluise-normalr, p2) ;
end else begin
pflag := true;
end;
end;
4: begin
if skal_prod(clipvolume.normald, p2) <> 0 then begin
ts := skal_prod(clipvolume.normald, p1)/ skal_prod(clipvolume.normald, p2);
end else begin
pflag := true;
end;
end;
3: begin
if skal_prod(clipvolume.normalu, p2) <> 0
then begin
ts := skal_prod(clipvolume.normalu, pl)/ skal_prod(clipvolume.normalu, p2);
end else begin
pflag := true;
end;
end;
2: begin
if p2[3] - pl[31 <> 0 then begin
ts := (w.zv - p1[3])/(p2[3] - pl[3]);
end else begin
pflag := true;
end;
end;
1: begin
if p2[3] - pl[33 <> 0 then begin ts := (w.zh - pl[33)/(p2[3J - pl[3]); end else begin pflag := true; end; end; end;
if (pflag = false) then begin
{Schnittpunktberechnung nur bei Nichtparallelität}
ts:=-ts;
P[1] := point[1][1] + (point[2][1] -point[1][1])*ts;
P[2] := point[1][2] + (point[2][2] -point[1] [2])*ts;
P[3] := point[1][3] + (point[2][3] -point[1][3])*ts;
end;
end;
procedure swap(var p1, p2:vec3dh);
{Vertauscht zwei Punkte}
var
t : vec3dh;
begin
t := p1;
p1 := p2;
p2 := t;
end;
procedure intersect ;
{Berechnet die logische UND-Verknüpfung derEndcodes}
var
j : integer;
begin
inter := 0;
for j := 1 to 6 do begin
inter := inter + trunc((e[1][j] + e[2][j])/2);
end;
end;
function sichtbar : sicht;
{Entscheidet, inwieweit eine Linie sichtbar ist}
var
j : integer;
begin
calc_endcode(point[1], 1);
calc_endcode(point[2], 2);
if (s [1] = 0) and (s[2] = 0) then begin
sichtbar := ja;
end else begin
intersect ;
if inter <> 0 then begin
sichtbar := nein;
end else begin
sichtbar := teilweise;
if s[1] = 0 then begin
swap(point[1], point[2]);
e[1] := e[2];
end;
end;
end;
end;
begin
point[1] := l.pl;
point[2] := l.p2;
f := sichtbar ;
if f = teilweise then begin
for j := 1 to 2 do begin
for i := 1 to 6 do begin
if e[1][i] = 1 then begin
calc_s(i, point[1]);
f := sichtbar ;
end;
end;
end;
end;
if f = ja then begin
do_clip3D := true;
l.p1 := point[1];
l.p2 := point[2];
end else begin
do_clip3D := false;
end;
end;
procedure do_project(var l: linienbuffer);
{Zentralprojektion auf die xy-Ebene, Zentralpunkt};
{auf der z-Achse}
var
t1, t2 : real;
begin
with l do begin
t1 := (-cop[3])/(l.pl[3] - cop[3));
t2 := (-cop[3])/(l.p2[3] - cop[3]);
l.pl[1] := cop[13 + (l.pl[1] - cop[1])*t1;
l.pl[2) := cop[2] + (l.pl[2] - cop[2])*t1;
l.pl[3] := 0;
l.p2[1] := cop[1] + (l.p2[1] - cop[1])*t2;
l.p2[2] := cop[2] + (l.p2[2] - cop[2])*t2;
l.p2[3] := 0;
end;
end;
Modifizierte view_trans-Routine
procedure view_trans(l: linienbuffer);
var
x1, y1, x2, y2 : integer;
begin
x1 : = round(l.p1[1]*xmax + xstart);
x2 := round(l.p2[1]*xmax + xstart);
y1 := -round(l.p1[2]*ymax - ystart);
y2 := -round(l.p2[2]*ymax - ystart);
Draw(x1, y1, x2, y2);
{Der Aufruf der Prozedur zum Linienzeichnen}
{wurde der Einfachheit halber in die view_trans-Routine}
{verlegt. Hier kann eine beliebige Prozedur zum Ziehen}
{von Linien zwischen xl,yl und x2,y2 aufgerufen werden}
end;
Do_display und Ablaufteil
procedure do_display ;
{Anzeigeroutine fuer die 'Welt'}
var i, j ; integer;
lbuf : linienbuffer; {Dient zum Zwischen speichern}
{der transformierten Linien-Koordinaten}
obuf : objekttype;
{Dient zum Zwischenspeichern eines Objektes}
begin
Writeln(chr(27),'E');
for i := 1 to nro do begin
if weit[i].onoff then begin
obuf := welt[i};
transform_objekt(obuf);
for j := 1 to obuf.nr1 do begin
lbuf.p1 := obuf.p[obuf.1[j].P1];
lbuf.p2 := obuf.p[obuf.1[j].P2];
if do_clip3D (lbuf) then begin
do_project (lbuf) ;
wvp_transform(lbuf);
view_trans(lbuf);
end;
end;
end;
end;
end;
{Ablaufteil}
begin
ende := false;
init ;
init_welt ;
do_display ;
repeat
writeln(chr(27),'E');
writeln('1. Transformation editieren');
writeln('2. Window/Viewport editieren');
writeln('3. Neues Bild zeichnen');
writeln('e=Ende');
readln(g);
case g of
'1': begin
edit__transform ;
end;
'2': begin
edit_wvp ;
end;
'3': begin
do_display ;
end;
'e': begin
ende:= true;
end;
else begin
{Nichts tun, zur Sicherheit}
end;
end;
until ende = true;
end.