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 ) ) ) {
80 void CheckStack( leaf_t *leaf, threaddata_t *thread ){
83 for ( p = thread->pstack_head.next ; p ; p = p->next )
86 if ( p->leaf == leaf ) {
87 Error( "CheckStack: leaf recursion" );
89 for ( p2 = thread->pstack_head.next ; p2 != p ; p2 = p2->next )
90 if ( p2->leaf == p->leaf ) {
91 Error( "CheckStack: late leaf recursion" );
98 fixedWinding_t *AllocStackWinding( pstack_t *stack ){
101 for ( i = 0 ; i < 3 ; i++ )
103 if ( stack->freewindings[i] ) {
104 stack->freewindings[i] = 0;
105 return &stack->windings[i];
109 Error( "AllocStackWinding: failed" );
114 void FreeStackWinding( fixedWinding_t *w, pstack_t *stack ){
117 i = w - stack->windings;
119 if ( i < 0 || i > 2 ) {
120 return; // not from local
123 if ( stack->freewindings[i] ) {
124 Error( "FreeStackWinding: allready free" );
126 stack->freewindings[i] = 1;
135 fixedWinding_t *VisChopWinding( fixedWinding_t *in, pstack_t *stack, visPlane_t *split ){
143 fixedWinding_t *neww;
145 counts[0] = counts[1] = counts[2] = 0;
147 // determine sides for each point
148 for ( i = 0 ; i < in->numpoints ; i++ )
150 dot = DotProduct( in->points[i], split->normal );
153 if ( dot > ON_EPSILON ) {
154 sides[i] = SIDE_FRONT;
156 else if ( dot < -ON_EPSILON ) {
157 sides[i] = SIDE_BACK;
167 return in; // completely on front side
171 FreeStackWinding( in, stack );
178 neww = AllocStackWinding( stack );
182 for ( i = 0 ; i < in->numpoints ; i++ )
186 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
187 FreeStackWinding( neww, stack );
188 return in; // can't chop -- fall back to original
191 if ( sides[i] == SIDE_ON ) {
192 VectorCopy( p1, neww->points[neww->numpoints] );
197 if ( sides[i] == SIDE_FRONT ) {
198 VectorCopy( p1, neww->points[neww->numpoints] );
202 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
206 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
207 FreeStackWinding( neww, stack );
208 return in; // can't chop -- fall back to original
211 // generate a split point
212 p2 = in->points[( i + 1 ) % in->numpoints];
214 dot = dists[i] / ( dists[i] - dists[i + 1] );
215 for ( j = 0 ; j < 3 ; j++ )
216 { // avoid round off error when possible
217 if ( split->normal[j] == 1 ) {
218 mid[j] = split->dist;
220 else if ( split->normal[j] == -1 ) {
221 mid[j] = -split->dist;
224 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
228 VectorCopy( mid, neww->points[neww->numpoints] );
232 // free the original winding
233 FreeStackWinding( in, stack );
242 Source, pass, and target are an ordering of portals.
244 Generates seperating planes canidates by taking two points from source and one
245 point from pass, and clips target by them.
247 If target is totally clipped away, that portal can not be seen through.
249 Normal clip keeps target on the same side as pass, which is correct if the
250 order goes source, pass, target. If the order goes pass, source, target then
251 flipclip should be set.
254 fixedWinding_t *ClipToSeperators( fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack ){
263 // check all combinations
264 for ( i = 0 ; i < source->numpoints ; i++ )
266 l = ( i + 1 ) % source->numpoints;
267 VectorSubtract( source->points[l], source->points[i], v1 );
269 // find a vertex of pass that makes a plane that puts all of the
270 // vertexes of pass on the front side and all of the vertexes of
271 // source on the back side
272 for ( j = 0 ; j < pass->numpoints ; j++ )
274 VectorSubtract( pass->points[j], source->points[i], v2 );
276 plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
277 plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
278 plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
280 // if points don't make a valid plane, skip it
282 length = plane.normal[0] * plane.normal[0]
283 + plane.normal[1] * plane.normal[1]
284 + plane.normal[2] * plane.normal[2];
286 if ( length < ON_EPSILON ) {
290 length = 1 / sqrt( length );
292 plane.normal[0] *= length;
293 plane.normal[1] *= length;
294 plane.normal[2] *= length;
296 plane.dist = DotProduct( pass->points[j], plane.normal );
299 // find out which side of the generated seperating plane has the
304 for ( k = 0 ; k < source->numpoints ; k++ )
306 if ( k == i || k == l ) {
309 d = DotProduct( source->points[k], plane.normal ) - plane.dist;
310 if ( d < -ON_EPSILON ) { // source is on the negative side, so we want all
311 // pass and target on the positive side
315 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
316 // pass and target on the negative side
321 if ( k == source->numpoints ) {
322 continue; // planar with source portal
328 // flip the normal if the source portal is backwards
331 VectorSubtract( vec3_origin, plane.normal, plane.normal );
332 plane.dist = -plane.dist;
336 // if all of the pass portal points are now on the positive side,
337 // this is the seperating plane
339 counts[0] = counts[1] = counts[2] = 0;
340 for ( k = 0 ; k < pass->numpoints ; k++ )
345 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
346 if ( d < -ON_EPSILON ) {
349 else if ( d > ON_EPSILON ) {
356 if ( k != pass->numpoints ) {
357 continue; // points on negative side, not a seperating plane
361 continue; // planar with seperating plane
364 k = ( j + 1 ) % pass->numpoints;
365 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
366 if ( d < -ON_EPSILON ) {
369 k = ( j + pass->numpoints - 1 ) % pass->numpoints;
370 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
371 if ( d < -ON_EPSILON ) {
376 // flip the normal if we want the back side
379 VectorSubtract( vec3_origin, plane.normal, plane.normal );
380 plane.dist = -plane.dist;
383 #ifdef SEPERATORCACHE
384 stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
385 if ( ++stack->numseperators[flipclip] >= MAX_SEPERATORS ) {
386 Error( "MAX_SEPERATORS" );
389 //MrE: fast check first
390 d = DotProduct( stack->portal->origin, plane.normal ) - plane.dist;
391 //if completely at the back of the seperator plane
392 if ( d < -stack->portal->radius ) {
395 //if completely on the front of the seperator plane
396 if ( d > stack->portal->radius ) {
401 // clip target by the seperating plane
403 target = VisChopWinding( target, stack, &plane );
405 return NULL; // target is not visible
408 break; // optimization by Antony Suter
419 Flood fill through the leafs
420 If src_portal is NULL, this is the originating leaf
423 void RecursiveLeafFlow( int leafnum, threaddata_t *thread, pstack_t *prevstack ){
426 visPlane_t backplane;
429 long *test, *might, *prevmight, *vis, more;
434 leaf = &leafs[leafnum];
435 // CheckStack (leaf, thread);
437 prevstack->next = &stack;
442 stack.depth = prevstack->depth + 1;
444 #ifdef SEPERATORCACHE
445 stack.numseperators[0] = 0;
446 stack.numseperators[1] = 0;
449 might = (long *)stack.mightsee;
450 vis = (long *)thread->base->portalvis;
452 // check all portals for flowing into other leafs
453 for ( i = 0; i < leaf->numportals; i++ )
455 p = leaf->portals[i];
461 /* MrE: portal trace debug code
463 int portaltrace[] = {13, 16, 17, 37};
466 s = &thread->pstack_head;
467 for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
469 if (s->portal->num != portaltrace[j])
472 if (j >= sizeof(portaltrace)/sizeof(int) - 1)
474 if (p->num == portaltrace[j])
475 n = 0; //traced through all the portals
480 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
481 continue; // can't possibly see it
484 // if the portal can't see anything we haven't allready seen, skip it
485 if ( p->status == stat_done ) {
486 test = (long *)p->portalvis;
490 test = (long *)p->portalflood;
494 prevmight = (long *)prevstack->mightsee;
495 for ( j = 0 ; j < portallongs ; j++ )
497 might[j] = prevmight[j] & test[j];
498 more |= ( might[j] & ~vis[j] );
502 ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
506 // get plane of portal, point normal into the neighbor leaf
507 stack.portalplane = p->plane;
508 VectorSubtract( vec3_origin, p->plane.normal, backplane.normal );
509 backplane.dist = -p->plane.dist;
515 stack.freewindings[0] = 1;
516 stack.freewindings[1] = 1;
517 stack.freewindings[2] = 1;
523 d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
524 d -= thread->pstack_head.portalplane.dist;
525 if ( d < -p->radius ) {
528 else if ( d > p->radius ) {
529 stack.pass = p->winding;
533 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
540 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
551 d = DotProduct( thread->base->origin, p->plane.normal );
555 if ( d > thread->base->radius ) {
559 //if (d < -p->radius)
560 else if ( d < -thread->base->radius ) {
561 stack.source = prevstack->source;
565 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
566 //FIXME: shouldn't we create a new source origin and radius for fast checks?
567 if ( !stack.source ) {
573 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
574 if ( !stack.source ) {
579 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
581 // mark the portal as visible
582 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
584 RecursiveLeafFlow( p->leaf, thread, &stack );
588 #ifdef SEPERATORCACHE
589 if ( stack.numseperators[0] ) {
590 for ( n = 0; n < stack.numseperators[0]; n++ )
592 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
594 break; // target is not visible
597 if ( n < stack.numseperators[0] ) {
603 stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
606 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
612 #ifdef SEPERATORCACHE
613 if ( stack.numseperators[1] ) {
614 for ( n = 0; n < stack.numseperators[1]; n++ )
616 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
618 break; // target is not visible
624 stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
627 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
633 // mark the portal as visible
634 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
636 // flow through it for real
637 RecursiveLeafFlow( p->leaf, thread, &stack );
647 generates the portalvis bit vector
650 void PortalFlow( int portalnum ){
657 Sys_Printf( "\r%6d", portalnum );
660 p = sorted_portals[portalnum];
663 p->status = stat_done;
667 p->status = stat_working;
669 c_might = CountBits( p->portalflood, numportals * 2 );
671 memset( &data, 0, sizeof( data ) );
674 data.pstack_head.portal = p;
675 data.pstack_head.source = p->winding;
676 data.pstack_head.portalplane = p->plane;
677 data.pstack_head.depth = 0;
678 for ( i = 0 ; i < portallongs ; i++ )
679 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
681 RecursiveLeafFlow( p->leaf, &data, &data.pstack_head );
683 p->status = stat_done;
685 c_can = CountBits( p->portalvis, numportals * 2 );
687 Sys_FPrintf( SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
688 (int)( p - portals ), c_might, c_can, data.c_chains );
696 void RecursivePassageFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
700 passage_t *passage, *nextpassage;
702 long *might, *vis, *prevmight, *cansee, *portalvis, more;
705 leaf = &leafs[portal->leaf];
707 prevstack->next = &stack;
710 stack.depth = prevstack->depth + 1;
712 vis = (long *)thread->base->portalvis;
714 passage = portal->passages;
715 nextpassage = passage;
716 // check all portals for flowing into other leafs
717 for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
719 p = leaf->portals[i];
723 nextpassage = passage->next;
726 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
727 continue; // can't possibly see it
730 // mark the portal as visible
731 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
733 prevmight = (long *)prevstack->mightsee;
734 cansee = (long *)passage->cansee;
735 might = (long *)stack.mightsee;
736 memcpy( might, prevmight, portalbytes );
737 if ( p->status == stat_done ) {
738 portalvis = (long *) p->portalvis;
741 portalvis = (long *) p->portalflood;
744 for ( j = 0; j < portallongs; j++ )
747 *might &= *cansee++ & *portalvis++;
748 more |= ( *might & ~vis[j] );
759 // can't see anything new
763 // flow through it for real
764 RecursivePassageFlow( p, thread, &stack );
775 void PassageFlow( int portalnum ){
779 // int c_might, c_can;
782 Sys_Printf( "\r%6d", portalnum );
785 p = sorted_portals[portalnum];
788 p->status = stat_done;
792 p->status = stat_working;
794 // c_might = CountBits (p->portalflood, numportals*2);
796 memset( &data, 0, sizeof( data ) );
799 data.pstack_head.portal = p;
800 data.pstack_head.source = p->winding;
801 data.pstack_head.portalplane = p->plane;
802 data.pstack_head.depth = 0;
803 for ( i = 0 ; i < portallongs ; i++ )
804 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
806 RecursivePassageFlow( p, &data, &data.pstack_head );
808 p->status = stat_done;
811 c_can = CountBits (p->portalvis, numportals*2);
813 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
814 (int)(p - portals), c_might, c_can, data.c_chains);
820 RecursivePassagePortalFlow
823 void RecursivePassagePortalFlow( vportal_t *portal, threaddata_t *thread, pstack_t *prevstack ){
827 visPlane_t backplane;
828 passage_t *passage, *nextpassage;
830 long *might, *vis, *prevmight, *cansee, *portalvis, more;
833 // thread->c_chains++;
835 leaf = &leafs[portal->leaf];
836 // CheckStack (leaf, thread);
838 prevstack->next = &stack;
843 stack.depth = prevstack->depth + 1;
845 #ifdef SEPERATORCACHE
846 stack.numseperators[0] = 0;
847 stack.numseperators[1] = 0;
850 vis = (long *)thread->base->portalvis;
852 passage = portal->passages;
853 nextpassage = passage;
854 // check all portals for flowing into other leafs
855 for ( i = 0; i < leaf->numportals; i++, passage = nextpassage )
857 p = leaf->portals[i];
861 nextpassage = passage->next;
864 if ( !( prevstack->mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
865 continue; // can't possibly see it
868 prevmight = (long *)prevstack->mightsee;
869 cansee = (long *)passage->cansee;
870 might = (long *)stack.mightsee;
871 memcpy( might, prevmight, portalbytes );
872 if ( p->status == stat_done ) {
873 portalvis = (long *) p->portalvis;
876 portalvis = (long *) p->portalflood;
879 for ( j = 0; j < portallongs; j++ )
882 *might &= *cansee++ & *portalvis++;
883 more |= ( *might & ~vis[j] );
893 if ( !more && ( thread->base->portalvis[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) { // can't see anything new
897 // get plane of portal, point normal into the neighbor leaf
898 stack.portalplane = p->plane;
899 VectorSubtract( vec3_origin, p->plane.normal, backplane.normal );
900 backplane.dist = -p->plane.dist;
906 stack.freewindings[0] = 1;
907 stack.freewindings[1] = 1;
908 stack.freewindings[2] = 1;
914 d = DotProduct( p->origin, thread->pstack_head.portalplane.normal );
915 d -= thread->pstack_head.portalplane.dist;
916 if ( d < -p->radius ) {
919 else if ( d > p->radius ) {
920 stack.pass = p->winding;
924 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
931 stack.pass = VisChopWinding( p->winding, &stack, &thread->pstack_head.portalplane );
942 d = DotProduct( thread->base->origin, p->plane.normal );
946 if ( d > thread->base->radius ) {
950 //if (d < -p->radius)
951 else if ( d < -thread->base->radius ) {
952 stack.source = prevstack->source;
956 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
957 //FIXME: shouldn't we create a new source origin and radius for fast checks?
958 if ( !stack.source ) {
964 stack.source = VisChopWinding( prevstack->source, &stack, &backplane );
965 if ( !stack.source ) {
970 if ( !prevstack->pass ) { // the second leaf can only be blocked if coplanar
972 // mark the portal as visible
973 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
975 RecursivePassagePortalFlow( p, thread, &stack );
979 #ifdef SEPERATORCACHE
980 if ( stack.numseperators[0] ) {
981 for ( n = 0; n < stack.numseperators[0]; n++ )
983 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[0][n] );
985 break; // target is not visible
988 if ( n < stack.numseperators[0] ) {
994 stack.pass = ClipToSeperators( prevstack->source, prevstack->pass, stack.pass, qfalse, &stack );
997 stack.pass = ClipToSeperators( stack.source, prevstack->pass, stack.pass, qfalse, &stack );
1003 #ifdef SEPERATORCACHE
1004 if ( stack.numseperators[1] ) {
1005 for ( n = 0; n < stack.numseperators[1]; n++ )
1007 stack.pass = VisChopWinding( stack.pass, &stack, &stack.seperators[1][n] );
1008 if ( !stack.pass ) {
1009 break; // target is not visible
1015 stack.pass = ClipToSeperators( prevstack->pass, prevstack->source, stack.pass, qtrue, &stack );
1018 stack.pass = ClipToSeperators( prevstack->pass, stack.source, stack.pass, qtrue, &stack );
1020 if ( !stack.pass ) {
1024 // mark the portal as visible
1025 thread->base->portalvis[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1027 // flow through it for real
1028 RecursivePassagePortalFlow( p, thread, &stack );
1039 void PassagePortalFlow( int portalnum ){
1043 // int c_might, c_can;
1046 Sys_Printf( "\r%6d", portalnum );
1049 p = sorted_portals[portalnum];
1052 p->status = stat_done;
1056 p->status = stat_working;
1058 // c_might = CountBits (p->portalflood, numportals*2);
1060 memset( &data, 0, sizeof( data ) );
1063 data.pstack_head.portal = p;
1064 data.pstack_head.source = p->winding;
1065 data.pstack_head.portalplane = p->plane;
1066 data.pstack_head.depth = 0;
1067 for ( i = 0 ; i < portallongs ; i++ )
1068 ( (long *)data.pstack_head.mightsee )[i] = ( (long *)p->portalflood )[i];
1070 RecursivePassagePortalFlow( p, &data, &data.pstack_head );
1072 p->status = stat_done;
1075 c_can = CountBits (p->portalvis, numportals*2);
1077 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
1078 (int)(p - portals), c_might, c_can, data.c_chains);
1082 fixedWinding_t *PassageChopWinding( fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split ){
1090 fixedWinding_t *neww;
1092 counts[0] = counts[1] = counts[2] = 0;
1094 // determine sides for each point
1095 for ( i = 0 ; i < in->numpoints ; i++ )
1097 dot = DotProduct( in->points[i], split->normal );
1100 if ( dot > ON_EPSILON ) {
1101 sides[i] = SIDE_FRONT;
1103 else if ( dot < -ON_EPSILON ) {
1104 sides[i] = SIDE_BACK;
1114 return in; // completely on front side
1121 sides[i] = sides[0];
1122 dists[i] = dists[0];
1126 neww->numpoints = 0;
1128 for ( i = 0 ; i < in->numpoints ; i++ )
1132 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1133 return in; // can't chop -- fall back to original
1136 if ( sides[i] == SIDE_ON ) {
1137 VectorCopy( p1, neww->points[neww->numpoints] );
1142 if ( sides[i] == SIDE_FRONT ) {
1143 VectorCopy( p1, neww->points[neww->numpoints] );
1147 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
1151 if ( neww->numpoints == MAX_POINTS_ON_FIXED_WINDING ) {
1152 return in; // can't chop -- fall back to original
1155 // generate a split point
1156 p2 = in->points[( i + 1 ) % in->numpoints];
1158 dot = dists[i] / ( dists[i] - dists[i + 1] );
1159 for ( j = 0 ; j < 3 ; j++ )
1160 { // avoid round off error when possible
1161 if ( split->normal[j] == 1 ) {
1162 mid[j] = split->dist;
1164 else if ( split->normal[j] == -1 ) {
1165 mid[j] = -split->dist;
1168 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
1172 VectorCopy( mid, neww->points[neww->numpoints] );
1184 int AddSeperators( fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators ){
1190 int counts[3], numseperators;
1194 // check all combinations
1195 for ( i = 0 ; i < source->numpoints ; i++ )
1197 l = ( i + 1 ) % source->numpoints;
1198 VectorSubtract( source->points[l], source->points[i], v1 );
1200 // find a vertex of pass that makes a plane that puts all of the
1201 // vertexes of pass on the front side and all of the vertexes of
1202 // source on the back side
1203 for ( j = 0 ; j < pass->numpoints ; j++ )
1205 VectorSubtract( pass->points[j], source->points[i], v2 );
1207 plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
1208 plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
1209 plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
1211 // if points don't make a valid plane, skip it
1213 length = plane.normal[0] * plane.normal[0]
1214 + plane.normal[1] * plane.normal[1]
1215 + plane.normal[2] * plane.normal[2];
1217 if ( length < ON_EPSILON ) {
1221 length = 1 / sqrt( length );
1223 plane.normal[0] *= length;
1224 plane.normal[1] *= length;
1225 plane.normal[2] *= length;
1227 plane.dist = DotProduct( pass->points[j], plane.normal );
1230 // find out which side of the generated seperating plane has the
1235 for ( k = 0 ; k < source->numpoints ; k++ )
1237 if ( k == i || k == l ) {
1240 d = DotProduct( source->points[k], plane.normal ) - plane.dist;
1241 if ( d < -ON_EPSILON ) { // source is on the negative side, so we want all
1242 // pass and target on the positive side
1246 else if ( d > ON_EPSILON ) { // source is on the positive side, so we want all
1247 // pass and target on the negative side
1252 if ( k == source->numpoints ) {
1253 continue; // planar with source portal
1256 fliptest = flipclip;
1259 // flip the normal if the source portal is backwards
1262 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1263 plane.dist = -plane.dist;
1267 // if all of the pass portal points are now on the positive side,
1268 // this is the seperating plane
1270 counts[0] = counts[1] = counts[2] = 0;
1271 for ( k = 0 ; k < pass->numpoints ; k++ )
1276 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1277 if ( d < -ON_EPSILON ) {
1280 else if ( d > ON_EPSILON ) {
1287 if ( k != pass->numpoints ) {
1288 continue; // points on negative side, not a seperating plane
1292 continue; // planar with seperating plane
1295 k = ( j + 1 ) % pass->numpoints;
1296 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1297 if ( d < -ON_EPSILON ) {
1300 k = ( j + pass->numpoints - 1 ) % pass->numpoints;
1301 d = DotProduct( pass->points[k], plane.normal ) - plane.dist;
1302 if ( d < -ON_EPSILON ) {
1307 // flip the normal if we want the back side
1310 VectorSubtract( vec3_origin, plane.normal, plane.normal );
1311 plane.dist = -plane.dist;
1314 if ( numseperators >= maxseperators ) {
1315 Error( "max seperators" );
1317 seperators[numseperators] = plane;
1322 return numseperators;
1329 MrE: create passages from one portal to all the portals in the leaf the portal leads to
1330 every passage has a cansee bit string with all the portals that can be
1331 seen through the passage
1334 void CreatePassages( int portalnum ){
1335 int i, j, k, n, numseperators, numsee;
1337 vportal_t *portal, *p, *target;
1339 passage_t *passage, *lastpassage;
1340 visPlane_t seperators[MAX_SEPERATORS * 2];
1342 fixedWinding_t in, out, *res;
1346 Sys_Printf( "\r%6d", portalnum );
1349 portal = sorted_portals[portalnum];
1351 if ( portal->removed ) {
1352 portal->status = stat_done;
1357 leaf = &leafs[portal->leaf];
1358 for ( i = 0; i < leaf->numportals; i++ )
1360 target = leaf->portals[i];
1361 if ( target->removed ) {
1365 passage = (passage_t *) safe_malloc0( sizeof( passage_t ) + portalbytes );
1366 numseperators = AddSeperators( portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS * 2 );
1367 numseperators += AddSeperators( target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS * 2 - numseperators );
1369 passage->next = NULL;
1370 if ( lastpassage ) {
1371 lastpassage->next = passage;
1374 portal->passages = passage;
1376 lastpassage = passage;
1379 //create the passage->cansee
1380 for ( j = 0; j < numportals * 2; j++ )
1386 if ( !( target->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1389 if ( !( portal->portalflood[j >> 3] & ( 1 << ( j & 7 ) ) ) ) {
1392 for ( k = 0; k < numseperators; k++ )
1395 d = DotProduct( p->origin, seperators[k].normal ) - seperators[k].dist;
1396 //if completely at the back of the seperator plane
1397 if ( d < -p->radius + ON_EPSILON ) {
1401 for ( n = 0; n < w->numpoints; n++ )
1403 d = DotProduct( w->points[n], seperators[k].normal ) - seperators[k].dist;
1404 //if at the front of the seperator
1405 if ( d > ON_EPSILON ) {
1409 //if no points are at the front of the seperator
1410 if ( n >= w->numpoints ) {
1414 if ( k < numseperators ) {
1418 /* explitive deleted */
1421 /* ydnar: prefer correctness to stack overflow */
1422 //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1423 if ( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING ) {
1424 memcpy( &in, p->winding, (size_t) &( ( (fixedWinding_t*) 0 )->points[ p->winding->numpoints ] ) );
1427 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1431 for ( k = 0; k < numseperators; k++ )
1433 /* ydnar: this is a shitty crutch */
1434 if ( in.numpoints > MAX_POINTS_ON_FIXED_WINDING ) {
1435 //% Sys_Printf( "[%d]", p->winding->numpoints );
1436 in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1439 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1440 if ( res == &out ) {
1441 memcpy( &in, &out, sizeof( fixedWinding_t ) );
1445 if ( res == NULL ) {
1449 if ( k < numseperators ) {
1452 passage->cansee[j >> 3] |= ( 1 << ( j & 7 ) );
1458 void PassageMemory( void ){
1459 int i, j, totalmem, totalportals;
1460 vportal_t *portal, *target;
1465 for ( i = 0; i < numportals; i++ )
1467 portal = sorted_portals[i];
1468 if ( portal->removed ) {
1471 leaf = &leafs[portal->leaf];
1472 for ( j = 0; j < leaf->numportals; j++ )
1474 target = leaf->portals[j];
1475 if ( target->removed ) {
1478 totalmem += sizeof( passage_t ) + portalbytes;
1482 Sys_Printf( "%7i average number of passages per leaf\n", totalportals / numportals );
1483 Sys_Printf( "%7i MB required passage memory\n", totalmem >> 10 >> 10 );
1487 ===============================================================================
1489 This is a rough first-order aproximation that is used to trivially reject some
1490 of the final calculations.
1493 Calculates portalfront and portalflood bit vectors
1497 typedef struct passage_s
1499 struct passage_s *next;
1500 struct portal_s *to;
1501 stryct sep_s *seperators;
1505 typedef struct portal_s
1507 struct passage_s *passages;
1508 int leaf; // leaf portal faces into
1516 calc portal visibility
1522 for a portal to be visible to a passage, it must be on the front of
1523 all seperating planes, and both portals must be behind the new portal
1525 ===============================================================================
1537 void SimpleFlood( vportal_t *srcportal, int leafnum ){
1543 leaf = &leafs[leafnum];
1545 for ( i = 0 ; i < leaf->numportals ; i++ )
1547 p = leaf->portals[i];
1552 if ( !( srcportal->portalfront[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1556 if ( srcportal->portalflood[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) {
1560 srcportal->portalflood[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1562 SimpleFlood( srcportal, p->leaf );
1571 void BasePortalVis( int portalnum ){
1579 p = portals + portalnum;
1585 p->portalfront = safe_malloc0( portalbytes );
1587 p->portalflood = safe_malloc0( portalbytes );
1589 p->portalvis = safe_malloc0( portalbytes );
1591 for ( j = 0, tp = portals ; j < numportals * 2 ; j++, tp++ )
1593 if ( j == portalnum ) {
1596 if ( tp->removed ) {
1600 /* ydnar: this is old farplane vis code from mre */
1602 if (farplanedist >= 0)
1605 VectorSubtract(p->origin, tp->origin, dir);
1606 if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1611 /* ydnar: this is known-to-be-working farplane code */
1612 if ( !p->sky && !tp->sky && farPlaneDist > 0.0f ) {
1613 VectorSubtract( p->origin, tp->origin, dir );
1614 if ( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist ) {
1621 for ( k = 0 ; k < w->numpoints ; k++ )
1623 d = DotProduct( w->points[k], p->plane.normal )
1625 if ( d > ON_EPSILON ) {
1629 if ( k == w->numpoints ) {
1630 continue; // no points on front
1634 for ( k = 0 ; k < w->numpoints ; k++ )
1636 d = DotProduct( w->points[k], tp->plane.normal )
1638 if ( d < -ON_EPSILON ) {
1642 if ( k == w->numpoints ) {
1643 continue; // no points on front
1646 p->portalfront[j >> 3] |= ( 1 << ( j & 7 ) );
1649 SimpleFlood( p, p->leaf );
1651 p->nummightsee = CountBits( p->portalflood, numportals * 2 );
1652 // Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1653 c_flood += p->nummightsee;
1661 ===============================================================================
1663 This is a second order aproximation
1665 Calculates portalvis bit vector
1669 ===============================================================================
1674 RecursiveLeafBitFlow
1678 void RecursiveLeafBitFlow( int leafnum, byte *mightsee, byte *cansee ){
1684 byte newmight[MAX_PORTALS / 8];
1686 leaf = &leafs[leafnum];
1688 // check all portals for flowing into other leafs
1689 for ( i = 0 ; i < leaf->numportals ; i++ )
1691 p = leaf->portals[i];
1697 // if some previous portal can't see it, skip
1698 if ( !( mightsee[pnum >> 3] & ( 1 << ( pnum & 7 ) ) ) ) {
1702 // if this portal can see some portals we mightsee, recurse
1704 for ( j = 0 ; j < portallongs ; j++ )
1706 ( (long *)newmight )[j] = ( (long *)mightsee )[j]
1707 & ( (long *)p->portalflood )[j];
1708 more |= ( (long *)newmight )[j] & ~( (long *)cansee )[j];
1712 continue; // can't see anything new
1715 cansee[pnum >> 3] |= ( 1 << ( pnum & 7 ) );
1717 RecursiveLeafBitFlow( p->leaf, newmight, cansee );
1726 void BetterPortalVis( int portalnum ){
1729 p = portals + portalnum;
1735 RecursiveLeafBitFlow( p->leaf, p->portalflood, p->portalvis );
1737 // build leaf vis information
1738 p->nummightsee = CountBits( p->portalvis, numportals * 2 );
1739 c_vis += p->nummightsee;