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