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                         fliptest = false;
 287                         for (k=0 ; k<source->numpoints ; k++)
 288                         {
 289                                 if (k == i || k == l)
 290                                         continue;
 291                                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
 292                                 if (d < -ON_EPSILON)
 293                                 {       // source is on the negative side, so we want all
 294                                         // pass and target on the positive side
 295                                         fliptest = false;
 296                                         break;
 297                                 }
 298                                 else if (d > ON_EPSILON)
 299                                 {       // source is on the positive side, so we want all
 300                                         // pass and target on the negative side
 301                                         fliptest = true;
 302                                         break;
 303                                 }
 304                         }
 305                         if (k == source->numpoints)
 306                                 continue;               // planar with source portal
 307                 //
 308                 // flip the normal if the source portal is backwards
 309                 //
 310                         if (fliptest)
 311                         {
 312                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
 313                                 plane.dist = -plane.dist;
 314                         }
 315                 //
 316                 // if all of the pass portal points are now on the positive side,
 317                 // this is the seperating plane
 318                 //
 319                         counts[0] = counts[1] = counts[2] = 0;
 320                         for (k=0 ; k<pass->numpoints ; k++)
 321                         {
 322                                 if (k==j)
 323                                         continue;
 324                                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
 325                                 if (d < -ON_EPSILON)
 326                                         break;
 327                                 else if (d > ON_EPSILON)
 328                                         counts[0]++;
 329                                 else
 330                                         counts[2]++;
 331                         }
 332                         if (k != pass->numpoints)
 333                                 continue;       // points on negative side, not a seperating plane
 334
 335                         if (!counts[0])
 336                                 continue;       // planar with seperating plane
 337                 //
 338                 // flip the normal if we want the back side
 339                 //
 340                         if (flipclip)
 341                         {
 342                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
 343                                 plane.dist = -plane.dist;
 344                         }
 345
 346                 //
 347                 // clip target by the seperating plane
 348                 //
 349                         target = ChopWinding (target, stack, &plane);
 350                         if (!target)
 351                                 return NULL;            // target is not visible
 352                 }
 353         }
 354
 355         return target;
 356 }
 357
 358
 359
 360 /*
 361 ==================
 362 RecursiveLeafFlow
 363
 364 Flood fill through the leafs
 365 If src_portal is NULL, this is the originating leaf
 366 ==================
 367 */
 368 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
 369 {
 370         pstack_t        stack;
 371         portal_t        *p;
 372         plane_t         backplane;
 373         leaf_t          *leaf;
 374         int                     i, j;
 375         long            *test, *might, *vis, more;
 376         int                     pnum;
 377
 378         thread->c_chains++;
 379
 380         leaf = &leafs[leafnum];
 381 //      CheckStack (leaf, thread);
 382
 383         prevstack->next = &stack;
 384
 385         stack.next = NULL;
 386         stack.leaf = leaf;
 387         stack.portal = NULL;
 388
 389         might = (long *)stack.mightsee;
 390         vis = (long *)thread->base->portalvis;
 391
 392 // check all portals for flowing into other leafs
 393         for (i=0 ; i<leaf->numportals ; i++)
 394         {
 395                 p = leaf->portals[i];
 396                 pnum = p - portals;
 397
 398                 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
 399                 {
 400                         continue;       // can't possibly see it
 401                 }
 402
 403         // if the portal can't see anything we haven't allready seen, skip it
 404                 if (p->status == stat_done)
 405                 {
 406                         test = (long *)p->portalvis;
 407                 }
 408                 else
 409                 {
 410                         test = (long *)p->portalflood;
 411                 }
 412
 413                 more = 0;
 414                 for (j=0 ; j<portallongs ; j++)
 415                 {
 416                         might[j] = ((long *)prevstack->mightsee)[j] & test[j];
 417                         more |= (might[j] & ~vis[j]);
 418                 }
 419
 420                 if (!more &&
 421                         (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
 422                 {       // can't see anything new
 423                         continue;
 424                 }
 425
 426                 // get plane of portal, point normal into the neighbor leaf
 427                 stack.portalplane = p->plane;
 428                 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
 429                 backplane.dist = -p->plane.dist;
 430
 431                 stack.portal = p;
 432                 stack.next = NULL;
 433                 stack.freewindings[0] = 1;
 434                 stack.freewindings[1] = 1;
 435                 stack.freewindings[2] = 1;
 436
 437 {
 438 float d;
 439
 440         d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
 441         d -= thread->pstack_head.portalplane.dist;
 442         if (d < -p->radius)
 443         {
 444                 continue;
 445         }
 446         else if (d > p->radius)
 447         {
 448                 stack.pass = p->winding;
 449         }
 450         else
 451         {
 452                 stack.pass = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
 453                 if (!stack.pass)
 454                         continue;
 455         }
 456 }
 457
 458
 459 {
 460 float d;
 461
 462         d = DotProduct (thread->base->origin, p->plane.normal);
 463         d -= p->plane.dist;
 464         if (d > p->radius)
 465         {
 466                 continue;
 467         }
 468         else if (d < -p->radius)
 469         {
 470                 stack.source = prevstack->source;
 471         }
 472         else
 473         {
 474                 stack.source = ChopWinding (prevstack->source, &stack, &backplane);
 475                 if (!stack.source)
 476                         continue;
 477         }
 478 }
 479
 480                 if (!prevstack->pass)
 481                 {       // the second leaf can only be blocked if coplanar
 482
 483                         // mark the portal as visible
 484                         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
 485
 486                         RecursiveLeafFlow (p->leaf, thread, &stack);
 487                         continue;
 488                 }
 489
 490                 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);
 491                 if (!stack.pass)
 492                         continue;
 493
 494                 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);
 495                 if (!stack.pass)
 496                         continue;
 497
 498                 // mark the portal as visible
 499                 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
 500
 501                 // flow through it for real
 502                 RecursiveLeafFlow (p->leaf, thread, &stack);
 503         }
 504 }
 505
 506
 507 /*
 508 ===============
 509 PortalFlow
 510
 511 generates the portalvis bit vector
 512 ===============
 513 */
 514 void PortalFlow (int portalnum)
 515 {
 516         threaddata_t    data;
 517         int                             i;
 518         portal_t                *p;
 519         int                             c_might, c_can;
 520
 521         p = sorted_portals[portalnum];
 522         p->status = stat_working;
 523
 524         c_might = CountBits (p->portalflood, numportals*2);
 525
 526         memset (&data, 0, sizeof(data));
 527         data.base = p;
 528
 529         data.pstack_head.portal = p;
 530         data.pstack_head.source = p->winding;
 531         data.pstack_head.portalplane = p->plane;
 532         for (i=0 ; i<portallongs ; i++)
 533                 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
 534         RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
 535
 536         p->status = stat_done;
 537
 538         c_can = CountBits (p->portalvis, numportals*2);
 539
 540         qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n",
 541                 (int)(p - portals),     c_might, c_can, data.c_chains);
 542 }
 543
 544
 545 /*
 546 ===============================================================================
 547
 548 This is a rough first-order aproximation that is used to trivially reject some
 549 of the final calculations.
 550
 551
 552 Calculates portalfront and portalflood bit vectors
 553
 554 thinking about:
 555
 556 typedef struct passage_s
 557 {
 558         struct passage_s        *next;
 559         struct portal_s         *to;
 560         stryct sep_s            *seperators;
 561         byte                            *mightsee;
 562 } passage_t;
 563
 564 typedef struct portal_s
 565 {
 566         struct passage_s        *passages;
 567         int                                     leaf;           // leaf portal faces into
 568 } portal_s;
 569
 570 leaf = portal->leaf
 571 clear
 572 for all portals
 573
 574
 575 calc portal visibility
 576         clear bit vector
 577         for all passages
 578                 passage visibility
 579
 580
 581 for a portal to be visible to a passage, it must be on the front of
 582 all seperating planes, and both portals must be behind the mew portal
 583
 584 ===============================================================================
 585 */
 586
 587 int             c_flood, c_vis;
 588
 589
 590 /*
 591 ==================
 592 SimpleFlood
 593
 594 ==================
 595 */
 596 void SimpleFlood (portal_t *srcportal, int leafnum)
 597 {
 598         int             i;
 599         leaf_t  *leaf;
 600         portal_t        *p;
 601         int             pnum;
 602
 603         leaf = &leafs[leafnum];
 604
 605         for (i=0 ; i<leaf->numportals ; i++)
 606         {
 607                 p = leaf->portals[i];
 608                 pnum = p - portals;
 609                 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
 610                         continue;
 611
 612                 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
 613                         continue;
 614
 615                 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
 616
 617                 SimpleFlood (srcportal, p->leaf);
 618         }
 619 }
 620
 621 /*
 622 ==============
 623 BasePortalVis
 624 ==============
 625 */
 626 void BasePortalVis (int portalnum)
 627 {
 628         int                     j, k;
 629         portal_t        *tp, *p;
 630         float           d;
 631         winding_t       *w;
 632
 633         p = portals+portalnum;
 634
 635         p->portalfront = malloc (portalbytes);
 636         memset (p->portalfront, 0, portalbytes);
 637
 638         p->portalflood = malloc (portalbytes);
 639         memset (p->portalflood, 0, portalbytes);
 640
 641         p->portalvis = malloc (portalbytes);
 642         memset (p->portalvis, 0, portalbytes);
 643
 644         for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
 645         {
 646                 if (j == portalnum)
 647                         continue;
 648                 w = tp->winding;
 649                 for (k=0 ; k<w->numpoints ; k++)
 650                 {
 651                         d = DotProduct (w->points[k], p->plane.normal)
 652                                 - p->plane.dist;
 653                         if (d > ON_EPSILON)
 654                                 break;
 655                 }
 656                 if (k == w->numpoints)
 657                         continue;       // no points on front
 658
 659                 w = p->winding;
 660                 for (k=0 ; k<w->numpoints ; k++)
 661                 {
 662                         d = DotProduct (w->points[k], tp->plane.normal)
 663                                 - tp->plane.dist;
 664                         if (d < -ON_EPSILON)
 665                                 break;
 666                 }
 667                 if (k == w->numpoints)
 668                         continue;       // no points on front
 669
 670                 p->portalfront[j>>3] |= (1<<(j&7));
 671         }
 672
 673         SimpleFlood (p, p->leaf);
 674
 675         p->nummightsee = CountBits (p->portalflood, numportals*2);
 676 //      printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
 677         c_flood += p->nummightsee;
 678 }
 679
 680
 681
 682
 683
 684 /*
 685 ===============================================================================
 686
 687 This is a second order aproximation
 688
 689 Calculates portalvis bit vector
 690
 691 WAAAAAAY too slow.
 692
 693 ===============================================================================
 694 */
 695
 696 /*
 697 ==================
 698 RecursiveLeafBitFlow
 699
 700 ==================
 701 */
 702 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
 703 {
 704         portal_t        *p;
 705         leaf_t          *leaf;
 706         int                     i, j;
 707         long            more;
 708         int                     pnum;
 709         byte            newmight[MAX_PORTALS/8];
 710
 711         leaf = &leafs[leafnum];
 712
 713 // check all portals for flowing into other leafs
 714         for (i=0 ; i<leaf->numportals ; i++)
 715         {
 716                 p = leaf->portals[i];
 717                 pnum = p - portals;
 718
 719                 // if some previous portal can't see it, skip
 720                 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
 721                         continue;
 722
 723                 // if this portal can see some portals we mightsee, recurse
 724                 more = 0;
 725                 for (j=0 ; j<portallongs ; j++)
 726                 {
 727                         ((long *)newmight)[j] = ((long *)mightsee)[j]
 728                                 & ((long *)p->portalflood)[j];
 729                         more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
 730                 }
 731
 732                 if (!more)
 733                         continue;       // can't see anything new
 734
 735                 cansee[pnum>>3] |= (1<<(pnum&7));
 736
 737                 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
 738         }
 739 }
 740
 741 /*
 742 ==============
 743 BetterPortalVis
 744 ==============
 745 */
 746 void BetterPortalVis (int portalnum)
 747 {
 748         portal_t        *p;
 749
 750         p = portals+portalnum;
 751
 752         RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
 753
 754         // build leaf vis information
 755         p->nummightsee = CountBits (p->portalvis, numportals*2);
 756         c_vis += p->nummightsee;
 757 }
 758
 759