tools/quake3/q3map2/visflow.c

   1 /* -------------------------------------------------------------------------------
   2
   3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4    For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6    This file is part of GtkRadiant.
   7
   8    GtkRadiant is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    GtkRadiant is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GtkRadiant; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22    ----------------------------------------------------------------------------------
  23
  24    This code has been altered significantly from its original form, to support
  25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27    ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define VISFLOW_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41
  42 /*
  43
  44    each portal will have a list of all possible to see from first portal
  45
  46    if (!thread->portalmightsee[portalnum])
  47
  48    portal mightsee
  49
  50    for p2 = all other portals in leaf
  51     get sperating planes
  52     for all portals that might be seen by p2
  53         mark as unseen if not present in seperating plane
  54     flood fill a new mightsee
  55     save as passagemightsee
  56
  57
  58    void CalcMightSee (leaf_t *leaf,
  59  */
  60
  61 int CountBits( byte *bits, int numbits ){
  62         int i;
  63         int c;
  64
  65         c = 0;
  66         for ( i = 0 ; i < numbits ; i++ )
  67                 if ( bits[i >> 3] & ( 1 << ( i & 7 ) ) ) {
  68                         c++;
  69                 }
  70
  71         return c;
  72 }
  73
  74 int c_fullskip;
  75
  76 int c_chop, c_nochop;
  77
  78 int active;
  79
  80 void CheckStack( leaf_t *leaf, threaddata_t *thread ){
  81         pstack_t    *p, *p2;
  82
  83         for ( p = thread->pstack_head.next ; p ; p = p->next )
  84         {
  85 //              Sys_Printf ("=");
  86                 if ( p->leaf == leaf ) {
  87                         Error( "CheckStack: leaf recursion" );
  88                 }
  89                 for ( p2 = thread->pstack_head.next ; p2 != p ; p2 = p2->next )
  90                         if ( p2->leaf == p->leaf ) {
  91                                 Error( "CheckStack: late leaf recursion" );
  92                         }
  93         }
  94 //      Sys_Printf ("\n");
  95 }
  96
  97
  98 fixedWinding_t *AllocStackWinding( pstack_t *stack ){
  99         int i;
 100
 101         for ( i = 0 ; i < 3 ; i++ )
 102         {
 103                 if ( stack->freewindings[i] ) {
 104                         stack->freewindings[i] = 0;
 105                         return &stack->windings[i];
 106                 }
 107         }
 108
 109         Error( "AllocStackWinding: failed" );
 110
 111         return NULL;
 112 }
 113
 114 void FreeStackWinding( fixedWinding_t *w, pstack_t *stack ){
 115         int i;
 116
 117         i = w - stack->windings;
 118
 119         if ( i < 0 || i > 2 ) {
 120                 return;     // not from local
 121
 122         }
 123         if ( stack->freewindings[i] ) {
 124                 Error( "FreeStackWinding: allready free" );
 125         }
 126         stack->freewindings[i] = 1;
 127 }
 128
 129 /*
 130    ==============
 131    VisChopWinding
 132
 133    ==============
 134  */
 135 fixedWinding_t  *VisChopWinding( fixedWinding_t *in, pstack_t *stack, visPlane_t *split ){
 136         vec_t dists[128];
 137         int sides[128];
 138         int counts[3];
 139         vec_t dot;
 140         int i, j;
 141         vec_t   *p1, *p2;
 142         vec3_t mid;
 143         fixedWinding_t  *neww;
 144
 145         counts[0] = counts[1] = counts[2] = 0;
 146
 147         // determine sides for each point
 148         for ( i = 0 ; i < in->numpoints ; i++ )
 149         {
 150                 dot = DotProduct( in->points[i], split->normal );
 151                 dot -= split->dist;
 152                 dists[i] = dot;
 153                 if ( dot > ON_EPSILON ) {
 154                         sides[i] = SIDE_FRONT;
 155                 }
 156                 else if ( dot < -ON_EPSILON ) {
 157                         sides[i] = SIDE_BACK;
 158                 }
 159                 else
 160                 {
 161                         sides[i] = SIDE_ON;
 162                 }
 163                 counts[sides[i]]++;
 164         }
 165
 166         if ( !counts[1] ) {
 167                 return in;      // completely on front side
 168
 169         }
 170         if ( !counts[0] ) {
 171                 FreeStackWinding( in, stack );
 172                 return NULL;
 173         }
 174
 175         sides[i] = sides[0];
 176         dists[i] = dists[0];
 177
 178         neww = AllocStackWinding( stack );
 179
 180         neww->numpoints = 0;
 181
 182         for ( i = 0 ; i < in->numpoints ; i++ )
 183         {
 184                 p1 = in->points[i];
 185
 186                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
 187                         FreeStackWinding( neww, stack );
 188                         return in;      // can't chop -- fall back to original
 189                 }
 190
 191                 if ( sides[i] == SIDE_ON ) {
 192                         VectorCopy( p1, neww->points[neww->numpoints] );
 193                         neww->numpoints++;
 194                         continue;
 195                 }
 196
 197                 if ( sides[i] == SIDE_FRONT ) {
 198                         VectorCopy( p1, neww->points[neww->numpoints] );
 199                         neww->numpoints++;
 200                 }
 201
 202                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 203                         continue;
 204                 }
 205
 206                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
 207                         FreeStackWinding( neww, stack );
 208                         return in;      // can't chop -- fall back to original
 209                 }
 210
 211                 // generate a split point
 212                 p2 = in->points[( i + 1 ) % in->numpoints];
 213
 214                 dot = dists[i] / ( dists[i] - dists[i + 1] );
 215                 for ( j = 0 ; j < 3 ; j++ )
 216                 {   // avoid round off error when possible
 217                         if ( split->normal[j] == 1 ) {
 218                                 mid[j] = split->dist;
 219                         }
 220                         else if ( split->normal[j] == -1 ) {
 221                                 mid[j] = -split->dist;
 222                         }
 223                         else{
 224                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
 225                         }
 226                 }
 227
 228                 VectorCopy( mid, neww->points[neww->numpoints] );
 229                 neww->numpoints++;
 230         }
 231
 232         // free the original winding
 233         FreeStackWinding( in, stack );
 234
 235         return neww;
 236 }
 237
 238 /*
 239    ==============
 240    ClipToSeperators
 241
 242    Source, pass, and target are an ordering of portals.
 243
 244    Generates seperating planes canidates by taking two points from source and one
 245    point from pass, and clips target by them.
 246
 247    If target is totally clipped away, that portal can not be seen through.
 248
 249    Normal clip keeps target on the same side as pass, which is correct if the
 250    order goes source, pass, target.  If the order goes pass, source, target then
 251    flipclip should be set.
 252    ==============
 253  */
 254 fixedWinding_t  *ClipToSeperators( fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack ){
 255         int i, j, k, l;
 256         visPlane_t plane;
 257         vec3_t v1, v2;
 258         float d;
 259         vec_t length;
 260         int counts[3];
 261         qboolean fliptest;
 262
 263         // check all combinations
 264         for ( i = 0 ; i < source->numpoints ; i++ )
 265         {
 266                 l = ( i + 1 ) % source->numpoints;
 267                 VectorSubtract( source->points[l], source->points[i], v1 );
 268
 269                 // find a vertex of pass that makes a plane that puts all of the
 270                 // vertexes of pass on the front side and all of the vertexes of
 271                 // source on the back side
 272                 for ( j = 0 ; j < pass->numpoints ; j++ )
 273                 {
 274                         VectorSubtract( pass->points[j], source->points[i], v2 );
 275
 276                         plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
 277                         plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
 278                         plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
 279
 280                         // if points don't make a valid plane, skip it
 281
 282                         length = plane.normal[0] * plane.normal[0]
 283                                          + plane.normal[1] * plane.normal[1]
 284                                          + plane.normal[2] * plane.normal[2];
 285
 286                         if ( length < ON_EPSILON ) {
 287                                 continue;
 288                         }
 289
 290                         length = 1 / sqrt( length );
 291
 292                         plane.normal[0] *= length;
 293                         plane.normal[1] *= length;
 294                         plane.normal[2] *= length;
 295
 296                         plane.dist = DotProduct( pass->points[j], plane.normal );
 297
 298                         //
 299                         // find out which side of the generated seperating plane has the
 300                         // source portal
 301                         //
 302 #if 1
 303                         fliptest = qfalse;
 304                         for ( k = 0 ; k < source->numpoints ; k++ )
 305                         {
 306                                 if ( k == i || k == l ) {
 307                                         continue;
 308                                 }
 309                                 d = DotProduct( source->points[k], plane.normal ) - plane.dist;
 310                                 if ( d < -ON_EPSILON ) { // source is on the negative side, so we want all
 311                                                             // pass and target on the positive side
 312                                         fliptest = qfalse;
 313                                         break;
 314                                 }
 315                                 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
 316                                                                 // pass and target on the negative side
 317                                         fliptest = qtrue;
 318                                         break;
 319                                 }
 320                         }
 321                         if ( k == source->numpoints ) {
 322                                 continue;       // planar with source portal
 323                         }
 324 #else
 325                         fliptest = flipclip;
 326 #endif
 327                         //
 328                         // flip the normal if the source portal is backwards
 329                         //
 330                         if ( fliptest ) {
 331                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
 332                                 plane.dist = -plane.dist;
 333                         }
 334 #if 1
 335                         //
 336                         // if all of the pass portal points are now on the positive side,
 337                         // this is the seperating plane
 338                         //
 339                         counts[0] = counts[1] = counts[2] = 0;
 340                         for ( k = 0 ; k < pass->numpoints ; k++ )
 341                         {
 342                                 if ( k == j ) {
 343                                         continue;
 344                                 }
 345                                 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
 346                                 if ( d < -ON_EPSILON ) {
 347                                         break;
 348                                 }
 349                                 else if ( d > ON_EPSILON ) {
 350                                         counts[0]++;
 351                                 }
 352                                 else{
 353                                         counts[2]++;
 354                                 }
 355                         }
 356                         if ( k != pass->numpoints ) {
 357                                 continue;   // points on negative side, not a seperating plane
 358
 359                         }
 360                         if ( !counts[0] ) {
 361                                 continue;   // planar with seperating plane
 362                         }
 363 #else
 364                         k = ( j + 1 ) % pass->numpoints;
 365                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
 366                         if ( d < -ON_EPSILON ) {
 367                                 continue;
 368                         }
 369                         k = ( j + pass->numpoints - 1 ) % pass->numpoints;
 370                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
 371                         if ( d < -ON_EPSILON ) {
 372                                 continue;
 373                         }
 374 #endif
 375                         //
 376                         // flip the normal if we want the back side
 377                         //
 378                         if ( flipclip ) {
 379                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
 380                                 plane.dist = -plane.dist;
 381                         }
 382
 383 #ifdef SEPERATORCACHE
 384                         stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
 385                         if ( ++stack->numseperators[flipclip] >= MAX_SEPERATORS ) {
 386                                 Error( "MAX_SEPERATORS" );
 387                         }
 388 #endif
 389                         //MrE: fast check first
 390                         d = DotProduct( stack->portal->origin, plane.normal ) - plane.dist;
 391                         //if completely at the back of the seperator plane
 392                         if ( d < -stack->portal->radius ) {
 393                                 return NULL;
 394                         }
 395                         //if completely on the front of the seperator plane
 396                         if ( d > stack->portal->radius ) {
 397                                 break;
 398                         }
 399
 400                         //
 401                         // clip target by the seperating plane
 402                         //
 403                         target = VisChopWinding( target, stack, &plane );
 404                         if ( !target ) {
 405                                 return NULL;        // target is not visible
 406
 407                         }
 408                         break;      // optimization by Antony Suter
 409                 }
 410         }
 411
 412         return target;
 413 }
 414
 415 /*
 416    ==================
 417    RecursiveLeafFlow
 418
 419    Flood fill through the leafs
 420    If src_portal is NULL, this is the originating leaf
 421    ==================
 422  */
 423 void RecursiveLeafFlow( int leafnum, threaddata_t *thread, pstack_t *prevstack ){
 424         pstack_t stack;
 425         vportal_t   *p;
 426         visPlane_t backplane;
 427         leaf_t      *leaf;
 428         int i, j, n;
 429         long        *test, *might, *prevmight, *vis, more;
 430         int pnum;
 431
 432         thread->c_chains++;
 433
 434         leaf = &leafs[leafnum];
 435 //      CheckStack (leaf, thread);
 436
 437         prevstack->next = &stack;
 438
 439         stack.next = NULL;
 440         stack.leaf = leaf;
 441         stack.portal = NULL;
 442         stack.depth = prevstack->depth + 1;
 443
 444 #ifdef SEPERATORCACHE
 445         stack.numseperators[0] = 0;
 446         stack.numseperators[1] = 0;
 447 #endif
 448
 449         might = (long *)stack.mightsee;
 450         vis = (long *)thread->base->portalvis;
 451
 452         // check all portals for flowing into other leafs
 453         for ( i = 0; i < leaf->numportals; i++ )
 454         {
 455                 p = leaf->portals[i];
 456                 if ( p->removed ) {
 457                         continue;
 458                 }
 459                 pnum = p - portals;
 460
 461                 /* MrE: portal trace debug code
 462                    {
 463                     int portaltrace[] = {13, 16, 17, 37};
 464                     pstack_t *s;
 465
 466                     s = &thread->pstack_head;
 467                     for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
 468                     {
 469                         if (s->portal->num != portaltrace[j])
 470                             break;
 471                     }
 472                     if (j >= sizeof(portaltrace)/sizeof(int) - 1)
 473                     {
 474                         if (p->num == portaltrace[j])
 475                             n = 0; //traced through all the portals
 476                     }
 477                    }
 478                  */
 479
 480                 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
 481                         continue;   // can't possibly see it
 482                 }
 483
 484                 // if the portal can't see anything we haven't allready seen, skip it
 485                 if ( p->status == stat_done ) {
 486                         test = (long *)p->portalvis;
 487                 }
 488                 else
 489                 {
 490                         test = (long *)p->portalflood;
 491                 }
 492
 493                 more = 0;
 494                 prevmight = (long *)prevstack->mightsee;
 495                 for ( j = 0 ; j < portallongs ; j++ )
 496                 {
 497                         might[j] = prevmight[j] & test[j];
 498                         more |= ( might[j] & ~vis[j] );
 499                 }
 500
 501                 if ( !more &&
 502                          ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
 503                         continue;
 504                 }
 505
 506                 // get plane of portal, point normal into the neighbor leaf
 507                 stack.portalplane = p->plane;
 508                 VectorSubtract( vec3_origin, p->plane.normal, backplane.normal );
 509                 backplane.dist = -p->plane.dist;
 510
 511 //              c_portalcheck++;
 512
 513                 stack.portal = p;
 514                 stack.next = NULL;
 515                 stack.freewindings[0] = 1;
 516                 stack.freewindings[1] = 1;
 517                 stack.freewindings[2] = 1;
 518
 519 #if 1
 520                 {
 521                         float d;
 522
 523                         d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
 524                         d -= thread->pstack_head.portalplane.dist;
 525                         if ( d < -p->radius ) {
 526                                 continue;
 527                         }
 528                         else if ( d > p->radius ) {
 529                                 stack.pass = p->winding;
 530                         }
 531                         else
 532                         {
 533                                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 534                                 if ( !stack.pass ) {
 535                                         continue;
 536                                 }
 537                         }
 538                 }
 539 #else
 540                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 541                 if ( !stack.pass ) {
 542                         continue;
 543                 }
 544 #endif
 545
 546
 547 #if 1
 548                 {
 549                         float d;
 550
 551                         d = DotProduct( thread->base->origin, p->plane.normal );
 552                         d -= p->plane.dist;
 553                         //MrE: vis-bug fix
 554                         //if (d > p->radius)
 555                         if ( d > thread->base->radius ) {
 556                                 continue;
 557                         }
 558                         //MrE: vis-bug fix
 559                         //if (d < -p->radius)
 560                         else if ( d < -thread->base->radius ) {
 561                                 stack.source = prevstack->source;
 562                         }
 563                         else
 564                         {
 565                                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 566                                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
 567                                 if ( !stack.source ) {
 568                                         continue;
 569                                 }
 570                         }
 571                 }
 572 #else
 573                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 574                 if ( !stack.source ) {
 575                         continue;
 576                 }
 577 #endif
 578
 579                 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
 580
 581                         // mark the portal as visible
 582                         thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 583
 584                         RecursiveLeafFlow( p->leaf, thread, &stack );
 585                         continue;
 586                 }
 587
 588 #ifdef SEPERATORCACHE
 589                 if ( stack.numseperators[0] ) {
 590                         for ( n = 0; n < stack.numseperators[0]; n++ )
 591                         {
 592                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
 593                                 if ( !stack.pass ) {
 594                                         break;      // target is not visible
 595                                 }
 596                         }
 597                         if ( n < stack.numseperators[0] ) {
 598                                 continue;
 599                         }
 600                 }
 601                 else
 602                 {
 603                         stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
 604                 }
 605 #else
 606                 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
 607 #endif
 608                 if ( !stack.pass ) {
 609                         continue;
 610                 }
 611
 612 #ifdef SEPERATORCACHE
 613                 if ( stack.numseperators[1] ) {
 614                         for ( n = 0; n < stack.numseperators[1]; n++ )
 615                         {
 616                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
 617                                 if ( !stack.pass ) {
 618                                         break;      // target is not visible
 619                                 }
 620                         }
 621                 }
 622                 else
 623                 {
 624                         stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
 625                 }
 626 #else
 627                 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
 628 #endif
 629                 if ( !stack.pass ) {
 630                         continue;
 631                 }
 632
 633                 // mark the portal as visible
 634                 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 635
 636                 // flow through it for real
 637                 RecursiveLeafFlow( p->leaf, thread, &stack );
 638                 //
 639                 stack.next = NULL;
 640         }
 641 }
 642
 643 /*
 644    ===============
 645    PortalFlow
 646
 647    generates the portalvis bit vector
 648    ===============
 649  */
 650 void PortalFlow( int portalnum ){
 651         threaddata_t data;
 652         int i;
 653         vportal_t       *p;
 654         int c_might, c_can;
 655
 656 #ifdef MREDEBUG
 657         Sys_Printf( "\r%6d", portalnum );
 658 #endif
 659
 660         p = sorted_portals[portalnum];
 661
 662         if ( p->removed ) {
 663                 p->status = stat_done;
 664                 return;
 665         }
 666
 667         p->status = stat_working;
 668
 669         c_might = CountBits( p->portalflood, numportals * 2 );
 670
 671         memset( &data, 0, sizeof( data ) );
 672         data.base = p;
 673
 674         data.pstack_head.portal = p;
 675         data.pstack_head.source = p->winding;
 676         data.pstack_head.portalplane = p->plane;
 677         data.pstack_head.depth = 0;
 678         for ( i = 0 ; i < portallongs ; i++ )
 679                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
 680
 681         RecursiveLeafFlow( p->leaf, &data, &data.pstack_head );
 682
 683         p->status = stat_done;
 684
 685         c_can = CountBits( p->portalvis, numportals * 2 );
 686
 687         Sys_FPrintf( SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
 688                                  (int)( p - portals ), c_might, c_can, data.c_chains );
 689 }
 690
 691 /*
 692    ==================
 693    RecursivePassageFlow
 694    ==================
 695  */
 696 void RecursivePassageFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
 697         pstack_t stack;
 698         vportal_t   *p;
 699         leaf_t      *leaf;
 700         passage_t   *passage, *nextpassage;
 701         int i, j;
 702         long        *might, *vis, *prevmight, *cansee, *portalvis, more;
 703         int pnum;
 704
 705         leaf = &leafs[portal->leaf];
 706
 707         prevstack->next = &stack;
 708
 709         stack.next = NULL;
 710         stack.depth = prevstack->depth + 1;
 711
 712         vis = (long *)thread->base->portalvis;
 713
 714         passage = portal->passages;
 715         nextpassage = passage;
 716         // check all portals for flowing into other leafs
 717         for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
 718         {
 719                 p = leaf->portals[i];
 720                 if ( p->removed ) {
 721                         continue;
 722                 }
 723                 nextpassage = passage->next;
 724                 pnum = p - portals;
 725
 726                 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
 727                         continue;   // can't possibly see it
 728                 }
 729
 730                 // mark the portal as visible
 731                 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 732
 733                 prevmight = (long *)prevstack->mightsee;
 734                 cansee = (long *)passage->cansee;
 735                 might = (long *)stack.mightsee;
 736                 memcpy( might, prevmight, portalbytes );
 737                 if ( p->status == stat_done ) {
 738                         portalvis = (long *) p->portalvis;
 739                 }
 740                 else{
 741                         portalvis = (long *) p->portalflood;
 742                 }
 743                 more = 0;
 744                 for ( j = 0; j < portallongs; j++ )
 745                 {
 746                         if ( *might ) {
 747                                 *might &= *cansee++ & *portalvis++;
 748                                 more |= ( *might & ~vis[j] );
 749                         }
 750                         else
 751                         {
 752                                 cansee++;
 753                                 portalvis++;
 754                         }
 755                         might++;
 756                 }
 757
 758                 if ( !more ) {
 759                         // can't see anything new
 760                         continue;
 761                 }
 762
 763                 // flow through it for real
 764                 RecursivePassageFlow( p, thread, &stack );
 765
 766                 stack.next = NULL;
 767         }
 768 }
 769
 770 /*
 771    ===============
 772    PassageFlow
 773    ===============
 774  */
 775 void PassageFlow( int portalnum ){
 776         threaddata_t data;
 777         int i;
 778         vportal_t       *p;
 779 //      int                             c_might, c_can;
 780
 781 #ifdef MREDEBUG
 782         Sys_Printf( "\r%6d", portalnum );
 783 #endif
 784
 785         p = sorted_portals[portalnum];
 786
 787         if ( p->removed ) {
 788                 p->status = stat_done;
 789                 return;
 790         }
 791
 792         p->status = stat_working;
 793
 794 //      c_might = CountBits (p->portalflood, numportals*2);
 795
 796         memset( &data, 0, sizeof( data ) );
 797         data.base = p;
 798
 799         data.pstack_head.portal = p;
 800         data.pstack_head.source = p->winding;
 801         data.pstack_head.portalplane = p->plane;
 802         data.pstack_head.depth = 0;
 803         for ( i = 0 ; i < portallongs ; i++ )
 804                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
 805
 806         RecursivePassageFlow( p, &data, &data.pstack_head );
 807
 808         p->status = stat_done;
 809
 810         /*
 811            c_can = CountBits (p->portalvis, numportals*2);
 812
 813            Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
 814             (int)(p - portals), c_might, c_can, data.c_chains);
 815          */
 816 }
 817
 818 /*
 819    ==================
 820    RecursivePassagePortalFlow
 821    ==================
 822  */
 823 void RecursivePassagePortalFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
 824         pstack_t stack;
 825         vportal_t   *p;
 826         leaf_t      *leaf;
 827         visPlane_t backplane;
 828         passage_t   *passage, *nextpassage;
 829         int i, j, n;
 830         long        *might, *vis, *prevmight, *cansee, *portalvis, more;
 831         int pnum;
 832
 833 //      thread->c_chains++;
 834
 835         leaf = &leafs[portal->leaf];
 836 //      CheckStack (leaf, thread);
 837
 838         prevstack->next = &stack;
 839
 840         stack.next = NULL;
 841         stack.leaf = leaf;
 842         stack.portal = NULL;
 843         stack.depth = prevstack->depth + 1;
 844
 845 #ifdef SEPERATORCACHE
 846         stack.numseperators[0] = 0;
 847         stack.numseperators[1] = 0;
 848 #endif
 849
 850         vis = (long *)thread->base->portalvis;
 851
 852         passage = portal->passages;
 853         nextpassage = passage;
 854         // check all portals for flowing into other leafs
 855         for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
 856         {
 857                 p = leaf->portals[i];
 858                 if ( p->removed ) {
 859                         continue;
 860                 }
 861                 nextpassage = passage->next;
 862                 pnum = p - portals;
 863
 864                 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
 865                         continue;   // can't possibly see it
 866
 867                 }
 868                 prevmight = (long *)prevstack->mightsee;
 869                 cansee = (long *)passage->cansee;
 870                 might = (long *)stack.mightsee;
 871                 memcpy( might, prevmight, portalbytes );
 872                 if ( p->status == stat_done ) {
 873                         portalvis = (long *) p->portalvis;
 874                 }
 875                 else{
 876                         portalvis = (long *) p->portalflood;
 877                 }
 878                 more = 0;
 879                 for ( j = 0; j < portallongs; j++ )
 880                 {
 881                         if ( *might ) {
 882                                 *might &= *cansee++ & *portalvis++;
 883                                 more |= ( *might & ~vis[j] );
 884                         }
 885                         else
 886                         {
 887                                 cansee++;
 888                                 portalvis++;
 889                         }
 890                         might++;
 891                 }
 892
 893                 if ( !more && ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
 894                         continue;
 895                 }
 896
 897                 // get plane of portal, point normal into the neighbor leaf
 898                 stack.portalplane = p->plane;
 899                 VectorSubtract( vec3_origin, p->plane.normal, backplane.normal );
 900                 backplane.dist = -p->plane.dist;
 901
 902 //              c_portalcheck++;
 903
 904                 stack.portal = p;
 905                 stack.next = NULL;
 906                 stack.freewindings[0] = 1;
 907                 stack.freewindings[1] = 1;
 908                 stack.freewindings[2] = 1;
 909
 910 #if 1
 911                 {
 912                         float d;
 913
 914                         d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
 915                         d -= thread->pstack_head.portalplane.dist;
 916                         if ( d < -p->radius ) {
 917                                 continue;
 918                         }
 919                         else if ( d > p->radius ) {
 920                                 stack.pass = p->winding;
 921                         }
 922                         else
 923                         {
 924                                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 925                                 if ( !stack.pass ) {
 926                                         continue;
 927                                 }
 928                         }
 929                 }
 930 #else
 931                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 932                 if ( !stack.pass ) {
 933                         continue;
 934                 }
 935 #endif
 936
 937
 938 #if 1
 939                 {
 940                         float d;
 941
 942                         d = DotProduct( thread->base->origin, p->plane.normal );
 943                         d -= p->plane.dist;
 944                         //MrE: vis-bug fix
 945                         //if (d > p->radius)
 946                         if ( d > thread->base->radius ) {
 947                                 continue;
 948                         }
 949                         //MrE: vis-bug fix
 950                         //if (d < -p->radius)
 951                         else if ( d < -thread->base->radius ) {
 952                                 stack.source = prevstack->source;
 953                         }
 954                         else
 955                         {
 956                                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 957                                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
 958                                 if ( !stack.source ) {
 959                                         continue;
 960                                 }
 961                         }
 962                 }
 963 #else
 964                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 965                 if ( !stack.source ) {
 966                         continue;
 967                 }
 968 #endif
 969
 970                 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
 971
 972                         // mark the portal as visible
 973                         thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 974
 975                         RecursivePassagePortalFlow( p, thread, &stack );
 976                         continue;
 977                 }
 978
 979 #ifdef SEPERATORCACHE
 980                 if ( stack.numseperators[0] ) {
 981                         for ( n = 0; n < stack.numseperators[0]; n++ )
 982                         {
 983                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
 984                                 if ( !stack.pass ) {
 985                                         break;      // target is not visible
 986                                 }
 987                         }
 988                         if ( n < stack.numseperators[0] ) {
 989                                 continue;
 990                         }
 991                 }
 992                 else
 993                 {
 994                         stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
 995                 }
 996 #else
 997                 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
 998 #endif
 999                 if ( !stack.pass ) {
1000                         continue;
1001                 }
1002
1003 #ifdef SEPERATORCACHE
1004                 if ( stack.numseperators[1] ) {
1005                         for ( n = 0; n < stack.numseperators[1]; n++ )
1006                         {
1007                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
1008                                 if ( !stack.pass ) {
1009                                         break;      // target is not visible
1010                                 }
1011                         }
1012                 }
1013                 else
1014                 {
1015                         stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
1016                 }
1017 #else
1018                 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
1019 #endif
1020                 if ( !stack.pass ) {
1021                         continue;
1022                 }
1023
1024                 // mark the portal as visible
1025                 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1026
1027                 // flow through it for real
1028                 RecursivePassagePortalFlow( p, thread, &stack );
1029                 //
1030                 stack.next = NULL;
1031         }
1032 }
1033
1034 /*
1035    ===============
1036    PassagePortalFlow
1037    ===============
1038  */
1039 void PassagePortalFlow( int portalnum ){
1040         threaddata_t data;
1041         int i;
1042         vportal_t       *p;
1043 //      int                             c_might, c_can;
1044
1045 #ifdef MREDEBUG
1046         Sys_Printf( "\r%6d", portalnum );
1047 #endif
1048
1049         p = sorted_portals[portalnum];
1050
1051         if ( p->removed ) {
1052                 p->status = stat_done;
1053                 return;
1054         }
1055
1056         p->status = stat_working;
1057
1058 //      c_might = CountBits (p->portalflood, numportals*2);
1059
1060         memset( &data, 0, sizeof( data ) );
1061         data.base = p;
1062
1063         data.pstack_head.portal = p;
1064         data.pstack_head.source = p->winding;
1065         data.pstack_head.portalplane = p->plane;
1066         data.pstack_head.depth = 0;
1067         for ( i = 0 ; i < portallongs ; i++ )
1068                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
1069
1070         RecursivePassagePortalFlow( p, &data, &data.pstack_head );
1071
1072         p->status = stat_done;
1073
1074         /*
1075            c_can = CountBits (p->portalvis, numportals*2);
1076
1077            Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
1078             (int)(p - portals), c_might, c_can, data.c_chains);
1079          */
1080 }
1081
1082 fixedWinding_t *PassageChopWinding( fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split ){
1083         vec_t dists[128];
1084         int sides[128];
1085         int counts[3];
1086         vec_t dot;
1087         int i, j;
1088         vec_t   *p1, *p2;
1089         vec3_t mid;
1090         fixedWinding_t  *neww;
1091
1092         counts[0] = counts[1] = counts[2] = 0;
1093
1094         // determine sides for each point
1095         for ( i = 0 ; i < in->numpoints ; i++ )
1096         {
1097                 dot = DotProduct( in->points[i], split->normal );
1098                 dot -= split->dist;
1099                 dists[i] = dot;
1100                 if ( dot > ON_EPSILON ) {
1101                         sides[i] = SIDE_FRONT;
1102                 }
1103                 else if ( dot < -ON_EPSILON ) {
1104                         sides[i] = SIDE_BACK;
1105                 }
1106                 else
1107                 {
1108                         sides[i] = SIDE_ON;
1109                 }
1110                 counts[sides[i]]++;
1111         }
1112
1113         if ( !counts[1] ) {
1114                 return in;      // completely on front side
1115
1116         }
1117         if ( !counts[0] ) {
1118                 return NULL;
1119         }
1120
1121         sides[i] = sides[0];
1122         dists[i] = dists[0];
1123
1124         neww = out;
1125
1126         neww->numpoints = 0;
1127
1128         for ( i = 0 ; i < in->numpoints ; i++ )
1129         {
1130                 p1 = in->points[i];
1131
1132                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1133                         return in;      // can't chop -- fall back to original
1134                 }
1135
1136                 if ( sides[i] == SIDE_ON ) {
1137                         VectorCopy( p1, neww->points[neww->numpoints] );
1138                         neww->numpoints++;
1139                         continue;
1140                 }
1141
1142                 if ( sides[i] == SIDE_FRONT ) {
1143                         VectorCopy( p1, neww->points[neww->numpoints] );
1144                         neww->numpoints++;
1145                 }
1146
1147                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
1148                         continue;
1149                 }
1150
1151                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1152                         return in;      // can't chop -- fall back to original
1153                 }
1154
1155                 // generate a split point
1156                 p2 = in->points[( i + 1 ) % in->numpoints];
1157
1158                 dot = dists[i] / ( dists[i] - dists[i + 1] );
1159                 for ( j = 0 ; j < 3 ; j++ )
1160                 {   // avoid round off error when possible
1161                         if ( split->normal[j] == 1 ) {
1162                                 mid[j] = split->dist;
1163                         }
1164                         else if ( split->normal[j] == -1 ) {
1165                                 mid[j] = -split->dist;
1166                         }
1167                         else{
1168                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
1169                         }
1170                 }
1171
1172                 VectorCopy( mid, neww->points[neww->numpoints] );
1173                 neww->numpoints++;
1174         }
1175
1176         return neww;
1177 }
1178
1179 /*
1180    ===============
1181    AddSeperators
1182    ===============
1183  */
1184 int AddSeperators( fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators ){
1185         int i, j, k, l;
1186         visPlane_t plane;
1187         vec3_t v1, v2;
1188         float d;
1189         vec_t length;
1190         int counts[3], numseperators;
1191         qboolean fliptest;
1192
1193         numseperators = 0;
1194         // check all combinations
1195         for ( i = 0 ; i < source->numpoints ; i++ )
1196         {
1197                 l = ( i + 1 ) % source->numpoints;
1198                 VectorSubtract( source->points[l], source->points[i], v1 );
1199
1200                 // find a vertex of pass that makes a plane that puts all of the
1201                 // vertexes of pass on the front side and all of the vertexes of
1202                 // source on the back side
1203                 for ( j = 0 ; j < pass->numpoints ; j++ )
1204                 {
1205                         VectorSubtract( pass->points[j], source->points[i], v2 );
1206
1207                         plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
1208                         plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
1209                         plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
1210
1211                         // if points don't make a valid plane, skip it
1212
1213                         length = plane.normal[0] * plane.normal[0]
1214                                          + plane.normal[1] * plane.normal[1]
1215                                          + plane.normal[2] * plane.normal[2];
1216
1217                         if ( length < ON_EPSILON ) {
1218                                 continue;
1219                         }
1220
1221                         length = 1 / sqrt( length );
1222
1223                         plane.normal[0] *= length;
1224                         plane.normal[1] *= length;
1225                         plane.normal[2] *= length;
1226
1227                         plane.dist = DotProduct( pass->points[j], plane.normal );
1228
1229                         //
1230                         // find out which side of the generated seperating plane has the
1231                         // source portal
1232                         //
1233 #if 1
1234                         fliptest = qfalse;
1235                         for ( k = 0 ; k < source->numpoints ; k++ )
1236                         {
1237                                 if ( k == i || k == l ) {
1238                                         continue;
1239                                 }
1240                                 d = DotProduct( source->points[k], plane.normal ) - plane.dist;
1241                                 if ( d < -ON_EPSILON ) { // source is on the negative side, so we want all
1242                                                             // pass and target on the positive side
1243                                         fliptest = qfalse;
1244                                         break;
1245                                 }
1246                                 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
1247                                                                 // pass and target on the negative side
1248                                         fliptest = qtrue;
1249                                         break;
1250                                 }
1251                         }
1252                         if ( k == source->numpoints ) {
1253                                 continue;       // planar with source portal
1254                         }
1255 #else
1256                         fliptest = flipclip;
1257 #endif
1258                         //
1259                         // flip the normal if the source portal is backwards
1260                         //
1261                         if ( fliptest ) {
1262                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1263                                 plane.dist = -plane.dist;
1264                         }
1265 #if 1
1266                         //
1267                         // if all of the pass portal points are now on the positive side,
1268                         // this is the seperating plane
1269                         //
1270                         counts[0] = counts[1] = counts[2] = 0;
1271                         for ( k = 0 ; k < pass->numpoints ; k++ )
1272                         {
1273                                 if ( k == j ) {
1274                                         continue;
1275                                 }
1276                                 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1277                                 if ( d < -ON_EPSILON ) {
1278                                         break;
1279                                 }
1280                                 else if ( d > ON_EPSILON ) {
1281                                         counts[0]++;
1282                                 }
1283                                 else{
1284                                         counts[2]++;
1285                                 }
1286                         }
1287                         if ( k != pass->numpoints ) {
1288                                 continue;   // points on negative side, not a seperating plane
1289
1290                         }
1291                         if ( !counts[0] ) {
1292                                 continue;   // planar with seperating plane
1293                         }
1294 #else
1295                         k = ( j + 1 ) % pass->numpoints;
1296                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1297                         if ( d < -ON_EPSILON ) {
1298                                 continue;
1299                         }
1300                         k = ( j + pass->numpoints - 1 ) % pass->numpoints;
1301                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1302                         if ( d < -ON_EPSILON ) {
1303                                 continue;
1304                         }
1305 #endif
1306                         //
1307                         // flip the normal if we want the back side
1308                         //
1309                         if ( flipclip ) {
1310                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1311                                 plane.dist = -plane.dist;
1312                         }
1313
1314                         if ( numseperators >= maxseperators ) {
1315                                 Error( "max seperators" );
1316                         }
1317                         seperators[numseperators] = plane;
1318                         numseperators++;
1319                         break;
1320                 }
1321         }
1322         return numseperators;
1323 }
1324
1325 /*
1326    ===============
1327    CreatePassages
1328
1329    MrE: create passages from one portal to all the portals in the leaf the portal leads to
1330      every passage has a cansee bit string with all the portals that can be
1331      seen through the passage
1332    ===============
1333  */
1334 void CreatePassages( int portalnum ){
1335         int i, j, k, n, numseperators, numsee;
1336         float d;
1337         vportal_t       *portal, *p, *target;
1338         leaf_t          *leaf;
1339         passage_t       *passage, *lastpassage;
1340         visPlane_t seperators[MAX_SEPERATORS * 2];
1341         fixedWinding_t  *w;
1342         fixedWinding_t in, out, *res;
1343
1344
1345 #ifdef MREDEBUG
1346         Sys_Printf( "\r%6d", portalnum );
1347 #endif
1348
1349         portal = sorted_portals[portalnum];
1350
1351         if ( portal->removed ) {
1352                 portal->status = stat_done;
1353                 return;
1354         }
1355
1356         lastpassage = NULL;
1357         leaf = &leafs[portal->leaf];
1358         for ( i = 0; i < leaf->numportals; i++ )
1359         {
1360                 target = leaf->portals[i];
1361                 if ( target->removed ) {
1362                         continue;
1363                 }
1364
1365                 passage = (passage_t *) safe_malloc0( sizeof( passage_t ) + portalbytes );
1366                 numseperators = AddSeperators( portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS * 2 );
1367                 numseperators += AddSeperators( target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS * 2 - numseperators );
1368
1369                 passage->next = NULL;
1370                 if ( lastpassage ) {
1371                         lastpassage->next = passage;
1372                 }
1373                 else{
1374                         portal->passages = passage;
1375                 }
1376                 lastpassage = passage;
1377
1378                 numsee = 0;
1379                 //create the passage->cansee
1380                 for ( j = 0; j < numportals * 2; j++ )
1381                 {
1382                         p = &portals[j];
1383                         if ( p->removed ) {
1384                                 continue;
1385                         }
1386                         if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1387                                 continue;
1388                         }
1389                         if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1390                                 continue;
1391                         }
1392                         for ( k = 0; k < numseperators; k++ )
1393                         {
1394                                 //
1395                                 d = DotProduct( p->origin, seperators[k].normal ) - seperators[k].dist;
1396                                 //if completely at the back of the seperator plane
1397                                 if ( d < -p->radius + ON_EPSILON ) {
1398                                         break;
1399                                 }
1400                                 w = p->winding;
1401                                 for ( n = 0; n < w->numpoints; n++ )
1402                                 {
1403                                         d = DotProduct( w->points[n], seperators[k].normal ) - seperators[k].dist;
1404                                         //if at the front of the seperator
1405                                         if ( d > ON_EPSILON ) {
1406                                                 break;
1407                                         }
1408                                 }
1409                                 //if no points are at the front of the seperator
1410                                 if ( n >= w->numpoints ) {
1411                                         break;
1412                                 }
1413                         }
1414                         if ( k < numseperators ) {
1415                                 continue;
1416                         }
1417
1418                         /* explitive deleted */
1419
1420
1421                         /* ydnar: prefer correctness to stack overflow  */
1422                         //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1423                         if ( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) {
1424                                 memcpy( &in, p->winding, (size_t) &( ( (fixedWinding_t*) 0 )->points[ p->winding->numpoints ] ) );
1425                         }
1426                         else{
1427                                 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1428                         }
1429
1430
1431                         for ( k = 0; k < numseperators; k++ )
1432                         {
1433                                 /* ydnar: this is a shitty crutch */
1434                                 if ( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) {
1435                                         //% Sys_Printf( "[%d]", p->winding->numpoints );
1436                                         in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1437                                 }
1438
1439                                 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1440                                 if ( res == &out ) {
1441                                         memcpy( &in, &out, sizeof( fixedWinding_t ) );
1442                                 }
1443
1444
1445                                 if ( res == NULL ) {
1446                                         break;
1447                                 }
1448                         }
1449                         if ( k < numseperators ) {
1450                                 continue;
1451                         }
1452                         passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) );
1453                         numsee++;
1454                 }
1455         }
1456 }
1457
1458 void PassageMemory( void ){
1459         int i, j, totalmem, totalportals;
1460         vportal_t *portal, *target;
1461         leaf_t *leaf;
1462
1463         totalmem = 0;
1464         totalportals = 0;
1465         for ( i = 0; i < numportals; i++ )
1466         {
1467                 portal = sorted_portals[i];
1468                 if ( portal->removed ) {
1469                         continue;
1470                 }
1471                 leaf = &leafs[portal->leaf];
1472                 for ( j = 0; j < leaf->numportals; j++ )
1473                 {
1474                         target = leaf->portals[j];
1475                         if ( target->removed ) {
1476                                 continue;
1477                         }
1478                         totalmem += sizeof( passage_t ) + portalbytes;
1479                         totalportals++;
1480                 }
1481         }
1482         Sys_Printf( "%7i average number of passages per leaf\n", totalportals / numportals );
1483         Sys_Printf( "%7i MB required passage memory\n", totalmem >> 10 >> 10 );
1484 }
1485
1486 /*
1487    ===============================================================================
1488
1489    This is a rough first-order aproximation that is used to trivially reject some
1490    of the final calculations.
1491
1492
1493    Calculates portalfront and portalflood bit vectors
1494
1495    thinking about:
1496
1497    typedef struct passage_s
1498    {
1499     struct passage_s    *next;
1500     struct portal_s             *to;
1501     stryct sep_s                *seperators;
1502     byte                                *mightsee;
1503    } passage_t;
1504
1505    typedef struct portal_s
1506    {
1507     struct passage_s    *passages;
1508     int                                 leaf;           // leaf portal faces into
1509    } portal_s;
1510
1511    leaf = portal->leaf
1512    clear
1513    for all portals
1514
1515
1516    calc portal visibility
1517     clear bit vector
1518     for all passages
1519         passage visibility
1520
1521
1522    for a portal to be visible to a passage, it must be on the front of
1523    all seperating planes, and both portals must be behind the new portal
1524
1525    ===============================================================================
1526  */
1527
1528 int c_flood, c_vis;
1529
1530
1531 /*
1532    ==================
1533    SimpleFlood
1534
1535    ==================
1536  */
1537 void SimpleFlood( vportal_t *srcportal, int leafnum ){
1538         int i;
1539         leaf_t  *leaf;
1540         vportal_t   *p;
1541         int pnum;
1542
1543         leaf = &leafs[leafnum];
1544
1545         for ( i = 0 ; i < leaf->numportals ; i++ )
1546         {
1547                 p = leaf->portals[i];
1548                 if ( p->removed ) {
1549                         continue;
1550                 }
1551                 pnum = p - portals;
1552                 if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1553                         continue;
1554                 }
1555
1556                 if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) {
1557                         continue;
1558                 }
1559
1560                 srcportal->portalflood[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1561
1562                 SimpleFlood( srcportal, p->leaf );
1563         }
1564 }
1565
1566 /*
1567    ==============
1568    BasePortalVis
1569    ==============
1570  */
1571 void BasePortalVis( int portalnum ){
1572         int j, k;
1573         vportal_t   *tp, *p;
1574         float d;
1575         fixedWinding_t  *w;
1576         vec3_t dir;
1577
1578
1579         p = portals + portalnum;
1580
1581         if ( p->removed ) {
1582                 return;
1583         }
1584
1585         p->portalfront = safe_malloc0( portalbytes );
1586
1587         p->portalflood = safe_malloc0( portalbytes );
1588
1589         p->portalvis = safe_malloc0( portalbytes );
1590
1591         for ( j = 0, tp = portals ; j < numportals * 2 ; j++, tp++ )
1592         {
1593                 if ( j == portalnum ) {
1594                         continue;
1595                 }
1596                 if ( tp->removed ) {
1597                         continue;
1598                 }
1599
1600                 /* ydnar: this is old farplane vis code from mre */
1601                 /*
1602                    if (farplanedist >= 0)
1603                    {
1604                     vec3_t dir;
1605                     VectorSubtract(p->origin, tp->origin, dir);
1606                     if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1607                         continue;
1608                    }
1609                  */
1610
1611                 if( !p->sky && !tp->sky && farPlaneDist != 0.0f && farPlaneDistMode == 'o' )
1612                 {
1613                         VectorSubtract( p->origin, tp->origin, dir );
1614                         if( VectorLength( dir ) > farPlaneDist )
1615                                 continue;
1616                 }
1617
1618                 if( !p->sky && !tp->sky && farPlaneDist != 0.0f && farPlaneDistMode == 'e' )
1619                 {
1620                         VectorSubtract( p->origin, tp->origin, dir );
1621                         if( VectorLength( dir ) + p->radius + tp->radius > 2.0f * farPlaneDist )
1622                                 continue;
1623                 }
1624
1625                 if( !p->sky && !tp->sky && farPlaneDist != 0.0f && farPlaneDistMode == 'r' )
1626                 {
1627                         if( p->radius + tp->radius > farPlaneDist )
1628                                 continue;
1629                 }
1630
1631                 /* ydnar: this is known-to-be-working farplane code */
1632                 if ( !p->sky && !tp->sky && farPlaneDist != 0.0f ) {
1633                         VectorSubtract( p->origin, tp->origin, dir );
1634                         if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) {
1635                                 continue;
1636                         }
1637                 }
1638
1639
1640                 w = tp->winding;
1641                 for ( k = 0 ; k < w->numpoints ; k++ )
1642                 {
1643                         d = DotProduct( w->points[k], p->plane.normal )
1644                                 - p->plane.dist;
1645                         if ( d > ON_EPSILON ) {
1646                                 break;
1647                         }
1648                 }
1649                 if ( k == w->numpoints ) {
1650                         continue;   // no points on front
1651
1652                 }
1653                 w = p->winding;
1654                 for ( k = 0 ; k < w->numpoints ; k++ )
1655                 {
1656                         d = DotProduct( w->points[k], tp->plane.normal )
1657                                 - tp->plane.dist;
1658                         if ( d < -ON_EPSILON ) {
1659                                 break;
1660                         }
1661                 }
1662                 if ( k == w->numpoints ) {
1663                         continue;   // no points on front
1664
1665                 }
1666                 p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) );
1667         }
1668
1669         SimpleFlood( p, p->leaf );
1670
1671         p->nummightsee = CountBits( p->portalflood, numportals * 2 );
1672 //      Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1673         c_flood += p->nummightsee;
1674 }
1675
1676
1677
1678
1679
1680 /*
1681    ===============================================================================
1682
1683    This is a second order aproximation
1684
1685    Calculates portalvis bit vector
1686
1687    WAAAAAAY too slow.
1688
1689    ===============================================================================
1690  */
1691
1692 /*
1693    ==================
1694    RecursiveLeafBitFlow
1695
1696    ==================
1697  */
1698 void RecursiveLeafBitFlow( int leafnum, byte *mightsee, byte *cansee ){
1699         vportal_t   *p;
1700         leaf_t      *leaf;
1701         int i, j;
1702         long more;
1703         int pnum;
1704         byte newmight[MAX_PORTALS / 8];
1705
1706         leaf = &leafs[leafnum];
1707
1708         // check all portals for flowing into other leafs
1709         for ( i = 0 ; i < leaf->numportals ; i++ )
1710         {
1711                 p = leaf->portals[i];
1712                 if ( p->removed ) {
1713                         continue;
1714                 }
1715                 pnum = p - portals;
1716
1717                 // if some previous portal can't see it, skip
1718                 if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1719                         continue;
1720                 }
1721
1722                 // if this portal can see some portals we mightsee, recurse
1723                 more = 0;
1724                 for ( j = 0 ; j < portallongs ; j++ )
1725                 {
1726                         ( (long *)newmight )[j] = ( (long *)mightsee )[j]
1727                                                                           & ( (long *)p->portalflood )[j];
1728                         more |= ( (long *)newmight )[j] & ~( (long *)cansee )[j];
1729                 }
1730
1731                 if ( !more ) {
1732                         continue;   // can't see anything new
1733
1734                 }
1735                 cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1736
1737                 RecursiveLeafBitFlow( p->leaf, newmight, cansee );
1738         }
1739 }
1740
1741 /*
1742    ==============
1743    BetterPortalVis
1744    ==============
1745  */
1746 void BetterPortalVis( int portalnum ){
1747         vportal_t   *p;
1748
1749         p = portals + portalnum;
1750
1751         if ( p->removed ) {
1752                 return;
1753         }
1754
1755         RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis );
1756
1757         // build leaf vis information
1758         p->nummightsee = CountBits( p->portalvis, numportals * 2 );
1759         c_vis += p->nummightsee;
1760 }