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
 366         // check the select and range ssgSelector node
 367         // object can't cast shadow if it is not visible
 368
 369         if( first_select && ! isSelected( first_select) )
 370                 return;
 371
 372                 sgMat4 transform ;
 373                 sgMat4 invTransform;
 374                 // get the transformations : this comes from animation code for example
 375                 // or static transf
 376                 getNetTransform( (ssgBranch *) geometry_leaf, transform );
 377                 sgMat4 transf;
 378                 sgCopyMat4( transf, transform );
 379                 sgPostMultMat4( transf, rotation_translation );
 380                 sgPostMultMat4( transform, rotation );
 381                 sgTransposeNegateMat4 ( invTransform, transform );
 382
 383                 glLoadMatrixf ( (float *) states->CameraViewM ) ;
 384                 glMultMatrixf( (float *) transf );
 385
 386                 sgVec3 lightPos;
 387                 sgCopyVec3( lightPos, states->sunPos );
 388                 sgXformPnt3( lightPos, invTransform );
 389
 390                 sgVec3 lightPosNorm;
 391                 sgNormaliseVec3( lightPosNorm, lightPos );
 392                 float deltaPos = sgAbs(lightPosNorm[0] - last_lightpos[0]) +
 393                                 sgAbs(lightPosNorm[1] - last_lightpos[1]) +
 394                                 sgAbs(lightPosNorm[2] - last_lightpos[2]);
 395                 // if the geometry has rotated/moved enought then
 396                 // we need to recompute the silhouette
 397                 // but this computation does not need to be done each frame
 398                 if( (deltaPos > 0.0) && ( states->frameNumber - frameNumber > 4)) {
 399                         CalculateSilhouetteEdges( lightPos );
 400                         sgCopyVec3( last_lightpos, lightPosNorm );
 401                         frameNumber = states->frameNumber ;
 402                         statSilhouette ++;
 403                 }
 404
 405         if( states->shadowsDebug_enabled )
 406         {
 407                 glStencilFunc(GL_ALWAYS, 0, ~0);
 408                 glDisable( GL_CULL_FACE  );
 409                 glDisable( GL_DEPTH_TEST );
 410                 glDisable(GL_STENCIL_TEST);
 411                 glColorMask(1, 1, 1, 1);
 412                 glColor4f(0.0, 0.0, 1.0, 1.0);
 413                 glBegin(GL_LINES);
 414                 for(int i=0; i<numTriangles; ++i)
 415                 {
 416                         if(!triangles[i].isFacingLight)
 417                                 continue;
 418                         int v = i*3;
 419                         //Loop through edges on this face
 420                         sgVec3 vertex1, vertex2, vertex3;
 421                         sgCopyVec3(vertex1, vertices[indices[v+0]]);
 422                         sgCopyVec3(vertex2, vertices[indices[v+1]]);
 423                         sgCopyVec3(vertex3, vertices[indices[v+2]]);
 424
 425                         if(triangles[i].isSilhouetteEdge[0]) {
 426                                 glVertex3fv(vertex2);
 427                                 glVertex3fv(vertex1);
 428                         }
 429                         if(triangles[i].isSilhouetteEdge[1]) {
 430                                 glVertex3fv(vertex2);
 431                                 glVertex3fv(vertex3);
 432                         }
 433                         if(triangles[i].isSilhouetteEdge[2]) {
 434                                 glVertex3fv(vertex3);
 435                                 glVertex3fv(vertex1);
 436                         }
 437                 }
 438                 glEnd();
 439                 glColorMask(0, 0, 0, 0);
 440                 glEnable( GL_CULL_FACE  );
 441                 glEnable( GL_DEPTH_TEST );
 442                 glEnable(GL_STENCIL_TEST);
 443         }
 444
 445
 446                 // TODO:compute intersection with near clip plane...
 447                 bool needZFail=false;
 448
 449                 // GL_INCR_WRAP_EXT, GL_DECR_WRAP_EXT
 450
 451                 if(needZFail)
 452                 {
 453                         //Increment stencil buffer for back face depth fail
 454                         glStencilFunc(GL_ALWAYS, 0, ~0);
 455                         glStencilOp(GL_KEEP, GL_INCR, GL_KEEP);
 456                         glCullFace(GL_FRONT);
 457
 458                         DrawInfiniteShadowVolume( lightPos, true);
 459
 460                         //Decrement stencil buffer for front face depth fail
 461                         glStencilOp(GL_KEEP, GL_DECR, GL_KEEP);
 462                         glCullFace(GL_BACK);
 463
 464                         DrawInfiniteShadowVolume( lightPos, true);
 465                 }
 466                 else    //using zpass
 467                 {
 468                         //Increment stencil buffer for front face depth pass
 469                         if( states->use_alpha ) {
 470                                 glBlendEquationPtr( GL_FUNC_ADD );
 471                                 glBlendFunc( GL_ONE, GL_ONE );
 472                                 glColor4ub(1, 1, 1, 16);
 473                         } else {
 474                                 glColor4f(1.0f, 1.0f, 0.0f, 0.5f);
 475                                 glStencilFunc(GL_ALWAYS, 0, ~0);
 476                                 glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
 477                         }
 478                         glCullFace(GL_BACK);
 479
 480                         DrawInfiniteShadowVolume( lightPos, false);
 481
 482                         //Decrement stencil buffer for back face depth pass
 483                         if( states->use_alpha ) {
 484                                 glBlendEquationPtr( GL_FUNC_REVERSE_SUBTRACT );
 485                                 glBlendFunc( GL_ONE, GL_ONE );
 486                                 glColor4ub(1, 1, 1, 16);
 487                         } else {
 488                                 glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
 489                         }
 490                         glCullFace(GL_FRONT);
 491
 492                         DrawInfiniteShadowVolume( lightPos, false);
 493                 }
 494 }
 495
 496
 497 void SGShadowVolume::SceneryObject::computeShadows(void) {
 498
 499         bool intersect = true;
 500         // compute intersection with view frustum
 501         // use pending_object (pointer on obj transform) & tile transform
 502         // to get position
 503         sgMat4 position, CamXpos;
 504         sgFrustum *f = ssgGetFrustum();
 505         pending_object->getParent(0)->getNetTransform( position );
 506         sgCopyMat4 ( CamXpos, states->CameraViewM ) ;
 507         sgPreMultMat4 ( CamXpos, position ) ;
 508
 509         sgSphere tmp = *(pending_object->getBSphere()) ;
 510         if ( tmp.isEmpty () )
 511                 intersect = false;
 512         else {
 513                 // 7000
 514                 float max_dist = 5000.0f;
 515                 tmp . orthoXform ( CamXpos ) ;
 516                 // cull if too far
 517                 if ( -tmp.center[2] - tmp.radius > max_dist )
 518                         intersect = false;
 519                 else if( tmp.center[2] == 0.0 )
 520                         intersect = true;
 521                 // cull if too small on screen
 522                 else if ( tmp.radius / sgAbs(tmp.center[2]) < 1.0 / 40.0 )
 523                         intersect = false;
 524                 else
 525                         intersect = SSG_OUTSIDE != (ssgCullResult) f -> contains ( &tmp );
 526         }
 527
 528         if( intersect ) {
 529                 if( !scenery_object ) {
 530                         if( states->frameNumber - states->lastTraverseTreeFrame > 5 ) {
 531                                 find_trans();
 532                                 if( scenery_object )
 533                                         traverseTree( pending_object );
 534                                         states->lastTraverseTreeFrame = states->frameNumber;
 535                         }
 536                         return;
 537                 }
 538                 sgMat4 rotation, rotation_translation;
 539                 scenery_object->getNetTransform ( rotation_translation );
 540                 // split placement offset into rotation and offset
 541                 // rotation from model inside world
 542                 // we are not interested in translation since the light is very far away
 543                 // without translation we reduce the frequency of updates of the silouhette
 544                 sgCopyMat4( rotation, rotation_translation );
 545                 sgSetVec4( rotation[3], 0, 0, 0, 1);
 546
 547                 ShadowCaster_list::iterator iShadowCaster;
 548                 for(iShadowCaster = parts.begin() ; iShadowCaster != parts.end() ; iShadowCaster ++ ) {
 549                         (*iShadowCaster)->computeShadows(rotation, rotation_translation);
 550                 }
 551         }
 552 }
 553
 554 /*
 555         1) starting at the root of a scene object we follow all branch to find vertex leaf.
 556         each vertex leaf will create a shadow sub object so that the shadow casted by this
 557         geometry can be correctly rendered according to select or transform nodes.
 558         2) models are not optimized for shadows because the geometry is cut by
 559                 - select / transform nodes
 560                 - material differences
 561         since we are not interested in the geometry material we try to merge same level
 562         leafs. this can divide the number of shadow sub models by a lot (reducing the cpu
 563         overhead for matrix computation) and at the end this will reduce the number of
 564         silouhette edge by a lot too.
 565 */
 566 static bool filterName(const char *leaf_name) {
 567         if( ! leaf_name )
 568                 return true;
 569         char lname[20];
 570         int l = 0;
 571         char *buff;
 572         for( buff = lname; *leaf_name && l < (sizeof( lname )-1); ++buff, l++ )
 573              *buff = tolower(*leaf_name++);
 574         *buff = 0;
 575         if( !strncmp(lname, "noshadow", 8) )
 576                 return false;
 577         return true;
 578 }
 579 void SGShadowVolume::SceneryObject::traverseTree(ssgBranch *branch) {
 580         int num_tri = 0;
 581         int num_leaf = 0;
 582
 583         if( sgCheckAnimationBranch( (ssgEntity *) branch ) ) {
 584                 if( ((SGAnimation *) branch->getUserData())->get_animation_type() == 1)
 585                         return;
 586         }
 587
 588         for(int i = 0 ; i < branch->getNumKids() ; i++) {
 589                 ssgEntity *this_kid = branch->getKid( i );
 590                 if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
 591                         if( filterName( this_kid->getName()) ) {
 592                                 num_tri += ((ssgLeaf *) this_kid)->getNumTriangles();
 593                                 num_leaf ++;
 594                         }
 595                 } else
 596                         traverseTree( (ssgBranch *) this_kid );
 597         }
 598         if( num_tri > 0) {
 599                 int tri_idx = 0;
 600                 int ind_idx = 0;
 601                 ShadowCaster *new_part = new ShadowCaster( num_tri, branch);
 602                 new_part->scenery_object = scenery_object;
 603                 new_part->lib_object = lib_object;
 604                 for(int i = 0 ; i < branch->getNumKids() ; i++) {
 605                         ssgEntity *this_kid = branch->getKid( i );
 606                         if( this_kid->isAKindOf(ssgTypeLeaf()) ) {
 607                                 if( filterName( this_kid->getName()) )
 608                                         new_part->addLeaf( tri_idx, ind_idx, (ssgLeaf *) this_kid );
 609                         }
 610                 }
 611                 new_part->SetConnectivity();
 612                 parts.push_back( new_part );
 613         }
 614 }
 615
 616 void SGShadowVolume::SceneryObject::find_trans(void) {
 617         ssgBranch *branch = pending_object;
 618         ssgBranch *prev_branch = pending_object;
 619         // check the existence of the root node
 620         while( branch && branch->getNumParents() > 0 ) {
 621                 prev_branch = branch;
 622                 branch = branch->getParent(0);
 623         }
 624         // check if we are connected to the scene graph
 625         if( !branch->isA(ssgTypeRoot() ) )
 626                 return;
 627         scenery_object = pending_object;
 628 }
 629
 630 SGShadowVolume::SceneryObject::SceneryObject(ssgBranch *_scenery_object, OccluderType _occluder_type) :
 631         pending_object ( _scenery_object ),
 632         occluder_type ( _occluder_type ),
 633         scenery_object ( 0 )
 634 {
 635         // queue objects, don't do all the work in the first frames because of
 636         // massive cpu power needed
 637         statObj++;
 638         if( occluder_type == SGShadowVolume::occluderTypeAircraft )
 639                 lib_object = _scenery_object;
 640         else
 641                 lib_object = (ssgBranch *) ((ssgBranch *)_scenery_object->getKid(0))->getKid(0);
 642 }
 643
 644 SGShadowVolume::SceneryObject::~SceneryObject()
 645 {
 646         ShadowCaster_list::iterator iParts;
 647         for(iParts = parts.begin() ; iParts != parts.end(); iParts++ ) {
 648                 delete *iParts;
 649         }
 650         parts.clear();
 651 }
 652
 653 void SGShadowVolume::computeShadows(void) {
 654
 655         // intensity = ambient + lights
 656         // lights = sun_const * (sun_angle . normal)
 657         double dot_light = cos(sun_angle);
 658         // do nothing if sun is under horizon
 659         if( dot_light < 0.2 )
 660                 return;
 661
 662         //Draw shadow volumes
 663         glPushAttrib(GL_ALL_ATTRIB_BITS);
 664         glPushClientAttrib ( GL_CLIENT_VERTEX_ARRAY_BIT ) ;
 665         glDisableClientState ( GL_COLOR_ARRAY         ) ;
 666         glDisableClientState ( GL_NORMAL_ARRAY        ) ;
 667         glDisableClientState ( GL_TEXTURE_COORD_ARRAY ) ;
 668
 669         if( use_alpha ) {
 670                 glColorMask(0, 0, 0, 1);
 671                 glClearColor(0.0, 0.0, 0.0, 0.0 );
 672                 glClear(GL_COLOR_BUFFER_BIT);
 673                 glDisable(GL_ALPHA);
 674                 glEnable(GL_BLEND);
 675         } else {
 676                 glClearStencil( 0 );
 677                 glClear(GL_STENCIL_BUFFER_BIT);
 678                 glColorMask(0, 0, 0, 0);
 679                 glEnable(GL_STENCIL_TEST);
 680                 glDisable(GL_ALPHA);
 681                 glDisable(GL_BLEND);
 682         }
 683         glDisable( GL_LIGHTING );
 684         glDisable( GL_FOG );
 685         glEnable( GL_CULL_FACE  );
 686 //      glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
 687 //    glPolygonOffset(0.0,5.0);
 688     glPolygonOffset(0.0,30.0);
 689     glEnable(GL_POLYGON_OFFSET_FILL);
 690
 691         glShadeModel(GL_FLAT);
 692
 693         glDepthMask( false );
 694         glEnable( GL_DEPTH_TEST );
 695         glDepthFunc(GL_LESS);
 696
 697         SceneryObject_map::iterator iSceneryObject;
 698         // compute shadows for each objects
 699         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 700                 SceneryObject *an_occluder = iSceneryObject->second;
 701                 if( shadowsTO_enabled && (an_occluder->occluder_type == occluderTypeTileObject) ||
 702                         shadowsAI_enabled && (an_occluder->occluder_type == occluderTypeAI ) ||
 703                         shadowsAC_enabled && (an_occluder->occluder_type == occluderTypeAircraft ) )
 704                                 an_occluder->computeShadows();
 705         }
 706
 707
 708         glMatrixMode   ( GL_PROJECTION ) ;
 709         glPushMatrix   () ;
 710         glLoadIdentity () ;
 711         glOrtho        ( -100, 100, -100, 100, -1, 1 ) ;
 712         glMatrixMode   ( GL_MODELVIEW ) ;
 713         glPushMatrix   () ;
 714         glLoadIdentity () ;
 715
 716         glDisable(GL_DEPTH_TEST);
 717         glDisable(GL_CULL_FACE);
 718 //      glBindTexture(GL_TEXTURE_2D, 0);
 719         glPolygonMode(GL_FRONT, GL_FILL);
 720         if( use_alpha ) {
 721                 // there is a flaw in the Roettger paper, this does not work for some geometry
 722                 // where we increment (multiply) the buffer a few times then we
 723                 // decrement (divide) a few times. Decrementing more then once will give a
 724                 // non shadowed parts with mask value < 0.25 because the incrementation was
 725                 // clamped
 726                 // Solution : don't use a start value as high as 0.25 but the smallest value
 727                 // posible ie 1/256. This is not a general solution, a stencil buffer will
 728                 // support 255 incrementation before clamping, the alpha mask only 7.
 729                 // => that still does not work with our geometry so use subtractive blend
 730
 731                 // clamp mask = {0,16,32,64,...} => {0,16,16,16,...}
 732                 glBlendEquationPtr( GL_MIN_EXT );
 733                 glBlendFunc( GL_DST_COLOR, GL_ONE );
 734                 glColor4ub(1, 1, 1, 16);
 735                 glRectf(-100,-100,100,100);
 736                 // scale mask = {0,16} => {0,64}
 737                 glBlendEquationPtr( GL_FUNC_ADD );
 738                 glBlendFunc( GL_DST_COLOR, GL_ONE );
 739                 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 740                 glRectf(-100,-100,100,100);
 741                 glRectf(-100,-100,100,100);
 742                 // negate mask => {0,64} => {255, 191}
 743                 glBlendFunc( GL_ONE_MINUS_DST_COLOR, GL_ZERO );
 744                 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
 745                 glRectf(-100,-100,100,100);
 746                 // apply mask
 747                 glColorMask(1, 1, 1, 1);
 748                 glBlendFunc( GL_ZERO, GL_DST_ALPHA );
 749                 glColor4f(1.0f, 0.5f, 0.2f, 1.0f);
 750                 glRectf(-100,-100,100,100);
 751         } else {
 752                 // now the stencil contains 0 for scenery in light and != 0 for parts in shadow
 753                 // draw a quad covering the screen, the stencil will be the mask
 754                 // we darken the shadowed parts
 755                 glColorMask(1, 1, 1, 1);
 756                 glStencilFunc(GL_NOTEQUAL, 0, ~0);
 757                 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 758                 glEnable(GL_STENCIL_TEST);
 759                 glEnable(GL_ALPHA);
 760                 glAlphaFunc(GL_GREATER, 0.0f);
 761                 glEnable(GL_BLEND);
 762                 glBlendFunc ( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA ) ;
 763                 glColor4f(0.0, 0.0, 0.0, sgLerp(0.1, 0.3, dot_light) );
 764                 // fixed value is better, the previous line is surely wrong
 765                 glColor4f(0.0, 0.0, 0.0, 0.3 );
 766                 glRectf(-100,-100,100,100);
 767         }
 768         glMatrixMode   ( GL_PROJECTION ) ;
 769         glPopMatrix    () ;
 770         glMatrixMode   ( GL_MODELVIEW ) ;
 771         glPopMatrix    () ;
 772
 773         glDisable(GL_STENCIL_TEST);
 774         glPopClientAttrib ( ) ;
 775         glPopAttrib();
 776 }
 777
 778 SGShadowVolume::SGShadowVolume() :
 779         init_done( false ),
 780         shadows_enabled( false ),
 781         frameNumber( 0 ),
 782         lastTraverseTreeFrame ( 0 )
 783 {
 784         states = this;
 785 }
 786
 787 SGShadowVolume::~SGShadowVolume() {
 788         SceneryObject_map::iterator iSceneryObject;
 789         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 790                 delete iSceneryObject->second;
 791         }
 792         sceneryObjects.clear();
 793 }
 794
 795 void SGShadowVolume::init(SGPropertyNode *sim_rendering_options) {
 796         init_done = true;
 797         shadows_enabled = true;
 798         sim_rendering = sim_rendering_options;
 799         int stencilBits = 0, alphaBits = 0;
 800         glGetIntegerv( GL_STENCIL_BITS, &stencilBits );
 801         glGetIntegerv( GL_ALPHA_BITS, &alphaBits );
 802         bool hasSubtractiveBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_subtract");
 803         bool hasMinMaxBlend = SGIsOpenGLExtensionSupported("GL_EXT_blend_minmax");
 804         if( hasSubtractiveBlend )
 805                 glBlendEquationPtr = (glBlendEquationProc ) SGLookupFunction("glBlendEquationEXT");
 806         canDoAlpha = (alphaBits >= 8) && hasSubtractiveBlend && hasMinMaxBlend;
 807         canDoStencil = (stencilBits >= 3);
 808         if( !canDoStencil )
 809                 if( canDoAlpha )
 810                         SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer, using alpha buffer");
 811                 else
 812                         SG_LOG(SG_ALL, SG_WARN, "SGShadowVolume:no stencil buffer and no alpha buffer");
 813 }
 814
 815 void SGShadowVolume::startOfFrame(void) {
 816 }
 817 void SGShadowVolume::deleteOccluderFromTile(ssgBranch *tile) {
 818         SceneryObject_map::iterator iSceneryObject, iPrevious;
 819         iPrevious = sceneryObjects.begin();
 820         for(iSceneryObject = sceneryObjects.begin() ; iSceneryObject != sceneryObjects.end(); iSceneryObject++ ) {
 821                 if( iSceneryObject->second->tile == tile ) {
 822                         delete iSceneryObject->second;
 823                         sceneryObjects.erase( iSceneryObject );
 824                         iSceneryObject = iPrevious;
 825                 }
 826                 iPrevious = iSceneryObject;
 827         }
 828 }
 829
 830 void SGShadowVolume::deleteOccluder(ssgBranch *occluder) {
 831         ssgBranch *branch = occluder;
 832         // skip first node and go to first transform (placement)
 833         while( occluder && !occluder->isA(ssgTypeTransform()))
 834                 occluder = (ssgBranch *) occluder->getKid(0);
 835
 836         // check if we allready know this object
 837         SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
 838         if( iSceneryObject != sceneryObjects.end() ) {
 839                 delete iSceneryObject->second;
 840                 sceneryObjects.erase( occluder );
 841         }
 842 }
 843
 844 void SGShadowVolume::addOccluder(ssgBranch *occluder, OccluderType occluder_type, ssgBranch *tile) {
 845
 846         ssgBranch *branch = occluder;
 847
 848         // skip first node and go to first transform (placement)
 849         while( occluder && !occluder->isA(ssgTypeTransform()))
 850                 occluder = (ssgBranch *) occluder->getKid(0);
 851
 852         // check if we allready know this object
 853         SceneryObject_map::iterator iSceneryObject = sceneryObjects.find( occluder );
 854         if( iSceneryObject == sceneryObjects.end() ) {
 855 //              printf("adding model %x %x\n", occluder, tile);
 856                 SceneryObject *entry = new SceneryObject( occluder, occluder_type );
 857                 entry->tile = tile;
 858                 sceneryObjects[ occluder ] = entry;
 859         }
 860
 861 }
 862
 863 void SGShadowVolume::setupShadows( double lon, double lat,
 864                 double gst, double SunRightAscension, double SunDeclination, double sunAngle) {
 865
 866         shadowsAC_enabled = sim_rendering->getBoolValue("shadows-ac", false);
 867         shadowsAI_enabled = sim_rendering->getBoolValue("shadows-ai", false);
 868         shadowsTO_enabled = sim_rendering->getBoolValue("shadows-to", false);
 869         shadowsDebug_enabled = sim_rendering->getBoolValue("shadows-debug", false);
 870 //      shadows_enabled   = sim_rendering->getBoolValue("shadows", false);
 871         shadows_enabled = shadowsAC_enabled || shadowsAI_enabled || shadowsTO_enabled;
 872         shadows_enabled &= canDoAlpha || canDoStencil;
 873         use_alpha = ((!canDoStencil) || sim_rendering->getBoolValue("shadows-alpha", false)) &&
 874                 canDoAlpha;
 875
 876         if( ! shadows_enabled )
 877                 return;
 878
 879         sgMat4 view_angle;
 880         sun_angle = sunAngle;
 881         {
 882                 sgMat4 LON, LAT;
 883                 sgVec3 axis;
 884
 885                 sgSetVec3( axis, 0.0, 0.0, 1.0 );
 886                 sgMakeRotMat4( LON, lon, axis );
 887
 888                 sgSetVec3( axis, 0.0, 1.0, 0.0 );
 889                 sgMakeRotMat4( LAT, 90.0 - lat, axis );
 890
 891                 sgMat4 TRANSFORM;
 892
 893                 sgMakeIdentMat4 ( TRANSFORM );
 894                 sgPreMultMat4( TRANSFORM, LON );
 895                 sgPreMultMat4( TRANSFORM, LAT );
 896
 897                 sgCoord pos;
 898                 sgSetCoord( &pos, TRANSFORM );
 899
 900                 sgMakeCoordMat4( view_angle, &pos );
 901         }
 902         {
 903         sgMat4 GST, RA, DEC;
 904         sgVec3 axis;
 905
 906
 907         sgSetVec3( axis, 0.0, 0.0, -1.0 );
 908         sgMakeRotMat4( GST, (gst) * 15.0, axis );
 909
 910         sgSetVec3( axis, 0.0, 0.0, 1.0 );
 911         sgMakeRotMat4( RA, (SunRightAscension * SGD_RADIANS_TO_DEGREES) - 90.0, axis );
 912
 913         sgSetVec3( axis, 1.0, 0.0, 0.0 );
 914         sgMakeRotMat4( DEC, SunDeclination * SGD_RADIANS_TO_DEGREES, axis );
 915
 916         sgInvertMat4( invViewAngle, view_angle);
 917
 918         sgMat4 TRANSFORM;
 919         sgMakeIdentMat4( TRANSFORM );
 920         sgPreMultMat4( TRANSFORM, GST );
 921         sgPreMultMat4( TRANSFORM, RA );
 922         sgPreMultMat4( TRANSFORM, DEC );
 923         sgSetVec3( sunPos, 0.0, 9900000.0, 0.0);
 924         sgXformPnt3( sunPos, TRANSFORM );
 925         }
 926
 927         ssgGetModelviewMatrix( CameraViewM );
 928
 929 }
 930
 931 void SGShadowVolume::endOfFrame(void) {
 932         if( ! shadows_enabled )
 933                 return;
 934         glBindTexture(GL_TEXTURE_2D, 0);
 935         glBindTexture(GL_TEXTURE_1D, 0);
 936
 937         glMatrixMode(GL_MODELVIEW);
 938
 939         computeShadows();
 940
 941         frameNumber ++;
 942 }
 943