Merge remote-tracking branch 'origin/divVerent/weird-shift-a'
[divverent/netradiant.git] / tools / quake3 / q3map2 / visflow.c
1 /* -------------------------------------------------------------------------------
2
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6 This file is part of GtkRadiant.
7
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21
22 ----------------------------------------------------------------------------------
23
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26
27 ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define VISFLOW_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41
42 /*
43
44   each portal will have a list of all possible to see from first portal
45
46   if (!thread->portalmightsee[portalnum])
47
48   portal mightsee
49
50   for p2 = all other portals in leaf
51         get sperating planes
52         for all portals that might be seen by p2
53                 mark as unseen if not present in seperating plane
54         flood fill a new mightsee
55         save as passagemightsee
56
57
58   void CalcMightSee (leaf_t *leaf, 
59 */
60
61 int CountBits (byte *bits, int numbits)
62 {
63         int             i;
64         int             c;
65
66         c = 0;
67         for (i=0 ; i<numbits ; i++)
68                 if (bits[i>>3] & (1<<(i&7)) )
69                         c++;
70
71         return c;
72 }
73
74 int             c_fullskip;
75 int             c_portalskip, c_leafskip;
76 int             c_vistest, c_mighttest;
77
78 int             c_chop, c_nochop;
79
80 int             active;
81
82 void CheckStack (leaf_t *leaf, threaddata_t *thread)
83 {
84         pstack_t        *p, *p2;
85
86         for (p=thread->pstack_head.next ; p ; p=p->next)
87         {
88 //              Sys_Printf ("=");
89                 if (p->leaf == leaf)
90                         Error ("CheckStack: leaf recursion");
91                 for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
92                         if (p2->leaf == p->leaf)
93                                 Error ("CheckStack: late leaf recursion");
94         }
95 //      Sys_Printf ("\n");
96 }
97
98
99 fixedWinding_t *AllocStackWinding (pstack_t *stack)
100 {
101         int             i;
102
103         for (i=0 ; i<3 ; i++)
104         {
105                 if (stack->freewindings[i])
106                 {
107                         stack->freewindings[i] = 0;
108                         return &stack->windings[i];
109                 }
110         }
111
112         Error ("AllocStackWinding: failed");
113
114         return NULL;
115 }
116
117 void FreeStackWinding (fixedWinding_t *w, pstack_t *stack)
118 {
119         int             i;
120
121         i = w - stack->windings;
122
123         if (i<0 || i>2)
124                 return;         // not from local
125
126         if (stack->freewindings[i])
127                 Error ("FreeStackWinding: allready free");
128         stack->freewindings[i] = 1;
129 }
130
131 /*
132 ==============
133 VisChopWinding
134
135 ==============
136 */
137 fixedWinding_t  *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_t *split)
138 {
139         vec_t   dists[128];
140         int             sides[128];
141         int             counts[3];
142         vec_t   dot;
143         int             i, j;
144         vec_t   *p1, *p2;
145         vec3_t  mid;
146         fixedWinding_t  *neww;
147
148         counts[0] = counts[1] = counts[2] = 0;
149
150         // determine sides for each point
151         for (i=0 ; i<in->numpoints ; i++)
152         {
153                 dot = DotProduct (in->points[i], split->normal);
154                 dot -= split->dist;
155                 dists[i] = dot;
156                 if (dot > ON_EPSILON)
157                         sides[i] = SIDE_FRONT;
158                 else if (dot < -ON_EPSILON)
159                         sides[i] = SIDE_BACK;
160                 else
161                 {
162                         sides[i] = SIDE_ON;
163                 }
164                 counts[sides[i]]++;
165         }
166
167         if (!counts[1])
168                 return in;              // completely on front side
169         
170         if (!counts[0])
171         {
172                 FreeStackWinding (in, stack);
173                 return NULL;
174         }
175
176         sides[i] = sides[0];
177         dists[i] = dists[0];
178         
179         neww = AllocStackWinding (stack);
180
181         neww->numpoints = 0;
182
183         for (i=0 ; i<in->numpoints ; i++)
184         {
185                 p1 = in->points[i];
186
187                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
188                 {
189                         FreeStackWinding (neww, stack);
190                         return in;              // can't chop -- fall back to original
191                 }
192
193                 if (sides[i] == SIDE_ON)
194                 {
195                         VectorCopy (p1, neww->points[neww->numpoints]);
196                         neww->numpoints++;
197                         continue;
198                 }
199         
200                 if (sides[i] == SIDE_FRONT)
201                 {
202                         VectorCopy (p1, neww->points[neww->numpoints]);
203                         neww->numpoints++;
204                 }
205                 
206                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
207                         continue;
208                         
209                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
210                 {
211                         FreeStackWinding (neww, stack);
212                         return in;              // can't chop -- fall back to original
213                 }
214
215                 // generate a split point
216                 p2 = in->points[(i+1)%in->numpoints];
217                 
218                 dot = dists[i] / (dists[i]-dists[i+1]);
219                 for (j=0 ; j<3 ; j++)
220                 {       // avoid round off error when possible
221                         if (split->normal[j] == 1)
222                                 mid[j] = split->dist;
223                         else if (split->normal[j] == -1)
224                                 mid[j] = -split->dist;
225                         else
226                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
227                 }
228                         
229                 VectorCopy (mid, neww->points[neww->numpoints]);
230                 neww->numpoints++;
231         }
232         
233         // free the original winding
234         FreeStackWinding (in, stack);
235         
236         return neww;
237 }
238
239 /*
240 ==============
241 ClipToSeperators
242
243 Source, pass, and target are an ordering of portals.
244
245 Generates seperating planes canidates by taking two points from source and one
246 point from pass, and clips target by them.
247
248 If target is totally clipped away, that portal can not be seen through.
249
250 Normal clip keeps target on the same side as pass, which is correct if the
251 order goes source, pass, target.  If the order goes pass, source, target then
252 flipclip should be set.
253 ==============
254 */
255 fixedWinding_t  *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack)
256 {
257         int                     i, j, k, l;
258         visPlane_t              plane;
259         vec3_t          v1, v2;
260         float           d;
261         vec_t           length;
262         int                     counts[3];
263         qboolean                fliptest;
264
265         // check all combinations       
266         for (i=0 ; i<source->numpoints ; i++)
267         {
268                 l = (i+1)%source->numpoints;
269                 VectorSubtract (source->points[l] , source->points[i], v1);
270
271                 // find a vertex of pass that makes a plane that puts all of the
272                 // vertexes of pass on the front side and all of the vertexes of
273                 // source on the back side
274                 for (j=0 ; j<pass->numpoints ; j++)
275                 {
276                         VectorSubtract (pass->points[j], source->points[i], v2);
277
278                         plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
279                         plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
280                         plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
281                         
282                         // if points don't make a valid plane, skip it
283
284                         length = plane.normal[0] * plane.normal[0]
285                         + plane.normal[1] * plane.normal[1]
286                         + plane.normal[2] * plane.normal[2];
287                         
288                         if (length < ON_EPSILON)
289                                 continue;
290
291                         length = 1/sqrt(length);
292                         
293                         plane.normal[0] *= length;
294                         plane.normal[1] *= length;
295                         plane.normal[2] *= length;
296
297                         plane.dist = DotProduct (pass->points[j], plane.normal);
298
299                         //
300                         // find out which side of the generated seperating plane has the
301                         // source portal
302                         //
303 #if 1
304                         fliptest = qfalse;
305                         for (k=0 ; k<source->numpoints ; k++)
306                         {
307                                 if (k == i || k == l)
308                                         continue;
309                                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
310                                 if (d < -ON_EPSILON)
311                                 {       // source is on the negative side, so we want all
312                                         // pass and target on the positive side
313                                         fliptest = qfalse;
314                                         break;
315                                 }
316                                 else if (d > ON_EPSILON)
317                                 {       // source is on the positive side, so we want all
318                                         // pass and target on the negative side
319                                         fliptest = qtrue;
320                                         break;
321                                 }
322                         }
323                         if (k == source->numpoints)
324                                 continue;               // planar with source portal
325 #else
326                         fliptest = flipclip;
327 #endif
328                         //
329                         // flip the normal if the source portal is backwards
330                         //
331                         if (fliptest)
332                         {
333                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
334                                 plane.dist = -plane.dist;
335                         }
336 #if 1
337                         //
338                         // if all of the pass portal points are now on the positive side,
339                         // this is the seperating plane
340                         //
341                         counts[0] = counts[1] = counts[2] = 0;
342                         for (k=0 ; k<pass->numpoints ; k++)
343                         {
344                                 if (k==j)
345                                         continue;
346                                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
347                                 if (d < -ON_EPSILON)
348                                         break;
349                                 else if (d > ON_EPSILON)
350                                         counts[0]++;
351                                 else
352                                         counts[2]++;
353                         }
354                         if (k != pass->numpoints)
355                                 continue;       // points on negative side, not a seperating plane
356                                 
357                         if (!counts[0])
358                                 continue;       // planar with seperating plane
359 #else
360                         k = (j+1)%pass->numpoints;
361                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;
362                         if (d < -ON_EPSILON)
363                                 continue;
364                         k = (j+pass->numpoints-1)%pass->numpoints;
365                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;
366                         if (d < -ON_EPSILON)
367                                 continue;                       
368 #endif
369                         //
370                         // flip the normal if we want the back side
371                         //
372                         if (flipclip)
373                         {
374                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
375                                 plane.dist = -plane.dist;
376                         }
377
378 #ifdef SEPERATORCACHE
379                         stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
380                         if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
381                                 Error("MAX_SEPERATORS");
382 #endif
383                         //MrE: fast check first
384                         d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
385                         //if completely at the back of the seperator plane
386                         if (d < -stack->portal->radius)
387                                 return NULL;
388                         //if completely on the front of the seperator plane
389                         if (d > stack->portal->radius)
390                                 break;
391
392                         //
393                         // clip target by the seperating plane
394                         //
395                         target = VisChopWinding (target, stack, &plane);
396                         if (!target)
397                                 return NULL;            // target is not visible
398
399                         break;          // optimization by Antony Suter
400                 }
401         }
402         
403         return target;
404 }
405
406 /*
407 ==================
408 RecursiveLeafFlow
409
410 Flood fill through the leafs
411 If src_portal is NULL, this is the originating leaf
412 ==================
413 */
414 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
415 {
416         pstack_t        stack;
417         vportal_t       *p;
418         visPlane_t              backplane;
419         leaf_t          *leaf;
420         int                     i, j, n;
421         long            *test, *might, *prevmight, *vis, more;
422         int                     pnum;
423
424         thread->c_chains++;
425
426         leaf = &leafs[leafnum];
427 //      CheckStack (leaf, thread);
428
429         prevstack->next = &stack;
430
431         stack.next = NULL;
432         stack.leaf = leaf;
433         stack.portal = NULL;
434         stack.depth = prevstack->depth + 1;
435
436 #ifdef SEPERATORCACHE
437         stack.numseperators[0] = 0;
438         stack.numseperators[1] = 0;
439 #endif
440
441         might = (long *)stack.mightsee;
442         vis = (long *)thread->base->portalvis;
443         
444         // check all portals for flowing into other leafs       
445         for (i = 0; i < leaf->numportals; i++)
446         {
447                 p = leaf->portals[i];
448                 if (p->removed)
449                         continue;
450                 pnum = p - portals;
451
452                 /* MrE: portal trace debug code
453                 {
454                         int portaltrace[] = {13, 16, 17, 37};
455                         pstack_t *s;
456
457                         s = &thread->pstack_head;
458                         for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
459                         {
460                                 if (s->portal->num != portaltrace[j])
461                                         break;
462                         }
463                         if (j >= sizeof(portaltrace)/sizeof(int) - 1)
464                         {
465                                 if (p->num == portaltrace[j])
466                                         n = 0; //traced through all the portals
467                         }
468                 }
469                 */
470
471                 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
472                 {
473                         continue;       // can't possibly see it
474                 }
475
476                 // if the portal can't see anything we haven't allready seen, skip it
477                 if (p->status == stat_done)
478                 {
479                         test = (long *)p->portalvis;
480                 }
481                 else
482                 {
483                         test = (long *)p->portalflood;
484                 }
485
486                 more = 0;
487                 prevmight = (long *)prevstack->mightsee;
488                 for (j=0 ; j<portallongs ; j++)
489                 {
490                         might[j] = prevmight[j] & test[j];
491                         more |= (might[j] & ~vis[j]);
492                 }
493                 
494                 if (!more && 
495                         (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
496                 {       // can't see anything new
497                         continue;
498                 }
499
500                 // get plane of portal, point normal into the neighbor leaf
501                 stack.portalplane = p->plane;
502                 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
503                 backplane.dist = -p->plane.dist;
504                 
505 //              c_portalcheck++;
506                 
507                 stack.portal = p;
508                 stack.next = NULL;
509                 stack.freewindings[0] = 1;
510                 stack.freewindings[1] = 1;
511                 stack.freewindings[2] = 1;
512                 
513 #if 1
514                 {
515                         float d;
516
517                         d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
518                         d -= thread->pstack_head.portalplane.dist;
519                         if (d < -p->radius)
520                         {
521                                 continue;
522                         }
523                         else if (d > p->radius)
524                         {
525                                 stack.pass = p->winding;
526                         }
527                         else    
528                         {
529                                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
530                                 if (!stack.pass)
531                                         continue;
532                         }
533                 }
534 #else
535                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
536                 if (!stack.pass)
537                         continue;
538 #endif
539
540         
541 #if 1
542                 {
543                         float d;
544
545                         d = DotProduct (thread->base->origin, p->plane.normal);
546                         d -= p->plane.dist;
547                         //MrE: vis-bug fix
548                         //if (d > p->radius)
549                         if (d > thread->base->radius)
550                         {
551                                 continue;
552                         }
553                         //MrE: vis-bug fix
554                         //if (d < -p->radius)
555                         else if (d < -thread->base->radius)
556                         {
557                                 stack.source = prevstack->source;
558                         }
559                         else    
560                         {
561                                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
562                                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
563                                 if (!stack.source)
564                                         continue;
565                         }
566                 }
567 #else
568                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
569                 if (!stack.source)
570                         continue;
571 #endif
572
573                 if (!prevstack->pass)
574                 {       // the second leaf can only be blocked if coplanar
575
576                         // mark the portal as visible
577                         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
578
579                         RecursiveLeafFlow (p->leaf, thread, &stack);
580                         continue;
581                 }
582
583 #ifdef SEPERATORCACHE
584                 if (stack.numseperators[0])
585                 {
586                         for (n = 0; n < stack.numseperators[0]; n++)
587                         {
588                                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
589                                 if (!stack.pass)
590                                         break;          // target is not visible
591                         }
592                         if (n < stack.numseperators[0])
593                                 continue;
594                 }
595                 else
596                 {
597                         stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
598                 }
599 #else
600                 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
601 #endif
602                 if (!stack.pass)
603                         continue;
604
605 #ifdef SEPERATORCACHE
606                 if (stack.numseperators[1])
607                 {
608                         for (n = 0; n < stack.numseperators[1]; n++)
609                         {
610                                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
611                                 if (!stack.pass)
612                                         break;          // target is not visible
613                         }
614                 }
615                 else
616                 {
617                         stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
618                 }
619 #else
620                 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
621 #endif
622                 if (!stack.pass)
623                         continue;
624
625                 // mark the portal as visible
626                 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
627
628                 // flow through it for real
629                 RecursiveLeafFlow (p->leaf, thread, &stack);
630                 //
631                 stack.next = NULL;
632         }       
633 }
634
635 /*
636 ===============
637 PortalFlow
638
639 generates the portalvis bit vector
640 ===============
641 */
642 void PortalFlow (int portalnum)
643 {
644         threaddata_t    data;
645         int                             i;
646         vportal_t               *p;
647         int                             c_might, c_can;
648
649 #ifdef MREDEBUG
650         Sys_Printf("\r%6d", portalnum);
651 #endif
652
653         p = sorted_portals[portalnum];
654
655         if (p->removed)
656         {
657                 p->status = stat_done;
658                 return;
659         }
660
661         p->status = stat_working;
662
663         c_might = CountBits (p->portalflood, numportals*2);
664
665         memset (&data, 0, sizeof(data));
666         data.base = p;
667         
668         data.pstack_head.portal = p;
669         data.pstack_head.source = p->winding;
670         data.pstack_head.portalplane = p->plane;
671         data.pstack_head.depth = 0;
672         for (i=0 ; i<portallongs ; i++)
673                 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
674
675         RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
676
677         p->status = stat_done;
678
679         c_can = CountBits (p->portalvis, numportals*2);
680
681         Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
682                 (int)(p - portals),     c_might, c_can, data.c_chains);
683 }
684
685 /*
686 ==================
687 RecursivePassageFlow
688 ==================
689 */
690 void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
691 {
692         pstack_t        stack;
693         vportal_t       *p;
694         leaf_t          *leaf;
695         passage_t       *passage, *nextpassage;
696         int                     i, j;
697         long            *might, *vis, *prevmight, *cansee, *portalvis, more;
698         int                     pnum;
699
700         leaf = &leafs[portal->leaf];
701
702         prevstack->next = &stack;
703
704         stack.next = NULL;
705         stack.depth = prevstack->depth + 1;
706
707         vis = (long *)thread->base->portalvis;
708
709         passage = portal->passages;
710         nextpassage = passage;
711         // check all portals for flowing into other leafs       
712         for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
713         {
714                 p = leaf->portals[i];
715                 if ( p->removed ) {
716                         continue;
717                 }
718                 nextpassage = passage->next;
719                 pnum = p - portals;
720
721                 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
722                         continue;       // can't possibly see it
723                 }
724
725                 // mark the portal as visible
726                 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
727
728                 prevmight = (long *)prevstack->mightsee;
729                 cansee = (long *)passage->cansee;
730                 might = (long *)stack.mightsee;
731                 memcpy(might, prevmight, portalbytes);
732                 if (p->status == stat_done)
733                         portalvis = (long *) p->portalvis;
734                 else
735                         portalvis = (long *) p->portalflood;
736                 more = 0;
737                 for (j = 0; j < portallongs; j++)
738                 {
739                         if (*might)
740                         {
741                                 *might &= *cansee++ & *portalvis++;
742                                 more |= (*might & ~vis[j]);
743                         }
744                         else
745                         {
746                                 cansee++;
747                                 portalvis++;
748                         }
749                         might++;
750                 }
751
752                 if ( !more ) {
753                         // can't see anything new
754                         continue;
755                 }
756
757                 // flow through it for real
758                 RecursivePassageFlow(p, thread, &stack);
759
760                 stack.next = NULL;
761         }
762 }
763
764 /*
765 ===============
766 PassageFlow
767 ===============
768 */
769 void PassageFlow (int portalnum)
770 {
771         threaddata_t    data;
772         int                             i;
773         vportal_t               *p;
774 //      int                             c_might, c_can;
775
776 #ifdef MREDEBUG
777         Sys_Printf("\r%6d", portalnum);
778 #endif
779
780         p = sorted_portals[portalnum];
781
782         if (p->removed)
783         {
784                 p->status = stat_done;
785                 return;
786         }
787
788         p->status = stat_working;
789
790 //      c_might = CountBits (p->portalflood, numportals*2);
791
792         memset (&data, 0, sizeof(data));
793         data.base = p;
794         
795         data.pstack_head.portal = p;
796         data.pstack_head.source = p->winding;
797         data.pstack_head.portalplane = p->plane;
798         data.pstack_head.depth = 0;
799         for (i=0 ; i<portallongs ; i++)
800                 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
801
802         RecursivePassageFlow (p, &data, &data.pstack_head);
803
804         p->status = stat_done;
805
806         /*
807         c_can = CountBits (p->portalvis, numportals*2);
808
809         Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
810                 (int)(p - portals),     c_might, c_can, data.c_chains);
811         */
812 }
813
814 /*
815 ==================
816 RecursivePassagePortalFlow
817 ==================
818 */
819 void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
820 {
821         pstack_t        stack;
822         vportal_t       *p;
823         leaf_t          *leaf;
824         visPlane_t              backplane;
825         passage_t       *passage, *nextpassage;
826         int                     i, j, n;
827         long            *might, *vis, *prevmight, *cansee, *portalvis, more;
828         int                     pnum;
829
830 //      thread->c_chains++;
831
832         leaf = &leafs[portal->leaf];
833 //      CheckStack (leaf, thread);
834
835         prevstack->next = &stack;
836
837         stack.next = NULL;
838         stack.leaf = leaf;
839         stack.portal = NULL;
840         stack.depth = prevstack->depth + 1;
841
842 #ifdef SEPERATORCACHE
843         stack.numseperators[0] = 0;
844         stack.numseperators[1] = 0;
845 #endif
846
847         vis = (long *)thread->base->portalvis;
848
849         passage = portal->passages;
850         nextpassage = passage;
851         // check all portals for flowing into other leafs       
852         for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
853         {
854                 p = leaf->portals[i];
855                 if (p->removed)
856                         continue;
857                 nextpassage = passage->next;
858                 pnum = p - portals;
859
860                 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
861                         continue;       // can't possibly see it
862
863                 prevmight = (long *)prevstack->mightsee;
864                 cansee = (long *)passage->cansee;
865                 might = (long *)stack.mightsee;
866                 memcpy(might, prevmight, portalbytes);
867                 if (p->status == stat_done)
868                         portalvis = (long *) p->portalvis;
869                 else
870                         portalvis = (long *) p->portalflood;
871                 more = 0;
872                 for (j = 0; j < portallongs; j++)
873                 {
874                         if (*might)
875                         {
876                                 *might &= *cansee++ & *portalvis++;
877                                 more |= (*might & ~vis[j]);
878                         }
879                         else
880                         {
881                                 cansee++;
882                                 portalvis++;
883                         }
884                         might++;
885                 }
886
887                 if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
888                 {       // can't see anything new
889                         continue;
890                 }
891
892                 // get plane of portal, point normal into the neighbor leaf
893                 stack.portalplane = p->plane;
894                 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
895                 backplane.dist = -p->plane.dist;
896                 
897 //              c_portalcheck++;
898                 
899                 stack.portal = p;
900                 stack.next = NULL;
901                 stack.freewindings[0] = 1;
902                 stack.freewindings[1] = 1;
903                 stack.freewindings[2] = 1;
904
905 #if 1
906                 {
907                         float d;
908
909                         d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
910                         d -= thread->pstack_head.portalplane.dist;
911                         if (d < -p->radius)
912                         {
913                                 continue;
914                         }
915                         else if (d > p->radius)
916                         {
917                                 stack.pass = p->winding;
918                         }
919                         else    
920                         {
921                                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
922                                 if (!stack.pass)
923                                         continue;
924                         }
925                 }
926 #else
927                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
928                 if (!stack.pass)
929                         continue;
930 #endif
931
932         
933 #if 1
934                 {
935                         float d;
936
937                         d = DotProduct (thread->base->origin, p->plane.normal);
938                         d -= p->plane.dist;
939                         //MrE: vis-bug fix
940                         //if (d > p->radius)
941                         if (d > thread->base->radius)
942                         {
943                                 continue;
944                         }
945                         //MrE: vis-bug fix
946                         //if (d < -p->radius)
947                         else if (d < -thread->base->radius)
948                         {
949                                 stack.source = prevstack->source;
950                         }
951                         else    
952                         {
953                                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
954                                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
955                                 if (!stack.source)
956                                         continue;
957                         }
958                 }
959 #else
960                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
961                 if (!stack.source)
962                         continue;
963 #endif
964
965                 if (!prevstack->pass)
966                 {       // the second leaf can only be blocked if coplanar
967
968                         // mark the portal as visible
969                         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
970
971                         RecursivePassagePortalFlow (p, thread, &stack);
972                         continue;
973                 }
974
975 #ifdef SEPERATORCACHE
976                 if (stack.numseperators[0])
977                 {
978                         for (n = 0; n < stack.numseperators[0]; n++)
979                         {
980                                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
981                                 if (!stack.pass)
982                                         break;          // target is not visible
983                         }
984                         if (n < stack.numseperators[0])
985                                 continue;
986                 }
987                 else
988                 {
989                         stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
990                 }
991 #else
992                 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
993 #endif
994                 if (!stack.pass)
995                         continue;
996
997 #ifdef SEPERATORCACHE
998                 if (stack.numseperators[1])
999                 {
1000                         for (n = 0; n < stack.numseperators[1]; n++)
1001                         {
1002                                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
1003                                 if (!stack.pass)
1004                                         break;          // target is not visible
1005                         }
1006                 }
1007                 else
1008                 {
1009                         stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
1010                 }
1011 #else
1012                 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
1013 #endif
1014                 if (!stack.pass)
1015                         continue;
1016
1017                 // mark the portal as visible
1018                 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
1019
1020                 // flow through it for real
1021                 RecursivePassagePortalFlow(p, thread, &stack);
1022                 //
1023                 stack.next = NULL;
1024         }
1025 }
1026
1027 /*
1028 ===============
1029 PassagePortalFlow
1030 ===============
1031 */
1032 void PassagePortalFlow (int portalnum)
1033 {
1034         threaddata_t    data;
1035         int                             i;
1036         vportal_t               *p;
1037 //      int                             c_might, c_can;
1038
1039 #ifdef MREDEBUG
1040         Sys_Printf("\r%6d", portalnum);
1041 #endif
1042
1043         p = sorted_portals[portalnum];
1044
1045         if (p->removed)
1046         {
1047                 p->status = stat_done;
1048                 return;
1049         }
1050
1051         p->status = stat_working;
1052
1053 //      c_might = CountBits (p->portalflood, numportals*2);
1054
1055         memset (&data, 0, sizeof(data));
1056         data.base = p;
1057         
1058         data.pstack_head.portal = p;
1059         data.pstack_head.source = p->winding;
1060         data.pstack_head.portalplane = p->plane;
1061         data.pstack_head.depth = 0;
1062         for (i=0 ; i<portallongs ; i++)
1063                 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
1064
1065         RecursivePassagePortalFlow (p, &data, &data.pstack_head);
1066
1067         p->status = stat_done;
1068
1069         /*
1070         c_can = CountBits (p->portalvis, numportals*2);
1071
1072         Sys_FPrintf (SYS_VRB,"portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
1073                 (int)(p - portals),     c_might, c_can, data.c_chains);
1074         */
1075 }
1076
1077 fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split)
1078 {
1079         vec_t   dists[128];
1080         int             sides[128];
1081         int             counts[3];
1082         vec_t   dot;
1083         int             i, j;
1084         vec_t   *p1, *p2;
1085         vec3_t  mid;
1086         fixedWinding_t  *neww;
1087
1088         counts[0] = counts[1] = counts[2] = 0;
1089
1090         // determine sides for each point
1091         for (i=0 ; i<in->numpoints ; i++)
1092         {
1093                 dot = DotProduct (in->points[i], split->normal);
1094                 dot -= split->dist;
1095                 dists[i] = dot;
1096                 if (dot > ON_EPSILON)
1097                         sides[i] = SIDE_FRONT;
1098                 else if (dot < -ON_EPSILON)
1099                         sides[i] = SIDE_BACK;
1100                 else
1101                 {
1102                         sides[i] = SIDE_ON;
1103                 }
1104                 counts[sides[i]]++;
1105         }
1106
1107         if (!counts[1])
1108                 return in;              // completely on front side
1109         
1110         if (!counts[0])
1111         {
1112                 return NULL;
1113         }
1114
1115         sides[i] = sides[0];
1116         dists[i] = dists[0];
1117         
1118         neww = out;
1119
1120         neww->numpoints = 0;
1121
1122         for (i=0 ; i<in->numpoints ; i++)
1123         {
1124                 p1 = in->points[i];
1125
1126                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1127                 {
1128                         return in;              // can't chop -- fall back to original
1129                 }
1130
1131                 if (sides[i] == SIDE_ON)
1132                 {
1133                         VectorCopy (p1, neww->points[neww->numpoints]);
1134                         neww->numpoints++;
1135                         continue;
1136                 }
1137         
1138                 if (sides[i] == SIDE_FRONT)
1139                 {
1140                         VectorCopy (p1, neww->points[neww->numpoints]);
1141                         neww->numpoints++;
1142                 }
1143                 
1144                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1145                         continue;
1146                         
1147                 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1148                 {
1149                         return in;              // can't chop -- fall back to original
1150                 }
1151
1152                 // generate a split point
1153                 p2 = in->points[(i+1)%in->numpoints];
1154                 
1155                 dot = dists[i] / (dists[i]-dists[i+1]);
1156                 for (j=0 ; j<3 ; j++)
1157                 {       // avoid round off error when possible
1158                         if (split->normal[j] == 1)
1159                                 mid[j] = split->dist;
1160                         else if (split->normal[j] == -1)
1161                                 mid[j] = -split->dist;
1162                         else
1163                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1164                 }
1165                         
1166                 VectorCopy (mid, neww->points[neww->numpoints]);
1167                 neww->numpoints++;
1168         }
1169         
1170         return neww;
1171 }
1172
1173 /*
1174 ===============
1175 AddSeperators
1176 ===============
1177 */
1178 int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators)
1179 {
1180         int                     i, j, k, l;
1181         visPlane_t              plane;
1182         vec3_t          v1, v2;
1183         float           d;
1184         vec_t           length;
1185         int                     counts[3], numseperators;
1186         qboolean        fliptest;
1187
1188         numseperators = 0;
1189         // check all combinations       
1190         for (i=0 ; i<source->numpoints ; i++)
1191         {
1192                 l = (i+1)%source->numpoints;
1193                 VectorSubtract (source->points[l] , source->points[i], v1);
1194
1195                 // find a vertex of pass that makes a plane that puts all of the
1196                 // vertexes of pass on the front side and all of the vertexes of
1197                 // source on the back side
1198                 for (j=0 ; j<pass->numpoints ; j++)
1199                 {
1200                         VectorSubtract (pass->points[j], source->points[i], v2);
1201
1202                         plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
1203                         plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
1204                         plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
1205                         
1206                         // if points don't make a valid plane, skip it
1207
1208                         length = plane.normal[0] * plane.normal[0]
1209                         + plane.normal[1] * plane.normal[1]
1210                         + plane.normal[2] * plane.normal[2];
1211                         
1212                         if (length < ON_EPSILON)
1213                                 continue;
1214
1215                         length = 1/sqrt(length);
1216                         
1217                         plane.normal[0] *= length;
1218                         plane.normal[1] *= length;
1219                         plane.normal[2] *= length;
1220
1221                         plane.dist = DotProduct (pass->points[j], plane.normal);
1222
1223                         //
1224                         // find out which side of the generated seperating plane has the
1225                         // source portal
1226                         //
1227 #if 1
1228                         fliptest = qfalse;
1229                         for (k=0 ; k<source->numpoints ; k++)
1230                         {
1231                                 if (k == i || k == l)
1232                                         continue;
1233                                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
1234                                 if (d < -ON_EPSILON)
1235                                 {       // source is on the negative side, so we want all
1236                                         // pass and target on the positive side
1237                                         fliptest = qfalse;
1238                                         break;
1239                                 }
1240                                 else if (d > ON_EPSILON)
1241                                 {       // source is on the positive side, so we want all
1242                                         // pass and target on the negative side
1243                                         fliptest = qtrue;
1244                                         break;
1245                                 }
1246                         }
1247                         if (k == source->numpoints)
1248                                 continue;               // planar with source portal
1249 #else
1250                         fliptest = flipclip;
1251 #endif
1252                         //
1253                         // flip the normal if the source portal is backwards
1254                         //
1255                         if (fliptest)
1256                         {
1257                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1258                                 plane.dist = -plane.dist;
1259                         }
1260 #if 1
1261                         //
1262                         // if all of the pass portal points are now on the positive side,
1263                         // this is the seperating plane
1264                         //
1265                         counts[0] = counts[1] = counts[2] = 0;
1266                         for (k=0 ; k<pass->numpoints ; k++)
1267                         {
1268                                 if (k==j)
1269                                         continue;
1270                                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1271                                 if (d < -ON_EPSILON)
1272                                         break;
1273                                 else if (d > ON_EPSILON)
1274                                         counts[0]++;
1275                                 else
1276                                         counts[2]++;
1277                         }
1278                         if (k != pass->numpoints)
1279                                 continue;       // points on negative side, not a seperating plane
1280                                 
1281                         if (!counts[0])
1282                                 continue;       // planar with seperating plane
1283 #else
1284                         k = (j+1)%pass->numpoints;
1285                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1286                         if (d < -ON_EPSILON)
1287                                 continue;
1288                         k = (j+pass->numpoints-1)%pass->numpoints;
1289                         d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1290                         if (d < -ON_EPSILON)
1291                                 continue;                       
1292 #endif
1293                         //
1294                         // flip the normal if we want the back side
1295                         //
1296                         if (flipclip)
1297                         {
1298                                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1299                                 plane.dist = -plane.dist;
1300                         }
1301
1302                         if (numseperators >= maxseperators)
1303                                 Error("max seperators");
1304                         seperators[numseperators] = plane;
1305                         numseperators++;
1306                         break;
1307                 }
1308         }
1309         return numseperators;
1310 }
1311
1312 /*
1313 ===============
1314 CreatePassages
1315
1316 MrE: create passages from one portal to all the portals in the leaf the portal leads to
1317          every passage has a cansee bit string with all the portals that can be
1318          seen through the passage
1319 ===============
1320 */
1321 void CreatePassages(int portalnum)
1322 {
1323         int                             i, j, k, n, numseperators, numsee;
1324         float                   d;
1325         vportal_t               *portal, *p, *target;
1326         leaf_t                  *leaf;
1327         passage_t               *passage, *lastpassage;
1328         visPlane_t              seperators[MAX_SEPERATORS*2];
1329         fixedWinding_t  *w;
1330         fixedWinding_t  in, out, *res;
1331         
1332         
1333 #ifdef MREDEBUG
1334         Sys_Printf("\r%6d", portalnum);
1335 #endif
1336
1337         portal = sorted_portals[portalnum];
1338
1339         if (portal->removed)
1340         {
1341                 portal->status = stat_done;
1342                 return;
1343         }
1344
1345         lastpassage = NULL;
1346         leaf = &leafs[portal->leaf];
1347         for (i = 0; i < leaf->numportals; i++)
1348         {
1349                 target = leaf->portals[i];
1350                 if (target->removed)
1351                         continue;
1352
1353                 passage = (passage_t *) safe_malloc(sizeof(passage_t) + portalbytes);
1354                 memset(passage, 0, sizeof(passage_t) + portalbytes);
1355                 numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
1356                 numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
1357
1358                 passage->next = NULL;
1359                 if (lastpassage)
1360                         lastpassage->next = passage;
1361                 else
1362                         portal->passages = passage;
1363                 lastpassage = passage;
1364
1365                 numsee = 0;
1366                 //create the passage->cansee
1367                 for (j = 0; j < numportals * 2; j++)
1368                 {
1369                         p = &portals[j];
1370                         if (p->removed)
1371                                 continue;
1372                         if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
1373                                 continue;
1374                         if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
1375                                 continue;
1376                         for (k = 0; k < numseperators; k++)
1377                         {
1378                                 //
1379                                 d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
1380                                 //if completely at the back of the seperator plane
1381                                 if (d < -p->radius + ON_EPSILON)
1382                                         break;
1383                                 w = p->winding;
1384                                 for (n = 0; n < w->numpoints; n++)
1385                                 {
1386                                         d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
1387                                         //if at the front of the seperator
1388                                         if (d > ON_EPSILON)
1389                                                 break;
1390                                 }
1391                                 //if no points are at the front of the seperator
1392                                 if (n >= w->numpoints)
1393                                         break;
1394                         }
1395                         if (k < numseperators)
1396                                 continue;
1397                         
1398                         /* explitive deleted */
1399                         
1400                         
1401                         /* ydnar: prefer correctness to stack overflow  */
1402                         //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1403                         if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING )
1404                                 memcpy( &in, p->winding, (size_t) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) );
1405                         else
1406                                 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1407                         
1408                         
1409                         for( k = 0; k < numseperators; k++ )
1410                         {
1411                                 /* ydnar: this is a shitty crutch */
1412                                 if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING )
1413                                 {
1414                                         //% Sys_Printf( "[%d]", p->winding->numpoints );
1415                                         in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1416                                 }
1417                                 
1418                                 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1419                                 if( res == &out )
1420                                         memcpy( &in, &out, sizeof( fixedWinding_t ) );
1421
1422                         
1423                                 if( res == NULL )
1424                                         break;
1425                         }
1426                         if (k < numseperators)
1427                                 continue;
1428                         passage->cansee[j >> 3] |= (1<<(j&7));
1429                         numsee++;
1430                 }
1431         }
1432 }
1433
1434 void PassageMemory(void)
1435 {
1436         int i, j, totalmem, totalportals;
1437         vportal_t *portal, *target;
1438         leaf_t *leaf;
1439
1440         totalmem = 0;
1441         totalportals = 0;
1442         for (i = 0; i < numportals; i++)
1443         {
1444                 portal = sorted_portals[i];
1445                 if (portal->removed)
1446                         continue;
1447                 leaf = &leafs[portal->leaf];
1448                 for (j = 0; j < leaf->numportals; j++)
1449                 {
1450                         target = leaf->portals[j];
1451                         if (target->removed)
1452                                 continue;
1453                         totalmem += sizeof(passage_t) + portalbytes;
1454                         totalportals++;
1455                 }
1456         }
1457         Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals);
1458         Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
1459 }
1460
1461 /*
1462 ===============================================================================
1463
1464 This is a rough first-order aproximation that is used to trivially reject some
1465 of the final calculations.
1466
1467
1468 Calculates portalfront and portalflood bit vectors
1469
1470 thinking about:
1471
1472 typedef struct passage_s
1473 {
1474         struct passage_s        *next;
1475         struct portal_s         *to;
1476         stryct sep_s            *seperators;
1477         byte                            *mightsee;
1478 } passage_t;
1479
1480 typedef struct portal_s
1481 {
1482         struct passage_s        *passages;
1483         int                                     leaf;           // leaf portal faces into
1484 } portal_s;
1485
1486 leaf = portal->leaf
1487 clear 
1488 for all portals
1489
1490
1491 calc portal visibility
1492         clear bit vector
1493         for all passages
1494                 passage visibility
1495
1496
1497 for a portal to be visible to a passage, it must be on the front of
1498 all seperating planes, and both portals must be behind the new portal
1499
1500 ===============================================================================
1501 */
1502
1503 int             c_flood, c_vis;
1504
1505
1506 /*
1507 ==================
1508 SimpleFlood
1509
1510 ==================
1511 */
1512 void SimpleFlood (vportal_t *srcportal, int leafnum)
1513 {
1514         int             i;
1515         leaf_t  *leaf;
1516         vportal_t       *p;
1517         int             pnum;
1518
1519         leaf = &leafs[leafnum];
1520         
1521         for (i=0 ; i<leaf->numportals ; i++)
1522         {
1523                 p = leaf->portals[i];
1524                 if (p->removed)
1525                         continue;
1526                 pnum = p - portals;
1527                 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
1528                         continue;
1529
1530                 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
1531                         continue;
1532
1533                 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
1534                 
1535                 SimpleFlood (srcportal, p->leaf);
1536         }
1537 }
1538
1539 /*
1540 ==============
1541 BasePortalVis
1542 ==============
1543 */
1544 void BasePortalVis( int portalnum )
1545 {
1546         int                     j, k;
1547         vportal_t       *tp, *p;
1548         float           d;
1549         fixedWinding_t  *w;
1550         vec3_t          dir;
1551         
1552
1553         p = portals+portalnum;
1554
1555         if (p->removed)
1556                 return;
1557
1558         p->portalfront = safe_malloc (portalbytes);
1559         memset (p->portalfront, 0, portalbytes);
1560
1561         p->portalflood = safe_malloc (portalbytes);
1562         memset (p->portalflood, 0, portalbytes);
1563         
1564         p->portalvis = safe_malloc (portalbytes);
1565         memset (p->portalvis, 0, portalbytes);
1566         
1567         for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
1568         {
1569                 if( j == portalnum )
1570                         continue;
1571                 if( tp->removed )
1572                         continue;
1573
1574                 /* ydnar: this is old farplane vis code from mre */
1575                 /*
1576                 if (farplanedist >= 0)
1577                 {
1578                         vec3_t dir;
1579                         VectorSubtract(p->origin, tp->origin, dir);
1580                         if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1581                                 continue;
1582                 }
1583                 */
1584                 
1585                 /* ydnar: this is known-to-be-working farplane code */
1586                 if( farPlaneDist > 0.0f )
1587                 {
1588                         VectorSubtract( p->origin, tp->origin, dir );
1589                         if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist )
1590                                 continue;
1591                 }
1592                 
1593                 
1594                 w = tp->winding;
1595                 for (k=0 ; k<w->numpoints ; k++)
1596                 {
1597                         d = DotProduct (w->points[k], p->plane.normal)
1598                                 - p->plane.dist;
1599                         if (d > ON_EPSILON)
1600                                 break;
1601                 }
1602                 if (k == w->numpoints)
1603                         continue;       // no points on front
1604
1605                 w = p->winding;
1606                 for (k=0 ; k<w->numpoints ; k++)
1607                 {
1608                         d = DotProduct (w->points[k], tp->plane.normal)
1609                                 - tp->plane.dist;
1610                         if (d < -ON_EPSILON)
1611                                 break;
1612                 }
1613                 if (k == w->numpoints)
1614                         continue;       // no points on front
1615
1616                 p->portalfront[j>>3] |= (1<<(j&7));
1617         }
1618         
1619         SimpleFlood (p, p->leaf);
1620
1621         p->nummightsee = CountBits (p->portalflood, numportals*2);
1622 //      Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1623         c_flood += p->nummightsee;
1624 }
1625
1626
1627
1628
1629
1630 /*
1631 ===============================================================================
1632
1633 This is a second order aproximation 
1634
1635 Calculates portalvis bit vector
1636
1637 WAAAAAAY too slow.
1638
1639 ===============================================================================
1640 */
1641
1642 /*
1643 ==================
1644 RecursiveLeafBitFlow
1645
1646 ==================
1647 */
1648 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
1649 {
1650         vportal_t       *p;
1651         leaf_t          *leaf;
1652         int                     i, j;
1653         long            more;
1654         int                     pnum;
1655         byte            newmight[MAX_PORTALS/8];
1656
1657         leaf = &leafs[leafnum];
1658         
1659         // check all portals for flowing into other leafs
1660         for (i=0 ; i<leaf->numportals ; i++)
1661         {
1662                 p = leaf->portals[i];
1663                 if (p->removed)
1664                         continue;
1665                 pnum = p - portals;
1666
1667                 // if some previous portal can't see it, skip
1668                 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
1669                         continue;
1670
1671                 // if this portal can see some portals we mightsee, recurse
1672                 more = 0;
1673                 for (j=0 ; j<portallongs ; j++)
1674                 {
1675                         ((long *)newmight)[j] = ((long *)mightsee)[j] 
1676                                 & ((long *)p->portalflood)[j];
1677                         more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
1678                 }
1679
1680                 if (!more)
1681                         continue;       // can't see anything new
1682
1683                 cansee[pnum>>3] |= (1<<(pnum&7));
1684
1685                 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
1686         }       
1687 }
1688
1689 /*
1690 ==============
1691 BetterPortalVis
1692 ==============
1693 */
1694 void BetterPortalVis (int portalnum)
1695 {
1696         vportal_t       *p;
1697
1698         p = portals+portalnum;
1699
1700         if (p->removed)
1701                 return;
1702
1703         RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
1704
1705         // build leaf vis information
1706         p->nummightsee = CountBits (p->portalvis, numportals*2);
1707         c_vis += p->nummightsee;
1708 }
1709
1710