tools/quake2/q2map/flow.c

   1 /*\r
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 */\r
  21 #include "qvis.h"\r
  22 \r
  23 /*\r
  24 \r
  25   each portal will have a list of all possible to see from first portal\r
  26 \r
  27   if (!thread->portalmightsee[portalnum])\r
  28 \r
  29   portal mightsee\r
  30 \r
  31   for p2 = all other portals in leaf\r
  32         get sperating planes\r
  33         for all portals that might be seen by p2\r
  34                 mark as unseen if not present in seperating plane\r
  35         flood fill a new mightsee\r
  36         save as passagemightsee\r
  37 \r
  38 \r
  39   void CalcMightSee (leaf_t *leaf, \r
  40 */\r
  41 \r
  42 int CountBits (byte *bits, int numbits)\r
  43 {\r
  44         int             i;\r
  45         int             c;\r
  46 \r
  47         c = 0;\r
  48         for (i=0 ; i<numbits ; i++)\r
  49                 if (bits[i>>3] & (1<<(i&7)) )\r
  50                         c++;\r
  51 \r
  52         return c;\r
  53 }\r
  54 \r
  55 int             c_fullskip;\r
  56 int             c_portalskip, c_leafskip;\r
  57 int             c_vistest, c_mighttest;\r
  58 \r
  59 int             c_chop, c_nochop;\r
  60 \r
  61 int             active;\r
  62 \r
  63 void CheckStack (leaf_t *leaf, threaddata_t *thread)\r
  64 {\r
  65         pstack_t        *p, *p2;\r
  66 \r
  67         for (p=thread->pstack_head.next ; p ; p=p->next)\r
  68         {\r
  69 //              printf ("=");\r
  70                 if (p->leaf == leaf)\r
  71                         Error ("CheckStack: leaf recursion");\r
  72                 for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)\r
  73                         if (p2->leaf == p->leaf)\r
  74                                 Error ("CheckStack: late leaf recursion");\r
  75         }\r
  76 //      printf ("\n");\r
  77 }\r
  78 \r
  79 \r
  80 winding_t *AllocStackWinding (pstack_t *stack)\r
  81 {\r
  82         int             i;\r
  83 \r
  84         for (i=0 ; i<3 ; i++)\r
  85         {\r
  86                 if (stack->freewindings[i])\r
  87                 {\r
  88                         stack->freewindings[i] = 0;\r
  89                         return &stack->windings[i];\r
  90                 }\r
  91         }\r
  92 \r
  93         Error ("AllocStackWinding: failed");\r
  94 \r
  95         return NULL;\r
  96 }\r
  97 \r
  98 void FreeStackWinding (winding_t *w, pstack_t *stack)\r
  99 {\r
 100         int             i;\r
 101 \r
 102         i = w - stack->windings;\r
 103 \r
 104         if (i<0 || i>2)\r
 105                 return;         // not from local\r
 106 \r
 107         if (stack->freewindings[i])\r
 108                 Error ("FreeStackWinding: allready free");\r
 109         stack->freewindings[i] = 1;\r
 110 }\r
 111 \r
 112 /*\r
 113 ==============\r
 114 Vis_ChopWinding\r
 115 \r
 116 ==============\r
 117 */\r
 118 winding_t       *Vis_ChopWinding (winding_t *in, pstack_t *stack, plane_t *split)\r
 119 {\r
 120         vec_t   dists[128];\r
 121         int             sides[128];\r
 122         int             counts[3];\r
 123         vec_t   dot;\r
 124         int             i, j;\r
 125         vec_t   *p1, *p2;\r
 126         vec3_t  mid;\r
 127         winding_t       *neww;\r
 128 \r
 129         counts[0] = counts[1] = counts[2] = 0;\r
 130 \r
 131 // determine sides for each point\r
 132         for (i=0 ; i<in->numpoints ; i++)\r
 133         {\r
 134                 dot = DotProduct (in->points[i], split->normal);\r
 135                 dot -= split->dist;\r
 136                 dists[i] = dot;\r
 137                 if (dot > ON_EPSILON)\r
 138                         sides[i] = SIDE_FRONT;\r
 139                 else if (dot < -ON_EPSILON)\r
 140                         sides[i] = SIDE_BACK;\r
 141                 else\r
 142                 {\r
 143                         sides[i] = SIDE_ON;\r
 144                 }\r
 145                 counts[sides[i]]++;\r
 146         }\r
 147 \r
 148         if (!counts[1])\r
 149                 return in;              // completely on front side\r
 150         \r
 151         if (!counts[0])\r
 152         {\r
 153                 FreeStackWinding (in, stack);\r
 154                 return NULL;\r
 155         }\r
 156 \r
 157         sides[i] = sides[0];\r
 158         dists[i] = dists[0];\r
 159         \r
 160         neww = AllocStackWinding (stack);\r
 161 \r
 162         neww->numpoints = 0;\r
 163 \r
 164         for (i=0 ; i<in->numpoints ; i++)\r
 165         {\r
 166                 p1 = in->points[i];\r
 167 \r
 168                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
 169                 {\r
 170                         FreeStackWinding (neww, stack);\r
 171                         return in;              // can't chop -- fall back to original\r
 172                 }\r
 173 \r
 174                 if (sides[i] == SIDE_ON)\r
 175                 {\r
 176                         VectorCopy (p1, neww->points[neww->numpoints]);\r
 177                         neww->numpoints++;\r
 178                         continue;\r
 179                 }\r
 180         \r
 181                 if (sides[i] == SIDE_FRONT)\r
 182                 {\r
 183                         VectorCopy (p1, neww->points[neww->numpoints]);\r
 184                         neww->numpoints++;\r
 185                 }\r
 186                 \r
 187                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
 188                         continue;\r
 189                         \r
 190                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
 191                 {\r
 192                         FreeStackWinding (neww, stack);\r
 193                         return in;              // can't chop -- fall back to original\r
 194                 }\r
 195 \r
 196         // generate a split point\r
 197                 p2 = in->points[(i+1)%in->numpoints];\r
 198                 \r
 199                 dot = dists[i] / (dists[i]-dists[i+1]);\r
 200                 for (j=0 ; j<3 ; j++)\r
 201                 {       // avoid round off error when possible\r
 202                         if (split->normal[j] == 1)\r
 203                                 mid[j] = split->dist;\r
 204                         else if (split->normal[j] == -1)\r
 205                                 mid[j] = -split->dist;\r
 206                         else\r
 207                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
 208                 }\r
 209                         \r
 210                 VectorCopy (mid, neww->points[neww->numpoints]);\r
 211                 neww->numpoints++;\r
 212         }\r
 213         \r
 214 // free the original winding\r
 215         FreeStackWinding (in, stack);\r
 216         \r
 217         return neww;\r
 218 }\r
 219 \r
 220 \r
 221 /*\r
 222 ==============\r
 223 ClipToSeperators\r
 224 \r
 225 Source, pass, and target are an ordering of portals.\r
 226 \r
 227 Generates seperating planes canidates by taking two points from source and one\r
 228 point from pass, and clips target by them.\r
 229 \r
 230 If target is totally clipped away, that portal can not be seen through.\r
 231 \r
 232 Normal clip keeps target on the same side as pass, which is correct if the\r
 233 order goes source, pass, target.  If the order goes pass, source, target then\r
 234 flipclip should be set.\r
 235 ==============\r
 236 */\r
 237 winding_t       *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)\r
 238 {\r
 239         int                     i, j, k, l;\r
 240         plane_t         plane;\r
 241         vec3_t          v1, v2;\r
 242         float           d;\r
 243         vec_t           length;\r
 244         int                     counts[3];\r
 245         qboolean                fliptest;\r
 246 \r
 247 // check all combinations       \r
 248         for (i=0 ; i<source->numpoints ; i++)\r
 249         {\r
 250                 l = (i+1)%source->numpoints;\r
 251                 VectorSubtract (source->points[l] , source->points[i], v1);\r
 252 \r
 253         // fing a vertex of pass that makes a plane that puts all of the\r
 254         // vertexes of pass on the front side and all of the vertexes of\r
 255         // source on the back side\r
 256                 for (j=0 ; j<pass->numpoints ; j++)\r
 257                 {\r
 258                         VectorSubtract (pass->points[j], source->points[i], v2);\r
 259 \r
 260                         plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];\r
 261                         plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];\r
 262                         plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];\r
 263                         \r
 264                 // if points don't make a valid plane, skip it\r
 265 \r
 266                         length = plane.normal[0] * plane.normal[0]\r
 267                         + plane.normal[1] * plane.normal[1]\r
 268                         + plane.normal[2] * plane.normal[2];\r
 269                         \r
 270                         if (length < ON_EPSILON)\r
 271                                 continue;\r
 272 \r
 273                         length = 1/sqrt(length);\r
 274                         \r
 275                         plane.normal[0] *= length;\r
 276                         plane.normal[1] *= length;\r
 277                         plane.normal[2] *= length;\r
 278 \r
 279                         plane.dist = DotProduct (pass->points[j], plane.normal);\r
 280 \r
 281                 //\r
 282                 // find out which side of the generated seperating plane has the\r
 283                 // source portal\r
 284                 //\r
 285 #if 1\r
 286                         fliptest = false;\r
 287                         for (k=0 ; k<source->numpoints ; k++)\r
 288                         {\r
 289                                 if (k == i || k == l)\r
 290                                         continue;\r
 291                                 d = DotProduct (source->points[k], plane.normal) - plane.dist;\r
 292                                 if (d < -ON_EPSILON)\r
 293                                 {       // source is on the negative side, so we want all\r
 294                                         // pass and target on the positive side\r
 295                                         fliptest = false;\r
 296                                         break;\r
 297                                 }\r
 298                                 else if (d > ON_EPSILON)\r
 299                                 {       // source is on the positive side, so we want all\r
 300                                         // pass and target on the negative side\r
 301                                         fliptest = true;\r
 302                                         break;\r
 303                                 }\r
 304                         }\r
 305                         if (k == source->numpoints)\r
 306                                 continue;               // planar with source portal\r
 307 #else\r
 308                         fliptest = flipclip;\r
 309 #endif\r
 310                 //\r
 311                 // flip the normal if the source portal is backwards\r
 312                 //\r
 313                         if (fliptest)\r
 314                         {\r
 315                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
 316                                 plane.dist = -plane.dist;\r
 317                         }\r
 318 #if 1\r
 319                 //\r
 320                 // if all of the pass portal points are now on the positive side,\r
 321                 // this is the seperating plane\r
 322                 //\r
 323                         counts[0] = counts[1] = counts[2] = 0;\r
 324                         for (k=0 ; k<pass->numpoints ; k++)\r
 325                         {\r
 326                                 if (k==j)\r
 327                                         continue;\r
 328                                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
 329                                 if (d < -ON_EPSILON)\r
 330                                         break;\r
 331                                 else if (d > ON_EPSILON)\r
 332                                         counts[0]++;\r
 333                                 else\r
 334                                         counts[2]++;\r
 335                         }\r
 336                         if (k != pass->numpoints)\r
 337                                 continue;       // points on negative side, not a seperating plane\r
 338                                 \r
 339                         if (!counts[0])\r
 340                                 continue;       // planar with seperating plane\r
 341 #else\r
 342                         k = (j+1)%pass->numpoints;\r
 343                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
 344                         if (d < -ON_EPSILON)\r
 345                                 continue;\r
 346                         k = (j+pass->numpoints-1)%pass->numpoints;\r
 347                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
 348                         if (d < -ON_EPSILON)\r
 349                                 continue;                       \r
 350 #endif\r
 351                 //\r
 352                 // flip the normal if we want the back side\r
 353                 //\r
 354                         if (flipclip)\r
 355                         {\r
 356                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
 357                                 plane.dist = -plane.dist;\r
 358                         }\r
 359                         \r
 360                 //\r
 361                 // clip target by the seperating plane\r
 362                 //\r
 363                         target = Vis_ChopWinding (target, stack, &plane);\r
 364                         if (!target)\r
 365                                 return NULL;            // target is not visible\r
 366                 }\r
 367         }\r
 368         \r
 369         return target;\r
 370 }\r
 371 \r
 372 \r
 373 \r
 374 /*\r
 375 ==================\r
 376 RecursiveLeafFlow\r
 377 \r
 378 Flood fill through the leafs\r
 379 If src_portal is NULL, this is the originating leaf\r
 380 ==================\r
 381 */\r
 382 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)\r
 383 {\r
 384         pstack_t        stack;\r
 385         portal_t        *p;\r
 386         plane_t         backplane;\r
 387         leaf_t          *leaf;\r
 388         int                     i, j;\r
 389         long            *test, *might, *vis, more;\r
 390         int                     pnum;\r
 391 \r
 392         thread->c_chains++;\r
 393 \r
 394         leaf = &leafs[leafnum];\r
 395 //      CheckStack (leaf, thread);\r
 396 \r
 397         prevstack->next = &stack;\r
 398 \r
 399         stack.next = NULL;\r
 400         stack.leaf = leaf;\r
 401         stack.portal = NULL;\r
 402 \r
 403         might = (long *)stack.mightsee;\r
 404         vis = (long *)thread->base->portalvis;\r
 405         \r
 406 // check all portals for flowing into other leafs       \r
 407         for (i=0 ; i<leaf->numportals ; i++)\r
 408         {\r
 409                 p = leaf->portals[i];\r
 410                 pnum = p - portals;\r
 411 \r
 412                 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )\r
 413                 {\r
 414                         continue;       // can't possibly see it\r
 415                 }\r
 416 \r
 417         // if the portal can't see anything we haven't allready seen, skip it\r
 418                 if (p->status == stat_done)\r
 419                 {\r
 420                         test = (long *)p->portalvis;\r
 421                 }\r
 422                 else\r
 423                 {\r
 424                         test = (long *)p->portalflood;\r
 425                 }\r
 426 \r
 427                 more = 0;\r
 428                 for (j=0 ; j<portallongs ; j++)\r
 429                 {\r
 430                         might[j] = ((long *)prevstack->mightsee)[j] & test[j];\r
 431                         more |= (might[j] & ~vis[j]);\r
 432                 }\r
 433                 \r
 434                 if (!more && \r
 435                         (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )\r
 436                 {       // can't see anything new\r
 437                         continue;\r
 438                 }\r
 439 \r
 440                 // get plane of portal, point normal into the neighbor leaf\r
 441                 stack.portalplane = p->plane;\r
 442                 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);\r
 443                 backplane.dist = -p->plane.dist;\r
 444                 \r
 445 //              c_portalcheck++;\r
 446                 \r
 447                 stack.portal = p;\r
 448                 stack.next = NULL;\r
 449                 stack.freewindings[0] = 1;\r
 450                 stack.freewindings[1] = 1;\r
 451                 stack.freewindings[2] = 1;\r
 452                 \r
 453 #if 1\r
 454 {\r
 455 float d;\r
 456 \r
 457         d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);\r
 458         d -= thread->pstack_head.portalplane.dist;\r
 459         if (d < -p->radius)\r
 460         {\r
 461                 continue;\r
 462         }\r
 463         else if (d > p->radius)\r
 464         {\r
 465                 stack.pass = p->winding;\r
 466         }\r
 467         else    \r
 468         {\r
 469                 stack.pass = Vis_ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
 470                 if (!stack.pass)\r
 471                         continue;\r
 472         }\r
 473 }\r
 474 #else\r
 475                 stack.pass = Vis_ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
 476                 if (!stack.pass)\r
 477                         continue;\r
 478 #endif\r
 479 \r
 480         \r
 481 #if 1\r
 482 {\r
 483 float d;\r
 484 \r
 485         d = DotProduct (thread->base->origin, p->plane.normal);\r
 486         d -= p->plane.dist;\r
 487         if (d > p->radius)\r
 488         {\r
 489                 continue;\r
 490         }\r
 491         else if (d < -p->radius)\r
 492         {\r
 493                 stack.source = prevstack->source;\r
 494         }\r
 495         else    \r
 496         {\r
 497                 stack.source = Vis_ChopWinding (prevstack->source, &stack, &backplane);\r
 498                 if (!stack.source)\r
 499                         continue;\r
 500         }\r
 501 }\r
 502 #else\r
 503                 stack.source = Vis_ChopWinding (prevstack->source, &stack, &backplane);\r
 504                 if (!stack.source)\r
 505                         continue;\r
 506 #endif\r
 507 \r
 508                 if (!prevstack->pass)\r
 509                 {       // the second leaf can only be blocked if coplanar\r
 510 \r
 511                         // mark the portal as visible\r
 512                         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
 513 \r
 514                         RecursiveLeafFlow (p->leaf, thread, &stack);\r
 515                         continue;\r
 516                 }\r
 517 \r
 518                 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);\r
 519                 if (!stack.pass)\r
 520                         continue;\r
 521                 \r
 522                 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);\r
 523                 if (!stack.pass)\r
 524                         continue;\r
 525 \r
 526                 // mark the portal as visible\r
 527                 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
 528 \r
 529                 // flow through it for real\r
 530                 RecursiveLeafFlow (p->leaf, thread, &stack);\r
 531         }       \r
 532 }\r
 533 \r
 534 \r
 535 /*\r
 536 ===============\r
 537 PortalFlow\r
 538 \r
 539 generates the portalvis bit vector\r
 540 ===============\r
 541 */\r
 542 void PortalFlow (int portalnum)\r
 543 {\r
 544         threaddata_t    data;\r
 545         int                             i;\r
 546         portal_t                *p;\r
 547         int                             c_might, c_can;\r
 548 \r
 549         p = sorted_portals[portalnum];\r
 550         p->status = stat_working;\r
 551 \r
 552         c_might = CountBits (p->portalflood, numportals*2);\r
 553 \r
 554         memset (&data, 0, sizeof(data));\r
 555         data.base = p;\r
 556         \r
 557         data.pstack_head.portal = p;\r
 558         data.pstack_head.source = p->winding;\r
 559         data.pstack_head.portalplane = p->plane;\r
 560         for (i=0 ; i<portallongs ; i++)\r
 561                 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];\r
 562         RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);\r
 563 \r
 564         p->status = stat_done;\r
 565 \r
 566         c_can = CountBits (p->portalvis, numportals*2);\r
 567 \r
 568         Sys_FPrintf ( SYS_VRB, "portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", \r
 569                 (int)(p - portals),     c_might, c_can, data.c_chains);\r
 570 }\r
 571 \r
 572 \r
 573 /*\r
 574 ===============================================================================\r
 575 \r
 576 This is a rough first-order aproximation that is used to trivially reject some\r
 577 of the final calculations.\r
 578 \r
 579 \r
 580 Calculates portalfront and portalflood bit vectors\r
 581 \r
 582 thinking about:\r
 583 \r
 584 typedef struct passage_s\r
 585 {\r
 586         struct passage_s        *next;\r
 587         struct portal_s         *to;\r
 588         stryct sep_s            *seperators;\r
 589         byte                            *mightsee;\r
 590 } passage_t;\r
 591 \r
 592 typedef struct portal_s\r
 593 {\r
 594         struct passage_s        *passages;\r
 595         int                                     leaf;           // leaf portal faces into\r
 596 } portal_s;\r
 597 \r
 598 leaf = portal->leaf\r
 599 clear \r
 600 for all portals\r
 601 \r
 602 \r
 603 calc portal visibility\r
 604         clear bit vector\r
 605         for all passages\r
 606                 passage visibility\r
 607 \r
 608 \r
 609 for a portal to be visible to a passage, it must be on the front of\r
 610 all seperating planes, and both portals must be behind the mew portal\r
 611 \r
 612 ===============================================================================\r
 613 */\r
 614 \r
 615 int             c_flood, c_vis;\r
 616 \r
 617 \r
 618 /*\r
 619 ==================\r
 620 SimpleFlood\r
 621 \r
 622 ==================\r
 623 */\r
 624 void SimpleFlood (portal_t *srcportal, int leafnum)\r
 625 {\r
 626         int             i;\r
 627         leaf_t  *leaf;\r
 628         portal_t        *p;\r
 629         int             pnum;\r
 630 \r
 631         leaf = &leafs[leafnum];\r
 632         \r
 633         for (i=0 ; i<leaf->numportals ; i++)\r
 634         {\r
 635                 p = leaf->portals[i];\r
 636                 pnum = p - portals;\r
 637                 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )\r
 638                         continue;\r
 639 \r
 640                 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )\r
 641                         continue;\r
 642 \r
 643                 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));\r
 644                 \r
 645                 SimpleFlood (srcportal, p->leaf);\r
 646         }\r
 647 }\r
 648 \r
 649 /*\r
 650 ==============\r
 651 BasePortalVis\r
 652 ==============\r
 653 */\r
 654 void BasePortalVis (int portalnum)\r
 655 {\r
 656         int                     j, k;\r
 657         portal_t        *tp, *p;\r
 658         float           d;\r
 659         winding_t       *w;\r
 660 \r
 661         p = portals+portalnum;\r
 662 \r
 663         p->portalfront = malloc (portalbytes);\r
 664         memset (p->portalfront, 0, portalbytes);\r
 665 \r
 666         p->portalflood = malloc (portalbytes);\r
 667         memset (p->portalflood, 0, portalbytes);\r
 668         \r
 669         p->portalvis = malloc (portalbytes);\r
 670         memset (p->portalvis, 0, portalbytes);\r
 671         \r
 672         for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)\r
 673         {\r
 674                 if (j == portalnum)\r
 675                         continue;\r
 676                 w = tp->winding;\r
 677                 for (k=0 ; k<w->numpoints ; k++)\r
 678                 {\r
 679                         d = DotProduct (w->points[k], p->plane.normal)\r
 680                                 - p->plane.dist;\r
 681                         if (d > ON_EPSILON)\r
 682                                 break;\r
 683                 }\r
 684                 if (k == w->numpoints)\r
 685                         continue;       // no points on front\r
 686 \r
 687                 w = p->winding;\r
 688                 for (k=0 ; k<w->numpoints ; k++)\r
 689                 {\r
 690                         d = DotProduct (w->points[k], tp->plane.normal)\r
 691                                 - tp->plane.dist;\r
 692                         if (d < -ON_EPSILON)\r
 693                                 break;\r
 694                 }\r
 695                 if (k == w->numpoints)\r
 696                         continue;       // no points on front\r
 697 \r
 698                 p->portalfront[j>>3] |= (1<<(j&7));\r
 699         }\r
 700         \r
 701         SimpleFlood (p, p->leaf);\r
 702 \r
 703         p->nummightsee = CountBits (p->portalflood, numportals*2);\r
 704 //      printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);\r
 705         c_flood += p->nummightsee;\r
 706 }\r
 707 \r
 708 \r
 709 \r
 710 \r
 711 \r
 712 /*\r
 713 ===============================================================================\r
 714 \r
 715 This is a second order aproximation \r
 716 \r
 717 Calculates portalvis bit vector\r
 718 \r
 719 WAAAAAAY too slow.\r
 720 \r
 721 ===============================================================================\r
 722 */\r
 723 \r
 724 /*\r
 725 ==================\r
 726 RecursiveLeafBitFlow\r
 727 \r
 728 ==================\r
 729 */\r
 730 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)\r
 731 {\r
 732         portal_t        *p;\r
 733         leaf_t          *leaf;\r
 734         int                     i, j;\r
 735         long            more;\r
 736         int                     pnum;\r
 737         byte            newmight[MAX_PORTALS/8];\r
 738 \r
 739         leaf = &leafs[leafnum];\r
 740         \r
 741 // check all portals for flowing into other leafs       \r
 742         for (i=0 ; i<leaf->numportals ; i++)\r
 743         {\r
 744                 p = leaf->portals[i];\r
 745                 pnum = p - portals;\r
 746 \r
 747                 // if some previous portal can't see it, skip\r
 748                 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )\r
 749                         continue;\r
 750 \r
 751                 // if this portal can see some portals we mightsee, recurse\r
 752                 more = 0;\r
 753                 for (j=0 ; j<portallongs ; j++)\r
 754                 {\r
 755                         ((long *)newmight)[j] = ((long *)mightsee)[j] \r
 756                                 & ((long *)p->portalflood)[j];\r
 757                         more |= ((long *)newmight)[j] & ~((long *)cansee)[j];\r
 758                 }\r
 759 \r
 760                 if (!more)\r
 761                         continue;       // can't see anything new\r
 762 \r
 763                 cansee[pnum>>3] |= (1<<(pnum&7));\r
 764 \r
 765                 RecursiveLeafBitFlow (p->leaf, newmight, cansee);\r
 766         }       \r
 767 }\r
 768 \r
 769 /*\r
 770 ==============\r
 771 BetterPortalVis\r
 772 ==============\r
 773 */\r
 774 void BetterPortalVis (int portalnum)\r
 775 {\r
 776         portal_t        *p;\r
 777 \r
 778         p = portals+portalnum;\r
 779 \r
 780         RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);\r
 781 \r
 782         // build leaf vis information\r
 783         p->nummightsee = CountBits (p->portalvis, numportals*2);\r
 784         c_vis += p->nummightsee;\r
 785 }\r
 786 \r
 787 \r