tools/quake2/q2map/flow.c

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