simgear/scene/model/shadowvolume.cxx

   1 // Shadow volume class
   2 //
   3 // Written by Harald JOHNSEN, started June 2005.
   4 //
   5 // Copyright (C) 2005  Harald JOHNSEN - hjohnsen@evc.net
   6 //
   7 // This program is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU General Public License as
   9 // published by the Free Software Foundation; either version 2 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this program; if not, write to the Free Software
  19 // Foundation, 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA
  20 //
  21 //
  22
  23 #include <plib/sg.h>
  24 #include <plib/ssg.h>
  25 #include <simgear/props/props.hxx>
  26 #include <simgear/debug/logstream.hxx>
  27 #include <simgear/screen/extensions.hxx>
  28 #include <simgear/scene/model/animation.hxx>
  29 #include <simgear/scene/model/model.hxx>
  30 #include SG_GLU_H
  31
  32 #include "shadowvolume.hxx"
  33
  34 /*
  35  geometry and edge list
  36  - traverse object graph until leaf to get geometry
  37  - what about transform and selection ?
  38         - use sub objects rather then objects
  39         - get local transform and selection
  40                 - range anim : ssgRangeSelector ( min, max ) => ssgSelector ( true/false )
  41                         => selection [0..n], kids [0..n]
  42                 - select/timed anim : ssgSelector ( true/false )
  43                         => isSelected( nkid )
  44                 - spin/rotate/trans/scale/... : ssgTransform ( matrix )
  45                         => getNetTransform
  46  - on new object :
  47         - for one object branch
  48                 - for each leaf
  49                         - save geometry
  50                         - save address in cache
  51  - when rendering object
  52         - for each leaf
  53                 - getNetTransform + object global rotation (ac) => transform for light position
  54                 - go up in tree and check isSelected( self )
  55  - generate connectivity each time the geometry change
  56         => using local light so connectivity never changes
  57  - generate active edge list when :
  58         - light moves
  59         - subpart moves (animation code)
  60         - ac rotate
  61                 => cache rotation matrix and generate edge list only if something change
  62                 => even if it changes, no need to do that every frame
  63
  64  - static objects have static edge list if light does not move
  65
  66  shadowing a scene
  67  - render full scene as normal
  68  - render occluder in stencil buffer with their shadow volumes
  69  - apply stencil to framebuffer (darkens shadowed parts)
  70
  71         shadows using the alpha buffer
  72         http://wwwvis.informatik.uni-stuttgart.de/~roettger/html/Pages/shadows.html
  73 */
  74
  75 // TODO
  76 //      - shadow for objects
  77 //              * aircraft
  78 //              * tile objects (from .stg)
  79 //              - ai objects
  80 //              - random objects => tie shadow geometry to lib objects and reuse them
  81 //      - zfail if camera inside shadow
  82 //      - queue geometry work if lot of objects
  83 //      * add a render property on/off (for aircraft, for scene objects, for ai)
  84 //      * add a render property in rendering dialog
  85 //      * filter : halo, light, shadow, disc, disk, flame, (exhaust), noshadow
  86
  87 static int statSilhouette=0;
  88 static int statGeom=0;
  89 static int statObj=0;
  90
  91 static SGShadowVolume *states;
  92 static glBlendEquationProc glBlendEquationPtr = NULL;
  93 #define GL_MIN_EXT                          0x8007
  94 #define GL_MAX_EXT                          0x8008
  95
  96
  97 SGShadowVolume::ShadowCaster::ShadowCaster( int _num_tri, ssgBranch * _geometry_leaf ) :
  98         geometry_leaf ( _geometry_leaf ),
  99         scenery_object ( 0 ),
 100         first_select ( 0 ),
 101         frameNumber ( 0 ),
 102         numTriangles ( 0 ),
 103         indices ( 0 ),
 104         vertices ( 0 ),
 105         lastSilhouetteIndicesCount ( 0 )
 106 {
 107         int num_tri = _num_tri;
 108         numTriangles = num_tri;
 109         triangles = new triData[ num_tri ];
 110         indices = new int[1 + num_tri * 3];
 111         vertices = new sgVec4[1 + num_tri * 3];
 112         silhouetteEdgeIndices = new GLushort[(1+num_tri) * 3*3];
 113         indices [ num_tri * 3 ] = num_tri * 3;
 114         sgSetVec3(last_lightpos, 0.0, 0.0, 0.0);
 115         statGeom ++;
 116
 117         ssgBranch *branch = (ssgBranch *) _geometry_leaf;
 118         while( branch && branch->getNumParents() > 0 ) {
 119                 if( !first_select && branch->isA(ssgTypeSelector())) {
 120                         first_select = branch;
 121                         break;
 122                 }
 123                 branch = branch->getParent(0);
 124         }
 125 }
 126
 127 void SGShadowVolume::ShadowCaster::addLeaf( int & tri_idx, int & ind_idx, ssgLeaf *geometry_leaf ) {
 128         int num_tri = geometry_leaf->getNumTriangles();
 129         for(int i = 0; i < num_tri ; i ++ ) {
 130                 short v1, v2, v3;
 131                 sgVec3 a, b, c;
 132                 geometry_leaf->getTriangle( i, &v1, &v2, &v3 );
 133                 sgCopyVec3(a, geometry_leaf->getVertex(v1));
 134                 sgCopyVec3(b, geometry_leaf->getVertex(v2));
 135                 sgCopyVec3(c, geometry_leaf->getVertex(v3));
 136
 137                 int p = tri_idx;
 138                 sgMakePlane ( triangles[p].planeEquations, a, b, c );
 139                 sgCopyVec3(vertices[ind_idx + v1], a);
 140                 sgCopyVec3(vertices[ind_idx + v2], b);
 141                 sgCopyVec3(vertices[ind_idx + v3], c);
 142                 vertices[ind_idx + v1][SG_W] = 1.0f;
 143                 vertices[ind_idx + v2][SG_W] = 1.0f;
 144                 vertices[ind_idx + v3][SG_W] = 1.0f;
 145                 indices[p*3] = ind_idx + v1;
 146                 indices[p*3+1] = ind_idx + v2;
 147                 indices[p*3+2] = ind_idx + v3;
 148
 149                 tri_idx++;
 150         }
 151         if( num_tri == 0 )
 152                 return;
 153         int num_ind = geometry_leaf->getNumVertices();
 154         ind_idx += num_ind;
 155 }
 156
 157 SGShadowVolume::ShadowCaster::~ShadowCaster() {
 158         delete [] indices ;
 159         delete [] vertices ;
 160         delete [] triangles;
 161         delete [] silhouetteEdgeIndices;
 162 }
 163
 164
 165
 166 bool SGShadowVolume::ShadowCaster::sameVertex(int edge1, int edge2) {
 167         if( edge1 == edge2)
 168                 return true;
 169         sgVec3 delta_v;
 170         sgSubVec3( delta_v, vertices[edge1], vertices[edge2]);
 171         if( delta_v[SG_X] != 0.0)       return false;
 172         if( delta_v[SG_Y] != 0.0)       return false;
 173         if( delta_v[SG_Z] != 0.0)       return false;
 174         return true;
 175 }
 176
 177
 178 //Calculate neighbour faces for each edge
 179 // caution, this is O(n2)
 180 void SGShadowVolume::ShadowCaster::SetConnectivity(void)
 181 {
 182         int edgeCount = 0;
 183
 184         //set the neighbour indices to be -1
 185         for(int ii=0; ii<numTriangles; ++ii)
 186                 triangles[ii].neighbourIndices[0] =
 187                 triangles[ii].neighbourIndices[1] =
 188                 triangles[ii].neighbourIndices[2] = -1;
 189
 190         //loop through triangles
 191         for(int i=0; i<numTriangles-1; ++i)
 192         {
 193                 //loop through edges on the first triangle
 194                 for(int edgeI=0; edgeI<3; ++edgeI)
 195                 {
 196                         //continue if this edge already has a neighbour set
 197                         if(triangles[i].neighbourIndices[ edgeI ]!=-1)
 198                                 continue;
 199
 200                         //get the vertex indices on each edge
 201                         int edgeI1=indices[i*3+edgeI];
 202                         int edgeI2=indices[i*3+(edgeI == 2 ? 0 : edgeI+1)];
 203
 204                         //loop through triangles with greater indices than this one
 205                         for(int j=i+1; j<numTriangles; ++j)
 206                         {
 207                                 //loop through edges on triangle j
 208                                 for(int edgeJ=0; edgeJ<3; ++edgeJ)
 209                                 {
 210                                         //continue if this edge already has a neighbour set
 211                                         if(triangles[j].neighbourIndices[ edgeJ ]!=-1) {
 212                                                 continue;
 213                                         }
 214                                         //get the vertex indices on each edge
 215                                         int edgeJ1=indices[j*3+edgeJ];
 216                                         int edgeJ2=indices[j*3+(edgeJ == 2 ? 0 : edgeJ+1)];
 217
 218                                         //if these are the same (possibly reversed order), these faces are neighbours
 219 #if 0
 220                                         //no, we only use reverse order because same order means that
 221                                         //the triangle is wrongly oriented and that will cause shadow artifact
 222                                         if(     sameVertex(edgeI1, edgeJ1) && sameVertex(edgeI2, edgeJ2) ) {
 223                                                         // can happens with 'bad' geometry
 224 //                                                      printf("flipped triangle detected...check your model\n");
 225                                                 continue;
 226                                         }
 227 #endif
 228                                         if(     sameVertex(edgeI1, edgeJ2) && sameVertex(edgeI2, edgeJ1) )
 229                                         {
 230                                                 int edgeI3=indices[i*3+(edgeI == 0 ? 2 : edgeI-1)];
 231                                                 int edgeJ3=indices[j*3+(edgeJ == 0 ? 2 : edgeJ-1)];
 232                                                 if(     sameVertex(edgeI3, edgeJ3) ) {
 233                                                         // can happens with 'bad' geometry
 234 //                                                      printf("duplicated tri...check your model\n");
 235                                                         // exit loop
 236                                                         break;
 237                                                 }
 238                                                 triangles[i].neighbourIndices[edgeI]=j;
 239                                                 triangles[j].neighbourIndices[edgeJ]=i;
 240                                                 edgeCount ++;
 241                                                 // exit loop
 242                                                 j = numTriangles;
 243                                                 break;
 244                                         }
 245                                 }
 246                         }
 247                 }
 248         }
 249 //      printf("submodel has %d triangles and %d shared edges\n", numTriangles, edgeCount);
 250 }
 251
 252 //calculate silhouette edges
 253 void SGShadowVolume::ShadowCaster::CalculateSilhouetteEdges(sgVec3 lightPosition)
 254 {
 255         //Calculate which faces face the light
 256         for(int i=0; i<numTriangles; ++i)
 257         {
 258                 if( sgDistToPlaneVec3 ( triangles[i].planeEquations, lightPosition ) > 0.0 )
 259                         triangles[i].isFacingLight=true;
 260                 else
 261                         triangles[i].isFacingLight=false;
 262         }
 263
 264         //loop through faces
 265         int iEdgeIndices = 0;
 266         sgVec4 farCap = {-lightPosition[SG_X], -lightPosition[SG_Y], -lightPosition[SG_Z], 1.0f};
 267         sgCopyVec4( vertices[ numTriangles*3 ], farCap );
 268
 269         for(int t=0; t < numTriangles; t++) {
 270                 int v = t * 3;
 271                 //if this face is not facing the light, not a silhouette edge
 272                 if(!triangles[t].isFacingLight)
 273                 {
 274                         triangles[t].isSilhouetteEdge[0]=false;
 275                         triangles[t].isSilhouetteEdge[1]=false;
 276                         triangles[t].isSilhouetteEdge[2]=false;
 277                         continue;
 278                 }
 279                 //loop through edges
 280                 for(int j = 0 ; j < 3 ; j++) {
 281                         //this face is facing the light
 282                         //if the neighbouring face is not facing the light, or there is no neighbouring face,
 283                         //then this is a silhouette edge
 284                         if(triangles[t].neighbourIndices[j]==-1 ||
 285                                 !triangles[triangles[t].neighbourIndices[j]].isFacingLight ) {
 286                                 triangles[t].isSilhouetteEdge[j]=true;
 287                                 silhouetteEdgeIndices[ iEdgeIndices++ ] = indices[v+(j == 2 ? 0 : j+1)];
 288                                 silhouetteEdgeIndices[ iEdgeIndices++ ] = indices[v+j];
 289                                 silhouetteEdgeIndices[ iEdgeIndices++ ] = numTriangles * 3;
 290                         }
 291                         else
 292                                 triangles[t].isSilhouetteEdge[j]=false;
 293                 }
 294         }
 295         lastSilhouetteIndicesCount = iEdgeIndices;
 296 }
 297
 298 void SGShadowVolume::ShadowCaster::DrawInfiniteShadowVolume(sgVec3 lightPosition, bool drawCaps)
 299 {
 300         glEnableClientState ( GL_VERTEX_ARRAY ) ;
 301         glVertexPointer ( 4, GL_FLOAT, 0, vertices ) ;
 302         glDrawElements ( GL_TRIANGLES, lastSilhouetteIndicesCount, GL_UNSIGNED_SHORT, silhouetteEdgeIndices ) ;
 303
 304         //Draw caps if required
 305         if(drawCaps)
 306         {
 307                 glBegin(GL_TRIANGLES);
 308                 {
 309                         for(int i=0; i<numTriangles; ++i)
 310                         {
 311                                 if(triangles[i].isFacingLight) {
 312                                         int v = i*3;
 313                                         glVertex3fv( vertices[indices[v+0]] );
 314                                         glVertex3fv( vertices[indices[v+1]] );
 315                                         glVertex3fv( vertices[indices[v+2]] );
 316                                 }
 317                         }
 318                 }
 319                 glEnd();
 320         }
 321 }
 322
 323
 324 void SGShadowVolume::ShadowCaster::getNetTransform ( ssgBranch * branch, sgMat4 xform )
 325 {
 326         // one less matmult...
 327         bool first = true;
 328         while( branch && branch != lib_object ) {
 329                 if( branch->isA(ssgTypeTransform()) ) {
 330                         sgMat4 transform;
 331                         if( first ) {
 332                                 ((ssgTransform *) branch)->getTransform( xform );
 333                                 first = false;
 334                         } else {
 335                                 ((ssgTransform *) branch)->getTransform(transform);
 336                                 sgPostMultMat4 ( xform, transform ) ;
 337                         }
 338                 }
 339                 branch = branch->getParent( 0 );
 340         }
 341         if( first )
 342                 sgMakeIdentMat4 ( xform ) ;
 343 }
 344
 345 // check the value of <select> and <range> animation
 346 // wich have been computed during the rendering
 347 bool SGShadowVolume::ShadowCaster::isSelected (  ssgBranch * branch ) {
 348         while( branch && branch != lib_object) {
 349                 if( branch->isA(ssgTypeSelector()) )
 350                         if( !((ssgSelector *) branch)->isSelected(0) )
 351                                 return false;
 352                 branch = branch->getParent(0);
 353         }
 354         return true;
 355 }
 356 /*
 357         trans ----- personality ---- shared object
 358         perso1 *-----
 359                      \
 360                       *--------* shared object
 361                      /
 362         perso2 *-----
 363 */
 364 void SGShadowVolume::ShadowCaster::computeShadows(sgMat4 rotation, sgMat4 rotation_translation,
 365         OccluderType occluder_type) {
 366
 367         // check the select and range ssgSelector node
 368         // object can't cast shadow if it is not visible
 369
 370         if( first_select && ! isSelected( first_select) )
 371                 return;
 372
 373                 // get the transformations : this comes from animation code for example
 374                 // or static transf
 375         sgMat4 transf;
 376         sgVec3 lightPos;
 377         int deltaFrame = occluder_type == SGShadowVolume::occluderTypeAircraft ? 0 : 9;
 378         if( states->frameNumber - frameNumber > deltaFrame) {
 379                 sgMat4 transform ;
 380                 sgMat4 invTransform;
 381                 getNetTransform( (ssgBranch *) geometry_leaf, transform );
 382                 sgCopyMat4( last_transform, transform );
 383                 sgPostMultMat4( transform, rotation );
 384                 sgTransposeNegateMat4 ( invTransform, transform );
 385
 386                 sgCopyVec3( lightPos, states->sunPos );
 387                 sgXformPnt3( lightPos, invTransform );
 388
 389                 sgVec3 lightPosNorm;
 390                 sgNormaliseVec3( lightPosNorm, lightPos );
 391                 float deltaPos = sgAbs(lightPosNorm[0] - last_lightpos[0]) +
 392                                 sgAbs(lightPosNorm[1] - last_lightpos[1]) +
 393                                 sgAbs(lightPosNorm[2] - last_lightpos[2]);
 394                 // if the geometry has rotated/moved enought then
 395                 // we need to recompute the silhouette
 396                 // but this computation does not need to be done each frame
 397                 if( deltaPos > 0.0 ) {
 398                         CalculateSilhouetteEdges( lightPos );
 399                         sgCopyVec3( last_lightpos, lightPosNorm );
 400                         frameNumber = states->frameNumber ;
 401                         statSilhouette ++;
 402                 }
 403         }
 404         sgCopyMat4( transf, last_transform );
 405         sgPostMultMat4( transf, rotation_translation );
 406         glLoadMatrixf ( (float *) states->CameraViewM ) ;
 407         glMultMatrixf( (float *) transf );
 408
 409         if( states->shadowsDebug_enabled )
 410         {
 411                 glStencilFunc(GL_ALWAYS, 0, ~0);
 412                 glDisable( GL_CULL_FACE  );
 413                 glDisable( GL_DEPTH_TEST );
 414                 glDisable(GL_STENCIL_TEST);
 415                 glColorMask(1, 1, 1, 1);
 416                 glColor4f(0.0, 0.0, 1.0, 1.0);
 417                 glBegin(GL_LINES);
 418                 for(int i=0; i<numTriangles; ++i)
 419                 {
 420                         if(!triangles[i].isFacingLight)
 421                                 continue;
 422                         int v = i*3;
 423                         //Loop through edges on this face
 424                         sgVec3 vertex1, vertex2, vertex3;
 425                         sgCopyVec3(vertex1, vertices[indices[v+0]]);
 426                         sgCopyVec3(vertex2, vertices[indices[v+1]]);
 427                         sgCopyVec3(vertex3, vertices[indices[v+2]]);
 428
 429                         if(triangles[i].isSilhouetteEdge[0]) {
 430                                 glVertex3fv(vertex2);
 431                                 glVertex3fv(vertex1);
 432                         }
 433                         if(triangles[i].isSilhouetteEdge[1]) {
 434                                 glVertex3fv(vertex2);
 435                                 glVertex3fv(vertex3);
 436                         }
 437                         if(triangles[i].isSilhouetteEdge[2]) {
 438                                 glVertex3fv(vertex3);
 439                                 glVertex3fv(vertex1);
 440                         }
 441                 }
 442                 glEnd();
 443                 glColorMask(0, 0, 0, 0);
 444                 glEnable( GL_CULL_FACE  );
 445                 glEnable( GL_DEPTH_TEST );
 446                 glEnable(GL_STENCIL_TEST);
 447         }
 448
 449
 450                 // TODO:compute intersection with near clip plane...
 451                 bool needZFail=false;
 452
 453                 // GL_INCR_WRAP_EXT, GL_DECR_WRAP_EXT
 454
 455                 if(needZFail)
 456                 {
 457                         //Increment stencil buffer for back face depth fail
 458                         glStencilFunc(GL_ALWAYS, 0, ~0);
 459                         glStencilOp(GL_KEEP, GL_INCR, GL_KEEP);
 460                         glCullFace(GL_FRONT);
 461
 462                         DrawInfiniteShadowVolume( lightPos, true);
 463
 464                         //Decrement stencil buffer for front face depth fail
 465                         glStencilOp(GL_KEEP, GL_DECR, GL_KEEP);
 466                         glCullFace(GL_BACK);
 467
 468                         DrawInfiniteShadowVolume( lightPos, true);
 469                 }
 470                 else    //using zpass
 471                 {
 472                         //Increment stencil buffer for front face depth pass
 473                         if( states->use_alpha ) {
 474                                 glBlendEquationPtr( GL_FUNC_ADD );
 475                                 glBlendFunc( GL_ONE, GL_ONE );
 476                                 glColor4ub(1, 1, 1, 16);
 477                         } else {
 478                                 glColor4f(1.0f, 1.0f, 0.0f, 0.5f);
 479                                 glStencilFunc(GL_ALWAYS, 0, ~0);
 480                                 glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
 481                         }
 482                         glCullFace(GL_BACK);
 483
 484                         DrawInfiniteShadowVolume( lightPos, false);
 485
 486                         //Decrement stencil buffer for back face depth pass
 487                         if( states->use_alpha ) {
 488                                 glBlendEquationPtr( GL_FUNC_REVERSE_SUBTRACT );
 489                                 glBlendFunc( GL_ONE, GL_ONE );
 490                                 glColor4ub(1, 1, 1, 16);
 491                         } else {
 492                                 glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
 493                         }
 494                         glCullFace(GL_FRONT);
 495
 496                         DrawInfiniteShadowVolume( lightPos, false);
 497                 }
 498 }
 499
 500
 501 void SGShadowVolume::SceneryObject::computeShadows(void) {
 502
 503         bool intersect = true;
 504         // compute intersection with view frustum
 505         // use pending_object (pointer on obj transform) & tile transform
 506         // to get position
 507         sgMat4 position, CamXpos;
 508         sgFrustum *f = ssgGetFrustum();
 509         pending_object->getParent(0)->getNetTransform( position );
 510         sgCopyMat4 ( CamXpos, states->CameraViewM ) ;
 511         sgPreMultMat4 ( CamXpos, position ) ;
 512
 513         sgSphere tmp = *(pending_object->getBSphere()) ;
 514         if ( tmp.isEmpty () )
 515                 intersect = false;
 516         else {
 517                 // 7000
 518                 float max_dist = 5000.0f;
 519                 tmp . orthoXform ( CamXpos ) ;
 520                 // cull if too far
 521                 if ( -tmp.center[2] - tmp.radius > max_dist )
 522                         intersect = false;
 523                 else if( tmp.center[2] == 0.0 )
 524                         intersect = true;
 525                 // cull if too small on screen
 526                 else if ( tmp.radius / sgAbs(tmp.center[2]) < 1.0 / 40.0 )
 527                         intersect = false;
 528                 else
 529                         intersect = SSG_OUTSIDE != (ssgCullResult) f -> contains ( &tmp );
 530         }
 531
 532         if( intersect ) {
 533                 if( !scenery_object ) {
 534                         if( states->frameNumber - states->lastTraverseTreeFrame > 5 ) {
 535                                 find_trans();
 536                                 if( scenery_object )
 537                                         traverseTree( pending_object );
 538                                         states->lastTraverseTreeFrame = states->frameNumber;
 539                         }
 540                         return;
 541                 }
 542                 sgMat4 rotation, rotation_translation;
 543                 scenery_object->getNetTransform ( rotation_translation );
 544                 // split placement offset into rotation and offset
 545                 // rotation from model inside world
 546                 // we are not interested in translation since the light is very far away
 547                 // without translation we reduce the frequency of updates of the silouhette
 548                 sgCopyMat4( rotation, rotation_translation );
 549                 sgSetVec4( rotation[3], 0, 0, 0, 1);
 550
 551                 ShadowCaster_list::iterator iShadowCaster;
 552                 for(iShadowCaster = parts.begin() ; iShadowCaster != parts.end() ; iShadowCaster ++ ) {
 553                         (*iShadowCaster)->computeShadows(rotation, rotation_translation, occluder_type);
 554                 }
 555         }
 556 }
 557
 558 /*
 559         1) starting at the root of a scene object we follow all branch to find vertex leaf.
 560         each vertex leaf will create a shadow sub object so that the shadow casted by this
 561         geometry can be correctly rendered according to select or transform nodes.
 562         2) models are not optimized for shadows because the geometry is cut by
 563                 - select / transform nodes
 564                 - material differences
 565         since we are not interested in the geometry material we try to merge same level
 566         leafs. this can divide the number of shadow sub models by a lot (reducing the cpu
 567         overhead for matrix computation) and at the end this will reduce the number of
 568         silouhette edge by a lot too.
 569 */
 570 static bool filterName(const char *leaf_name) {
 571         if( ! leaf_name )
 572                 return true;
 573         char lname[20];
 574         int l = 0;
 575         char *buff;
 576         for( buff = lname; *leaf_name && l < (sizeof( lname )-1); ++buff, l++ )
 577              *buff = tolower(*leaf_name++);
 578         *buff = 0;
 579         if( !strncmp(lname, "noshadow", 8) )
 580                 return false;
 581         return true;
 582 }
 583 void SGShadowVolume::SceneryObject::traverseTree(ssgBranch *branch) {
 584         int num_tri = 0;
 585         int num_leaf = 0;
 586
 587         if( sgCheckAnimationBranch( (ssgEntity *) branch ) ) {
 588                 if( ((SGAnimation *) branch->getUserData())->get_animation_type() == 1)
 589                         return;
 590         }
 591
 592         for(int i = 0 ; i < branch->getNumKids() ; i++) {
 593                 ssgEntity *this_kid = branch->getKid( i );
 594                 if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
 595                         if( filterName( this_kid->getName()) ) {
 596                                 num_tri += ((ssgLeaf *) this_kid)->getNumTriangles();
 597                                 num_leaf ++;
 598                         }
 599                 } else
 600                         traverseTree( (ssgBranch *) this_kid );
 601         }
 602         if( num_tri > 0) {
 603                 int tri_idx = 0;
 604                 int ind_idx = 0;
 605                 ShadowCaster *new_part = new ShadowCaster( num_tri, branch);
 606                 new_part->scenery_object = scenery_object;
 607                 new_part->lib_object = lib_object;
 608                 for(int i = 0 ; i < branch->getNumKids() ; i++) {
 609                         ssgEntity *this_kid = branch->getKid( i );
 610                         if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
 611                                 if( filterName( this_kid->getName()) )
 612                                         new_part->addLeaf( tri_idx, ind_idx, (ssgLeaf *) this_kid );
 613                         }
 614                 }
 615                 new_part->SetConnectivity();
 616                 parts.push_back( new_part );
 617         }
 618 }
 619
 620 void SGShadowVolume::SceneryObject::find_trans(void) {
 621         ssgBranch *branch = pending_object;
 622         ssgBranch *prev_branch = pending_object;
 623         // check the existence of the root node
 624         while( branch && branch->getNumParents() > 0 ) {
 625                 prev_branch = branch;
 626                 branch = branch->getParent(0);
 627         }
 628         // check if we are connected to the scene graph
 629         if( !branch->isA(ssgTypeRoot() ) )
 630                 return;
 631         scenery_object = pending_object;
 632 }
 633
 634 SGShadowVolume::SceneryObject::SceneryObject(ssgBranch *_scenery_object, OccluderType _occluder_type) :
 635         pending_object ( _scenery_object ),
 636         occluder_type ( _occluder_type ),
 637         scenery_object ( 0 )
 638 {
 639         // queue objects, don't do all the work in the first frames because of
 640         // massive cpu power needed
 641         statObj++;
 642         if( occluder_type == SGShadowVolume::occluderTypeAircraft )
 643                 lib_object = _scenery_object;
 644         else
 645                 lib_object = (ssgBranch *) ((ssgBranch *)_scenery_object->getKid(0))->getKid(0);
 646 }
 647
 648 SGShadowVolume::SceneryObject::~SceneryObject()
 649 {
 650         ShadowCaster_list::iterator iParts;
 651         for(iParts = parts.begin() ; iParts != parts.end(); iParts++ ) {
 652                 delete *iParts;
 653         }
 654         parts.clear();
 655 }
 656
 657 void SGShadowVolume::computeShadows(void) {
 658
 659         // intensity = ambient + lights
 660         // lights = sun_const * (sun_angle . normal)
 661         double dot_light = cos(sun_angle);
 662         // do nothing if sun is under horizon
 663         if( dot_light < 0.2 )
 664                 return;
 665
 666         //Draw shadow volumes
 667         glPushAttrib(GL_ALL_ATTRIB_BITS);
 668         glPushClientAttrib ( GL_CLIENT_VERTEX_ARRAY_BIT ) ;
 669         glDisableClientState ( GL_COLOR_ARRAY         ) ;
 670         glDisableClientState ( GL_NORMAL_ARRAY        ) ;
 671         glDisableClientState ( GL_TEXTURE_COORD_ARRAY ) ;
 672
 673         if( use_alpha ) {
 674                 glColorMask(0, 0, 0, 1);
 675                 glClearColor(0.0, 0.0, 0.0, 0.0 );
 676                 glClear(GL_COLOR_BUFFER_BIT);
 677                 glDisable(GL_ALPHA);
 678                 glEnable(GL_BLEND);
 679         } else {
 680                 glClearStencil( 0 );
 681                 glClear(GL_STENCIL_BUFFER_BIT);
 682                 glColorMask(0, 0, 0, 0);
 683                 glEnable(GL_STENCIL_TEST);
 684                 glDisable(GL_ALPHA);
 685                 glDisable(GL_BLEND);
 686         }
 687         glDisable( GL_LIGHTING );
 688         glDisable( GL_FOG );
 689         glEnable( GL_CULL_FACE  );
 690 //      glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
 691 //    glPolygonOffset(0.0,5.0);
 692     glPolygonOffset(0.0,30.0);
 693     glEnable(GL_POLYGON_OFFSET_FILL);
 694
 695         glShadeModel(GL_FLAT);
 696
 697         glDepthMask( false );
 698         glEnable( GL_DEPTH_TEST );
 699         glDepthFunc(GL_LESS);
 700
 701         SceneryObject_map::iterator iSceneryObject;
 702         // compute shadows for each objects
 703         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 704                 SceneryObject *an_occluder = iSceneryObject->second;
 705                 if( shadowsTO_enabled && (an_occluder->occluder_type == occluderTypeTileObject) ||
 706                         shadowsAI_enabled && (an_occluder->occluder_type == occluderTypeAI ) ||
 707                         shadowsAC_enabled && (an_occluder->occluder_type == occluderTypeAircraft ) )
 708                                 an_occluder->computeShadows();
 709         }
 710
 711
 712         glMatrixMode   ( GL_PROJECTION ) ;
 713         glPushMatrix   () ;
 714         glLoadIdentity () ;
 715         glOrtho        ( -100, 100, -100, 100, -1, 1 ) ;
 716         glMatrixMode   ( GL_MODELVIEW ) ;
 717         glPushMatrix   () ;
 718         glLoadIdentity () ;
 719
 720         glDisable(GL_DEPTH_TEST);
 721         glDisable(GL_CULL_FACE);
 722 //      glBindTexture(GL_TEXTURE_2D, 0);
 723         glPolygonMode(GL_FRONT, GL_FILL);
 724         if( use_alpha ) {
 725                 // there is a flaw in the Roettger paper, this does not work for some geometry
 726                 // where we increment (multiply) the buffer a few times then we
 727                 // decrement (divide) a few times. Decrementing more then once will give a
 728                 // non shadowed parts with mask value < 0.25 because the incrementation was
 729                 // clamped
 730                 // Solution : don't use a start value as high as 0.25 but the smallest value
 731                 // posible ie 1/256. This is not a general solution, a stencil buffer will
 732                 // support 255 incrementation before clamping, the alpha mask only 7.
 733                 // => that still does not work with our geometry so use subtractive blend
 734
 735                 // clamp mask = {0,16,32,64,...} => {0,16,16,16,...}
 736                 glBlendEquationPtr( GL_MIN_EXT );
 737                 glBlendFunc( GL_DST_COLOR, GL_ONE );
 738                 glColor4ub(1, 1, 1, 16);
 739                 glRectf(-100,-100,100,100);
 740                 // scale mask = {0,16} => {0,64}
 741                 glBlendEquationPtr( GL_FUNC_ADD );
 742                 glBlendFunc( GL_DST_COLOR, GL_ONE );
 743                 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 744                 glRectf(-100,-100,100,100);
 745                 glRectf(-100,-100,100,100);
 746                 // negate mask => {0,64} => {255, 191}
 747                 glBlendFunc( GL_ONE_MINUS_DST_COLOR, GL_ZERO );
 748                 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 749                 glRectf(-100,-100,100,100);
 750                 // apply mask
 751                 glColorMask(1, 1, 1, 1);
 752                 glBlendFunc( GL_ZERO, GL_DST_ALPHA );
 753                 glColor4f(1.0f, 0.5f, 0.2f, 1.0f);
 754                 glRectf(-100,-100,100,100);
 755         } else {
 756                 // now the stencil contains 0 for scenery in light and != 0 for parts in shadow
 757                 // draw a quad covering the screen, the stencil will be the mask
 758                 // we darken the shadowed parts
 759                 glColorMask(1, 1, 1, 1);
 760                 glStencilFunc(GL_NOTEQUAL, 0, ~0);
 761                 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 762                 glEnable(GL_STENCIL_TEST);
 763                 glEnable(GL_ALPHA);
 764                 glAlphaFunc(GL_GREATER, 0.0f);
 765                 glEnable(GL_BLEND);
 766                 glBlendFunc ( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA ) ;
 767                 glColor4f(0.0, 0.0, 0.0, sgLerp(0.1, 0.3, dot_light) );
 768                 // fixed value is better, the previous line is surely wrong
 769                 glColor4f(0.0, 0.0, 0.0, 0.3 );
 770                 glRectf(-100,-100,100,100);
 771         }
 772         glMatrixMode   ( GL_PROJECTION ) ;
 773         glPopMatrix    () ;
 774         glMatrixMode   ( GL_MODELVIEW ) ;
 775         glPopMatrix    () ;
 776
 777         glDisable(GL_STENCIL_TEST);
 778         glPopClientAttrib ( ) ;
 779         glPopAttrib();
 780 }
 781
 782 SGShadowVolume::SGShadowVolume() :
 783         init_done( false ),
 784         shadows_enabled( false ),
 785         frameNumber( 0 ),
 786         lastTraverseTreeFrame ( 0 )
 787 {
 788         states = this;
 789 }
 790
 791 SGShadowVolume::~SGShadowVolume() {
 792         SceneryObject_map::iterator iSceneryObject;
 793         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 794                 delete iSceneryObject->second;
 795         }
 796         sceneryObjects.clear();
 797 }
 798
 799 void SGShadowVolume::init(SGPropertyNode *sim_rendering_options) {
 800         init_done = true;
 801         shadows_enabled = true;
 802         sim_rendering = sim_rendering_options;
 803         int stencilBits = 0, alphaBits = 0;
 804         glGetIntegerv( GL_STENCIL_BITS, &stencilBits );
 805         glGetIntegerv( GL_ALPHA_BITS, &alphaBits );
 806         bool hasSubtractiveBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_subtract");
 807         bool hasMinMaxBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_minmax");
 808         if( hasSubtractiveBlend )
 809                 glBlendEquationPtr = (glBlendEquationProc ) SGLookupFunction("glBlendEquationEXT");
 810         canDoAlpha = (alphaBits >= 8) && hasSubtractiveBlend && hasMinMaxBlend;
 811         canDoStencil = (stencilBits >= 3);
 812         if( !canDoStencil )
 813                 if( canDoAlpha )
 814                         SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer, using alpha buffer");
 815                 else
 816                         SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer and no alpha buffer");
 817 }
 818
 819 void SGShadowVolume::startOfFrame(void) {
 820 }
 821 void SGShadowVolume::deleteOccluderFromTile(ssgBranch *tile) {
 822         SceneryObject_map::iterator iSceneryObject, iPrevious;
 823         iPrevious = sceneryObjects.begin();
 824         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 825                 if( iSceneryObject->second->tile == tile ) {
 826                         delete iSceneryObject->second;
 827                         sceneryObjects.erase( iSceneryObject );
 828                         iSceneryObject = iPrevious;
 829                 }
 830                 iPrevious = iSceneryObject;
 831         }
 832 }
 833
 834 void SGShadowVolume::deleteOccluder(ssgBranch *occluder) {
 835         ssgBranch *branch = occluder;
 836         // skip first node and go to first transform (placement)
 837         while( occluder && !occluder->isA(ssgTypeTransform()))
 838                 occluder = (ssgBranch *) occluder->getKid(0);
 839
 840         // check if we allready know this object
 841         SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
 842         if( iSceneryObject != sceneryObjects.end() ) {
 843                 delete iSceneryObject->second;
 844                 sceneryObjects.erase( occluder );
 845         }
 846 }
 847
 848 void SGShadowVolume::addOccluder(ssgBranch *occluder, OccluderType occluder_type, ssgBranch *tile) {
 849
 850         ssgBranch *branch = occluder;
 851
 852         // skip first node and go to first transform (placement)
 853         while( occluder && !occluder->isA(ssgTypeTransform()))
 854                 occluder = (ssgBranch *) occluder->getKid(0);
 855
 856         // check if we allready know this object
 857         SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
 858         if( iSceneryObject == sceneryObjects.end() ) {
 859 //              printf("adding model %x %x\n", occluder, tile);
 860                 SceneryObject *entry = new SceneryObject( occluder, occluder_type );
 861                 entry->tile = tile;
 862                 sceneryObjects[ occluder ] = entry;
 863         }
 864
 865 }
 866
 867 void SGShadowVolume::setupShadows( double lon, double lat,
 868                 double gst, double SunRightAscension, double SunDeclination, double sunAngle) {
 869
 870         shadowsAC_enabled = sim_rendering->getBoolValue("shadows-ac", false);
 871         shadowsAI_enabled = sim_rendering->getBoolValue("shadows-ai", false);
 872         shadowsTO_enabled = sim_rendering->getBoolValue("shadows-to", false);
 873         shadowsDebug_enabled = sim_rendering->getBoolValue("shadows-debug", false);
 874 //      shadows_enabled   = sim_rendering->getBoolValue("shadows", false);
 875         shadows_enabled = shadowsAC_enabled || shadowsAI_enabled || shadowsTO_enabled;
 876         shadows_enabled &= canDoAlpha || canDoStencil;
 877         use_alpha = ((!canDoStencil) || sim_rendering->getBoolValue("shadows-alpha", false)) &&
 878                 canDoAlpha;
 879
 880         if( ! shadows_enabled )
 881                 return;
 882
 883         sgMat4 view_angle;
 884         sun_angle = sunAngle;
 885         {
 886                 sgMat4 LON, LAT;
 887                 sgVec3 axis;
 888
 889                 sgSetVec3( axis, 0.0, 0.0, 1.0 );
 890                 sgMakeRotMat4( LON, lon, axis );
 891
 892                 sgSetVec3( axis, 0.0, 1.0, 0.0 );
 893                 sgMakeRotMat4( LAT, 90.0 - lat, axis );
 894
 895                 sgMat4 TRANSFORM;
 896
 897                 sgMakeIdentMat4 ( TRANSFORM );
 898                 sgPreMultMat4( TRANSFORM, LON );
 899                 sgPreMultMat4( TRANSFORM, LAT );
 900
 901                 sgCoord pos;
 902                 sgSetCoord( &pos, TRANSFORM );
 903
 904                 sgMakeCoordMat4( view_angle, &pos );
 905         }
 906         {
 907         sgMat4 GST, RA, DEC;
 908         sgVec3 axis;
 909
 910
 911         sgSetVec3( axis, 0.0, 0.0, -1.0 );
 912         sgMakeRotMat4( GST, (gst) * 15.0, axis );
 913
 914         sgSetVec3( axis, 0.0, 0.0, 1.0 );
 915         sgMakeRotMat4( RA, (SunRightAscension * SGD_RADIANS_TO_DEGREES) - 90.0, axis );
 916
 917         sgSetVec3( axis, 1.0, 0.0, 0.0 );
 918         sgMakeRotMat4( DEC, SunDeclination * SGD_RADIANS_TO_DEGREES, axis );
 919
 920         sgInvertMat4( invViewAngle, view_angle);
 921
 922         sgMat4 TRANSFORM;
 923         sgMakeIdentMat4( TRANSFORM );
 924         sgPreMultMat4( TRANSFORM, GST );
 925         sgPreMultMat4( TRANSFORM, RA );
 926         sgPreMultMat4( TRANSFORM, DEC );
 927         sgSetVec3( sunPos, 0.0, 9900000.0, 0.0);
 928         sgXformPnt3( sunPos, TRANSFORM );
 929         }
 930
 931         ssgGetModelviewMatrix( CameraViewM );
 932
 933 }
 934
 935 void SGShadowVolume::endOfFrame(void) {
 936         if( ! shadows_enabled )
 937                 return;
 938         glBindTexture(GL_TEXTURE_2D, 0);
 939         glBindTexture(GL_TEXTURE_1D, 0);
 940
 941         glMatrixMode(GL_MODELVIEW);
 942
 943         computeShadows();
 944
 945         frameNumber ++;
 946 }
 947