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