1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
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.
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.
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
22 ----------------------------------------------------------------------------------
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."
27 ------------------------------------------------------------------------------- */
44 each portal will have a list of all possible to see from first portal
46 if (!thread->portalmightsee[portalnum])
50 for p2 = all other portals in leaf
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
58 void CalcMightSee (leaf_t *leaf,
61 int CountBits( byte *bits, int numbits ){
66 for ( i = 0 ; i < numbits ; i++ )
67 if ( bits[i >> 3] & ( 1 << ( i & 7 ) ) ) {
75 int c_portalskip, c_leafskip;
76 int c_vistest, c_mighttest;
82 void CheckStack( leaf_t *leaf, threaddata_t *thread ){
85 for ( p = thread->pstack_head.next ; p ; p = p->next )
88 if ( p->leaf == leaf ) {
89 Error( "CheckStack: leaf recursion" );
91 for ( p2 = thread->pstack_head.next ; p2 != p ; p2 = p2->next )
92 if ( p2->leaf == p->leaf ) {
93 Error( "CheckStack: late leaf recursion" );
100 fixedWinding_t *AllocStackWinding( pstack_t *stack ){
103 for ( i = 0 ; i < 3 ; i++ )
105 if ( stack->freewindings[i] ) {
106 stack->freewindings[i] = 0;
107 return &stack->windings[i];
111 Error( "AllocStackWinding: failed" );
116 void FreeStackWinding( fixedWinding_t *w, pstack_t *stack ){
119 i = w - stack->windings;
121 if ( i < 0 || i > 2 ) {
122 return; // not from local
125 if ( stack->freewindings[i] ) {
126 Error( "FreeStackWinding: allready free" );
128 stack->freewindings[i] = 1;
137 fixedWinding_t *VisChopWinding( fixedWinding_t *in, pstack_t *stack, visPlane_t *split ){
145 fixedWinding_t *neww;
147 counts[0] = counts[1] = counts[2] = 0;
149 // determine sides for each point
150 for ( i = 0 ; i < in->numpoints ; i++ )
152 dot = DotProduct( in->points[i], split->normal );
155 if ( dot > ON_EPSILON ) {
156 sides[i] = SIDE_FRONT;
158 else if ( dot < -ON_EPSILON ) {
159 sides[i] = SIDE_BACK;
169 return in; // completely on front side
173 FreeStackWinding( in, stack );
180 neww = AllocStackWinding( stack );
184 for ( i = 0 ; i < in->numpoints ; i++ )
188 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
189 FreeStackWinding( neww, stack );
190 return in; // can't chop -- fall back to original
193 if ( sides[i] == SIDE_ON ) {
194 VectorCopy( p1, neww->points[neww->numpoints] );
199 if ( sides[i] == SIDE_FRONT ) {
200 VectorCopy( p1, neww->points[neww->numpoints] );
204 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
208 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
209 FreeStackWinding( neww, stack );
210 return in; // can't chop -- fall back to original
213 // generate a split point
214 p2 = in->points[( i + 1 ) % in->numpoints];
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;
222 else if ( split->normal[j] == -1 ) {
223 mid[j] = -split->dist;
226 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
230 VectorCopy( mid, neww->points[neww->numpoints] );
234 // free the original winding
235 FreeStackWinding( in, stack );
244 Source, pass, and target are an ordering of portals.
246 Generates seperating planes canidates by taking two points from source and one
247 point from pass, and clips target by them.
249 If target is totally clipped away, that portal can not be seen through.
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.
256 fixedWinding_t *ClipToSeperators( fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack ){
265 // check all combinations
266 for ( i = 0 ; i < source->numpoints ; i++ )
268 l = ( i + 1 ) % source->numpoints;
269 VectorSubtract( source->points[l], source->points[i], v1 );
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++ )
276 VectorSubtract( pass->points[j], source->points[i], v2 );
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];
282 // if points don't make a valid plane, skip it
284 length = plane.normal[0] * plane.normal[0]
285 + plane.normal[1] * plane.normal[1]
286 + plane.normal[2] * plane.normal[2];
288 if ( length < ON_EPSILON ) {
292 length = 1 / sqrt( length );
294 plane.normal[0] *= length;
295 plane.normal[1] *= length;
296 plane.normal[2] *= length;
298 plane.dist = DotProduct( pass->points[j], plane.normal );
301 // find out which side of the generated seperating plane has the
306 for ( k = 0 ; k < source->numpoints ; k++ )
308 if ( k == i || k == l ) {
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
317 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
318 // pass and target on the negative side
323 if ( k == source->numpoints ) {
324 continue; // planar with source portal
330 // flip the normal if the source portal is backwards
333 VectorSubtract( vec3_origin, plane.normal, plane.normal );
334 plane.dist = -plane.dist;
338 // if all of the pass portal points are now on the positive side,
339 // this is the seperating plane
341 counts[0] = counts[1] = counts[2] = 0;
342 for ( k = 0 ; k < pass->numpoints ; k++ )
347 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
348 if ( d < -ON_EPSILON ) {
351 else if ( d > ON_EPSILON ) {
358 if ( k != pass->numpoints ) {
359 continue; // points on negative side, not a seperating plane
363 continue; // planar with seperating plane
366 k = ( j + 1 ) % pass->numpoints;
367 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
368 if ( d < -ON_EPSILON ) {
371 k = ( j + pass->numpoints - 1 ) % pass->numpoints;
372 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
373 if ( d < -ON_EPSILON ) {
378 // flip the normal if we want the back side
381 VectorSubtract( vec3_origin, plane.normal, plane.normal );
382 plane.dist = -plane.dist;
385 #ifdef SEPERATORCACHE
386 stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
387 if ( ++stack->numseperators[flipclip] >= MAX_SEPERATORS ) {
388 Error( "MAX_SEPERATORS" );
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 ) {
397 //if completely on the front of the seperator plane
398 if ( d > stack->portal->radius ) {
403 // clip target by the seperating plane
405 target = VisChopWinding( target, stack, &plane );
407 return NULL; // target is not visible
410 break; // optimization by Antony Suter
421 Flood fill through the leafs
422 If src_portal is NULL, this is the originating leaf
425 void RecursiveLeafFlow( int leafnum, threaddata_t *thread, pstack_t *prevstack ){
428 visPlane_t backplane;
431 long *test, *might, *prevmight, *vis, more;
436 leaf = &leafs[leafnum];
437 // CheckStack (leaf, thread);
439 prevstack->next = &stack;
444 stack.depth = prevstack->depth + 1;
446 #ifdef SEPERATORCACHE
447 stack.numseperators[0] = 0;
448 stack.numseperators[1] = 0;
451 might = (long *)stack.mightsee;
452 vis = (long *)thread->base->portalvis;
454 // check all portals for flowing into other leafs
455 for ( i = 0; i < leaf->numportals; i++ )
457 p = leaf->portals[i];
463 /* MrE: portal trace debug code
465 int portaltrace[] = {13, 16, 17, 37};
468 s = &thread->pstack_head;
469 for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
471 if (s->portal->num != portaltrace[j])
474 if (j >= sizeof(portaltrace)/sizeof(int) - 1)
476 if (p->num == portaltrace[j])
477 n = 0; //traced through all the portals
482 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
483 continue; // can't possibly see it
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;
492 test = (long *)p->portalflood;
496 prevmight = (long *)prevstack->mightsee;
497 for ( j = 0 ; j < portallongs ; j++ )
499 might[j] = prevmight[j] & test[j];
500 more |= ( might[j] & ~vis[j] );
504 ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
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;
517 stack.freewindings[0] = 1;
518 stack.freewindings[1] = 1;
519 stack.freewindings[2] = 1;
525 d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
526 d -= thread->pstack_head.portalplane.dist;
527 if ( d < -p->radius ) {
530 else if ( d > p->radius ) {
531 stack.pass = p->winding;
535 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
542 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
553 d = DotProduct( thread->base->origin, p->plane.normal );
557 if ( d > thread->base->radius ) {
561 //if (d < -p->radius)
562 else if ( d < -thread->base->radius ) {
563 stack.source = prevstack->source;
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 ) {
575 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
576 if ( !stack.source ) {
581 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
583 // mark the portal as visible
584 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
586 RecursiveLeafFlow( p->leaf, thread, &stack );
590 #ifdef SEPERATORCACHE
591 if ( stack.numseperators[0] ) {
592 for ( n = 0; n < stack.numseperators[0]; n++ )
594 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
596 break; // target is not visible
599 if ( n < stack.numseperators[0] ) {
605 stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
608 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
614 #ifdef SEPERATORCACHE
615 if ( stack.numseperators[1] ) {
616 for ( n = 0; n < stack.numseperators[1]; n++ )
618 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
620 break; // target is not visible
626 stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
629 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
635 // mark the portal as visible
636 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
638 // flow through it for real
639 RecursiveLeafFlow( p->leaf, thread, &stack );
649 generates the portalvis bit vector
652 void PortalFlow( int portalnum ){
659 Sys_Printf( "\r%6d", portalnum );
662 p = sorted_portals[portalnum];
665 p->status = stat_done;
669 p->status = stat_working;
671 c_might = CountBits( p->portalflood, numportals * 2 );
673 memset( &data, 0, sizeof( data ) );
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];
683 RecursiveLeafFlow( p->leaf, &data, &data.pstack_head );
685 p->status = stat_done;
687 c_can = CountBits( p->portalvis, numportals * 2 );
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 );
698 void RecursivePassageFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
702 passage_t *passage, *nextpassage;
704 long *might, *vis, *prevmight, *cansee, *portalvis, more;
707 leaf = &leafs[portal->leaf];
709 prevstack->next = &stack;
712 stack.depth = prevstack->depth + 1;
714 vis = (long *)thread->base->portalvis;
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 )
721 p = leaf->portals[i];
725 nextpassage = passage->next;
728 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
729 continue; // can't possibly see it
732 // mark the portal as visible
733 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
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;
743 portalvis = (long *) p->portalflood;
746 for ( j = 0; j < portallongs; j++ )
749 *might &= *cansee++ & *portalvis++;
750 more |= ( *might & ~vis[j] );
761 // can't see anything new
765 // flow through it for real
766 RecursivePassageFlow( p, thread, &stack );
777 void PassageFlow( int portalnum ){
781 // int c_might, c_can;
784 Sys_Printf( "\r%6d", portalnum );
787 p = sorted_portals[portalnum];
790 p->status = stat_done;
794 p->status = stat_working;
796 // c_might = CountBits (p->portalflood, numportals*2);
798 memset( &data, 0, sizeof( data ) );
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];
808 RecursivePassageFlow( p, &data, &data.pstack_head );
810 p->status = stat_done;
813 c_can = CountBits (p->portalvis, numportals*2);
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);
822 RecursivePassagePortalFlow
825 void RecursivePassagePortalFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
829 visPlane_t backplane;
830 passage_t *passage, *nextpassage;
832 long *might, *vis, *prevmight, *cansee, *portalvis, more;
835 // thread->c_chains++;
837 leaf = &leafs[portal->leaf];
838 // CheckStack (leaf, thread);
840 prevstack->next = &stack;
845 stack.depth = prevstack->depth + 1;
847 #ifdef SEPERATORCACHE
848 stack.numseperators[0] = 0;
849 stack.numseperators[1] = 0;
852 vis = (long *)thread->base->portalvis;
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 )
859 p = leaf->portals[i];
863 nextpassage = passage->next;
866 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
867 continue; // can't possibly see it
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;
878 portalvis = (long *) p->portalflood;
881 for ( j = 0; j < portallongs; j++ )
884 *might &= *cansee++ & *portalvis++;
885 more |= ( *might & ~vis[j] );
895 if ( !more && ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
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;
908 stack.freewindings[0] = 1;
909 stack.freewindings[1] = 1;
910 stack.freewindings[2] = 1;
916 d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
917 d -= thread->pstack_head.portalplane.dist;
918 if ( d < -p->radius ) {
921 else if ( d > p->radius ) {
922 stack.pass = p->winding;
926 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
933 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
944 d = DotProduct( thread->base->origin, p->plane.normal );
948 if ( d > thread->base->radius ) {
952 //if (d < -p->radius)
953 else if ( d < -thread->base->radius ) {
954 stack.source = prevstack->source;
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 ) {
966 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
967 if ( !stack.source ) {
972 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
974 // mark the portal as visible
975 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
977 RecursivePassagePortalFlow( p, thread, &stack );
981 #ifdef SEPERATORCACHE
982 if ( stack.numseperators[0] ) {
983 for ( n = 0; n < stack.numseperators[0]; n++ )
985 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
987 break; // target is not visible
990 if ( n < stack.numseperators[0] ) {
996 stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
999 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
1001 if ( !stack.pass ) {
1005 #ifdef SEPERATORCACHE
1006 if ( stack.numseperators[1] ) {
1007 for ( n = 0; n < stack.numseperators[1]; n++ )
1009 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
1010 if ( !stack.pass ) {
1011 break; // target is not visible
1017 stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
1020 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
1022 if ( !stack.pass ) {
1026 // mark the portal as visible
1027 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1029 // flow through it for real
1030 RecursivePassagePortalFlow( p, thread, &stack );
1041 void PassagePortalFlow( int portalnum ){
1045 // int c_might, c_can;
1048 Sys_Printf( "\r%6d", portalnum );
1051 p = sorted_portals[portalnum];
1054 p->status = stat_done;
1058 p->status = stat_working;
1060 // c_might = CountBits (p->portalflood, numportals*2);
1062 memset( &data, 0, sizeof( data ) );
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];
1072 RecursivePassagePortalFlow( p, &data, &data.pstack_head );
1074 p->status = stat_done;
1077 c_can = CountBits (p->portalvis, numportals*2);
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);
1084 fixedWinding_t *PassageChopWinding( fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split ){
1092 fixedWinding_t *neww;
1094 counts[0] = counts[1] = counts[2] = 0;
1096 // determine sides for each point
1097 for ( i = 0 ; i < in->numpoints ; i++ )
1099 dot = DotProduct( in->points[i], split->normal );
1102 if ( dot > ON_EPSILON ) {
1103 sides[i] = SIDE_FRONT;
1105 else if ( dot < -ON_EPSILON ) {
1106 sides[i] = SIDE_BACK;
1116 return in; // completely on front side
1123 sides[i] = sides[0];
1124 dists[i] = dists[0];
1128 neww->numpoints = 0;
1130 for ( i = 0 ; i < in->numpoints ; i++ )
1134 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1135 return in; // can't chop -- fall back to original
1138 if ( sides[i] == SIDE_ON ) {
1139 VectorCopy( p1, neww->points[neww->numpoints] );
1144 if ( sides[i] == SIDE_FRONT ) {
1145 VectorCopy( p1, neww->points[neww->numpoints] );
1149 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
1153 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1154 return in; // can't chop -- fall back to original
1157 // generate a split point
1158 p2 = in->points[( i + 1 ) % in->numpoints];
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;
1166 else if ( split->normal[j] == -1 ) {
1167 mid[j] = -split->dist;
1170 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
1174 VectorCopy( mid, neww->points[neww->numpoints] );
1186 int AddSeperators( fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators ){
1192 int counts[3], numseperators;
1196 // check all combinations
1197 for ( i = 0 ; i < source->numpoints ; i++ )
1199 l = ( i + 1 ) % source->numpoints;
1200 VectorSubtract( source->points[l], source->points[i], v1 );
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++ )
1207 VectorSubtract( pass->points[j], source->points[i], v2 );
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];
1213 // if points don't make a valid plane, skip it
1215 length = plane.normal[0] * plane.normal[0]
1216 + plane.normal[1] * plane.normal[1]
1217 + plane.normal[2] * plane.normal[2];
1219 if ( length < ON_EPSILON ) {
1223 length = 1 / sqrt( length );
1225 plane.normal[0] *= length;
1226 plane.normal[1] *= length;
1227 plane.normal[2] *= length;
1229 plane.dist = DotProduct( pass->points[j], plane.normal );
1232 // find out which side of the generated seperating plane has the
1237 for ( k = 0 ; k < source->numpoints ; k++ )
1239 if ( k == i || k == l ) {
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
1248 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
1249 // pass and target on the negative side
1254 if ( k == source->numpoints ) {
1255 continue; // planar with source portal
1258 fliptest = flipclip;
1261 // flip the normal if the source portal is backwards
1264 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1265 plane.dist = -plane.dist;
1269 // if all of the pass portal points are now on the positive side,
1270 // this is the seperating plane
1272 counts[0] = counts[1] = counts[2] = 0;
1273 for ( k = 0 ; k < pass->numpoints ; k++ )
1278 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1279 if ( d < -ON_EPSILON ) {
1282 else if ( d > ON_EPSILON ) {
1289 if ( k != pass->numpoints ) {
1290 continue; // points on negative side, not a seperating plane
1294 continue; // planar with seperating plane
1297 k = ( j + 1 ) % pass->numpoints;
1298 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1299 if ( d < -ON_EPSILON ) {
1302 k = ( j + pass->numpoints - 1 ) % pass->numpoints;
1303 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1304 if ( d < -ON_EPSILON ) {
1309 // flip the normal if we want the back side
1312 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1313 plane.dist = -plane.dist;
1316 if ( numseperators >= maxseperators ) {
1317 Error( "max seperators" );
1319 seperators[numseperators] = plane;
1324 return numseperators;
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
1336 void CreatePassages( int portalnum ){
1337 int i, j, k, n, numseperators, numsee;
1339 vportal_t *portal, *p, *target;
1341 passage_t *passage, *lastpassage;
1342 visPlane_t seperators[MAX_SEPERATORS * 2];
1344 fixedWinding_t in, out, *res;
1348 Sys_Printf( "\r%6d", portalnum );
1351 portal = sorted_portals[portalnum];
1353 if ( portal->removed ) {
1354 portal->status = stat_done;
1359 leaf = &leafs[portal->leaf];
1360 for ( i = 0; i < leaf->numportals; i++ )
1362 target = leaf->portals[i];
1363 if ( target->removed ) {
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 );
1372 passage->next = NULL;
1373 if ( lastpassage ) {
1374 lastpassage->next = passage;
1377 portal->passages = passage;
1379 lastpassage = passage;
1382 //create the passage->cansee
1383 for ( j = 0; j < numportals * 2; j++ )
1389 if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1392 if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1395 for ( k = 0; k < numseperators; k++ )
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 ) {
1404 for ( n = 0; n < w->numpoints; n++ )
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 ) {
1412 //if no points are at the front of the seperator
1413 if ( n >= w->numpoints ) {
1417 if ( k < numseperators ) {
1421 /* explitive deleted */
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 ] ) );
1430 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1434 for ( k = 0; k < numseperators; k++ )
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;
1442 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1443 if ( res == &out ) {
1444 memcpy( &in, &out, sizeof( fixedWinding_t ) );
1448 if ( res == NULL ) {
1452 if ( k < numseperators ) {
1455 passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) );
1461 void PassageMemory( void ){
1462 int i, j, totalmem, totalportals;
1463 vportal_t *portal, *target;
1468 for ( i = 0; i < numportals; i++ )
1470 portal = sorted_portals[i];
1471 if ( portal->removed ) {
1474 leaf = &leafs[portal->leaf];
1475 for ( j = 0; j < leaf->numportals; j++ )
1477 target = leaf->portals[j];
1478 if ( target->removed ) {
1481 totalmem += sizeof( passage_t ) + portalbytes;
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 );
1490 ===============================================================================
1492 This is a rough first-order aproximation that is used to trivially reject some
1493 of the final calculations.
1496 Calculates portalfront and portalflood bit vectors
1500 typedef struct passage_s
1502 struct passage_s *next;
1503 struct portal_s *to;
1504 stryct sep_s *seperators;
1508 typedef struct portal_s
1510 struct passage_s *passages;
1511 int leaf; // leaf portal faces into
1519 calc portal visibility
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
1528 ===============================================================================
1540 void SimpleFlood( vportal_t *srcportal, int leafnum ){
1546 leaf = &leafs[leafnum];
1548 for ( i = 0 ; i < leaf->numportals ; i++ )
1550 p = leaf->portals[i];
1555 if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1559 if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) {
1563 srcportal->portalflood[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1565 SimpleFlood( srcportal, p->leaf );
1574 void BasePortalVis( int portalnum ){
1582 p = portals + portalnum;
1588 p->portalfront = safe_malloc( portalbytes );
1589 memset( p->portalfront, 0, portalbytes );
1591 p->portalflood = safe_malloc( portalbytes );
1592 memset( p->portalflood, 0, portalbytes );
1594 p->portalvis = safe_malloc( portalbytes );
1595 memset( p->portalvis, 0, portalbytes );
1597 for ( j = 0, tp = portals ; j < numportals * 2 ; j++, tp++ )
1599 if ( j == portalnum ) {
1602 if ( tp->removed ) {
1606 /* ydnar: this is old farplane vis code from mre */
1608 if (farplanedist >= 0)
1611 VectorSubtract(p->origin, tp->origin, dir);
1612 if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
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 ) {
1627 for ( k = 0 ; k < w->numpoints ; k++ )
1629 d = DotProduct( w->points[k], p->plane.normal )
1631 if ( d > ON_EPSILON ) {
1635 if ( k == w->numpoints ) {
1636 continue; // no points on front
1640 for ( k = 0 ; k < w->numpoints ; k++ )
1642 d = DotProduct( w->points[k], tp->plane.normal )
1644 if ( d < -ON_EPSILON ) {
1648 if ( k == w->numpoints ) {
1649 continue; // no points on front
1652 p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) );
1655 SimpleFlood( p, p->leaf );
1657 p->nummightsee = CountBits( p->portalflood, numportals * 2 );
1658 // Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1659 c_flood += p->nummightsee;
1667 ===============================================================================
1669 This is a second order aproximation
1671 Calculates portalvis bit vector
1675 ===============================================================================
1680 RecursiveLeafBitFlow
1684 void RecursiveLeafBitFlow( int leafnum, byte *mightsee, byte *cansee ){
1690 byte newmight[MAX_PORTALS / 8];
1692 leaf = &leafs[leafnum];
1694 // check all portals for flowing into other leafs
1695 for ( i = 0 ; i < leaf->numportals ; i++ )
1697 p = leaf->portals[i];
1703 // if some previous portal can't see it, skip
1704 if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1708 // if this portal can see some portals we mightsee, recurse
1710 for ( j = 0 ; j < portallongs ; j++ )
1712 ( (long *)newmight )[j] = ( (long *)mightsee )[j]
1713 & ( (long *)p->portalflood )[j];
1714 more |= ( (long *)newmight )[j] & ~( (long *)cansee )[j];
1718 continue; // can't see anything new
1721 cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1723 RecursiveLeafBitFlow( p->leaf, newmight, cansee );
1732 void BetterPortalVis( int portalnum ){
1735 p = portals + portalnum;
1741 RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis );
1743 // build leaf vis information
1744 p->nummightsee = CountBits( p->portalvis, numportals * 2 );
1745 c_vis += p->nummightsee;