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