tools/quake3/q3map2/visflow.c

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