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