]> de.git.xonotic.org Git - xonotic/netradiant.git/blob - tools/quake3/q3map2/visflow.c
q3map2: use safe_malloc0 when safe_malloc is followed by a memset to 0 with the same...
[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_malloc0( sizeof( passage_t ) + portalbytes );
1368                 numseperators = AddSeperators( portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS * 2 );
1369                 numseperators += AddSeperators( target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS * 2 - numseperators );
1370
1371                 passage->next = NULL;
1372                 if ( lastpassage ) {
1373                         lastpassage->next = passage;
1374                 }
1375                 else{
1376                         portal->passages = passage;
1377                 }
1378                 lastpassage = passage;
1379
1380                 numsee = 0;
1381                 //create the passage->cansee
1382                 for ( j = 0; j < numportals * 2; j++ )
1383                 {
1384                         p = &portals[j];
1385                         if ( p->removed ) {
1386                                 continue;
1387                         }
1388                         if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1389                                 continue;
1390                         }
1391                         if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1392                                 continue;
1393                         }
1394                         for ( k = 0; k < numseperators; k++ )
1395                         {
1396                                 //
1397                                 d = DotProduct( p->origin, seperators[k].normal ) - seperators[k].dist;
1398                                 //if completely at the back of the seperator plane
1399                                 if ( d < -p->radius + ON_EPSILON ) {
1400                                         break;
1401                                 }
1402                                 w = p->winding;
1403                                 for ( n = 0; n < w->numpoints; n++ )
1404                                 {
1405                                         d = DotProduct( w->points[n], seperators[k].normal ) - seperators[k].dist;
1406                                         //if at the front of the seperator
1407                                         if ( d > ON_EPSILON ) {
1408                                                 break;
1409                                         }
1410                                 }
1411                                 //if no points are at the front of the seperator
1412                                 if ( n >= w->numpoints ) {
1413                                         break;
1414                                 }
1415                         }
1416                         if ( k < numseperators ) {
1417                                 continue;
1418                         }
1419
1420                         /* explitive deleted */
1421
1422
1423                         /* ydnar: prefer correctness to stack overflow  */
1424                         //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1425                         if ( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) {
1426                                 memcpy( &in, p->winding, (size_t) &( ( (fixedWinding_t*) 0 )->points[ p->winding->numpoints ] ) );
1427                         }
1428                         else{
1429                                 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1430                         }
1431
1432
1433                         for ( k = 0; k < numseperators; k++ )
1434                         {
1435                                 /* ydnar: this is a shitty crutch */
1436                                 if ( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) {
1437                                         //% Sys_Printf( "[%d]", p->winding->numpoints );
1438                                         in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1439                                 }
1440
1441                                 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1442                                 if ( res == &out ) {
1443                                         memcpy( &in, &out, sizeof( fixedWinding_t ) );
1444                                 }
1445
1446
1447                                 if ( res == NULL ) {
1448                                         break;
1449                                 }
1450                         }
1451                         if ( k < numseperators ) {
1452                                 continue;
1453                         }
1454                         passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) );
1455                         numsee++;
1456                 }
1457         }
1458 }
1459
1460 void PassageMemory( void ){
1461         int i, j, totalmem, totalportals;
1462         vportal_t *portal, *target;
1463         leaf_t *leaf;
1464
1465         totalmem = 0;
1466         totalportals = 0;
1467         for ( i = 0; i < numportals; i++ )
1468         {
1469                 portal = sorted_portals[i];
1470                 if ( portal->removed ) {
1471                         continue;
1472                 }
1473                 leaf = &leafs[portal->leaf];
1474                 for ( j = 0; j < leaf->numportals; j++ )
1475                 {
1476                         target = leaf->portals[j];
1477                         if ( target->removed ) {
1478                                 continue;
1479                         }
1480                         totalmem += sizeof( passage_t ) + portalbytes;
1481                         totalportals++;
1482                 }
1483         }
1484         Sys_Printf( "%7i average number of passages per leaf\n", totalportals / numportals );
1485         Sys_Printf( "%7i MB required passage memory\n", totalmem >> 10 >> 10 );
1486 }
1487
1488 /*
1489    ===============================================================================
1490
1491    This is a rough first-order aproximation that is used to trivially reject some
1492    of the final calculations.
1493
1494
1495    Calculates portalfront and portalflood bit vectors
1496
1497    thinking about:
1498
1499    typedef struct passage_s
1500    {
1501     struct passage_s    *next;
1502     struct portal_s             *to;
1503     stryct sep_s                *seperators;
1504     byte                                *mightsee;
1505    } passage_t;
1506
1507    typedef struct portal_s
1508    {
1509     struct passage_s    *passages;
1510     int                                 leaf;           // leaf portal faces into
1511    } portal_s;
1512
1513    leaf = portal->leaf
1514    clear
1515    for all portals
1516
1517
1518    calc portal visibility
1519     clear bit vector
1520     for all passages
1521         passage visibility
1522
1523
1524    for a portal to be visible to a passage, it must be on the front of
1525    all seperating planes, and both portals must be behind the new portal
1526
1527    ===============================================================================
1528  */
1529
1530 int c_flood, c_vis;
1531
1532
1533 /*
1534    ==================
1535    SimpleFlood
1536
1537    ==================
1538  */
1539 void SimpleFlood( vportal_t *srcportal, int leafnum ){
1540         int i;
1541         leaf_t  *leaf;
1542         vportal_t   *p;
1543         int pnum;
1544
1545         leaf = &leafs[leafnum];
1546
1547         for ( i = 0 ; i < leaf->numportals ; i++ )
1548         {
1549                 p = leaf->portals[i];
1550                 if ( p->removed ) {
1551                         continue;
1552                 }
1553                 pnum = p - portals;
1554                 if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1555                         continue;
1556                 }
1557
1558                 if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) {
1559                         continue;
1560                 }
1561
1562                 srcportal->portalflood[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1563
1564                 SimpleFlood( srcportal, p->leaf );
1565         }
1566 }
1567
1568 /*
1569    ==============
1570    BasePortalVis
1571    ==============
1572  */
1573 void BasePortalVis( int portalnum ){
1574         int j, k;
1575         vportal_t   *tp, *p;
1576         float d;
1577         fixedWinding_t  *w;
1578         vec3_t dir;
1579
1580
1581         p = portals + portalnum;
1582
1583         if ( p->removed ) {
1584                 return;
1585         }
1586
1587         p->portalfront = safe_malloc0( portalbytes );
1588
1589         p->portalflood = safe_malloc0( portalbytes );
1590
1591         p->portalvis = safe_malloc0( portalbytes );
1592
1593         for ( j = 0, tp = portals ; j < numportals * 2 ; j++, tp++ )
1594         {
1595                 if ( j == portalnum ) {
1596                         continue;
1597                 }
1598                 if ( tp->removed ) {
1599                         continue;
1600                 }
1601
1602                 /* ydnar: this is old farplane vis code from mre */
1603                 /*
1604                    if (farplanedist >= 0)
1605                    {
1606                     vec3_t dir;
1607                     VectorSubtract(p->origin, tp->origin, dir);
1608                     if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1609                         continue;
1610                    }
1611                  */
1612
1613                 /* ydnar: this is known-to-be-working farplane code */
1614                 if ( !p->sky && !tp->sky && farPlaneDist > 0.0f ) {
1615                         VectorSubtract( p->origin, tp->origin, dir );
1616                         if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) {
1617                                 continue;
1618                         }
1619                 }
1620
1621
1622                 w = tp->winding;
1623                 for ( k = 0 ; k < w->numpoints ; k++ )
1624                 {
1625                         d = DotProduct( w->points[k], p->plane.normal )
1626                                 - p->plane.dist;
1627                         if ( d > ON_EPSILON ) {
1628                                 break;
1629                         }
1630                 }
1631                 if ( k == w->numpoints ) {
1632                         continue;   // no points on front
1633
1634                 }
1635                 w = p->winding;
1636                 for ( k = 0 ; k < w->numpoints ; k++ )
1637                 {
1638                         d = DotProduct( w->points[k], tp->plane.normal )
1639                                 - tp->plane.dist;
1640                         if ( d < -ON_EPSILON ) {
1641                                 break;
1642                         }
1643                 }
1644                 if ( k == w->numpoints ) {
1645                         continue;   // no points on front
1646
1647                 }
1648                 p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) );
1649         }
1650
1651         SimpleFlood( p, p->leaf );
1652
1653         p->nummightsee = CountBits( p->portalflood, numportals * 2 );
1654 //      Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1655         c_flood += p->nummightsee;
1656 }
1657
1658
1659
1660
1661
1662 /*
1663    ===============================================================================
1664
1665    This is a second order aproximation
1666
1667    Calculates portalvis bit vector
1668
1669    WAAAAAAY too slow.
1670
1671    ===============================================================================
1672  */
1673
1674 /*
1675    ==================
1676    RecursiveLeafBitFlow
1677
1678    ==================
1679  */
1680 void RecursiveLeafBitFlow( int leafnum, byte *mightsee, byte *cansee ){
1681         vportal_t   *p;
1682         leaf_t      *leaf;
1683         int i, j;
1684         long more;
1685         int pnum;
1686         byte newmight[MAX_PORTALS / 8];
1687
1688         leaf = &leafs[leafnum];
1689
1690         // check all portals for flowing into other leafs
1691         for ( i = 0 ; i < leaf->numportals ; i++ )
1692         {
1693                 p = leaf->portals[i];
1694                 if ( p->removed ) {
1695                         continue;
1696                 }
1697                 pnum = p - portals;
1698
1699                 // if some previous portal can't see it, skip
1700                 if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1701                         continue;
1702                 }
1703
1704                 // if this portal can see some portals we mightsee, recurse
1705                 more = 0;
1706                 for ( j = 0 ; j < portallongs ; j++ )
1707                 {
1708                         ( (long *)newmight )[j] = ( (long *)mightsee )[j]
1709                                                                           & ( (long *)p->portalflood )[j];
1710                         more |= ( (long *)newmight )[j] & ~( (long *)cansee )[j];
1711                 }
1712
1713                 if ( !more ) {
1714                         continue;   // can't see anything new
1715
1716                 }
1717                 cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1718
1719                 RecursiveLeafBitFlow( p->leaf, newmight, cansee );
1720         }
1721 }
1722
1723 /*
1724    ==============
1725    BetterPortalVis
1726    ==============
1727  */
1728 void BetterPortalVis( int portalnum ){
1729         vportal_t   *p;
1730
1731         p = portals + portalnum;
1732
1733         if ( p->removed ) {
1734                 return;
1735         }
1736
1737         RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis );
1738
1739         // build leaf vis information
1740         p->nummightsee = CountBits( p->portalvis, numportals * 2 );
1741         c_vis += p->nummightsee;
1742 }