Yi = Ym - D / Fimax · arcsin ( yi / sqrt ( y'i
Ri = D / Fimax · arcsin ( ri / |BPi| )
Die n Kugeln sind in der Reihenfolge zu zeichnen, daß die von der Betrachterposition am weitesten entfernte Kugel zuerst dargestellt wird und die am nächsten liegende Kugel zuletzt, wodurch die Überlappungen korrekt dargestellt werden. Um bei einem Programm die Rechenzeit und damit die Zeit, die für die Darstellung benötigt wird, minimal zu halten, sollten Terme, die für die Berechnung der Bildschirmkoordinaten aller Kugeln gleich sind, nur einmal berechnet werden (z.B. (ÂT)-1 , Xm , Ym , D/Rmax , D/Rmax · |BN| und D/Fimax ). Es ist zu beachten, daß, wenn die Anzahl der Kugeln groß ist, der Hauptanteil der Rechenzeit zum Ordnen der Kugeln entsprechend ihrer Entfernung zur Betrachterposition benötigt wird. Es sollte deswegen ein schneller Sortieralgorithmus (z.B. Mergesort oder Quicksort) verwendet werden, wobei nicht die Objekte selbst, sondern nur ihre Adressen sortiert werden sollten (indirektes Sortieren). Das Invertieren der Matrix kann man z.B. mit dem als "Gauß-Algorithmus mit teilweiser Pivotsuche" bekannten Verfahren realisieren, auf die Pivotisierung darf dabei nicht verzichtet werden.
4. Berechnung der Anfangs- und Endkoordinaten von Verbindungslinien
Eine Verbindungslinie zwischen zwei Kugeln ist eine Strecke von der Oberfläche der einen Kugel zur Oberfläche der anderen Kugel, wobei die Strecke auf einer Geraden verläuft, die durch die Mittelpunkte beider Kugeln geht. Für zwei Kugeln, von denen die Mittelpunktskoordinaten und die Radien bezüglich eines orthonomalen Koordinatensystems bekannt seien, sollen die Anfangs- und Endkoordinaten der Verbindungslinie berechnet werden:| geg.: | Pi ( xi , yi , zi ) Position der Kugel i |
| ri Radius der Kugel i | |
| Pj ( xj , yj , zj ) Position der Kugel j | |
| rj Radius der Kugel j |
Für die Anfangs- und Endkoordinaten Si und Sj der Verbindungslinie zwischen den Kugeln erhält man:
| OSi = OPi + ri · PiPj / |PiPj| | |
| und | OSj = OPj - rj · PiPj / |PiPj| |
5. Drehung der Betrachterposition um die Blickposition
Für ein zyklisch arbeitendes Programm, bei dem sich die n Kugeln im Abbild um eine Achse drehen, die durch die Blickposition verläft, ist es einfacher, die Kugelkoordinaten beizubehalten und statt dessen die Betrachterposition um die Blickposition zu drehen. Es wird im folgenden der normierte Vektor a' berechnet, der einer Drehung des normierten Vektors a um einen senkrechten normierten Vektor s entspricht:| geg.: | a = BN / | BN | normierter Vektor Betrachterposition - Blickposition |
| s ( |s| = 1 ) senkrechter Vektor | |
| Fi ( |Fi| < 90 Grad ) Drehwinkel |
| Es gilt: | a = a||s + a|_s |
| a' = a'||s + a'|_s | |
| a'||s = a||s | |
| a'|_s = cos ( Fi ) · a|_s + sin ( Fi ) · ( s × a ) |
Man erhät als neuen normierten Vektor a' :
a' = ( a · s ) · s + cos ( Fi ) · ( a - ( a · s ) · s ) + sin ( Fi ) · ( s × a )
6. Berechnung des Abstandes eines Punktes von einer Ebene
Aus den n Kugeln sollen diejenigen ausgesucht werden, die höchstens einen gegebenen Maximalabstand von einer bestimmten Ebene E entfernt sind. Von der Ebene sind entweder drei Punkte gegeben oder ein Punkt und ein Normalenvektor.| geg.: | M Mittelpunkt einer Kugel |
| P1 Ebenenpunkt 1 | |
| P2 Ebenenpunkt 2 (Fall 1) | |
| P3 Ebenenpunkt 3 (Fall 1) | |
| n ( |n| = 1 ) Ebenennormale (Fall 2) | |
| Def.: | n = ( P1P2 × P1P3 ) / |P1P2 × P1P3| (nur für Fall 1) |
Für den Abstand d des Kugelmittelpunktes M von der Ebene E erhält man:
d = n · P1M
7. Schattierung einer Kugel
Zur besseren räumlichen Verdeutlichung ist es zweckmäßig, die Kugeln schattiert darzustellen. Es soll angenommen werden, daß das von einer Kugel abgegebene Licht aus einem reflektierten und einem diffusen Anteil besteht. Der reflektierte Anteil Iref sei durch eine gedachte punktförmige Lichtquelle in unendlicher Entfernung hervorgerufen, das diffuse Licht Idif durch die Eigenstrahlung der Kugel bzw. durch isotropes Hintergrundlicht. Es soll angenommen werden, daß die von einem Punkt der Oberfläche der Kugel abgegebene Lichtintensität in alle Richtungen gleich ist, unabhängig von der Richtung des einfallenden Lichtes. Des weiteren soll die gegenseitige Beeinflussung der Kugeln durch Schattenwurf oder Mehrfachreflexion vernachlässigt werden. Als hellster Punkt S ( Symmetriepunkt ) einer Kugel erscheint dann die Stelle, an der die Oberflächennormale in Richtung Lichtquelle zeigt. Es soll angenommen werden, daß der Symmetriepunkt stets auf der dem Betrachter zugewandten Seite liegt. Die abgegebene Lichtintensität des Symmetriepunktes sei normiert durch:IS = ISref + Idif = 1
Die abgegebene Lichtintensität unterscheidet sich für verschiedene Oberflächenpunkte einer Kugel nur im reflektierten Anteil. Für einen beliebigen Oberflächenpunkt P der Kugel mit dem Mittelpunkt M und dem Symmetriepunkt S erhält man dann:
IP = IPref + Idif mit
IPref = Max { ISref · cos ( Fi ) , 0 }
wobei Fi der Winkel zwischen den Vektoren MS und MP ist. Über die Beziehungen
sin ( Fi /2 ) = 1/2 · |SP| / |MS| ,
cos2 ( Fi /2 ) = 1 - sin2 ( Fi /2 ) und
cos ( Fi ) = 2 · cos2 ( Fi /2 ) - 1 erhält man
cos ( Fi ) = 1 - 1/2 · |SP|2 / |MS|2.
Die Berechnung der Helligkeit kann für alle darzustellenden Oberflächenpunkte einer Kugel direkt im Bildschirmkoordinatensystem erfolgen:
| geg.: | M ( XM , YM ) Mittelpunkt der Kugel |
| r Radius der Kugel (im Bildschirmkoordinatensystem) | |
| Idif ( 0 < Idif < 1 ) diffuser Lichtanteil | |
| S ( XS , YS ) Symmetriepunkt der Kugel | |
| Def.: | ZS = sqrt ( r2 - ( XS - XM )2 - ( YS - YM )2 ) |
| geg.: | P ( XP , YP ) Oberflächenpunkt der Kugel |
| Def.: | ZP = sqrt ( r2 - ( XP - XM )2 - ( YP - YM )2 ) |
Für die darzustellende Helligkeit des Oberflächenpunktes P der Kugel erhält man somit:
IP = ( 1 - Idif ) · Max {1 - 1/2 · ( ( XS - XP )2 + ( YS - YP )2 + ( ZS - ZP )2 ) / r2 , 0 } + Idif
Beim Zeichnen ist darauf zu achten, daß Terme, die für alle darzustellenden Oberflächenpunkte gleich sind, nur einmal berechnet werden ( z.B. ZS und r2 ), um somit die Rechenzeit und damit die Zeit, die für die Darstellung benötigt wird, minimal zu halten. Dem berechnete Helligkeitswert im Bereich zwischen 0 und 1 ist dann jeweils ein entsprechender Pixelfarbwert zuzuordnen.
8. Darstellung von Kalotten
Wenn der Abstand der Mittelpunkte zweier Kugeln kleiner ist, als die Summe ihrer Radien, durchdringen sich ihre Oberflächen gegenseitig, die Schnittfigur ist ein Kreis. OP1 sei der Vektor zum Mittelpunkt der ersten Kugel mit dem Radius r1 , OP2 sei der Vektor zum Mittelpunkt der zweiten Kugel mit dem Radius r2 . Für jeden Punkt PK auf dem Kreis gilt dann:P1PK2 = r12 und
P2PK2 = r22 = ( P1PK - P1P2 )2 = P1PK2 - 2 · P1P2 · P1PK + P1P22
Daraus erhält man:
P1P2 · P1PK = ( r12 - r22 + P1P22 ) / 2
Für den Mittelpunkt M des Kreises gilt:
P1M = ( P1PK · P1P2 / |P1P2| ) · ( P1P2 / |P1P2| )
Durch Einsetzen erhält man:
P1M = 1/2 · ( r12 - r22 + P1P22 ) · P1P2 / |P1P2| 2
Für die weitere Berechnung ist es zweckmäßig, das Bildschirmkoordinatensystem zu verwenden. Die aktuell darzustellende Kugel sei Kugel 1. Es soll angenommen werden, daß der Mittelpunkt P1 der Kugel 1 im Ursprung des Bildschirmkoordinatensystems liegt. Für die Z-Koordinate Z = ZK eines Punkt P, der auf dem sichtbaren Teil der Oberfläche der Kugel 1 liegt, gilt dann:
ZK = sqrt ( r12 - X2 - Y2 )
Für einen Punkt P, der auf der Ebene liegt, die durch den Schnittkreis der beiden Kugeln geht, gilt:
MP · OM = 0
( X - XM ) · XM + ( Y - YM ) · YM + ( Z - ZM ) · ZM = 0
Daraus erhält man für die Z-Koordinate Z = ZE des Ebenen-Punktes P:
ZE = ( XM2 + YM2 + ZM2 - X · XM - Y · YM ) / ZM
Mit Hilfe der Z-Komponenten läßt sich für jeden Bildschirmpunkt ermitteln, ob die Kugel oder die Kreisebene näher an der Betrachterposition liegt. Nach entsprechenden Fallunterscheidungen läßt sich somit für jeden Bildschirmpunkt ermitteln, ob er zu Kugel 1, Kugel 2, zur Schnittfläche oder zum Hintergrund gehört. Terme, die für alle Bildschirmpunkte einer Kugel gleich sind, sollten auch hier nur einmal berechnet werden (z.B. XM2 + YM2 + ZM2 ).
9. Darstellung von Koordinationspolyedern
Gegeben seien die (distinkten) Eckpunkte P1 ... Pn (n > 2) eines konvexen Polyeders, gesucht sind alle Facetten f1 ... fm des Polyeders. Diese Facetten sind konvexe Polygone und sollen als Listen von Punkten ermittelt werden, so daß zwei benachbarte Punkte in der Liste stets einer Kante der Facette entsprechen.Bei Koordinationspolyedern haben alle Eckpunkte in der Regel einen konstanten Abstand zum Mittelpunkt M und können folgendermaßen aus einer Menge von Punkten ermittelt werden:
- Ermittlung des Minimalabstandes r = Min {|MP1|, |MP2|, ...} eines Punktes vom Mittelpunkt
- alle Punkte i mit |MPi| <= c · r sind Eckpunkte des Polyeders, c ist geringfügig größer als 1 und gibt die maximal zulässige Verzerrung des Koordinationspolyeders an.
- Erzeuge (entartetes) Polyeder mit den 3 Eckpunkten P1, P2 und P3 und den 2 Facetten f1 = {P1, P2, P3} und f2 = {P1, P3, P2} mit den 2 Normalenvektoren n1 = - n2.
- Für j = 4 bis n wiederhole:
- Markiere alle Kanten, die nicht im neuen Polyeder enthalten sind:
Jede Kante gehört zu genau 2 Facetten und wenn sie nicht im neuen Polyeder enthalten ist, gilt für die 2 Facetten fk und fl, die diese Kante gemeinsam haben:
nk · PkPj > - EPSILON und nl · PlPj > - EPSILON
Pk und Pl sind beliebige Punkte der Facetten fk bzw. fl. Die Markierung der Kanten benötigt nur ein Bit und kann somit i. d. R. ohne zusätzlichen Speicherplatzbedarf realisiert werden (z. B. Vorzeichen bei integer-Index-Listen der Eckpunkte der Facetten verwenden). - Füge den Punkt Pj zu allen Facetten hinzu, wenn er in der Ebene der jeweiligen Facette liegt:
Ein Punkt Pj liegt genau dann in der Ebene der Facette fk, wenn gilt:
|nk · PkPj| < EPSILON
Der Punkt Pj ist in die Liste der Punkte der Facette entweder vor oder nach dem Punkt , zu dem er den geringsten Abstand hat, einzufügen. Von den beiden Varianten ist diejenige zu wählen, bei der sich für den Winkel am Punkt Pj (bzw. das Skalarprodukt der normierten Vektoren) der größere Wert ergibt, andernfalls erhält man kein konvexes Polygon. - Ersetze alle anderen Facetten, die nicht im neuen Polyeder enthalten sind, durch Dreiecks-Facetten:
Eine andere Facette fk ist genau dann nicht im neuen Polyeder enthalten, wenn gilt:
nk · PkPj > 0
Es ist für jede unmarkierte Kante dieser Facette eine neue Facette zu erzeugen, die die zwei Punkte der Kante und den Punkt Pj (in gleicher Reihenfolge) enthält, die ursprüngliche Facette ist zu löschen. - Setze alle Markierungen zurück
10. Berechnung der Orientierung eines gedrehten Koordinatensystems
Gegeben seien zwei orthonormale Koordinatensysteme im 3-dimensionalen Raum, die den selben Ursprung besitzen. Gesucht ist der Einheitsvektor r in Richtung der Rotationsachse und der Winkel Fi, so daß das erste Koordinatensystem bei einer Drehung um r mit dem Winkel Fi in das zweite Koordinatensystem überführt wird. Die Koordinatensysteme seien definiert durch je zwei senkrecht aufeinander stehende Einheitsvektoren e1 und e2 bzw. e'1 und e'2 (der jeweils dritte Einheitsvektor ergibt sich daraus zwangsläufig). Es können die folgenden Fälle unterschieden werden:- e1 = e'1, e2 = e'2: r = e1, Fi = 0
- e1 = e'1, e2 = - e'2: r = e1, Fi = 180°
- e1 = e'1, |e2 × e'2| > 0: r = (e2 × e'2) / |e2 × e'2|, Fi = arccos (e2 · e'2)
- e1 = - e'1, e2 = e'2: r = e2, Fi = 180°
- e1 = - e'1, e2 = - e'2: r = e1 × e2, Fi = 180°
- e1 = - e'1, |e2 × e'2| > 0: r = (e2 + e'2) / |e2 + e'2|, Fi = 180°
- |e1 × e'1| > 0, e2 = e'2: r = (e1 × e'1) / |e1 × e'1|, Fi = arccos (e1 · e'1)
- |e1 × e'1| > 0, e2 = - e'2: r = (e1 + e'1) / |e1 + e'1|, Fi = 180°
- |e1 × e'1| > 0, |e2 × e'2| > 0
(allgemeiner Fall):
s = (((e1 + e'1) × (e1 × e'1)) × ((e2 + e'2) × (e2 × e'2)))
wenn (|s × e1| > |s × e2|) dann u = s × e1, u' = s × e'1
sonst u = s × e2, u' = s × e'2
wenn ((u × u') · s > 0 ) dann r = s / |s| sonst r = - s / |s|, Fi = arccos ((u / |u|) · (u' / |u'|))
Werbung - Advertisement:
