tools/quake2/extra/bsp/qvis3/flow.c

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