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         p = sorted_portals[portalnum];
 659
 660         if ( p->removed ) {
 661                 p->status = stat_done;
 662                 return;
 663         }
 664
 665         p->status = stat_working;
 666
 667         c_might = CountBits( p->portalflood, numportals * 2 );
 668
 669         memset( &data, 0, sizeof( data ) );
 670         data.base = p;
 671
 672         data.pstack_head.portal = p;
 673         data.pstack_head.source = p->winding;
 674         data.pstack_head.portalplane = p->plane;
 675         data.pstack_head.depth = 0;
 676         for ( i = 0 ; i < portallongs ; i++ )
 677                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
 678
 679         RecursiveLeafFlow( p->leaf, &data, &data.pstack_head );
 680
 681         p->status = stat_done;
 682
 683         c_can = CountBits( p->portalvis, numportals * 2 );
 684
 685         Sys_FPrintf( SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
 686                                  (int)( p - portals ), c_might, c_can, data.c_chains );
 687 }
 688
 689 /*
 690    ==================
 691    RecursivePassageFlow
 692    ==================
 693  */
 694 void RecursivePassageFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
 695         pstack_t stack;
 696         vportal_t   *p;
 697         leaf_t      *leaf;
 698         passage_t   *passage, *nextpassage;
 699         int i, j;
 700         long        *might, *vis, *prevmight, *cansee, *portalvis, more;
 701         int pnum;
 702
 703         leaf = &leafs[portal->leaf];
 704
 705         prevstack->next = &stack;
 706
 707         stack.next = NULL;
 708         stack.depth = prevstack->depth + 1;
 709
 710         vis = (long *)thread->base->portalvis;
 711
 712         passage = portal->passages;
 713         nextpassage = passage;
 714         // check all portals for flowing into other leafs
 715         for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
 716         {
 717                 p = leaf->portals[i];
 718                 if ( p->removed ) {
 719                         continue;
 720                 }
 721                 nextpassage = passage->next;
 722                 pnum = p - portals;
 723
 724                 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
 725                         continue;   // can't possibly see it
 726                 }
 727
 728                 // mark the portal as visible
 729                 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 730
 731                 prevmight = (long *)prevstack->mightsee;
 732                 cansee = (long *)passage->cansee;
 733                 might = (long *)stack.mightsee;
 734                 memcpy( might, prevmight, portalbytes );
 735                 if ( p->status == stat_done ) {
 736                         portalvis = (long *) p->portalvis;
 737                 }
 738                 else{
 739                         portalvis = (long *) p->portalflood;
 740                 }
 741                 more = 0;
 742                 for ( j = 0; j < portallongs; j++ )
 743                 {
 744                         if ( *might ) {
 745                                 *might &= *cansee++ & *portalvis++;
 746                                 more |= ( *might & ~vis[j] );
 747                         }
 748                         else
 749                         {
 750                                 cansee++;
 751                                 portalvis++;
 752                         }
 753                         might++;
 754                 }
 755
 756                 if ( !more ) {
 757                         // can't see anything new
 758                         continue;
 759                 }
 760
 761                 // flow through it for real
 762                 RecursivePassageFlow( p, thread, &stack );
 763
 764                 stack.next = NULL;
 765         }
 766 }
 767
 768 /*
 769    ===============
 770    PassageFlow
 771    ===============
 772  */
 773 void PassageFlow( int portalnum ){
 774         threaddata_t data;
 775         int i;
 776         vportal_t       *p;
 777
 778         p = sorted_portals[portalnum];
 779
 780         if ( p->removed ) {
 781                 p->status = stat_done;
 782                 return;
 783         }
 784
 785         p->status = stat_working;
 786
 787         memset( &data, 0, sizeof( data ) );
 788         data.base = p;
 789
 790         data.pstack_head.portal = p;
 791         data.pstack_head.source = p->winding;
 792         data.pstack_head.portalplane = p->plane;
 793         data.pstack_head.depth = 0;
 794         for ( i = 0 ; i < portallongs ; i++ )
 795                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
 796
 797         RecursivePassageFlow( p, &data, &data.pstack_head );
 798
 799         p->status = stat_done;
 800 }
 801
 802 /*
 803    ==================
 804    RecursivePassagePortalFlow
 805    ==================
 806  */
 807 void RecursivePassagePortalFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
 808         pstack_t stack;
 809         vportal_t   *p;
 810         leaf_t      *leaf;
 811         visPlane_t backplane;
 812         passage_t   *passage, *nextpassage;
 813         int i, j, n;
 814         long        *might, *vis, *prevmight, *cansee, *portalvis, more;
 815         int pnum;
 816
 817 //      thread->c_chains++;
 818
 819         leaf = &leafs[portal->leaf];
 820 //      CheckStack (leaf, thread);
 821
 822         prevstack->next = &stack;
 823
 824         stack.next = NULL;
 825         stack.leaf = leaf;
 826         stack.portal = NULL;
 827         stack.depth = prevstack->depth + 1;
 828
 829 #ifdef SEPERATORCACHE
 830         stack.numseperators[0] = 0;
 831         stack.numseperators[1] = 0;
 832 #endif
 833
 834         vis = (long *)thread->base->portalvis;
 835
 836         passage = portal->passages;
 837         nextpassage = passage;
 838         // check all portals for flowing into other leafs
 839         for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
 840         {
 841                 p = leaf->portals[i];
 842                 if ( p->removed ) {
 843                         continue;
 844                 }
 845                 nextpassage = passage->next;
 846                 pnum = p - portals;
 847
 848                 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
 849                         continue;   // can't possibly see it
 850
 851                 }
 852                 prevmight = (long *)prevstack->mightsee;
 853                 cansee = (long *)passage->cansee;
 854                 might = (long *)stack.mightsee;
 855                 memcpy( might, prevmight, portalbytes );
 856                 if ( p->status == stat_done ) {
 857                         portalvis = (long *) p->portalvis;
 858                 }
 859                 else{
 860                         portalvis = (long *) p->portalflood;
 861                 }
 862                 more = 0;
 863                 for ( j = 0; j < portallongs; j++ )
 864                 {
 865                         if ( *might ) {
 866                                 *might &= *cansee++ & *portalvis++;
 867                                 more |= ( *might & ~vis[j] );
 868                         }
 869                         else
 870                         {
 871                                 cansee++;
 872                                 portalvis++;
 873                         }
 874                         might++;
 875                 }
 876
 877                 if ( !more && ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
 878                         continue;
 879                 }
 880
 881                 // get plane of portal, point normal into the neighbor leaf
 882                 stack.portalplane = p->plane;
 883                 VectorSubtract( vec3_origin, p->plane.normal, backplane.normal );
 884                 backplane.dist = -p->plane.dist;
 885
 886 //              c_portalcheck++;
 887
 888                 stack.portal = p;
 889                 stack.next = NULL;
 890                 stack.freewindings[0] = 1;
 891                 stack.freewindings[1] = 1;
 892                 stack.freewindings[2] = 1;
 893
 894 #if 1
 895                 {
 896                         float d;
 897
 898                         d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
 899                         d -= thread->pstack_head.portalplane.dist;
 900                         if ( d < -p->radius ) {
 901                                 continue;
 902                         }
 903                         else if ( d > p->radius ) {
 904                                 stack.pass = p->winding;
 905                         }
 906                         else
 907                         {
 908                                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 909                                 if ( !stack.pass ) {
 910                                         continue;
 911                                 }
 912                         }
 913                 }
 914 #else
 915                 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
 916                 if ( !stack.pass ) {
 917                         continue;
 918                 }
 919 #endif
 920
 921
 922 #if 1
 923                 {
 924                         float d;
 925
 926                         d = DotProduct( thread->base->origin, p->plane.normal );
 927                         d -= p->plane.dist;
 928                         //MrE: vis-bug fix
 929                         //if (d > p->radius)
 930                         if ( d > thread->base->radius ) {
 931                                 continue;
 932                         }
 933                         //MrE: vis-bug fix
 934                         //if (d < -p->radius)
 935                         else if ( d < -thread->base->radius ) {
 936                                 stack.source = prevstack->source;
 937                         }
 938                         else
 939                         {
 940                                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 941                                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
 942                                 if ( !stack.source ) {
 943                                         continue;
 944                                 }
 945                         }
 946                 }
 947 #else
 948                 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
 949                 if ( !stack.source ) {
 950                         continue;
 951                 }
 952 #endif
 953
 954                 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
 955
 956                         // mark the portal as visible
 957                         thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
 958
 959                         RecursivePassagePortalFlow( p, thread, &stack );
 960                         continue;
 961                 }
 962
 963 #ifdef SEPERATORCACHE
 964                 if ( stack.numseperators[0] ) {
 965                         for ( n = 0; n < stack.numseperators[0]; n++ )
 966                         {
 967                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
 968                                 if ( !stack.pass ) {
 969                                         break;      // target is not visible
 970                                 }
 971                         }
 972                         if ( n < stack.numseperators[0] ) {
 973                                 continue;
 974                         }
 975                 }
 976                 else
 977                 {
 978                         stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
 979                 }
 980 #else
 981                 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
 982 #endif
 983                 if ( !stack.pass ) {
 984                         continue;
 985                 }
 986
 987 #ifdef SEPERATORCACHE
 988                 if ( stack.numseperators[1] ) {
 989                         for ( n = 0; n < stack.numseperators[1]; n++ )
 990                         {
 991                                 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
 992                                 if ( !stack.pass ) {
 993                                         break;      // target is not visible
 994                                 }
 995                         }
 996                 }
 997                 else
 998                 {
 999                         stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
1000                 }
1001 #else
1002                 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
1003 #endif
1004                 if ( !stack.pass ) {
1005                         continue;
1006                 }
1007
1008                 // mark the portal as visible
1009                 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1010
1011                 // flow through it for real
1012                 RecursivePassagePortalFlow( p, thread, &stack );
1013                 //
1014                 stack.next = NULL;
1015         }
1016 }
1017
1018 /*
1019    ===============
1020    PassagePortalFlow
1021    ===============
1022  */
1023 void PassagePortalFlow( int portalnum ){
1024         threaddata_t data;
1025         int i;
1026         vportal_t       *p;
1027
1028
1029         p = sorted_portals[portalnum];
1030
1031         if ( p->removed ) {
1032                 p->status = stat_done;
1033                 return;
1034         }
1035
1036         p->status = stat_working;
1037
1038         memset( &data, 0, sizeof( data ) );
1039         data.base = p;
1040
1041         data.pstack_head.portal = p;
1042         data.pstack_head.source = p->winding;
1043         data.pstack_head.portalplane = p->plane;
1044         data.pstack_head.depth = 0;
1045         for ( i = 0 ; i < portallongs ; i++ )
1046                 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
1047
1048         RecursivePassagePortalFlow( p, &data, &data.pstack_head );
1049
1050         p->status = stat_done;
1051
1052         /*
1053            c_can = CountBits (p->portalvis, numportals*2);
1054
1055            Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
1056             (int)(p - portals), c_might, c_can, data.c_chains);
1057          */
1058 }
1059
1060 fixedWinding_t *PassageChopWinding( fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split ){
1061         vec_t dists[128];
1062         int sides[128];
1063         int counts[3];
1064         vec_t dot;
1065         int i, j;
1066         vec_t   *p1, *p2;
1067         vec3_t mid;
1068         fixedWinding_t  *neww;
1069
1070         counts[0] = counts[1] = counts[2] = 0;
1071
1072         // determine sides for each point
1073         for ( i = 0 ; i < in->numpoints ; i++ )
1074         {
1075                 dot = DotProduct( in->points[i], split->normal );
1076                 dot -= split->dist;
1077                 dists[i] = dot;
1078                 if ( dot > ON_EPSILON ) {
1079                         sides[i] = SIDE_FRONT;
1080                 }
1081                 else if ( dot < -ON_EPSILON ) {
1082                         sides[i] = SIDE_BACK;
1083                 }
1084                 else
1085                 {
1086                         sides[i] = SIDE_ON;
1087                 }
1088                 counts[sides[i]]++;
1089         }
1090
1091         if ( !counts[1] ) {
1092                 return in;      // completely on front side
1093
1094         }
1095         if ( !counts[0] ) {
1096                 return NULL;
1097         }
1098
1099         sides[i] = sides[0];
1100         dists[i] = dists[0];
1101
1102         neww = out;
1103
1104         neww->numpoints = 0;
1105
1106         for ( i = 0 ; i < in->numpoints ; i++ )
1107         {
1108                 p1 = in->points[i];
1109
1110                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1111                         return in;      // can't chop -- fall back to original
1112                 }
1113
1114                 if ( sides[i] == SIDE_ON ) {
1115                         VectorCopy( p1, neww->points[neww->numpoints] );
1116                         neww->numpoints++;
1117                         continue;
1118                 }
1119
1120                 if ( sides[i] == SIDE_FRONT ) {
1121                         VectorCopy( p1, neww->points[neww->numpoints] );
1122                         neww->numpoints++;
1123                 }
1124
1125                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
1126                         continue;
1127                 }
1128
1129                 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1130                         return in;      // can't chop -- fall back to original
1131                 }
1132
1133                 // generate a split point
1134                 p2 = in->points[( i + 1 ) % in->numpoints];
1135
1136                 dot = dists[i] / ( dists[i] - dists[i + 1] );
1137                 for ( j = 0 ; j < 3 ; j++ )
1138                 {   // avoid round off error when possible
1139                         if ( split->normal[j] == 1 ) {
1140                                 mid[j] = split->dist;
1141                         }
1142                         else if ( split->normal[j] == -1 ) {
1143                                 mid[j] = -split->dist;
1144                         }
1145                         else{
1146                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
1147                         }
1148                 }
1149
1150                 VectorCopy( mid, neww->points[neww->numpoints] );
1151                 neww->numpoints++;
1152         }
1153
1154         return neww;
1155 }
1156
1157 /*
1158    ===============
1159    AddSeperators
1160    ===============
1161  */
1162 int AddSeperators( fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators ){
1163         int i, j, k, l;
1164         visPlane_t plane;
1165         vec3_t v1, v2;
1166         float d;
1167         vec_t length;
1168         int counts[3], numseperators;
1169         qboolean fliptest;
1170
1171         numseperators = 0;
1172         // check all combinations
1173         for ( i = 0 ; i < source->numpoints ; i++ )
1174         {
1175                 l = ( i + 1 ) % source->numpoints;
1176                 VectorSubtract( source->points[l], source->points[i], v1 );
1177
1178                 // find a vertex of pass that makes a plane that puts all of the
1179                 // vertexes of pass on the front side and all of the vertexes of
1180                 // source on the back side
1181                 for ( j = 0 ; j < pass->numpoints ; j++ )
1182                 {
1183                         VectorSubtract( pass->points[j], source->points[i], v2 );
1184
1185                         plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
1186                         plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
1187                         plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
1188
1189                         // if points don't make a valid plane, skip it
1190
1191                         length = plane.normal[0] * plane.normal[0]
1192                                          + plane.normal[1] * plane.normal[1]
1193                                          + plane.normal[2] * plane.normal[2];
1194
1195                         if ( length < ON_EPSILON ) {
1196                                 continue;
1197                         }
1198
1199                         length = 1 / sqrt( length );
1200
1201                         plane.normal[0] *= length;
1202                         plane.normal[1] *= length;
1203                         plane.normal[2] *= length;
1204
1205                         plane.dist = DotProduct( pass->points[j], plane.normal );
1206
1207                         //
1208                         // find out which side of the generated seperating plane has the
1209                         // source portal
1210                         //
1211 #if 1
1212                         fliptest = qfalse;
1213                         for ( k = 0 ; k < source->numpoints ; k++ )
1214                         {
1215                                 if ( k == i || k == l ) {
1216                                         continue;
1217                                 }
1218                                 d = DotProduct( source->points[k], plane.normal ) - plane.dist;
1219                                 if ( d < -ON_EPSILON ) { // source is on the negative side, so we want all
1220                                                             // pass and target on the positive side
1221                                         fliptest = qfalse;
1222                                         break;
1223                                 }
1224                                 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
1225                                                                 // pass and target on the negative side
1226                                         fliptest = qtrue;
1227                                         break;
1228                                 }
1229                         }
1230                         if ( k == source->numpoints ) {
1231                                 continue;       // planar with source portal
1232                         }
1233 #else
1234                         fliptest = flipclip;
1235 #endif
1236                         //
1237                         // flip the normal if the source portal is backwards
1238                         //
1239                         if ( fliptest ) {
1240                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1241                                 plane.dist = -plane.dist;
1242                         }
1243 #if 1
1244                         //
1245                         // if all of the pass portal points are now on the positive side,
1246                         // this is the seperating plane
1247                         //
1248                         counts[0] = counts[1] = counts[2] = 0;
1249                         for ( k = 0 ; k < pass->numpoints ; k++ )
1250                         {
1251                                 if ( k == j ) {
1252                                         continue;
1253                                 }
1254                                 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1255                                 if ( d < -ON_EPSILON ) {
1256                                         break;
1257                                 }
1258                                 else if ( d > ON_EPSILON ) {
1259                                         counts[0]++;
1260                                 }
1261                                 else{
1262                                         counts[2]++;
1263                                 }
1264                         }
1265                         if ( k != pass->numpoints ) {
1266                                 continue;   // points on negative side, not a seperating plane
1267
1268                         }
1269                         if ( !counts[0] ) {
1270                                 continue;   // planar with seperating plane
1271                         }
1272 #else
1273                         k = ( j + 1 ) % pass->numpoints;
1274                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1275                         if ( d < -ON_EPSILON ) {
1276                                 continue;
1277                         }
1278                         k = ( j + pass->numpoints - 1 ) % pass->numpoints;
1279                         d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1280                         if ( d < -ON_EPSILON ) {
1281                                 continue;
1282                         }
1283 #endif
1284                         //
1285                         // flip the normal if we want the back side
1286                         //
1287                         if ( flipclip ) {
1288                                 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1289                                 plane.dist = -plane.dist;
1290                         }
1291
1292                         if ( numseperators >= maxseperators ) {
1293                                 Error( "max seperators" );
1294                         }
1295                         seperators[numseperators] = plane;
1296                         numseperators++;
1297                         break;
1298                 }
1299         }
1300         return numseperators;
1301 }
1302
1303 /*
1304    ===============
1305    CreatePassages
1306
1307    MrE: create passages from one portal to all the portals in the leaf the portal leads to
1308      every passage has a cansee bit string with all the portals that can be
1309      seen through the passage
1310    ===============
1311  */
1312 void CreatePassages( int portalnum ){
1313         int i, j, k, n, numseperators, numsee;
1314         float d;
1315         vportal_t       *portal, *p, *target;
1316         leaf_t          *leaf;
1317         passage_t       *passage, *lastpassage;
1318         visPlane_t seperators[MAX_SEPERATORS * 2];
1319         fixedWinding_t  *w;
1320         fixedWinding_t in, out, *res;
1321
1322
1323         portal = sorted_portals[portalnum];
1324
1325         if ( portal->removed ) {
1326                 portal->status = stat_done;
1327                 return;
1328         }
1329
1330         lastpassage = NULL;
1331         leaf = &leafs[portal->leaf];
1332         for ( i = 0; i < leaf->numportals; i++ )
1333         {
1334                 target = leaf->portals[i];
1335                 if ( target->removed ) {
1336                         continue;
1337                 }
1338
1339                 passage = (passage_t *) safe_malloc( sizeof( passage_t ) + portalbytes );
1340                 memset( passage, 0, sizeof( passage_t ) + portalbytes );
1341                 numseperators = AddSeperators( portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS * 2 );
1342                 numseperators += AddSeperators( target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS * 2 - numseperators );
1343
1344                 passage->next = NULL;
1345                 if ( lastpassage ) {
1346                         lastpassage->next = passage;
1347                 }
1348                 else{
1349                         portal->passages = passage;
1350                 }
1351                 lastpassage = passage;
1352
1353                 numsee = 0;
1354                 //create the passage->cansee
1355                 for ( j = 0; j < numportals * 2; j++ )
1356                 {
1357                         p = &portals[j];
1358                         if ( p->removed ) {
1359                                 continue;
1360                         }
1361                         if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1362                                 continue;
1363                         }
1364                         if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1365                                 continue;
1366                         }
1367                         for ( k = 0; k < numseperators; k++ )
1368                         {
1369                                 //
1370                                 d = DotProduct( p->origin, seperators[k].normal ) - seperators[k].dist;
1371                                 //if completely at the back of the seperator plane
1372                                 if ( d < -p->radius + ON_EPSILON ) {
1373                                         break;
1374                                 }
1375                                 w = p->winding;
1376                                 for ( n = 0; n < w->numpoints; n++ )
1377                                 {
1378                                         d = DotProduct( w->points[n], seperators[k].normal ) - seperators[k].dist;
1379                                         //if at the front of the seperator
1380                                         if ( d > ON_EPSILON ) {
1381                                                 break;
1382                                         }
1383                                 }
1384                                 //if no points are at the front of the seperator
1385                                 if ( n >= w->numpoints ) {
1386                                         break;
1387                                 }
1388                         }
1389                         if ( k < numseperators ) {
1390                                 continue;
1391                         }
1392
1393                         /* explitive deleted */
1394
1395
1396                         /* ydnar: prefer correctness to stack overflow  */
1397                         //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1398                         if ( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) {
1399                                 memcpy( &in, p->winding, (size_t) &( ( (fixedWinding_t*) 0 )->points[ p->winding->numpoints ] ) );
1400                         }
1401                         else{
1402                                 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1403                         }
1404
1405
1406                         for ( k = 0; k < numseperators; k++ )
1407                         {
1408                                 /* ydnar: this is a shitty crutch */
1409                                 if ( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) {
1410                                         //% Sys_Printf( "[%d]", p->winding->numpoints );
1411                                         in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1412                                 }
1413
1414                                 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1415                                 if ( res == &out ) {
1416                                         memcpy( &in, &out, sizeof( fixedWinding_t ) );
1417                                 }
1418
1419
1420                                 if ( res == NULL ) {
1421                                         break;
1422                                 }
1423                         }
1424                         if ( k < numseperators ) {
1425                                 continue;
1426                         }
1427                         passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) );
1428                         numsee++;
1429                 }
1430         }
1431 }
1432
1433 void PassageMemory( void ){
1434         int i, j, totalmem, totalportals;
1435         vportal_t *portal, *target;
1436         leaf_t *leaf;
1437
1438         totalmem = 0;
1439         totalportals = 0;
1440         for ( i = 0; i < numportals; i++ )
1441         {
1442                 portal = sorted_portals[i];
1443                 if ( portal->removed ) {
1444                         continue;
1445                 }
1446                 leaf = &leafs[portal->leaf];
1447                 for ( j = 0; j < leaf->numportals; j++ )
1448                 {
1449                         target = leaf->portals[j];
1450                         if ( target->removed ) {
1451                                 continue;
1452                         }
1453                         totalmem += sizeof( passage_t ) + portalbytes;
1454                         totalportals++;
1455                 }
1456         }
1457         Sys_Printf( "%7i average number of passages per leaf\n", totalportals / numportals );
1458         Sys_Printf( "%7i MB required passage memory\n", totalmem >> 10 >> 10 );
1459 }
1460
1461 /*
1462    ===============================================================================
1463
1464    This is a rough first-order aproximation that is used to trivially reject some
1465    of the final calculations.
1466
1467
1468    Calculates portalfront and portalflood bit vectors
1469
1470    thinking about:
1471
1472    typedef struct passage_s
1473    {
1474     struct passage_s    *next;
1475     struct portal_s             *to;
1476     stryct sep_s                *seperators;
1477     byte                                *mightsee;
1478    } passage_t;
1479
1480    typedef struct portal_s
1481    {
1482     struct passage_s    *passages;
1483     int                                 leaf;           // leaf portal faces into
1484    } portal_s;
1485
1486    leaf = portal->leaf
1487    clear
1488    for all portals
1489
1490
1491    calc portal visibility
1492     clear bit vector
1493     for all passages
1494         passage visibility
1495
1496
1497    for a portal to be visible to a passage, it must be on the front of
1498    all seperating planes, and both portals must be behind the new portal
1499
1500    ===============================================================================
1501  */
1502
1503 int c_flood, c_vis;
1504
1505
1506 /*
1507    ==================
1508    SimpleFlood
1509
1510    ==================
1511  */
1512 void SimpleFlood( vportal_t *srcportal, int leafnum ){
1513         int i;
1514         leaf_t  *leaf;
1515         vportal_t   *p;
1516         int pnum;
1517
1518         leaf = &leafs[leafnum];
1519
1520         for ( i = 0 ; i < leaf->numportals ; i++ )
1521         {
1522                 p = leaf->portals[i];
1523                 if ( p->removed ) {
1524                         continue;
1525                 }
1526                 pnum = p - portals;
1527                 if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1528                         continue;
1529                 }
1530
1531                 if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) {
1532                         continue;
1533                 }
1534
1535                 srcportal->portalflood[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1536
1537                 SimpleFlood( srcportal, p->leaf );
1538         }
1539 }
1540
1541 /*
1542    ==============
1543    BasePortalVis
1544    ==============
1545  */
1546 void BasePortalVis( int portalnum ){
1547         int j, k;
1548         vportal_t   *tp, *p;
1549         float d;
1550         fixedWinding_t  *w;
1551         vec3_t dir;
1552
1553
1554         p = portals + portalnum;
1555
1556         if ( p->removed ) {
1557                 return;
1558         }
1559
1560         p->portalfront = safe_malloc( portalbytes );
1561         memset( p->portalfront, 0, portalbytes );
1562
1563         p->portalflood = safe_malloc( portalbytes );
1564         memset( p->portalflood, 0, portalbytes );
1565
1566         p->portalvis = safe_malloc( portalbytes );
1567         memset( p->portalvis, 0, portalbytes );
1568
1569         for ( j = 0, tp = portals ; j < numportals * 2 ; j++, tp++ )
1570         {
1571                 if ( j == portalnum ) {
1572                         continue;
1573                 }
1574                 if ( tp->removed ) {
1575                         continue;
1576                 }
1577
1578                 /* ydnar: this is old farplane vis code from mre */
1579                 /*
1580                    if (farplanedist >= 0)
1581                    {
1582                     vec3_t dir;
1583                     VectorSubtract(p->origin, tp->origin, dir);
1584                     if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1585                         continue;
1586                    }
1587                  */
1588
1589                 /* ydnar: this is known-to-be-working farplane code */
1590                 if ( !p->sky && !tp->sky && farPlaneDist > 0.0f ) {
1591                         VectorSubtract( p->origin, tp->origin, dir );
1592                         if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) {
1593                                 continue;
1594                         }
1595                 }
1596
1597
1598                 w = tp->winding;
1599                 for ( k = 0 ; k < w->numpoints ; k++ )
1600                 {
1601                         d = DotProduct( w->points[k], p->plane.normal )
1602                                 - p->plane.dist;
1603                         if ( d > ON_EPSILON ) {
1604                                 break;
1605                         }
1606                 }
1607                 if ( k == w->numpoints ) {
1608                         continue;   // no points on front
1609
1610                 }
1611                 w = p->winding;
1612                 for ( k = 0 ; k < w->numpoints ; k++ )
1613                 {
1614                         d = DotProduct( w->points[k], tp->plane.normal )
1615                                 - tp->plane.dist;
1616                         if ( d < -ON_EPSILON ) {
1617                                 break;
1618                         }
1619                 }
1620                 if ( k == w->numpoints ) {
1621                         continue;   // no points on front
1622
1623                 }
1624                 p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) );
1625         }
1626
1627         SimpleFlood( p, p->leaf );
1628
1629         p->nummightsee = CountBits( p->portalflood, numportals * 2 );
1630 //      Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1631         c_flood += p->nummightsee;
1632 }
1633
1634
1635
1636
1637
1638 /*
1639    ===============================================================================
1640
1641    This is a second order aproximation
1642
1643    Calculates portalvis bit vector
1644
1645    WAAAAAAY too slow.
1646
1647    ===============================================================================
1648  */
1649
1650 /*
1651    ==================
1652    RecursiveLeafBitFlow
1653
1654    ==================
1655  */
1656 void RecursiveLeafBitFlow( int leafnum, byte *mightsee, byte *cansee ){
1657         vportal_t   *p;
1658         leaf_t      *leaf;
1659         int i, j;
1660         long more;
1661         int pnum;
1662         byte newmight[MAX_PORTALS / 8];
1663
1664         leaf = &leafs[leafnum];
1665
1666         // check all portals for flowing into other leafs
1667         for ( i = 0 ; i < leaf->numportals ; i++ )
1668         {
1669                 p = leaf->portals[i];
1670                 if ( p->removed ) {
1671                         continue;
1672                 }
1673                 pnum = p - portals;
1674
1675                 // if some previous portal can't see it, skip
1676                 if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1677                         continue;
1678                 }
1679
1680                 // if this portal can see some portals we mightsee, recurse
1681                 more = 0;
1682                 for ( j = 0 ; j < portallongs ; j++ )
1683                 {
1684                         ( (long *)newmight )[j] = ( (long *)mightsee )[j]
1685                                                                           & ( (long *)p->portalflood )[j];
1686                         more |= ( (long *)newmight )[j] & ~( (long *)cansee )[j];
1687                 }
1688
1689                 if ( !more ) {
1690                         continue;   // can't see anything new
1691
1692                 }
1693                 cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1694
1695                 RecursiveLeafBitFlow( p->leaf, newmight, cansee );
1696         }
1697 }
1698
1699 /*
1700    ==============
1701    BetterPortalVis
1702    ==============
1703  */
1704 void BetterPortalVis( int portalnum ){
1705         vportal_t   *p;
1706
1707         p = portals + portalnum;
1708
1709         if ( p->removed ) {
1710                 return;
1711         }
1712
1713         RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis );
1714
1715         // build leaf vis information
1716         p->nummightsee = CountBits( p->portalvis, numportals * 2 );
1717         c_vis += p->nummightsee;
1718 }