neo/renderer/tr_shadowbounds.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28 #include "../idlib/precompiled.h"
  29 #pragma hdrstop
  30
  31 #include "tr_local.h"
  32
  33
  34
  35 // Compute conservative shadow bounds as the intersection
  36 // of the object's bounds' shadow volume and the light's bounds.
  37 //
  38 // --cass
  39
  40
  41 template <class T, int N>
  42 struct MyArray
  43 {
  44         MyArray() : s(0) {}
  45
  46         MyArray( const MyArray<T,N> & cpy ) : s(cpy.s)
  47         {
  48                 for(int i=0; i < s; i++)
  49                         v[i] = cpy.v[i];
  50         }
  51
  52         void push_back(const T & i) {
  53                 v[s] = i;
  54                 s++;
  55                 //if(s > max_size)
  56                 //      max_size = int(s);
  57         }
  58
  59         T & operator[](int i) {
  60                 return v[i];
  61         }
  62
  63         const T & operator[](int i) const {
  64                 return v[i];
  65         }
  66
  67         unsigned int size() const {
  68                 return s;
  69         }
  70
  71         void empty() {
  72                 s = 0;
  73         }
  74
  75         T v[N];
  76         int s;
  77 //      static int max_size;
  78 };
  79
  80 typedef MyArray<int, 4> MyArrayInt;
  81 //int MyArrayInt::max_size = 0;
  82 typedef MyArray<idVec4, 16> MyArrayVec4;
  83 //int MyArrayVec4::max_size = 0;
  84
  85 struct poly
  86 {
  87     MyArrayInt vi;
  88     MyArrayInt ni;
  89     idVec4 plane;
  90 };
  91
  92 typedef MyArray<poly, 9> MyArrayPoly;
  93 //int MyArrayPoly::max_size = 0;
  94
  95 struct edge
  96 {
  97     int vi[2];
  98     int pi[2];
  99 };
 100
 101 typedef MyArray<edge, 15> MyArrayEdge;
 102 //int MyArrayEdge::max_size = 0;
 103
 104 MyArrayInt four_ints(int a, int b, int c, int d)
 105 {
 106     MyArrayInt vi;
 107     vi.push_back(a);
 108     vi.push_back(b);
 109     vi.push_back(c);
 110     vi.push_back(d);
 111     return vi;
 112 }
 113
 114 idVec3 homogeneous_difference(idVec4 a, idVec4 b)
 115 {
 116     idVec3 v;
 117         v.x = b.x * a.w - a.x * b.w;
 118         v.y = b.y * a.w - a.y * b.w;
 119         v.z = b.z * a.w - a.z * b.w;
 120     return v;
 121 }
 122
 123 // handles positive w only
 124 idVec4 compute_homogeneous_plane(idVec4 a, idVec4 b, idVec4 c)
 125 {
 126     idVec4 v, t;
 127
 128     if(a[3] == 0)
 129     { t = a; a = b; b = c; c = t; }
 130     if(a[3] == 0)
 131     { t = a; a = b; b = c; c = t; }
 132
 133     // can't handle 3 infinite points
 134     if( a[3] == 0 )
 135         return v;
 136
 137     idVec3 vb = homogeneous_difference(a, b);
 138     idVec3 vc = homogeneous_difference(a, c);
 139
 140     idVec3 n = vb.Cross(vc);
 141     n.Normalize();
 142
 143         v.x = n.x;
 144         v.y = n.y;
 145         v.z = n.z;
 146
 147         v.w = - (n * idVec3(a.x, a.y, a.z)) / a.w ;
 148
 149     return v;
 150 }
 151
 152 struct polyhedron
 153 {
 154     MyArrayVec4 v;
 155     MyArrayPoly  p;
 156     MyArrayEdge  e;
 157
 158     void add_quad( int va, int vb, int vc, int vd )
 159     {
 160         poly pg;
 161         pg.vi = four_ints(va, vb, vc, vd);
 162         pg.ni = four_ints(-1, -1, -1, -1);
 163         pg.plane = compute_homogeneous_plane(v[va], v[vb], v[vc]);
 164         p.push_back(pg);
 165     }
 166
 167     void discard_neighbor_info()
 168     {
 169         for(unsigned int i = 0; i < p.size(); i++ )
 170         {
 171             MyArrayInt & ni = p[i].ni;
 172             for(unsigned int j = 0; j < ni.size(); j++)
 173                 ni[j] = -1;
 174         }
 175     }
 176
 177     void compute_neighbors()
 178     {
 179                 e.empty();
 180
 181         discard_neighbor_info();
 182
 183         bool found;
 184         int P = p.size();
 185         // for each polygon
 186         for(int i = 0; i < P-1; i++ )
 187         {
 188             const MyArrayInt & vi = p[i].vi;
 189             MyArrayInt & ni = p[i].ni;
 190             int Si = vi.size();
 191
 192             // for each edge of that polygon
 193             for(int ii=0; ii < Si; ii++)
 194             {
 195                 int ii0 = ii;
 196                 int ii1 = (ii+1) % Si;
 197
 198                 // continue if we've already found this neighbor
 199                 if(ni[ii] != -1)
 200                     continue;
 201                 found = false;
 202                 // check all remaining polygons
 203                 for(int j = i+1; j < P; j++ )
 204                 {
 205                     const MyArrayInt & vj = p[j].vi;
 206                     MyArrayInt & nj = p[j].ni;
 207                     int Sj = vj.size();
 208
 209                     for( int jj = 0; jj < Sj; jj++ )
 210                     {
 211                         int jj0 = jj;
 212                         int jj1 = (jj+1) % Sj;
 213                         if(vi[ii0] == vj[jj1] && vi[ii1] == vj[jj0])
 214                         {
 215                             edge ed;
 216                             ed.vi[0] = vi[ii0];
 217                             ed.vi[1] = vi[ii1];
 218                             ed.pi[0] = i;
 219                             ed.pi[1] = j;
 220                             e.push_back(ed);
 221                             ni[ii] = j;
 222                             nj[jj] = i;
 223                             found = true;
 224                             break;
 225                         }
 226                         else if ( vi[ii0] == vj[jj0] && vi[ii1] == vj[jj1] )
 227                         {
 228                             fprintf(stderr,"why am I here?\n");
 229                         }
 230                     }
 231                     if( found )
 232                         break;
 233                 }
 234             }
 235         }
 236     }
 237
 238     void recompute_planes()
 239     {
 240         // for each polygon
 241         for(unsigned int i = 0; i < p.size(); i++ )
 242         {
 243             p[i].plane = compute_homogeneous_plane(v[p[i].vi[0]], v[p[i].vi[1]], v[p[i].vi[2]]);
 244         }
 245     }
 246
 247     void transform(const idMat4 & m)
 248     {
 249         for(unsigned int i=0; i < v.size(); i++ )
 250             v[i] = m * v[i];
 251         recompute_planes();
 252     }
 253
 254 };
 255
 256 // make a unit cube
 257 polyhedron PolyhedronFromBounds( const idBounds & b )
 258 {
 259
 260 //       3----------2
 261 //       |\        /|
 262 //       | \      / |
 263 //       |   7--6   |
 264 //       |   |  |   |
 265 //       |   4--5   |
 266 //       |  /    \  |
 267 //       | /      \ |
 268 //       0----------1
 269 //
 270
 271         static polyhedron p;
 272
 273         if( p.e.size() == 0 ) {
 274
 275                 p.v.push_back(idVec4( -1, -1,  1, 1));
 276                 p.v.push_back(idVec4(  1, -1,  1, 1));
 277                 p.v.push_back(idVec4(  1,  1,  1, 1));
 278                 p.v.push_back(idVec4( -1,  1,  1, 1));
 279                 p.v.push_back(idVec4( -1, -1, -1, 1));
 280                 p.v.push_back(idVec4(  1, -1, -1, 1));
 281                 p.v.push_back(idVec4(  1,  1, -1, 1));
 282                 p.v.push_back(idVec4( -1,  1, -1, 1));
 283
 284                 p.add_quad( 0, 1, 2, 3 );
 285                 p.add_quad( 7, 6, 5, 4 );
 286                 p.add_quad( 1, 0, 4, 5 );
 287                 p.add_quad( 2, 1, 5, 6 );
 288                 p.add_quad( 3, 2, 6, 7 );
 289                 p.add_quad( 0, 3, 7, 4 );
 290
 291                 p.compute_neighbors();
 292                 p.recompute_planes();
 293                 p.v.empty(); // no need to copy this data since it'll be replaced
 294         }
 295
 296         polyhedron p2(p);
 297
 298         const idVec3 & min = b[0];
 299         const idVec3 & max = b[1];
 300
 301         p2.v.empty();
 302         p2.v.push_back(idVec4( min.x, min.y, max.z, 1));
 303         p2.v.push_back(idVec4( max.x, min.y, max.z, 1));
 304         p2.v.push_back(idVec4( max.x, max.y, max.z, 1));
 305         p2.v.push_back(idVec4( min.x, max.y, max.z, 1));
 306         p2.v.push_back(idVec4( min.x, min.y, min.z, 1));
 307         p2.v.push_back(idVec4( max.x, min.y, min.z, 1));
 308         p2.v.push_back(idVec4( max.x, max.y, min.z, 1));
 309         p2.v.push_back(idVec4( min.x, max.y, min.z, 1));
 310
 311         p2.recompute_planes();
 312     return p2;
 313 }
 314
 315
 316 polyhedron make_sv(const polyhedron & oc, idVec4 light)
 317 {
 318         static polyhedron lut[64];
 319         int index = 0;
 320
 321         for(unsigned int i = 0; i < 6; i++) {
 322                 if( ( oc.p[i].plane * light ) > 0 )
 323                         index |= 1<<i;
 324         }
 325
 326         if( lut[index].e.size() == 0 )
 327         {
 328                 polyhedron & ph = lut[index];
 329                 ph = oc;
 330
 331                 int V = ph.v.size();
 332                 for( int j = 0; j < V; j++ )
 333                 {
 334                         idVec3 proj = homogeneous_difference( light, ph.v[j] );
 335                         ph.v.push_back( idVec4(proj.x, proj.y, proj.z, 0) );
 336                 }
 337
 338                 ph.p.empty();
 339
 340                 for(unsigned int i=0; i < oc.p.size(); i++)
 341                 {
 342                         if( (oc.p[i].plane * light) > 0)
 343                         {
 344                                 ph.p.push_back(oc.p[i]);
 345                         }
 346                 }
 347
 348                 if(ph.p.size() == 0)
 349                         return ph = polyhedron();
 350
 351                 ph.compute_neighbors();
 352
 353                 MyArrayPoly vpg;
 354                 int I = ph.p.size();
 355
 356                 for(int i=0; i < I; i++)
 357                 {
 358                         MyArrayInt & vi = ph.p[i].vi;
 359                         MyArrayInt & ni = ph.p[i].ni;
 360                         int S = vi.size();
 361
 362                         for(int j = 0; j < S; j++)
 363                         {
 364                                 if( ni[j] == -1 )
 365                                 {
 366                                         poly pg;
 367                                         int a = vi[(j+1)%S];
 368                                         int b = vi[j];
 369                                         pg.vi = four_ints( a, b, b+V, a+V);
 370                                         pg.ni = four_ints(-1, -1, -1, -1);
 371                                         vpg.push_back(pg);
 372                                 }
 373                         }
 374                 }
 375                 for(unsigned int i = 0; i < vpg.size(); i++)
 376                         ph.p.push_back(vpg[i]);
 377
 378                 ph.compute_neighbors();
 379                 ph.v.empty(); // no need to copy this data since it'll be replaced
 380         }
 381
 382         polyhedron ph2 = lut[index];
 383
 384         // initalize vertices
 385         ph2.v = oc.v;
 386         int V = ph2.v.size();
 387         for( int j = 0; j < V; j++ )
 388         {
 389                 idVec3 proj = homogeneous_difference( light, ph2.v[j] );
 390                 ph2.v.push_back( idVec4(proj.x, proj.y, proj.z, 0) );
 391         }
 392
 393     // need to compute planes for the shadow volume (sv)
 394     ph2.recompute_planes();
 395
 396     return ph2;
 397 }
 398
 399 typedef MyArray<idVec4, 36> MySegments;
 400 //int MySegments::max_size = 0;
 401
 402 void polyhedron_edges(polyhedron & a, MySegments & e)
 403 {
 404         e.empty();
 405     if(a.e.size() == 0 && a.p.size() != 0)
 406         a.compute_neighbors();
 407
 408     for(unsigned int i = 0; i < a.e.size(); i++)
 409     {
 410         e.push_back(a.v[a.e[i].vi[0]]);
 411         e.push_back(a.v[a.e[i].vi[1]]);
 412     }
 413
 414 }
 415
 416 // clip the segments of e by the planes of polyhedron a.
 417 void clip_segments(const polyhedron & ph, MySegments & is, MySegments & os)
 418 {
 419     const MyArrayPoly & p = ph.p;
 420
 421     for(unsigned int i = 0; i < is.size(); i+=2 )
 422     {
 423         idVec4 a = is[i  ];
 424         idVec4 b = is[i+1];
 425         idVec4 c;
 426
 427         bool discard = false;
 428
 429         for(unsigned int j = 0; j < p.size(); j++ )
 430         {
 431             float da = a * p[j].plane;
 432             float db = b * p[j].plane;
 433             float rdw = 1/(da - db);
 434
 435             int code = 0;
 436             if( da > 0 )
 437                 code = 2;
 438             if( db > 0 )
 439                 code |= 1;
 440
 441
 442             switch ( code )
 443             {
 444             case 3:
 445                 discard = true;
 446                 break;
 447
 448             case 2:
 449                 c = -db * rdw * a + da * rdw * b;
 450                 a = c;
 451                 break;
 452
 453             case 1:
 454                 c = -db * rdw * a + da * rdw * b;
 455                 b = c;
 456                 break;
 457
 458             case 0:
 459                 break;
 460
 461             default:
 462                 common->Printf("bad clip code!\n");
 463                 break;
 464             }
 465
 466             if( discard )
 467                 break;
 468         }
 469
 470         if( ! discard )
 471         {
 472             os.push_back(a);
 473             os.push_back(b);
 474         }
 475     }
 476
 477 }
 478
 479 idMat4 make_idMat4(const float * m)
 480 {
 481         return idMat4( m[ 0], m[ 4], m[ 8], m[12],
 482                                    m[ 1], m[ 5], m[ 9], m[13],
 483                                    m[ 2], m[ 6], m[10], m[14],
 484                                    m[ 3], m[ 7], m[11], m[15] );
 485 }
 486
 487 idVec3 v4to3(const idVec4 & v)
 488 {
 489         return idVec3(v.x/v.w, v.y/v.w, v.z/v.w);
 490 }
 491
 492 void draw_polyhedron( const viewDef_t *viewDef, const polyhedron & p, idVec4 color )
 493 {
 494         for(unsigned int i = 0; i < p.e.size(); i++)
 495         {
 496                 viewDef->renderWorld->DebugLine( color, v4to3(p.v[p.e[i].vi[0]]), v4to3(p.v[p.e[i].vi[1]]));
 497         }
 498 }
 499
 500 void draw_segments( const viewDef_t *viewDef, const MySegments & s, idVec4 color )
 501 {
 502         for(unsigned int i = 0; i < s.size(); i+=2)
 503         {
 504                 viewDef->renderWorld->DebugLine( color, v4to3(s[i]), v4to3(s[i+1]));
 505         }
 506 }
 507
 508 void world_to_hclip( const viewDef_t *viewDef, const idVec4 &global, idVec4 &clip ) {
 509         int             i;
 510         idVec4  view;
 511
 512         for ( i = 0 ; i < 4 ; i ++ ) {
 513                 view[i] =
 514                         global[0] * viewDef->worldSpace.modelViewMatrix[ i + 0 * 4 ] +
 515                         global[1] * viewDef->worldSpace.modelViewMatrix[ i + 1 * 4 ] +
 516                         global[2] * viewDef->worldSpace.modelViewMatrix[ i + 2 * 4 ] +
 517                         global[3] *     viewDef->worldSpace.modelViewMatrix[ i + 3 * 4 ];
 518         }
 519
 520
 521         for ( i = 0 ; i < 4 ; i ++ ) {
 522                 clip[i] =
 523                         view[0] * viewDef->projectionMatrix[ i + 0 * 4 ] +
 524                         view[1] * viewDef->projectionMatrix[ i + 1 * 4 ] +
 525                         view[2] * viewDef->projectionMatrix[ i + 2 * 4 ] +
 526                         view[3] * viewDef->projectionMatrix[ i + 3 * 4 ];
 527         }
 528 }
 529
 530 idScreenRect R_CalcIntersectionScissor( const idRenderLightLocal * lightDef,
 531                                                                             const idRenderEntityLocal * entityDef,
 532                                                                                 const viewDef_t * viewDef ) {
 533
 534         idMat4 omodel = make_idMat4( entityDef->modelMatrix );
 535         idMat4 lmodel = make_idMat4( lightDef->modelMatrix );
 536
 537         // compute light polyhedron
 538         polyhedron lvol = PolyhedronFromBounds( lightDef->frustumTris->bounds );
 539         // transform it into world space
 540         //lvol.transform( lmodel );
 541
 542         // debug //
 543         if ( r_useInteractionScissors.GetInteger() == -2 ) {
 544                 draw_polyhedron( viewDef, lvol, colorRed );
 545         }
 546
 547         // compute object polyhedron
 548         polyhedron vol = PolyhedronFromBounds( entityDef->referenceBounds );
 549
 550         //viewDef->renderWorld->DebugBounds( colorRed, lightDef->frustumTris->bounds );
 551         //viewDef->renderWorld->DebugBox( colorBlue, idBox( model->Bounds(), entityDef->parms.origin, entityDef->parms.axis ) );
 552
 553         // transform it into world space
 554     vol.transform( omodel );
 555
 556         // debug //
 557         if ( r_useInteractionScissors.GetInteger() == -2 ) {
 558                 draw_polyhedron( viewDef, vol, colorBlue );
 559         }
 560
 561         // transform light position into world space
 562         idVec4 lightpos = idVec4(lightDef->globalLightOrigin.x,
 563                                                          lightDef->globalLightOrigin.y,
 564                                                          lightDef->globalLightOrigin.z,
 565                                                          1.0f );
 566
 567         // generate shadow volume "polyhedron"
 568     polyhedron sv = make_sv(vol, lightpos);
 569
 570     MySegments in_segs, out_segs;
 571
 572         // get shadow volume edges
 573     polyhedron_edges(sv, in_segs);
 574         // clip them against light bounds planes
 575     clip_segments(lvol, in_segs, out_segs);
 576
 577         // get light bounds edges
 578         polyhedron_edges(lvol, in_segs);
 579         // clip them by the shadow volume
 580     clip_segments(sv, in_segs, out_segs);
 581
 582         // debug //
 583         if ( r_useInteractionScissors.GetInteger() == -2 ) {
 584                 draw_segments( viewDef, out_segs, colorGreen );
 585         }
 586
 587         idBounds outbounds;
 588         outbounds.Clear();
 589         for( unsigned int i = 0; i < out_segs.size(); i++ ) {
 590
 591                 idVec4 v;
 592                 world_to_hclip( viewDef, out_segs[i], v );
 593
 594                 if( v.w <= 0.0f ) {
 595                         return lightDef->viewLight->scissorRect;
 596                 }
 597
 598                 idVec3 rv(v.x, v.y, v.z);
 599                 rv /= v.w;
 600
 601                 outbounds.AddPoint( rv );
 602         }
 603
 604         // limit the bounds to avoid an inside out scissor rectangle due to floating point to short conversion
 605         if ( outbounds[0].x < -1.0f ) {
 606                 outbounds[0].x = -1.0f;
 607         }
 608         if ( outbounds[1].x > 1.0f ) {
 609                 outbounds[1].x = 1.0f;
 610         }
 611         if ( outbounds[0].y < -1.0f ) {
 612                 outbounds[0].y = -1.0f;
 613         }
 614         if ( outbounds[1].y > 1.0f ) {
 615                 outbounds[1].y = 1.0f;
 616         }
 617
 618         float w2 = ( viewDef->viewport.x2 - viewDef->viewport.x1 + 1 ) / 2.0f;
 619         float x = viewDef->viewport.x1;
 620         float h2 = ( viewDef->viewport.y2 - viewDef->viewport.y1 + 1 ) / 2.0f;
 621         float y = viewDef->viewport.y1;
 622
 623         idScreenRect rect;
 624         rect.x1 = outbounds[0].x * w2 + w2 + x;
 625         rect.x2 = outbounds[1].x * w2 + w2 + x;
 626         rect.y1 = outbounds[0].y * h2 + h2 + y;
 627         rect.y2 = outbounds[1].y * h2 + h2 + y;
 628         rect.Expand();
 629
 630         rect.Intersect( lightDef->viewLight->scissorRect );
 631
 632         // debug //
 633         if ( r_useInteractionScissors.GetInteger() == -2 && !rect.IsEmpty() ) {
 634                 viewDef->renderWorld->DebugScreenRect( colorYellow, rect, viewDef );
 635         }
 636
 637         return rect;
 638 }