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