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
CountBits(byte * bits,int numbits)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
CheckStack(leaf_t * leaf,threaddata_t * thread)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
AllocStackWinding(pstack_t * stack)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
FreeStackWinding(winding_t * w,pstack_t * stack)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 */
ChopWinding(winding_t * in,pstack_t * stack,plane_t * split)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 */
ClipToSeperators(winding_t * source,winding_t * pass,winding_t * target,qboolean flipclip,pstack_t * stack)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 */
RecursiveLeafFlow(int leafnum,threaddata_t * thread,pstack_t * prevstack)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 */
PortalFlow(int portalnum)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 */
SimpleFlood(portal_t * srcportal,int leafnum)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 */
BasePortalVis(int portalnum)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 */
RecursiveLeafBitFlow(int leafnum,byte * mightsee,byte * cansee)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 */
BetterPortalVis(int portalnum)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
789