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