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