1 #pragma warning(disable: 4018) //amckern - 64bit - '<' Singed/Unsigned Mismatch
2
3 #include "vis.h"
4
5 // =====================================================================================
6 // CheckStack
7 // =====================================================================================
8 #ifdef USE_CHECK_STACK
CheckStack(const leaf_t * const leaf,const threaddata_t * const thread)9 static void CheckStack(const leaf_t* const leaf, const threaddata_t* const thread)
10 {
11 pstack_t* p;
12
13 for (p = thread->pstack_head.next; p; p = p->next)
14 {
15 if (p->leaf == leaf)
16 Error("CheckStack: leaf recursion");
17 }
18 }
19 #endif
20
21 // =====================================================================================
22 // AllocStackWinding
23 // =====================================================================================
AllocStackWinding(pstack_t * const stack)24 inline static winding_t* AllocStackWinding(pstack_t* const stack)
25 {
26 int i;
27
28 for (i = 0; i < 3; i++)
29 {
30 if (stack->freewindings[i])
31 {
32 stack->freewindings[i] = 0;
33 return &stack->windings[i];
34 }
35 }
36
37 Error("AllocStackWinding: failed");
38
39 return NULL;
40 }
41
42 // =====================================================================================
43 // FreeStackWinding
44 // =====================================================================================
FreeStackWinding(const winding_t * const w,pstack_t * const stack)45 inline static void FreeStackWinding(const winding_t* const w, pstack_t* const stack)
46 {
47 int i;
48
49 i = w - stack->windings;
50
51 if (i < 0 || i > 2)
52 return; // not from local
53
54 if (stack->freewindings[i])
55 Error("FreeStackWinding: allready free");
56 stack->freewindings[i] = 1;
57 }
58
59 // =====================================================================================
60 // ChopWinding
61 // =====================================================================================
ChopWinding(winding_t * const in,pstack_t * const stack,const plane_t * const split)62 inline winding_t* ChopWinding(winding_t* const in, pstack_t* const stack, const plane_t* const split)
63 {
64 vec_t dists[128];
65 int sides[128];
66 int counts[3];
67 vec_t dot;
68 int i;
69 vec3_t mid;
70 winding_t* neww;
71
72 counts[0] = counts[1] = counts[2] = 0;
73
74 if (in->numpoints > (sizeof(sides) / sizeof(*sides)))
75 {
76 Error("Winding with too many sides!");
77 }
78
79 // determine sides for each point
80 for (i = 0; i < in->numpoints; i++)
81 {
82 dot = DotProduct(in->points[i], split->normal);
83 dot -= split->dist;
84 dists[i] = dot;
85 if (dot > ON_EPSILON)
86 {
87 sides[i] = SIDE_FRONT;
88 }
89 else if (dot < -ON_EPSILON)
90 {
91 sides[i] = SIDE_BACK;
92 }
93 else
94 {
95 sides[i] = SIDE_ON;
96 }
97 counts[sides[i]]++;
98 }
99
100 if (!counts[1])
101 {
102 return in; // completely on front side
103 }
104
105 if (!counts[0])
106 {
107 FreeStackWinding(in, stack);
108 return NULL;
109 }
110
111 sides[i] = sides[0];
112 dists[i] = dists[0];
113
114 neww = AllocStackWinding(stack);
115
116 neww->numpoints = 0;
117
118 for (i = 0; i < in->numpoints; i++)
119 {
120 vec_t* p1 = in->points[i];
121
122 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
123 {
124 Warning("ChopWinding : rejected(1) due to too many points\n");
125 FreeStackWinding(neww, stack);
126 return in; // can't chop -- fall back to original
127 }
128
129 if (sides[i] == SIDE_ON)
130 {
131 VectorCopy(p1, neww->points[neww->numpoints]);
132 neww->numpoints++;
133 continue;
134 }
135 else if (sides[i] == SIDE_FRONT)
136 {
137 VectorCopy(p1, neww->points[neww->numpoints]);
138 neww->numpoints++;
139 }
140
141 if ((sides[i + 1] == SIDE_ON) | (sides[i + 1] == sides[i])) // | instead of || for branch optimization
142 {
143 continue;
144 }
145
146 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
147 {
148 Warning("ChopWinding : rejected(2) due to too many points\n");
149 FreeStackWinding(neww, stack);
150 return in; // can't chop -- fall back to original
151 }
152
153 // generate a split point
154 {
155 unsigned tmp = i + 1;
156 if (tmp >= in->numpoints)
157 {
158 tmp = 0;
159 }
160 const vec_t* p2 = in->points[tmp];
161
162 dot = dists[i] / (dists[i] - dists[i + 1]);
163
164 const vec_t* normal = split->normal;
165 const vec_t dist = split->dist;
166 unsigned int j;
167 for (j = 0; j < 3; j++)
168 { // avoid round off error when possible
169 if (normal[j] < (1.0 - NORMAL_EPSILON))
170 {
171 if (normal[j] > (-1.0 + NORMAL_EPSILON))
172 {
173 mid[j] = p1[j] + dot * (p2[j] - p1[j]);
174 }
175 else
176 {
177 mid[j] = -dist;
178 }
179 }
180 else
181 {
182 mid[j] = dist;
183 }
184 }
185 }
186
187 VectorCopy(mid, neww->points[neww->numpoints]);
188 neww->numpoints++;
189 }
190
191 // free the original winding
192 FreeStackWinding(in, stack);
193
194 return neww;
195 }
196
197 // =====================================================================================
198 // AddPlane
199 // =====================================================================================
200 #ifdef RVIS_LEVEL_2
AddPlane(pstack_t * const stack,const plane_t * const split)201 inline static void AddPlane(pstack_t* const stack, const plane_t* const split)
202 {
203 int j;
204
205 if (stack->clipPlaneCount)
206 {
207 for (j = 0; j < stack->clipPlaneCount; j++)
208 {
209 if (fabs((stack->clipPlane[j]).dist - split->dist) <= EQUAL_EPSILON &&
210 VectorCompare((stack->clipPlane[j]).normal, split->normal))
211 {
212 return;
213 }
214 }
215 }
216 stack->clipPlane[stack->clipPlaneCount] = *split;
217 stack->clipPlaneCount++;
218 }
219 #endif
220
221 // =====================================================================================
222 // ClipToSeperators
223 // Source, pass, and target are an ordering of portals.
224 // Generates seperating planes canidates by taking two points from source and one
225 // point from pass, and clips target by them.
226 // If the target argument is NULL, then a list of clipping planes is built in
227 // stack instead.
228 // If target is totally clipped away, that portal can not be seen through.
229 // Normal clip keeps target on the same side as pass, which is correct if the
230 // order goes source, pass, target. If the order goes pass, source, target then
231 // flipclip should be set.
232 // =====================================================================================
ClipToSeperators(const winding_t * const source,const winding_t * const pass,winding_t * const a_target,const bool flipclip,pstack_t * const stack)233 inline static winding_t* ClipToSeperators(
234 const winding_t* const source,
235 const winding_t* const pass,
236 winding_t* const a_target,
237 const bool flipclip,
238 pstack_t* const stack)
239 {
240 int i, j, k, l;
241 plane_t plane;
242 vec3_t v1, v2;
243 float d;
244 int counts[3];
245 bool fliptest;
246 winding_t* target = a_target;
247
248 const unsigned int numpoints = source->numpoints;
249
250 // check all combinations
251 for (i=0, l=1; i < numpoints; i++, l++)
252 {
253 if (l == numpoints)
254 {
255 l = 0;
256 }
257
258 VectorSubtract(source->points[l], source->points[i], v1);
259
260 // fing a vertex of pass that makes a plane that puts all of the
261 // vertexes of pass on the front side and all of the vertexes of
262 // source on the back side
263 for (j = 0; j < pass->numpoints; j++)
264 {
265 VectorSubtract(pass->points[j], source->points[i], v2);
266 CrossProduct(v1, v2, plane.normal);
267 if (VectorNormalize(plane.normal) < ON_EPSILON)
268 {
269 continue;
270 }
271 plane.dist = DotProduct(pass->points[j], plane.normal);
272
273 // find out which side of the generated seperating plane has the
274 // source portal
275 fliptest = false;
276 for (k = 0; k < numpoints; k++)
277 {
278 if ((k == i) | (k == l)) // | instead of || for branch optimization
279 {
280 continue;
281 }
282 d = DotProduct(source->points[k], plane.normal) - plane.dist;
283 if (d < -ON_EPSILON)
284 { // source is on the negative side, so we want all
285 // pass and target on the positive side
286 fliptest = false;
287 break;
288 }
289 else if (d > ON_EPSILON)
290 { // source is on the positive side, so we want all
291 // pass and target on the negative side
292 fliptest = true;
293 break;
294 }
295 }
296 if (k == numpoints)
297 {
298 continue; // planar with source portal
299 }
300
301 // flip the normal if the source portal is backwards
302 if (fliptest)
303 {
304 VectorSubtract(vec3_origin, plane.normal, plane.normal);
305 plane.dist = -plane.dist;
306 }
307
308 // if all of the pass portal points are now on the positive side,
309 // this is the seperating plane
310 counts[0] = counts[1] = counts[2] = 0;
311 for (k = 0; k < pass->numpoints; k++)
312 {
313 if (k == j)
314 {
315 continue;
316 }
317 d = DotProduct(pass->points[k], plane.normal) - plane.dist;
318 if (d < -ON_EPSILON)
319 {
320 break;
321 }
322 else if (d > ON_EPSILON)
323 {
324 counts[0]++;
325 }
326 else
327 {
328 counts[2]++;
329 }
330 }
331 if (k != pass->numpoints)
332 {
333 continue; // points on negative side, not a seperating plane
334 }
335
336 if (!counts[0])
337 {
338 continue; // planar with seperating plane
339 }
340
341 // flip the normal if we want the back side
342 if (flipclip)
343 {
344 VectorSubtract(vec3_origin, plane.normal, plane.normal);
345 plane.dist = -plane.dist;
346 }
347
348 if (target != NULL)
349 {
350 // clip target by the seperating plane
351 target = ChopWinding(target, stack, &plane);
352 if (!target)
353 {
354 return NULL; // target is not visible
355 }
356 }
357 else
358 {
359 AddPlane(stack, &plane);
360 }
361
362 #ifdef RVIS_LEVEL_1
363 break; /* Antony was here */
364 #endif
365 }
366 }
367
368 return target;
369 }
370
371 // =====================================================================================
372 // RecursiveLeafFlow
373 // Flood fill through the leafs
374 // If src_portal is NULL, this is the originating leaf
375 // =====================================================================================
RecursiveLeafFlow(const int leafnum,const threaddata_t * const thread,const pstack_t * const prevstack)376 inline static void RecursiveLeafFlow(const int leafnum, const threaddata_t* const thread, const pstack_t* const prevstack)
377 {
378 pstack_t stack;
379 leaf_t* leaf;
380
381 leaf = &g_leafs[leafnum];
382 #ifdef USE_CHECK_STACK
383 CheckStack(leaf, thread);
384 #endif
385
386 {
387 const unsigned offset = leafnum >> 3;
388 const unsigned bit = (1 << (leafnum & 7));
389
390 // mark the leaf as visible
391 if (!(thread->leafvis[offset] & bit))
392 {
393 thread->leafvis[offset] |= bit;
394 thread->base->numcansee++;
395 }
396 }
397
398 #ifdef USE_CHECK_STACK
399 prevstack->next = &stack;
400 stack.next = NULL;
401 #endif
402 stack.head = prevstack->head;
403 stack.leaf = leaf;
404 stack.portal = NULL;
405 #ifdef RVIS_LEVEL_2
406 stack.clipPlaneCount = -1;
407 stack.clipPlane = NULL;
408 #endif
409
410 // check all portals for flowing into other leafs
411 unsigned i;
412 portal_t** plist = leaf->portals;
413
414 for (i = 0; i < leaf->numportals; i++, plist++)
415 {
416 portal_t* p = *plist;
417
418 #if ZHLT_ZONES
419 portal_t * head_p = stack.head->portal;
420 if (g_Zones->check(head_p->zone, p->zone))
421 {
422 continue;
423 }
424 #endif
425
426 {
427 const unsigned offset = p->leaf >> 3;
428 const unsigned bit = 1 << (p->leaf & 7);
429
430 if (!(stack.head->mightsee[offset] & bit))
431 {
432 continue; // can't possibly see it
433 }
434 if (!(prevstack->mightsee[offset] & bit))
435 {
436 continue; // can't possibly see it
437 }
438 }
439
440 // if the portal can't see anything we haven't allready seen, skip it
441 {
442 long* test;
443
444 if (p->status == stat_done)
445 {
446 test = (long*)p->visbits;
447 }
448 else
449 {
450 test = (long*)p->mightsee;
451 }
452
453 {
454 const int bitlongs = g_bitlongs;
455
456 {
457 long* prevmight = (long*)prevstack->mightsee;
458 long* might = (long*)stack.mightsee;
459
460 unsigned j;
461 for (j = 0; j < bitlongs; j++, test++, might++, prevmight++)
462 {
463 (*might) = (*prevmight) & (*test);
464 }
465 }
466
467 {
468 long* might = (long*)stack.mightsee;
469 long* vis = (long*)thread->leafvis;
470 unsigned j;
471 for (j = 0; j < bitlongs; j++, might++, vis++)
472 {
473 if ((*might) & ~(*vis))
474 {
475 break;
476 }
477 }
478
479 if (j == g_bitlongs)
480 { // can't see anything new
481 continue;
482 }
483 }
484 }
485 }
486
487 // get plane of portal, point normal into the neighbor leaf
488 stack.portalplane = &p->plane;
489 plane_t backplane;
490 VectorSubtract(vec3_origin, p->plane.normal, backplane.normal);
491 backplane.dist = -p->plane.dist;
492
493 if (VectorCompare(prevstack->portalplane->normal, backplane.normal))
494 {
495 continue; // can't go out a coplanar face
496 }
497
498 stack.portal = p;
499 #ifdef USE_CHECK_STACK
500 stack.next = NULL;
501 #endif
502 stack.freewindings[0] = 1;
503 stack.freewindings[1] = 1;
504 stack.freewindings[2] = 1;
505
506 stack.pass = ChopWinding(p->winding, &stack, thread->pstack_head.portalplane);
507 if (!stack.pass)
508 {
509 continue;
510 }
511
512 stack.source = ChopWinding(prevstack->source, &stack, &backplane);
513 if (!stack.source)
514 {
515 continue;
516 }
517
518 if (!prevstack->pass)
519 { // the second leaf can only be blocked if coplanar
520 RecursiveLeafFlow(p->leaf, thread, &stack);
521 continue;
522 }
523
524 stack.pass = ChopWinding(stack.pass, &stack, prevstack->portalplane);
525 if (!stack.pass)
526 {
527 continue;
528 }
529
530 #ifdef RVIS_LEVEL_2
531 if (stack.clipPlaneCount == -1)
532 {
533 stack.clipPlaneCount = 0;
534 stack.clipPlane = (plane_t*)alloca(sizeof(plane_t) * prevstack->source->numpoints * prevstack->pass->numpoints);
535
536 ClipToSeperators(prevstack->source, prevstack->pass, NULL, false, &stack);
537 ClipToSeperators(prevstack->pass, prevstack->source, NULL, true, &stack);
538 }
539
540 if (stack.clipPlaneCount > 0)
541 {
542 unsigned j;
543 for (j = 0; j < stack.clipPlaneCount && stack.pass != NULL; j++)
544 {
545 stack.pass = ChopWinding(stack.pass, &stack, &(stack.clipPlane[j]));
546 }
547
548 if (stack.pass == NULL)
549 continue;
550 }
551 #else
552
553 stack.pass = ClipToSeperators(stack.source, prevstack->pass, stack.pass, false, &stack);
554 if (!stack.pass)
555 {
556 continue;
557 }
558
559 stack.pass = ClipToSeperators(prevstack->pass, stack.source, stack.pass, true, &stack);
560 if (!stack.pass)
561 {
562 continue;
563 }
564 #endif
565
566 if (g_fullvis)
567 {
568 stack.source = ClipToSeperators(stack.pass, prevstack->pass, stack.source, false, &stack);
569 if (!stack.source)
570 {
571 continue;
572 }
573
574 stack.source = ClipToSeperators(prevstack->pass, stack.pass, stack.source, true, &stack);
575 if (!stack.source)
576 {
577 continue;
578 }
579 }
580
581 // flow through it for real
582 RecursiveLeafFlow(p->leaf, thread, &stack);
583 }
584
585 #ifdef RVIS_LEVEL_2
586 #if 0
587 if (stack.clipPlane != NULL)
588 {
589 free(stack.clipPlane);
590 }
591 #endif
592 #endif
593 }
594
595 // =====================================================================================
596 // PortalFlow
597 // =====================================================================================
PortalFlow(portal_t * p)598 void PortalFlow(portal_t* p)
599 {
600 threaddata_t data;
601 unsigned i;
602
603 if (p->status != stat_working)
604 Error("PortalFlow: reflowed");
605
606 p->visbits = (byte*)calloc(1, g_bitbytes);
607
608 memset(&data, 0, sizeof(data));
609 data.leafvis = p->visbits;
610 data.base = p;
611
612 data.pstack_head.head = &data.pstack_head;
613 data.pstack_head.portal = p;
614 data.pstack_head.source = p->winding;
615 data.pstack_head.portalplane = &p->plane;
616 for (i = 0; i < g_bitlongs; i++)
617 {
618 ((long*)data.pstack_head.mightsee)[i] = ((long*)p->mightsee)[i];
619 }
620 RecursiveLeafFlow(p->leaf, &data, &data.pstack_head);
621
622 #ifdef ZHLT_NETVIS
623 p->fromclient = g_clientid;
624 #endif
625 p->status = stat_done;
626 #ifdef ZHLT_NETVIS
627 Flag_VIS_DONE_PORTAL(g_visportalindex);
628 #endif
629 }
630
631 // =====================================================================================
632 // SimpleFlood
633 // This is a rough first-order aproximation that is used to trivially reject some
634 // of the final calculations.
635 // =====================================================================================
SimpleFlood(byte * const srcmightsee,const int leafnum,byte * const portalsee,unsigned int * const c_leafsee)636 static void SimpleFlood(byte* const srcmightsee, const int leafnum, byte* const portalsee, unsigned int* const c_leafsee)
637 {
638 unsigned i;
639 leaf_t* leaf;
640 portal_t* p;
641
642 {
643 const unsigned offset = leafnum >> 3;
644 const unsigned bit = (1 << (leafnum & 7));
645
646 if (srcmightsee[offset] & bit)
647 {
648 return;
649 }
650 else
651 {
652 srcmightsee[offset] |= bit;
653 }
654 }
655
656 (*c_leafsee)++;
657 leaf = &g_leafs[leafnum];
658
659 for (i = 0; i < leaf->numportals; i++)
660 {
661 p = leaf->portals[i];
662 if (!portalsee[p - g_portals])
663 {
664 continue;
665 }
666 SimpleFlood(srcmightsee, p->leaf, portalsee, c_leafsee);
667 }
668 }
669
670 #define PORTALSEE_SIZE (MAX_PORTALS*2)
671 #ifdef SYSTEM_WIN32
672 #pragma warning(push)
673 #pragma warning(disable: 4100) // unreferenced formal parameter
674 #endif
675
676 #ifdef HLVIS_MAXDIST
677 // AJM: MVD
678 // =====================================================================================
679 // BlockVis
680 // =====================================================================================
BlockVis(intptr_t unused)681 void BlockVis(intptr_t unused)
682 {
683 int i, j, k, l, m;
684 portal_t *p;
685 visblocker_t *v;
686 visblocker_t *v2;
687 leaf_t *leaf;
688
689 while(1)
690 {
691 i = GetThreadWork();
692 if(i == -1)
693 break;
694
695 v = &g_visblockers[i];
696
697 // See which visblockers we need
698 for(j = 0; j < v->numnames; j++)
699 {
700 // Find visblocker
701 if(!(v2 = GetVisBlock(v->blocknames[j])))
702 continue;
703
704 // For each leaf in v2, eliminate visibility from v1
705 for(k = 0; k < v->numleafs; k++)
706 {
707 leaf = &g_leafs[v->blockleafs[k]];
708
709 for(l = 0; l < leaf->numportals; l++)
710 {
711 p = leaf->portals[l];
712
713 for(m = 0; m < v2->numleafs; m++)
714 {
715 const unsigned offset = v2->blockleafs[m] >> 3;
716 const unsigned bit = (1 << (v2->blockleafs[m] & 7));
717
718 p->mightsee[offset] &= ~bit;
719 }
720 }
721 }
722 }
723 }
724 }
725
726 // AJM: MVD
727 // =====================================================================================
728 // GetSplitPortal
729 // This function returns a portal on leaf1 that sucessfully seperates leaf1
730 // and leaf2
731 // =====================================================================================
GetSplitPortal(leaf_t * leaf1,leaf_t * leaf2)732 static portal_t *GetSplitPortal(leaf_t *leaf1, leaf_t *leaf2)
733 {
734 int i, k, l;
735
736 portal_t *p1;
737 portal_t *t;
738
739 float check_dist;
740
741 for(i = 0, p1 = leaf1->portals[0]; i < leaf1->numportals; i++, p1++)
742 {
743 hlassert(p1->winding->numpoints >= 3);
744
745 // Check to make sure all the points on the other leaf are in front of the portal plane
746 for(k = 0, t = leaf2->portals[0]; k < leaf2->numportals; k++, t++)
747 {
748 for(l = 0; l < t->winding->numpoints; l++)
749 {
750 check_dist = DotProduct(t->winding->points[l], p1->plane.normal) - p1->plane.dist;
751
752 // We make the assumption that all portals face away from their parent leaf
753 if(check_dist < -ON_EPSILON)
754 goto PostLoop;
755 }
756 }
757
758 PostLoop:
759 // If we didn't check all the leaf2 portals, then this leaf1 portal doesn't work
760 if(k < leaf2->numportals)
761 continue;
762
763 // If we reach this point, we found a good portal
764 return p1;
765 }
766
767 // Didn't find any
768 return NULL;
769 }
770
771 // AJM: MVD
772 // =====================================================================================
773 // MakeSplitPortalList
774 // This function returns a portal on leaf1 that sucessfully seperates leaf1
775 // and leaf2
776 // =====================================================================================
MakeSplitPortalList(leaf_t * leaf1,leaf_t * leaf2,portal_t ** portals,int * num_portals)777 static void MakeSplitPortalList(leaf_t *leaf1, leaf_t *leaf2, portal_t **portals, int *num_portals)
778 {
779 int i, k, l;
780
781 portal_t *p1;
782 portal_t *t;
783
784 *num_portals = 0;
785
786 float check_dist;
787
788 portal_t p_list[MAX_PORTALS_ON_LEAF];
789 int c_portal = 0;
790
791 if(*portals)
792 delete [] *portals;
793
794 for(i = 0, p1 = leaf1->portals[0]; i < leaf1->numportals; i++, p1++)
795 {
796 hlassert(p1->winding->numpoints >= 3);
797
798 // Check to make sure all the points on the other leaf are in front of the portal plane
799 for(k = 0, t = leaf2->portals[0]; k < leaf2->numportals; k++, t++)
800 {
801 for(l = 0; l < t->winding->numpoints; l++)
802 {
803 check_dist = DotProduct(t->winding->points[l], p1->plane.normal) - p1->plane.dist;
804
805 // We make the assumption that all portals face away from their parent leaf
806 if(check_dist < -ON_EPSILON)
807 goto PostLoop;
808 }
809 }
810
811 PostLoop:
812 // If we didn't check all the leaf2 portals, then this leaf1 portal doesn't work
813 if(k < leaf2->numportals)
814 continue;
815
816 // If we reach this point, we found a good portal
817 memcpy(&p_list[c_portal++], p1, sizeof(portal_t));
818
819 if(c_portal >= MAX_PORTALS_ON_LEAF)
820 Error("c_portal > MAX_PORTALS_ON_LEAF");
821 }
822
823 if(!c_portal)
824 return;
825
826 *num_portals = c_portal;
827
828 *portals = new portal_t[c_portal];
829 memcpy(*portals, p_list, c_portal * sizeof(portal_t));
830 }
831
832 // AJM: MVD
833 // =====================================================================================
834 // DisjointLeafVis
835 // This function returns TRUE if neither leaf can see the other
836 // Returns FALSE otherwise
837 // =====================================================================================
DisjointLeafVis(int leaf1,int leaf2)838 static bool DisjointLeafVis(int leaf1, int leaf2)
839 {
840 leaf_t *l = g_leafs + leaf1;
841 leaf_t *tl = g_leafs + leaf2;
842
843 const unsigned offset_l = leaf1 >> 3;
844 const unsigned bit_l = (1 << (leaf1 & 7));
845
846 const unsigned offset_tl = leaf2 >> 3;
847 const unsigned bit_tl = (1 << (leaf2 & 7));
848
849 for(int k = 0; k < l->numportals; k++)
850 {
851 for(int m = 0; m < tl->numportals; m++)
852 {
853 if(l->portals[k]->mightsee[offset_tl] & bit_tl)
854 goto RetFalse;
855 if(tl->portals[m]->mightsee[offset_l] & bit_l)
856 goto RetFalse;
857
858 if(l->portals[k]->status != stat_none)
859 {
860 if(l->portals[k]->visbits[offset_tl] & bit_tl)
861 goto RetFalse;
862 }
863 if(tl->portals[m]->status != stat_none)
864 {
865 if(tl->portals[m]->visbits[offset_l] & bit_l)
866 goto RetFalse;
867 }
868 }
869 }
870
871 return true;
872
873 RetFalse:
874 return false;
875 }
876
877 // AJM: MVD
878 // =====================================================================================
879 // GetPortalBounds
880 // This function take a portal and finds its bounds
881 // parallel to the normal of the portal. They will face inwards
882 // =====================================================================================
GetPortalBounds(portal_t * p,plane_t ** bounds)883 static void GetPortalBounds(portal_t *p, plane_t **bounds)
884 {
885 int i;
886 vec3_t vec1, vec2;
887
888 hlassert(p->winding->numpoints >= 3);
889
890 if(*bounds)
891 delete [] *bounds;
892
893 *bounds = new plane_t[p->winding->numpoints];
894
895 // Loop through each set of points and create a plane boundary for each
896 for(i = 0; i < p->winding->numpoints; i++)
897 {
898 VectorSubtract(p->winding->points[(i + 1) % p->winding->numpoints],p->winding->points[i],vec1);
899
900 // Create inward normal for this boundary
901 CrossProduct(p->plane.normal, vec1, vec2);
902 VectorNormalize(vec2);
903
904 VectorCopy(vec2, (*bounds)[i].normal);
905 (*bounds)[i].dist = DotProduct(p->winding->points[i], vec2);
906 }
907 }
908
909 // AJM: MVD
910 // =====================================================================================
911 // ClipWindingsToBounds
912 // clips all the windings with all the planes (including original face) and outputs
913 // what's left int "out"
914 // =====================================================================================
ClipWindingsToBounds(winding_t * windings,int numwindings,plane_t * bounds,int numbounds,plane_t & original_plane,winding_t ** out,int & num_out)915 static void ClipWindingsToBounds(winding_t *windings, int numwindings, plane_t *bounds, int numbounds, plane_t &original_plane, winding_t **out, int &num_out)
916 {
917 hlassert(windings);
918 hlassert(bounds);
919
920 winding_t out_windings[MAX_PORTALS_ON_LEAF];
921 num_out = 0;
922
923 int h, i;
924
925 *out = NULL;
926
927 Winding wind;
928
929 for(h = 0; h < numwindings; h++)
930 {
931 // For each winding...
932 // Create a winding with CWinding
933
934 wind.initFromPoints(windings[h].points, windings[h].numpoints);
935
936 // Clip winding to original plane
937 wind.Chop(original_plane.normal, original_plane.dist);
938
939 for(i = 0; i < numbounds, wind.Valid(); i++)
940 {
941 // For each bound...
942 // Chop the winding to the bounds
943 wind.Chop(bounds[i].normal, bounds[i].dist);
944 }
945
946 if(wind.Valid())
947 {
948 // We have a valid winding, copy to array
949 wind.CopyPoints(&out_windings[num_out].points[0], out_windings[num_out].numpoints);
950
951 num_out++;
952 }
953 }
954
955 if(!num_out) // Everything was clipped away
956 return;
957
958 // Otherwise, create out
959 *out = new winding_t[num_out];
960
961 memcpy(*out, out_windings, num_out * sizeof(winding_t));
962 }
963
964 // AJM: MVD
965 // =====================================================================================
966 // GenerateWindingList
967 // This function generates a list of windings for a leaf through its portals
968 // =====================================================================================
GenerateWindingList(leaf_t * leaf,winding_t ** winds)969 static void GenerateWindingList(leaf_t *leaf, winding_t **winds)
970 {
971
972
973 winding_t windings[MAX_PORTALS_ON_LEAF];
974 int numwinds = 0;
975
976 int i;
977
978 for(i = 0; i < leaf->numportals; i++)
979 {
980 memcpy(&windings[numwinds++], leaf->portals[i]->winding, sizeof(winding_t));
981 }
982
983 if(!numwinds)
984 return;
985
986 *winds = new winding_t[numwinds];
987 memcpy(*winds, &windings, sizeof(winding_t) * numwinds);
988 }
989
990 // AJM: MVD
991 // =====================================================================================
992 // CalcPortalBoundsAndClipPortals
993 // =====================================================================================
CalcPortalBoundsAndClipPortals(portal_t * portal,leaf_t * leaf,winding_t ** out,int & numout)994 static void CalcPortalBoundsAndClipPortals(portal_t *portal, leaf_t *leaf, winding_t **out, int &numout)
995 {
996 plane_t *bounds = NULL;
997 winding_t *windings = NULL;
998
999 GetPortalBounds(portal, &bounds);
1000 GenerateWindingList(leaf, &windings);
1001
1002 ClipWindingsToBounds(windings, leaf->numportals, bounds, portal->winding->numpoints, portal->plane, out, numout);
1003
1004 delete bounds;
1005 delete windings;
1006 }
1007
1008 // AJM: MVD
1009 // =====================================================================================
1010 // GetShortestDistance
1011 // Gets the shortest distance between both leaves
1012 // =====================================================================================
GetShortestDistance(leaf_t * leaf1,leaf_t * leaf2)1013 static float GetShortestDistance(leaf_t *leaf1, leaf_t *leaf2)
1014 {
1015 winding_t *final = NULL;
1016 int num_finals = 0;
1017
1018 int i, x, y;
1019 float check;
1020
1021 for(i = 0; i < leaf1->numportals; i++)
1022 {
1023 CalcPortalBoundsAndClipPortals(leaf1->portals[i], leaf2, &final, num_finals);
1024
1025 // Minimum point distance
1026 for(x = 0; x < num_finals; x++)
1027 {
1028 for(y = 0; y < final[x].numpoints; y++)
1029 {
1030 check = DotProduct(leaf1->portals[i]->plane.normal, final[x].points[y]) - leaf1->portals[i]->plane.dist;
1031
1032 if(check <= g_maxdistance)
1033 return check;
1034 }
1035 }
1036
1037 delete final;
1038 }
1039
1040 // Switch leaf 1 and 2
1041 for(i = 0; i < leaf2->numportals; i++)
1042 {
1043 CalcPortalBoundsAndClipPortals(leaf2->portals[i], leaf1, &final, num_finals);
1044
1045 // Minimum point distance
1046 for(x = 0; x < num_finals; x++)
1047 {
1048 for(y = 0; y < final[x].numpoints; y++)
1049 {
1050 check = DotProduct(leaf2->portals[i]->plane.normal, final[x].points[y]) - leaf2->portals[i]->plane.dist;
1051
1052 if(check <= g_maxdistance)
1053 return check;
1054 }
1055 }
1056
1057 delete final;
1058 }
1059
1060 return 9E10;
1061 }
1062
1063 // AJM: MVD
1064 // =====================================================================================
1065 // CalcSplitsAndDotProducts
1066 // This function finds the splits of the leaf, and generates windings (if applicable)
1067 // =====================================================================================
CalcSplitsAndDotProducts(plane_t * org_split_plane,leaf_t * leaf1,leaf_t * leaf2,plane_t * bounds,int num_bounds)1068 static float CalcSplitsAndDotProducts(plane_t *org_split_plane, leaf_t *leaf1, leaf_t *leaf2, plane_t *bounds, int num_bounds)
1069 {
1070 int i, j, k, l;
1071
1072 portal_t *splits = NULL;
1073 int num_splits;
1074
1075 float dist;
1076 float min_dist = 999999999.999;
1077
1078 vec3_t i_points[MAX_POINTS_ON_FIXED_WINDING * MAX_PORTALS_ON_LEAF * 2];
1079 vec3_t delta;
1080 int num_points = 0;
1081
1082 // First get splits
1083 MakeSplitPortalList(leaf1, leaf2, &splits, &num_splits);
1084
1085 if(!num_splits)
1086 return min_dist;
1087
1088 // If the number of splits = 1, then clip the plane using the boundary windings
1089 if(num_splits == 1)
1090 {
1091 Winding wind(splits[0].plane.normal, splits[0].plane.dist);
1092
1093 for(i = 0; i < num_bounds; i++)
1094 {
1095 wind.Chop(bounds[i].normal, bounds[i].dist);
1096 }
1097
1098 // The wind is chopped - get closest dot product
1099 for(i = 0; i < wind.m_NumPoints; i++)
1100 {
1101 dist = DotProduct(wind.m_Points[i], org_split_plane->normal) - org_split_plane->dist;
1102
1103 min_dist = std::min(min_dist, dist);
1104 }
1105
1106 return min_dist;
1107 }
1108
1109 // In this case, we have more than one split point, and we must calculate all intersections
1110 // Properties of convex objects allow us to assume that these intersections will be the closest
1111 // points to the other leaf, and our other checks before this eliminate exception cases
1112
1113 // Loop through each split portal, and using an inside loop, loop through every OTHER split portal
1114 // Common portal points in more than one split portal are intersections!
1115 for(i = 0; i < num_splits; i++)
1116 {
1117 for(j = 0; j < num_splits; j++)
1118 {
1119 if(i == j)
1120 {
1121 continue;
1122 }
1123
1124 // Loop through each point on both portals
1125 for(k = 0; k < splits[i].winding->numpoints; k++)
1126 {
1127 for(l = 0; l < splits[j].winding->numpoints; l++)
1128 {
1129 VectorSubtract(splits[i].winding->points[k], splits[j].winding->points[l], delta);
1130
1131 if(VectorLength(delta) < EQUAL_EPSILON)
1132 {
1133 memcpy(i_points[num_points++], splits[i].winding->points[k], sizeof(vec3_t));
1134 }
1135 }
1136 }
1137 }
1138 }
1139
1140 // Loop through each intersection point and check
1141 for(i = 0; i < num_points; i++)
1142 {
1143 dist = DotProduct(i_points[i], org_split_plane->normal) - org_split_plane->dist;
1144
1145 min_dist = std::min(min_dist, dist);
1146 }
1147
1148 if(splits)
1149 delete [] splits;
1150
1151 return min_dist;
1152 }
1153
1154 #endif // HLVIS_MAXDIST
1155
1156 // =====================================================================================
1157 // BasePortalVis
1158 // =====================================================================================
BasePortalVis(intptr_t unused)1159 void BasePortalVis(intptr_t unused)
1160 {
1161 int i, j, k;
1162 portal_t* tp;
1163 portal_t* p;
1164 float d;
1165 winding_t* w;
1166 byte portalsee[PORTALSEE_SIZE];
1167 const int portalsize = (g_numportals * 2);
1168
1169 #ifdef ZHLT_NETVIS
1170 {
1171 i = unused;
1172 #else
1173 while (1)
1174 {
1175 i = GetThreadWork();
1176 if (i == -1)
1177 break;
1178 #endif
1179 p = g_portals + i;
1180
1181 p->mightsee = (byte*)calloc(1, g_bitbytes);
1182
1183 memset(portalsee, 0, portalsize);
1184
1185 #if ZHLT_ZONES
1186 UINT32 zone = p->zone;
1187 #endif
1188
1189 for (j = 0, tp = g_portals; j < portalsize; j++, tp++)
1190 {
1191 if (j == i)
1192 {
1193 continue;
1194 }
1195 #if ZHLT_ZONES
1196 if (g_Zones->check(zone, tp->zone))
1197 {
1198 continue;
1199 }
1200 #endif
1201
1202 w = tp->winding;
1203 for (k = 0; k < w->numpoints; k++)
1204 {
1205 d = DotProduct(w->points[k], p->plane.normal) - p->plane.dist;
1206 if (d > ON_EPSILON)
1207 {
1208 break;
1209 }
1210 }
1211 if (k == w->numpoints)
1212 {
1213 continue; // no points on front
1214 }
1215
1216
1217 w = p->winding;
1218 for (k = 0; k < w->numpoints; k++)
1219 {
1220 d = DotProduct(w->points[k], tp->plane.normal) - tp->plane.dist;
1221 if (d < -ON_EPSILON)
1222 {
1223 break;
1224 }
1225 }
1226 if (k == w->numpoints)
1227 {
1228 continue; // no points on front
1229 }
1230
1231
1232 portalsee[j] = 1;
1233 }
1234
1235 SimpleFlood(p->mightsee, p->leaf, portalsee, &p->nummightsee);
1236 Verbose("portal:%4i nummightsee:%4i \n", i, p->nummightsee);
1237 }
1238 }
1239
1240 #ifdef HLVIS_MAXDIST
1241 // AJM: MVD
1242 // =====================================================================================
1243 // MaxDistVis
1244 // =====================================================================================
1245 void MaxDistVis(intptr_t unused)
1246 {
1247 int i, j, k, m;
1248 int a, b, c, d;
1249 leaf_t *l;
1250 leaf_t *tl;
1251 plane_t *boundary = NULL;
1252 vec3_t delta;
1253
1254 float new_dist;
1255
1256 unsigned offset_l;
1257 unsigned bit_l;
1258
1259 unsigned offset_tl;
1260 unsigned bit_tl;
1261
1262 while(1)
1263 {
1264 i = GetThreadWork();
1265 if (i == -1)
1266 break;
1267
1268 l = &g_leafs[i];
1269
1270 for(j = i + 1, tl = g_leafs + j; j < g_portalleafs; j++, tl++)
1271 {
1272 if(j == i) // Ideally, should never be true
1273 {
1274 continue;
1275 }
1276
1277 // If they already can't see each other, no use checking
1278 if(DisjointLeafVis(i, j))
1279 {
1280 continue;
1281 }
1282
1283 new_dist = GetShortestDistance(l, tl);
1284
1285 if(new_dist <= g_maxdistance)
1286 continue;
1287
1288 // Try out our NEW, IMPROVED ALGORITHM!!!!
1289
1290 // Get a portal on Leaf 1 that completely seperates the two leafs
1291 /*split = GetSplitPortal(l, tl);
1292
1293 if(!split)
1294 continue;
1295
1296 // We have a split, so create the bounds
1297 GetPortalBounds(split, &boundary);
1298
1299 // Now get the dot product for all points on the other leaf
1300 max_dist = 999999999.999;
1301
1302 /// Do the first check if mode is >= 2
1303 if(g_mdmode >= 2)
1304 {
1305 for(k = 0; k < tl->numportals; k++)
1306 {
1307 for(m = 0; m < tl->portals[k]->winding->numpoints; m++)
1308 {
1309 for(n = 0; n < split->winding->numpoints; n++) // numpoints of split portals = number of boundaries
1310 {
1311 dist = DotProduct(tl->portals[k]->winding->points[m], boundary[n].normal) - boundary[n].dist;
1312
1313 if(dist < -ON_EPSILON)
1314 {
1315 // Outside boundaries
1316 //max_dot = MaxDotProduct(tl->portals[k]->winding->points[m], boundary, split->winding->numpoints);
1317
1318 //max_dist = std::min(max_dist, max_dot);
1319
1320 // Break so we don't do inside boundary check
1321 break;
1322 }
1323 }
1324 if(n < split->winding->numpoints)
1325 continue;
1326
1327 // We found a point that's inside all the boundries!
1328 new_dist = DotProduct(tl->portals[k]->winding->points[m], split->plane.normal) - split->plane.dist;
1329
1330 max_dist = std::min(max_dist, new_dist);
1331 }
1332 }
1333 }
1334
1335 // This is now a special check. If Leaf 2 has a split plane, we generate a polygon by clipping the plane
1336 // with the borders. We then get the minimum dot products. If more than one split plane, use intersection.
1337 // Only do this is g_mdmode is 3
1338 if(g_mdmode >= 3) // For future mode expansion
1339 {
1340 new_dist = CalcSplitsAndDotProducts(&split->plane, tl, l, boundary, split->winding->numpoints);
1341
1342 max_dist = std::min(max_dist, new_dist);
1343 }*/
1344
1345 // Third and final check. If the whole of leaf2 is outside of leaf1 boundaries, this one will catch it
1346 // Basic "every point to every point" type of deal :)
1347 // This is done by default all the time
1348 for(a = 0; a < l->numportals; a++)
1349 {
1350 for(b = 0; b < tl->numportals; b++)
1351 {
1352 for(c = 0; c < l->portals[a]->winding->numpoints; c++)
1353 {
1354 for(d = 0; d < tl->portals[b]->winding->numpoints; d++)
1355 {
1356 VectorSubtract(l->portals[a]->winding->points[c], tl->portals[b]->winding->points[d], delta);
1357
1358 if(VectorLength(delta) <= g_maxdistance)
1359 goto NoWork;
1360 }
1361 }
1362 }
1363 }
1364
1365 offset_l = i >> 3;
1366 bit_l = (1 << (i & 7));
1367
1368 offset_tl = j >> 3;
1369 bit_tl = (1 << (j & 7));
1370
1371 for(k = 0; k < l->numportals; k++)
1372 {
1373 for(m = 0; m < tl->numportals; m++)
1374 {
1375 if(l->portals[k]->status != stat_none)
1376 l->portals[k]->visbits[offset_tl] &= ~bit_tl;
1377 else
1378 l->portals[k]->mightsee[offset_tl] &= ~bit_tl;
1379
1380 if(tl->portals[m]->status != stat_none)
1381 tl->portals[m]->visbits[offset_l] &= ~bit_l;
1382 else
1383 tl->portals[m]->mightsee[offset_l] &= ~bit_l;
1384 }
1385 }
1386
1387 NoWork:
1388 continue; // Hack to keep label from causing compile error
1389 }
1390 }
1391
1392 // Release potential memory
1393 if(boundary)
1394 delete [] boundary;
1395 }
1396 #endif // HLVIS_MAXDIST
1397
1398 #ifdef SYSTEM_WIN32
1399 #pragma warning(pop)
1400 #endif
1401