Grafische 3D-Projektionen

Hier geht es um einen Schnelleinstieg zu notwendigen Grafik-Grundwissen.

Topologische und metrische Daten

Topologische Daten bestehen wesentlich aus Abhängigkeiten von Datenstrukturen,wie z.B. BREP-Daten.

Metrische Daten entsprechen mehr einer Menge von gleichartigen ( beziehunlosen ) Daten, wie z.B. Bitmaps ( Folge voneinander unabhängigen Bits ).

Es gibt z.B.

Browser und Dateiformate

Welche Dateiformate unterstützt der Browser? Siehe  Mime-Toolchen

Hier sind Übersichttabellen zu Dateiformaten der Grafik.
Siehe wikipedia-Listen zu Dateiformaten für Rastergrafiken ,
Siehe wikipedia-Listen zu Dateiformaten für 2D-Vektorgrafiken ,
Siehe wikipedia-Listen zu Dateiformaten für 3D-Vektorgrafiken

Isometrie, Dimetrie, Kavalierperspektive, Militärperspektive Vektorgrafik

In der darstellenden Geometrie, ist die Axonometrie ein Verfahren, um räumliche Objekte in einer Zeichenebene darzustellen ( siehe z.B. auch Darstellende Geometrie für Architekten (1,5 MB .pdf, Skript Uni Darmstadt) , de.wikipedia Dimetrie , Kavalierperspektive , de.wikipedia Militärprojektion ).

Unterschiedliche Standorte des Betrachters ergeben die Vorder - Ansicht, die Seiten - Ansicht, die Drauf - Sicht eines Körpers. Wie können die Punkte P( u, v ) in der Zeichen - Ebene berechnet werden, wenn alle Raum - Punkte P( x, y, z ) eines Körpers bekannt sind?

projektion_einfach.gif

Ein Raumpunkt P ( x, y, z ) wird auf die Zeichen - Ebene abgebildet. In der Zeichenebene hat der Punkt die Koordinaten ( u, v ). Mit den Winkel w1, w2 setzt sich die horizontale Strecke u zusammen aus y . cos(w1) - x . cos(w2). Die vertikale Strecke v ergibt sich durch z - y . sin(w1) - x . sin(w2). 

 u = - x . cos(w2)  +  y . cos(w1)
 v = - x . sin(w2)  -  y . sin(w1) + z

Sollen die x, y - Werte gestaucht werden, so werden Faktoren ux, uy,vx, vy eingeführt. 

 u = - x . ux . cos(w2)  +  y . uy . cos(w1) 
 v = - x . vx . sin(w2)  -  y . vy . sin(w1)  +  z

Zusammenstellung der Konstanten ux, uy, vx, vy:

Dimetrie
( Höhen erscheinen in wahrer Größe ) 		w1 = 7.18° w2 = 41.43° ux = 0.5, uy = 1.0,
vx = 0.5, vy = 1.0
Isometrie
( Höhen erscheinen in wahrer Größe ) 		w1 = 30.0° w2 = 30.0° ux = 1.0, uy = 1.0,
vx = 1.0, vy = 1.0
Kavalierperspektive
( Vorderansichten erscheinen in wahrer Größe ) 		w1 = 0.0° w2 = 45.0° ux = 0.5, uy = 1.0,
vx = 0.5, vy = 1.0
Militärperspektive
( Grundflächen erscheinen in wahrer Größe ) 		w1 = 45.0° w2 = 45.0° ux = 1.0, uy = 1.0,
vx = 1.0, vy = 1.0

Einfachste Formeln

Besonders einfache Isometrie - Formeln ergeben sich für w1 = 30.0°, w2 = 30.0° ux = uy = 2/sqrt(3), vx = vy = 1.0
Bei geringer Hardwareunterstützung und für schnelle Spiele auf ganzen Zahlen wird deshalb oft verwendet: 

 // 3D - SPIELE 
 u = y - x ,
 v = z - ( x + y ) / 2

Dies entspricht einer 4x4 - Matrizen - Multiplikation: 

 ( u )     ( -1    1    0   0 )   ( x )
 ( v )  =  (-1/2 -1/2   1   0 ) . ( y )
 ( w )     (  0    0    1   0 )   ( z )
 ( 1 )     (  0    0    0   0 )   ( 1 )

Die Determinante dieser 4x4 - Matrix ist 1. Diese Projektion hat dann besondere Vorteile, wenn gerätespezifisch ( Pixel ) auf ganzen Zahlen operiert wird ( 3D - Spiele ). Die Division wird durch eine schnelle Shift - Operation ersetzt. Dadurch ergeben sich kurze Ausführungszeiten.

Orthogonale Projektion

Eine speziell orthogonale Projektion liegt vor, wenn anstelle von u = y - x, v = z - ( x + y ) / 2 die etwas geänderte Projektion 

 u = y - x ,
 v = z - ( x + y ) / sqrt(2)

benutzt wird. Die ( nicht normierten ) Richtungs - Vektoren der Zeichenebene sind dann 

 U = (      -1,         1,         0  )  
 V = ( -sqrt(1/2), sqrt(1/2),      1  )  
 W = (       1,         1,    sqrt(2) )

Der Vektor W entspricht der Normalen der Zeichen - Ebene.

3D-Orthogonale Projektion ( allgemein ) Herleitung

Achtung! Die Winkelbezeichnung w1, w2 bedeutet hier Winkel für die Kugelkoordinaten. Die Winkel w1, w2 sind verschieden von den obigen 2D - w1, w2 - Winkeln von Isometrie, Dimetrie, Kavalierperspektive, Militärperspektive.

Die Lage eines Punktes P(x, y, z) auf einer Kugel kann durch die Angabe von r, w1, w2 erfolgen. Die r -, w1 -, w2 - Bereiche sind:   0 <= r,   0 <= w1 < 2 pi,   0 <= w2 <= pi 

 x = r . sin(w2) . cos(w1) ,          0 <= r,
 y = r . sin(w2) . sin(w1) ,     mit  0 <= w1 < 2 pi,
 z = r . cos(w2)                      0 <= w2 <= pi

Hierbei ist der Kugel - Mittelpunkt P0( 0, 0, 0). Der Kugelradius ist r. Bei der "Erdkugel" entspricht die geographischen Länge dem Winkel w1 und die geographische Breite dem Winkel ( w2 - pi/2 ). Durch einen Punkt P(x, y, z) auf der Einheitskugel ( r = 1 ) 

 x = sin(w2) . cos(w1) ,          0 <= u,
 y = sin(w2) . sin(w1) ,     mit  0 <= w1 < 2 pi,
 z = cos(w2)                      0 <= w2 <= pi

gehen Längen - und Breiten - Kreise. Zusammen mit der Radius - Verlängerung ergibt sich daraus ein lokales Koordinaten - System im Punkt P(x,y,z). Die partiellen Ableitungen ( von P nach w2 ), ( von P nach w1 ) / sin(w2), und P selbst ergeben die Matrix 

 (  c2.c1  -s1   s2.c1 )
 (  c2.s1   c1   s2.s1 )
 ( -s2      0    c2    )

wobei c1 = cos(w1), c2 = cos(w2), s1 = sin(w1), s2 = sin(w2) ist. Die Matrix ist durch die beiden Winkel w1, w2 festgelegt. 

 (  c2.c1   c2.s1   -s2    )
 ( -s1      c1       0     )
 (  s2.c1   s2.s1    c2    )

Die Determinante ist (c12 + s12 ) .(c22 + s22 ) = 1. Die Beträge jeder Spalte und Zeile sind 1. Die inverse Matrix ergibt sich durch die Spiegelung der Matrix - Elemente an der Hauptdiagonalen. Mit den Faktoren 

 ux = -sin(w1),         uy = cos(w1) ,
 vx =  cos(w1).sin(w2), vy = sin(w1).sin(w2),  vz = cos(w2)
ergeben sich die Formeln für die orthogonale Projektion 
 u = ux . x  +  uy . y ,
 v = vx . x  +  vy . y   +  vz . z

Die ux, uy, vx, vy, vz - Zahlen werden einmal berechnet. Dann werden i.a. viele 3D - Punkte P( x, y, z ) in die 2D - Punkte ( u, v ) der Zeichen - Ebene umgerechnet. Der Vektor W = ( c2.c1, c2.s1, -s2 ) entspricht dem Normalen - Vektor der Zeichen - Ebene. W wird zur Sichtbarkeit - Berechnung von P benötigt.
Speziell für die Winkel w1 = 45°, w2 = - 45° ergibt sich 

 u =  ( y - x )/sqrt(2) ,
 v = -( x + y )/2  + z/sqrt(2)
oder anders skaliert 
 u = y - x ,
 v = z - ( x + y ) / sqrt(2)

Die ( u, v ) - Werte entsprechen den 2D - Bild - Koordinaten des 3D - Punktes P(x, y, z). Der Vektor W = ( 1, 1, sqrt(2) ) entspricht dem Normalen - Vektor der Zeichen - Ebene. W wird zur Berechnung der Sichtbarkeit von P benötigt.

Orthogonale Projektion ( Pseudo-Code )

Die orthogonale Projektion soll den 3D - Punkt bRxyz P in den Bildpunkt B um rechnen. Hierzu soll bRxyz B = P.Projektion() verwendet werden. Von B werden lediglich die Komponenten B.x, B.y verwendet.

Die überladene Funktion Projektion( w1, w2 ) hat keinen Rückgabewert. Es werden lediglich die static Variablen U, V, W der Zeichenebene berechnet und gespeichert. W entspricht der Haupt - Blickrichtung. 

 // Pseudo-Code
function projektion_init( double w1, double w2 ) {
    double x, y, z; U = V = W = null;
    w1 = w1/180*Math.PI; w2 = w2/180*Math.PI; //in Bogenmass
    x =-Math.sin(w1);              
    y = Math.cos(w1);              //Zeichenebene U, V, W
    z = 0.0;                       U = {x:x, y:y, z:y}; 
    x = Math.cos(w1)*Math.sin(w2); 
    y = Math.sin(w1)*Math.sin(w2); //Zeichenebene U, V, W
    z = Math.cos(w2);              V = = {x:x, y:y, z:y};
    x = Math.cos(w1)*Math.cos(w2); //Zeichenebene U, V, W
    y = Math.sin(w1)*Math.cos(w2); //W ist die Normale
    z =             -Math.sin(w2); W = {x:x, y:y, z:y}; 
    return {U:U, V:V, W:W};
}
function projektion( x, y, z ) {
    u = U.x * x + U.y * y ; 
    v = V.x * x + V.y * y  + V.z * z ; 
    return {u, v, 0}; 
}
};
⁝ 3D-Zentralprojektion Mathematische Herleitung
Historisches ( Perspektive [lat.] )

Historisches ( Perspektive [lat.] ): Bereits in der Antike verwendeten die Malerei und bildende Kunst bei Theater- und Wandmalerei die Raumtiefe und Verkürzungen nach "Gefühl".

Der Fluchtpunktsatz geht auf das 14.Jh.n.Chr. zurück. Beispiel: Fresko von Domenico Ghirlando Szene mit Jungfrau Maria ( 1486-1490, Cappela Tornabuoni)

fluchtpunkt.jpg

Heute fokusiert die Kamera-Linse mit Zentralprojektion:
kamera.jpg
Zentralprojektion ( Mathematische Herleitung )

In dem folgenden Bild sind die Bezeichnungen enthalten. Große Buchstaben sind 3D - Vektoren. Kleine Buchstaben skalare Werte ( Koordinaten ). Alle 3D - Raumpunkte werden in einem kartesischen x,y,z - Koordinatensystem angegeben. Die Körperpunkt werden mit P(x,y,z) bezeichnet. Der Körper besteht aus vielen 3D - Punkten. Diese Punkte werden auf die Bild - Ebene projiziert. Dann entsteht in dieser Eben das Bild des Körpers. Die Bild - Ebene ist durch die orthogonalen Einheitsvektoren U, V, W und den Bild - Bezugspunkt P0(x0,y0,z0) festgelegt. Wenn U, V, W, P0, E, P gegeben sind, so sollen nun

  • die u,v - Koordinaten in der Bildebene berechnet werden.
zentralprojektion.gif

Das Auge ( Eye ) entspricht dem Projektionszentrum ( Zentalprojektion ). Vom Auge E(ex,ey,ez) geht der Blickstrahl zu einem Körper - Punkt P(x,y,z).

Der Blickstrah durchstößt im Punkt B die Bild - Ebene. In der Geraden - Gleichung 

   B        =   E         + t . ( P - E )   oder
 ( B - P0 ) = ( E - P0 )  + t . ( P - E )

ist B und t unbekannt. Weil ( B - P0 ) in der Zeichenebene liegt und damit senkrecht zu W ist, wird das Skalarprodukt "o" dieser Gleichung mit W gebildet. ( B - P0 ) o W ist 0. 

 0 = ( E - P0 )o W  + t . ( P - E ) o W

Darau ergibt sich der gesuchte Geraden - Parameter t des Bild - Punktes B zu 

       ( P0 - E ) o W
  t = ----------------
       ( P  - E ) o W

Mit t kann ( B - P0 ) berechnet werden. Die u,v - Koordinaten in der Zeichenebene ergeben sich als Skalarprodukt von ( B - P0 ) mit dem Einheisvektoren U, V gemäß 

       ( P0 - E ) o W
  t = ----------------  ,
       ( P  - E ) o W

  u  = U o ( B - P0 )  =  U o { ( E - P0 )  +  t . ( P - E )  },

  v  = V o ( B - P0 )  =  V o { ( E - P0 )  +  t . ( P - E )  }

Zu einem gegebenen Körperpunkt P(x,y,z) kann zunächst t und dann u,v berechnet werden. Die Abbildung versagt, wenn das Auge in der Bildebene liegt oder ein Körperpunkt P im Auge E ist.

Wahl der Bildebene

Nun sollen die Vorüberlegungen zu üblichen U, V, W - Vorgaben vereinfacht werden. Diese Skalierung von N verkürzt die numerische Berechnung. Annahme: Die Netzhaut des Auges ist senkrecht zur Haupt - Blickrichtung. Die Haupt - Blickrichtung ist die Richtung vom Auge zur Bildmitte P0.

  • Das Auges E soll immer auf der Haupt - Blickrichtung sein.

Für die t - Berechnung kann Zähler und Nenner erweitert werden. Es wird t verwendet: 

       ( P0 - E ) o W      ( P0 - E ) o N
  t = ----------------  = ----------------
       ( P  - E ) o W      ( P  - E ) o N
  • Anstelle von W wird nun die Vereinfachung N := ( P0 - E ) ( P0 - E )2 gewählt.
zentralprojektion1.gif
  • Nun wird lediglich E ( Eye-Vector ), P0 ( Center-Point ), Vd ( up-Vector ) vorgegeben und daraus U, V, W berechnet.

Vd ist ein ( willkürlicher ) Vektor für die "(V)ertikale (d)irection". Z.B. kann Vd = ( 0.0, 1.0, 0.0 ) gewählt werden. Ist E, P0, Vd gegeben, so können die Einheitsvektoren U, V, W berechnet werden gemäß 

        ( P0 - E )
 N :=  -------------
        ( P0 - E )2
 U := N x Vd,    U := U / | U | ,
 V := U x N ,    V := V / | V | ,
 W := U x V
Berechnung der Einheitsvektoren U, V, W

Diese Berechnung der Einheitsvektoren U, V, W ist nur einmal erforderlich. Danach sind viele Körperpunkte P(x,y,z) in die Koordinaten u,v der Zeichen - Ebene umzurechnen. 

 nn  :=  N o ( P - E ),     Fehler, falls nn == 0 ist
 uu  :=  U o ( P - E ),     u  =  uu / nn
 vv  :=  V o ( P - E ),     v  =  vv / nn

Durch "o" wird das Skalarprodukt gekennzeichnt. Je Körperpunkt P sind 9 Multiplikationen und 2 Divisionen erforderlich.

  • Wandert der Körper - Punkt P vom Auge E zur Bild - Ebene, so läuft nn von 0.0 bis 1.0.
Bei z - Buffer - Sichtbarkeits - Verfahren wird nn direkt für die "Tiefe" eines Punktes verwendet.
Wahl des Bildmittelpunktes

Zur Beschreibung eines 3D - Körpers werden Punkte P(x,y,z) verwendet. Mit Hilfe dieser Punkte werden die Körper beschrieben. Alle gegebene Punkte liegen in einem umschließenden Quader. Die Bildebene soll so angeordnet werden, daß der Mittelpunkt P0(x0,y0,z0) der Bildebene gleich dem Mittelpunkt des umschließenden Quaders ist.

zentralprojektion2.gif

Zum besseren Vorstellen seien lediglich 4 Punkte Pk(xk,yk,zk) mit k = 0, 1, 2, 3 in einer Punkte - Tabelle gegeben.

k x[k] y[k] z[k] Bemerkungen
0  17.3   5.1   6.2 Indem alle xk durchgegangen werden ergeben sich xMin, xMax.
Indem alle yk durchgegangen werden ergeben sich yMin, yMax.
Indem alle zk durchgegangen werden ergeben sich zMin, zMax.
1  -1.3  -6.1  13.3
2  51.5 -55.5  -0.5
3  31.1 -33.3  -0.3
  xMin yMin zMin
  xMax yMax zMax

Alle Körper - Punkte Pk liegen in dem umschließenden Pmin, Pmax - Quader. Der Quader - Mittelpunkt P0 und die halbe Quader - Dagonale R ist dann 

 P0  = ( Pmax + Pmin ) / 2 ,
 R   = ( Pmax - Pmin ) / 2
  • R ist auch der Radius der umschließenden Kugel.
  • Alle Körper - Punkte Pk liegen in der umschließenden Kugel.

Der Rand - Blickstrahl berührt die umschließende Kugel tangential. Deshalb ist R etwas zu vergrößern, damit alle Punkte Pk in der

  • ( uMin, vMin, uMax, vMax ) - Bildebene

erscheinen. Aus dem umschließenden Pmin, Pmax - Quader kann die ( kleinste ) Größe der Bild - Ebene berechnet werden: 

 P0  = ( Pmax + Pmin ) / 2 ,
 R   = ( Pmax - Pmin ) / 2 ,

 r  = | R | ,  e  = | P0 - E | ,   e > r ,

                     r . e
 rr = -------------------------------
       sqrt( ( e - r ) . ( e + r ) )

 uMin = -rr ,  uMax = +rr ,
 vMin = -rr ,  vMax = +rr

Sind alle Körper - Punkte Pk und die Position E des Auges bekannt, so kann der Reihe nach Pmin, Pmax, P0, R, r, e, rr, uMin, vMin, uMax, vMax berechnet werden. Dann liegt auch die Haupt - Blick - Richtung N fest und mit Vd auch U, V, W fest. Die Zentalprojektion ( 4x4 Matrix ) kann durchgeführt werden. Alle 3D - Punkte Pk erscheinen in der ( u, v ) Bilde - Ebene.

Zentralprojektion in homogenen Koordinaten

Die obigen Formel können in eine 4x4 - Matrix übertragen werden. Die Skalar - Produkte NoE, UoE, VoE werden einmal berechnent. 

 ( uu )     (  ux    uy    uz |  - U o E)   ( x )   
 ( vv )     (  vx    vy    vz |  - V o E)   ( y )   
 ( 0  )  =  (  0     0     0  |      0  ) . ( z )   
 ------     (-----------------|---------)   -----   
 ( nn )     (  nx    ny    nz | - N o E )   ( 1 )

 u := uu / nn
 v := vv / nn
Sonderfälle

1. Sonderfall

P0 = ( 0, 0, 0 ), Eye E = ( ex, ey, ez ) aus. Der Reihe nach ergibt sich: 

 P0 := ( 0,0,0 ),  
 E := ( ex, ey, ez ); 
 U := ( 1, 0, 0 ),   V := ( 0, 1, 0 ),   W := (  0,  0,  1 ),
 N = (P0-E)/(P0-E)2 = -( ex, ey, ez )/ (ex^2 + ey^2 + ez^2) ,
 N o E = -1,   U o E = ex,   V o E = ey,
 nn := 1 - z * ( ez / e2 )
 
 Mit  e := (ex2 + ey2 + ez2) / ez  ergibt sich

 u = x / ( 1 - z / e )
 v = y / ( 1 - z / e )

2. Sonderfall

Befindet sich das Auge auf der z-Achse, so wird mit ex = 0, ey = 0, ez = e aus dem 1. Sonderfall: 

 Mit   e := ez  ergibt sich

 u = x / ( 1 - z / e )
 v = y / ( 1 - z / e )

3. Sonderfall

Wenn der zentrale Punkt E ins Unendliche wandert, so geht die Zentralprojektion in die Parallelprojektion über. Die Projektions - Formeln hängen dann nicht mehr von E ab. 

           ( P0 - E ) o W
 Mit  t = ----------------    --->  1   ergibt sich
           ( P  - E ) o W

 u  = U o ( P - P0 ) 
 v  = V o ( P - P0 )


Es werden folgende Berechnungen durchgefuehrt:

      Vd                    Vd = Vertikale Richtung
      Wd = Eye - Org        Wd = -Hauptblickrichtung

      U = Vd x Wd           U = U / |U|
      V = Wd x U            V = V / |V|
      W = Wd /|Wd|/|Wd|,    W hat gleiche Richtung wie Wd !

  if ( Eye == NULL ) Eye = MAT_set_vec( & Eye, 0.0, 0.0, -1.0/EPSILON ) ;
  if ( Org == NULL ) Org = MAT_set_vec( & OO,  0.0, 0.0, 0.0 ) ;
  if ( Vd == NULL )  Vd  = MAT_set_vec( & VV,  0.0, 1.0, 0.0 ) ;

  Wd.x = Eye.x - Org.x ;
  Wd.y = Eye.y - Org.y ;
  Wd.z = Eye.z - Org.z ;

  h2 = fabs( Wd.x * Wd.x + Wd.y * Wd.y + Wd.z * Wd.z ) ;

  if ( h2 < EPSILON ) { //Setze irgendwas, trotz Fehler!
    Eye.x = -1.0/EPSILON ; Eye.y = -2.0/EPSILON ; Eye.z = -10.0/EPSILON ;
    Wd.x = Eye.x - Org.x ; 
    Wd.y = Eye.y - Org.y ; 
    Wd.z = Eye.z - Org.z ;
    h2 = fabs( Wd.x * Wd.x + Wd.y * Wd.y + Wd.z * Wd.z ) ;
  }
  if ( h2 < EPSILON ) goto MAT_set_projErr ;

  MAT_vec_cross_prod( U, Vd, Wd ) ; isOk = MAT_vec_norm( U );

  if ( ! isOk ) {//Setze irgendwas, trotz Fehler!
    Vd.x = fabs( Wd.z ) + fabs( Wd.y ) ; Vd.y = fabs( Wd.x ) + fabs( Wd.z ) ; Vd.z = fabs( Wd.y ) + fabs( Wd.x ) ;
    MAT_vec_cross_prod( U,  Vd, Wd ) ; isOk = MAT_vec_norm( U );
  }

  MAT_vec_cross_prod( V, Wd, U ) ; isOk &= MAT_vec_norm( & V );

  W.x = Wd.x / h2 ;
  W.y = Wd.y / h2 ;
  W.z = Wd.z / h2 ;

  if ( ! isOk ) goto MAT_set_projErr ;
  //memset( & Mat, 0, sizeof( RMAT4X4 ) ) ; 

  MAT_vec_scalar_prod ( h2, W, Eye ) ; Mat[0][0] = +h2 ;
  MAT_vec_scalar_prod ( h2, U, Eye ) ; Mat[1][0] = -h2 ;
  MAT_vec_scalar_prod ( h2, V, Eye ) ; Mat[2][0] = -h2 ;

  Mat[0][1] = -W.x ; Mat[0][2] = -W.y ; Mat[0][3] = -W.z ;
  Mat[1][1] = +U.x ; Mat[1][2] = +U.y ; Mat[1][3] = +U.z ;
  Mat[2][1] = +V.x ; Mat[2][2] = +V.y ; Mat[2][3] = +V.z ;

//Alternative 1  
  Mat[3][0] = Mat[3][1] = Mat[3][2] = Mat[3][3] = 0.0 ; 
//?Alternative 2, W sollte Einheitsvektor, h2 ?
//Mat[3][0] = -h2 ; Mat[0][1] = W.x ; Mat[3][2] = W.y ; Mat[3][3] = W.z ;
  
  pRMAT4X4_EXT = MAT_set_4x4( idx, & Mat ) ;
OpenGL-Projetion

Eine perspektivische Projektion bildet mit Hilfe von Matrizen-Multiplikationen die Geometrie eines 3D - Objektes ( Model - Space ) auf ein "Einheitsvolumen" ab, das dann die reelle 2D - Ebene ( Projection Plane, Zeichenfläche ) ergibt. Speziell bei der orthogonalen Projektion wird ein (x2,y2,z2)-(x1,y1,z1)-Quader auf das (1,1,1)-(-1,-1,-1)-Volumen abgebildet. Z.B. kann für den (x2,y2,z2)-(x1,y1,z1)-Quader der alle Objekte umfassende Quader gewählt werden.

Die beiden folgenden Matrizen sind invers zueinander, d.h. es ist die 4x4 Einheitsmatrix = MAT * ORTHO = ORTHO * MAT. 

Mit
    dx := (x2 - x1)/2  
    sx := (x1 + x2)/2

        ( dx |  0 |  0 | sx  )
        (  0 | dy |  0 | sy  )
MAT   = (  0 |  0 | dz | sz  )
        (  0 |  0 |  0 |  1  ) 

Es ist det(MAT) = dx · dy · dz

        ( 1/dx |  0   |  0   |-sx/dx )
        (  0   | 1/dy |  0   |-sy/dy )
ORTHO = (  0   |  0   | 1/dz |-sz/dz )
        (  0   |  0   |  0   |   1   ) 

Es ist det(ORTHO) = 1 / ( dx · dy · dz )

Ist t die Transposition und 

  E1 = (-1,-1,-1, 1)t, P1 = (x1,y1,z1, 1)t,
  E2 = ( 1, 1, 1, 1)t, P2 = (x2,y2,z2, 1)t

so gilt 

  MAT * E1 = P1,     ORTO * P1 = E1, 
  MAT * E2 = P2,     ORTO * P2 = E2.

Alle Punkte P = (x,y,z) im umschließenden (x1,y1,z1, x2,y2,z2) - Quader
können mit Hilfe von ORTO * P in den (-1,-1,-1, 1, 1, 1) - Quader abgebildet werden mit Q = (qx,qy,qz) = MAT * (x,y,z) 

dx := (x2-x1)/2,  sx := (x1 + x2)/2

qx =  x · dx + sx  
qy =  y · dy + sy  
qz =  z · dz + sz   

x = ( qx - sx ) / dx
y = ( qy - sy ) / dx
z = ( qz - sz ) / dx
Sichbarkeit von 3D-Flächen Normalenvektor

Bei einem ( undurchsichtigen ) Körper sind lediglich die Oberflächen sichtbar. Um einen Körper im BREP-Daten-Modell zu beschreiben müssen alle Oberflächen des Körpers systematisch hinterlegt werden. Die Berechnung der Sichtbarkeiten von Objekten kann u.a. abhängen

Normalen- und Flächen-Vektor

Ein ebenes Polygon ist durch die Randpunkte Pi(xi, yi, zi ) festgelegt. Für ein n-Eck ist der Index i = 0, 1, 2, ..., (n-1). Die Punkt - Folge ist wichtig, weil die begrenzenden Kanten der Reihe nach gezeichnet werden. Wird die Fläche auf dem Rand umlaufen, so befindet sich die Fäche immer links vom Weg. Die Umlauf - Richtung legt den Normalen - Vektor und damit die Außen - Seite der Fläche fest. In dem folgenden Bild ist ein ebenes Fünf - Eck gezeichnet.

hidden1.gif Normalenvektor N

Das Vektor - Produkt ( x ) zweier Vektoren entspricht der aufgespannten Parallelogramm - Fläche. Aus den gegebnen 5 Punkten Pi(xi, yi, zi ) kann der Flächen - Vektor A( ax, ay, az ) mit den folgenden Vektor - Produkten berechnet werden. 

  2 . A  = 
           ( P1 - Q ) x ( P0 - Q )  +
         + ( P2 - Q ) x ( P1 - Q )  +
         + ( P3 - Q ) x ( P2 - Q )  +
         + ( P4 - Q ) x ( P3 - Q )  +
         + ( P0 - Q ) x ( P4 - Q )

Hierbei ist Q ein beliebiger Punkt. Das Ergebnis A hängt nicht von Q ab. Nach Vereinfachungen ergeben sich die folgenden Formeln zur Berechnung des Flächen - Vektors A( ax, ay, az ) 

 SUM summiert von i = 0 bis (n-1), 
 mit  j := i + 1 und falls  j >= n  dann j := 0
 ============================================
     ax  = 0.5 . SUM ( yi - yj ) . ( zi + zj )  
     ay  = 0.5 . SUM ( zi - zj ) . ( xi + xj )  
     az  = 0.5 . SUM ( xi - xj ) . ( yi + yj ) 
 ============================================
 | A | = sqrt( ax2 +  ay2 +  az2 )

Der Betrag | A | entspricht dem Fläche - Wert in m2. Der Normalenvektor N( nx, ny, nz ) ist der normierte Flächen - Vektor: 

   nx = ax / | A |  
   ny = ay / | A |  
   nz = az / | A |

Pyramidenvolumen

Die 5 Punkte P0, P1, P2, P3, P4 bilden in dieser Reihenfolge die Grundfläche einer Pyramide. Der Normalen - Vektor N zeigt nach außen. Die Pyramiden - Spitze ist Q.

pyramidenvolumen.gif

Die Pyramiden - Höhe ist h. Das Pyramiden - Volumen vol. 

 h   = ( Pi - Q ) o N ,

 vol = | A | . h / 3

Durch "o" wird das Skalar - Produkt gekennzeichnet. Für Pi kann irgend ein Punkt der Grund - Fläche verwendet werden. Es wird P0 benutzt. Dann ist das Pyramiden - Volumen: 

   vol = ( P0 - Q ) o A / 3

Das Volumen wird negativ, wenn die Reihenfolge der Punkte Pi invertiert wird.

Analytische Berechnung des Normalen-Vektors

Zur Veranschaulichung diene eine Regel - Fläche ( ruled surface ) Wird eine Gerade P = P1 + v . ( P2 - P1 ) im Raum bewegt, so entsteht die Fläche 

   P(u,v) = P1( u ) +   v  . ( P2( u ) - P1( u ) )
regel_flaeche.gif

Ist P'(u) die partielle Ableitung von P(u,v) nach u und P'(v) die partielle Ableitung von P(u,v) nach v, so ergibt sich der nicht normierte Normalen - Vektor 

 N(u,v) = P'(u) x P'(v)

als Vektor - Produkt der partielen Ableitungen. "x" kennzeichnet das Vektor - Produkt.
Für eine Regel-Fläche P(u,v) = P1(u) + v . ( P2(u) - P1(u) ) ergibt sich N(u,v) = { P1'(u)+ v.(P2'(u)-P1'(u)) } x ( P2 - P1 )

Siehe auch Differential Geometry of Surfaces .

Näherungsberechnung des Normalen-Vektors

Ist eine Fläche durch die Parameter - Funktion P(u,v) gegeben, so können innerhalb einer Doppel - Schleife ( u = u1 ... u2 step du, v = v1 ... v2 step dv ) die Koordinaten x(u,v), y(u,v), z(u,v) der Flächen - Punkte berechnet werden. Ist die Schrittweite du, dv hinreichend klein, so kann zwischen den benachbarten Punkten ein linearer Verlauf angenommen werden.

nomale1.gif

Der genäherte Normalen - Vektor N kann dann ( ohne Ableitungen ) durch das Vektor - Produkt 

 N(u,v)  =  dU x dV  =  ( P10 - P00 ) x ( P01 - P00 )

berechnet werden. N ist nicht normiert.

3D-Objektmodellierung CAD: BREP-Modell

Eines physikalisch-geometrisches Objekt ( Blume, Haus, Maschine, usw. ) kann mit Datenstrukturen modelliert werden. Eine solche Repräsentation mit Datenstrukturen ist mehr als nur ein Bild, das z.B. als Draht - Modell, Flächen - Modelle, Volumen - Modell gerndert werden kann. Ein physikalisch-geometrisches Objekt kann z.B. bewegt und mit grafischen Methoden in den Bildraum ( Bildebene ) projiziert werden. Die generierten Bilder sind dann nur ein otische Objekt-Präsentation Beispiele sind virtuelle 3D-Objekte, virtuelle Landschaften, Digitales Geländemodell, Kinematik, Gang durch ein virtuelles Gebäude, 3D-Spiele, usw.

Quader in B-REP-Modell ( Lehrbeispiel )

Das Speichern von grafischen Daten kann in unterschiedlicher Weise erfolgen. 2D - Bilder können z.B. pixelweise ( unter Verwendung von Kompressions-Algorithmen ) gespeichert werden. Diese Speicherart ist geräteabhängig. Zwischen den Bild - Elementen bestehen lediglich Pixel - Nachbarschaften.

Zum Speichern von geometrischen Körper - Daten ist die Model - Daten - Struktur wesentlich. Für einen Quader der Seitenlängen a = 2.0, b = 1.0, c = 3.0 können die folgenden Punkt -, Kanten - und Flächen - Tabelle aufgeschrieben werden.

  kartesische Koordinaten                Anfangs- und End- 
  für den i-ten                          Punkt-Nummer für die k-te 
  Eckpunkte P:                           Kanten K:
  |  j   x      y      z                          k   j1   j2  
  |----|------|-----|-----|             |----|----|----|----
  |  0 |  0.0 | 0.0 | 0.0 |             |  0 |  1 |  2 |
  |  1 |  2.0 | 0.0 | 0.0 |             |  1 |  2 |  6 |
  |  2 |  2.0 | 1.0 | 0.0 |             |  2 |  6 |  5 |    0. Fläche
  |  3 |  0.0 | 1.0 | 0.0 |             |  3 |  5 |  1 |
  |----|------|-----|-----|             |----|----|----|----
  |  4 |  0.0 | 0.0 | 3.0 |             |  4 |  0 |  4 |
  |  5 |  2.0 | 0.0 | 3.0 |             |  5 |  4 |  7 |
  |  6 |  2.0 | 1.0 | 3.0 |             |  6 |  7 |  3 |    1. Fläche
  |  7 |  0.0 | 1.0 | 3.0 |             |  7 |  3 |  0 |
  |----|------|-----|-----|             |----|----|----|----
                                        |  8 |  3 |  7 |
                                        |  9 |  7 |  6 |
                                        | 10 |  6 |  2 |    2. Fläche
  Anfangs- und End-                     | 11 |  2 |  3 |
  Punkt-Nummern der                     |----|----|----|----
  i-ten begrenzenden                   | 12 |  0 |  1 |
  Fläche A:                             | 13 |  1 |  5 |    3. Fläche
                                        | 14 |  5 |  4 |
     i   k1   k2                       | 15 |  4 |  0 |
  |----|----|----|---                   |----|----|----|----
  |  0 |  0 |  3 |                      | 16 |  4 |  5 |
  |  1 |  4 |  7 |                      | 17 |  5 |  6 |
  |  2 |  8 | 11 |                      | 18 |  6 |  7 |    4. Fläche
  |  3 | 12 | 15 |                      | 19 |  7 |  4 |
  |  4 | 16 | 19 |                      |----|----|----|----
  |  5 | 20 | 23 |                      | 20 |  0 |  3 |
  |----|----|----|---                   | 21 |  3 |  2 |
                                        | 22 |  2 |  1 |    5. Fläche
                                        | 23 |  1 |  0 |
                                        |----|----|----|----

Zum Speichern von geometrischen Körper-Daten ist die Daten - Struktur wesentlich. Die x-, y- , z - Koordinaten der Körper-Punkte können in x[],y[],z[] Arrays gespeichert werden. Z.B. hat der 5 - te Körper-Punkt ( j=5, P5 ) die 3D - Koordinaten ( 2.0, 0.0, 3.0 ).

Weil jede Fläche durch die Punkt - Folge ( Umlaufrichtung beachten ) festgelegt wird, so wird jede ( ungerichtete ) Kante in 2 entgegen gesetzte Richtungen durchlaufen. Die 1 - te Kante verbindet den Punkt P2 mit P6. Die 10 - te Kante verbindet den Punkt P6 mit P2. Die 1 - te Kante gehört zur 0 - ten Fläche. Die 10 - te Kante gehört zur 2 - ten Fläche.

  // Punkte  j=0.,  1.,  2.,  3.,   4.,  5.,  6.,  7.- Punkt
  double x[]={ 0.0, 2.0, 2.0, 0.0,  0.0, 2.0, 2.0, 0.0 }; 
  double y[]={ 0.0, 0.0, 1.0, 1.0,  0.0, 0.0, 1.0, 1.0 };
  double z[]={ 0.0, 0.0, 0.0, 0.0,  3.0, 3.0, 3.0, 3.0 };
  //Kanten k=0,1,2,3 | 4,5,6,7 | 8,9, .........................   22,23.-Kante
  int j1[]={ 1,2,6,5,  0,4,7,3,  3,7,6,2,  0,1,5,4,  4,5,6,7,  0,3,2,1 }; 
  int j2[]={ 2,6,5,1,  4,7,3,0,  7,6,2,3,  1,5,4,0,  5,6,7,4,  3,2,1,0 }; 
  for ( k = 0; i < 24; i ++ ) { //alle Kanten ( doppelt )
    xj1 = x [ j1 [ k ] ];  xj2 = x [ j2 [ k ] ]; 
    yj1 = y [ j1 [ k ] ];  yj2 = y [ j2 [ k ] ]; 
    zj1 = z [ j1 [ k ] ];  zj2 = z [ j2 [ k ] ];
    //Linie von (xj1, yj1, zj1) nach (xj2, yj2, zj2)
  }

Verbesserungen

Durch hinzufügen eines weiteren A - Index ( hier 6 ) kann auf die k2 Spalte in der Flächen - Tabelle A verzichtet werden. Zur 2 - te Fläche gehören in der Kanten - Tabelle die Indizes 8 bis ( 12 - 1 ). 

  Anfangs- und ( End-Punkt-Nummern +1 )
  der i-ten begrenzenden Fläche A:
                  
      i    k1     --> weitere Daten
  |--------------------------------------------------
  |   0  |  0 |   --> Daten für die 0 - te Fläche   
  |   1  |  4 |   --> Daten für die 1 - te Fläche   
  |   2  |  8 |   --> Daten für die 2 - te Fläche   
  |   3  | 12 |   --> Daten für die 3 - te Fläche   
  |   4  | 16 |   --> Daten für die 4 - te Fläche   
  |   5  | 20 |   --> Daten für die 5 - te Fläche   
  |   6  | 24 |   --> Daten für das Volumen
  |--------------------------------------------------

Auf die j2 - te Spalte der Kanten - Tabelle K kann verzichtet werden, weil zwei aufeinander folgende i Indizes der Flächen - Tabelle A die j Indizes der Kanten - Tabelle festlegen. /* Aufruf Quader * pQuader = new Quader(a,2.0-a,3.0); pQuader->draw(); delete pQuader; */

Quader als BREP-Modell

class Quader {
int A[7]; //Flaechentab A
double Area[6], Ax[6],Ay[6],Az[6];//normierte Normalen Ax,Ay,Az
int K[24]; //Kantentab K
double * pX,* pY,* pZ; //Punktetab X,Y,Z
public:
int anzA, anzK, anzP;
void drawArea( int i );
void draw();
bool calcNormalen();
~Quader() { delete pX; delete pY; delete pZ; }
Quader(double aa, double bb, double cc ) {
  anzA = 6;  //Flaechentabelle
  A[0]= 0;  A[1]= 4;  A[2]= 8;
  A[3]=12;  A[4]=16;  A[5]=20;  A[6]=24;
  anzK = 12;  //Kantentabelle
  K[ 0]=1;  K[ 1]=2;  K[ 2]=6;  K[ 3]=5;
  K[ 4]=0;  K[ 5]=4;  K[ 6]=7;  K[ 7]=3;
  K[ 8]=3;  K[ 9]=7;  K[10]=6;  K[11]=2;
  K[12]=0;  K[13]=1;  K[14]=5;  K[15]=4;
  K[16]=4;  K[17]=5;  K[18]=6;  K[19]=7;
  K[20]=0;  K[21]=3;  K[22]=2;  K[23]=1;
  anzP = 8;  //Punktetabelle
  pX = new double[anzP];
  pY = new double[anzP];
  pZ = new double[anzP];
  pX[0] = -aa; pY[0] = -bb; pZ[0] = -cc;
  pX[1] = +aa; pY[1] = -bb; pZ[1] = -cc;
  pX[2] = +aa; pY[2] = +bb; pZ[2] = -cc;
  pX[3] = -aa; pY[3] = +bb; pZ[3] = -cc;
  pX[4] = -aa; pY[4] = -bb; pZ[4] = +cc;
  pX[5] = +aa; pY[5] = -bb; pZ[5] = +cc;
  pX[6] = +aa; pY[6] = +bb; pZ[6] = +cc;
  pX[7] = -aa; pY[7] = +bb; pZ[7] = +cc;
  calcNormalen();
}
};
void Quader⁝drawArea( int i ) {
  double x, y, z; int j, k, k1, k2;
  glBegin( GL_LINE_STRIP );
  glNormal3d( Ax[i], Ay[i], Az[i] );
  k1 = A[i]; 
  k2 = A[i+1];
  for ( k = k1; k <= k2; k ++ ) {
    if ( k < k2 ) j = K[k ]; 
    else          j = K[k1];
    x = pX[j]; 
    y = pY[j]; 
    z = pZ[j]; 
    glVertex3d( x, y, z );
  }
  glEnd();
}
void Quader⁝draw(void) {
  for ( int i = 0; i < anzA; i ++ ) drawArea( i );
}
bool Quader⁝calcNormalen() {
int i, j, k, k1, k2 ; 
double x1, y1, z1, x2, y2, z2, ax, ay, az, a; 
for ( i = 0; i < anzA; i ++ ) { ax = ay = az = a = 0.0; 
  k1 = A[i]; 
  k2 = A[i+1];
  j  = K[k1]; 
  x1 = pX[j]; y1 = pY[j]; z1 = pZ[j]; 
  for ( k = k1+1; k <= k2; k ++ ) {
    j = K[k]; if ( k == k2 ) j = K[k1];
    x2 = pX[j]; y2 = pY[j]; z2 = pZ[j]; 
    ax += ( ( y1 - y2 ) * ( z1 + z2 ) ) ;
    ay += ( ( z1 - z2 ) * ( x1 + x2 ) ) ;
    az += ( ( x1 - x2 ) * ( y1 + y2 ) ) ;
    x1 = x2; y1 = y2; z1 = z2; 
  }
  a = sqrt( ax * ax + ay * ay + az * az ) ;
  if ( a < 1.0E-9 ) { 
    Area[i] = Ax[i] = Ay[i] = Az[i] = 0.0 ; 
    return FALSE ;
  } else { a *= 0.5; 
    Area[i] = a; //Area=Wert der Flaeche
    Ax[i] = ax / a; //NormalenKomp Ax,Ay,Az
    Ay[i] = ay / a; 
    Az[i] = az / a;
  }
}
  return TRUE ;
}