2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ----------------------------------------------------------------------------------
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26 ------------------------------------------------------------------------------- */
43 each portal will have a list of all possible to see from first portal
45 if (!thread->portalmightsee[portalnum])
49 for p2 = all other portals in leaf
51 for all portals that might be seen by p2
52 mark as unseen if not present in seperating plane
53 flood fill a new mightsee
54 save as passagemightsee
57 void CalcMightSee (leaf_t *leaf,
60 int CountBits (byte *bits, int numbits)
66 for (i=0 ; i<numbits ; i++)
67 if (bits[i>>3] & (1<<(i&7)) )
74 int c_portalskip, c_leafskip;
75 int c_vistest, c_mighttest;
81 void CheckStack (leaf_t *leaf, threaddata_t *thread)
85 for (p=thread->pstack_head.next ; p ; p=p->next)
89 Error ("CheckStack: leaf recursion");
90 for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
91 if (p2->leaf == p->leaf)
92 Error ("CheckStack: late leaf recursion");
98 fixedWinding_t *AllocStackWinding (pstack_t *stack)
102 for (i=0 ; i<3 ; i++)
104 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)
120 i = w - stack->windings;
123 return; // not from local
125 if (stack->freewindings[i])
126 Error ("FreeStackWinding: allready free");
127 stack->freewindings[i] = 1;
136 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;
157 else if (dot < -ON_EPSILON)
158 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)
188 FreeStackWinding (neww, stack);
189 return in; // can't chop -- fall back to original
192 if (sides[i] == SIDE_ON)
194 VectorCopy (p1, neww->points[neww->numpoints]);
199 if (sides[i] == SIDE_FRONT)
201 VectorCopy (p1, neww->points[neww->numpoints]);
205 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
208 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
210 FreeStackWinding (neww, stack);
211 return in; // can't chop -- fall back to original
214 // generate a split point
215 p2 = in->points[(i+1)%in->numpoints];
217 dot = dists[i] / (dists[i]-dists[i+1]);
218 for (j=0 ; j<3 ; j++)
219 { // avoid round off error when possible
220 if (split->normal[j] == 1)
221 mid[j] = split->dist;
222 else if (split->normal[j] == -1)
223 mid[j] = -split->dist;
225 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)
264 // check all combinations
265 for (i=0 ; i<source->numpoints ; i++)
267 l = (i+1)%source->numpoints;
268 VectorSubtract (source->points[l] , source->points[i], v1);
270 // find a vertex of pass that makes a plane that puts all of the
271 // vertexes of pass on the front side and all of the vertexes of
272 // source on the back side
273 for (j=0 ; j<pass->numpoints ; j++)
275 VectorSubtract (pass->points[j], source->points[i], v2);
277 plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
278 plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
279 plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
281 // if points don't make a valid plane, skip it
283 length = plane.normal[0] * plane.normal[0]
284 + plane.normal[1] * plane.normal[1]
285 + plane.normal[2] * plane.normal[2];
287 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)
308 d = DotProduct (source->points[k], plane.normal) - plane.dist;
310 { // source is on the negative side, so we want all
311 // pass and target on the positive side
315 else if (d > ON_EPSILON)
316 { // source is on the positive side, so we want all
317 // pass and target on the negative side
322 if (k == source->numpoints)
323 continue; // planar with source portal
328 // flip the normal if the source portal is backwards
332 VectorSubtract (vec3_origin, plane.normal, plane.normal);
333 plane.dist = -plane.dist;
337 // if all of the pass portal points are now on the positive side,
338 // this is the seperating plane
340 counts[0] = counts[1] = counts[2] = 0;
341 for (k=0 ; k<pass->numpoints ; k++)
345 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
348 else if (d > ON_EPSILON)
353 if (k != pass->numpoints)
354 continue; // points on negative side, not a seperating plane
357 continue; // planar with seperating plane
359 k = (j+1)%pass->numpoints;
360 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
363 k = (j+pass->numpoints-1)%pass->numpoints;
364 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
369 // flip the normal if we want the back side
373 VectorSubtract (vec3_origin, plane.normal, plane.normal);
374 plane.dist = -plane.dist;
377 #ifdef SEPERATORCACHE
378 stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
379 if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
380 Error("MAX_SEPERATORS");
382 //MrE: fast check first
383 d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
384 //if completely at the back of the seperator plane
385 if (d < -stack->portal->radius)
387 //if completely on the front of the seperator plane
388 if (d > stack->portal->radius)
392 // clip target by the seperating plane
394 target = VisChopWinding (target, stack, &plane);
396 return NULL; // target is not visible
398 break; // optimization by Antony Suter
409 Flood fill through the leafs
410 If src_portal is NULL, this is the originating leaf
413 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
417 visPlane_t backplane;
420 long *test, *might, *prevmight, *vis, more;
425 leaf = &leafs[leafnum];
426 // CheckStack (leaf, thread);
428 prevstack->next = &stack;
433 stack.depth = prevstack->depth + 1;
435 #ifdef SEPERATORCACHE
436 stack.numseperators[0] = 0;
437 stack.numseperators[1] = 0;
440 might = (long *)stack.mightsee;
441 vis = (long *)thread->base->portalvis;
443 // check all portals for flowing into other leafs
444 for (i = 0; i < leaf->numportals; i++)
446 p = leaf->portals[i];
451 /* MrE: portal trace debug code
453 int portaltrace[] = {13, 16, 17, 37};
456 s = &thread->pstack_head;
457 for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
459 if (s->portal->num != portaltrace[j])
462 if (j >= sizeof(portaltrace)/sizeof(int) - 1)
464 if (p->num == portaltrace[j])
465 n = 0; //traced through all the portals
470 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
472 continue; // can't possibly see it
475 // if the portal can't see anything we haven't allready seen, skip it
476 if (p->status == stat_done)
478 test = (long *)p->portalvis;
482 test = (long *)p->portalflood;
486 prevmight = (long *)prevstack->mightsee;
487 for (j=0 ; j<portallongs ; j++)
489 might[j] = prevmight[j] & test[j];
490 more |= (might[j] & ~vis[j]);
494 (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
495 { // can't see anything new
499 // get plane of portal, point normal into the neighbor leaf
500 stack.portalplane = p->plane;
501 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
502 backplane.dist = -p->plane.dist;
508 stack.freewindings[0] = 1;
509 stack.freewindings[1] = 1;
510 stack.freewindings[2] = 1;
516 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
517 d -= thread->pstack_head.portalplane.dist;
522 else if (d > p->radius)
524 stack.pass = p->winding;
528 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
534 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
544 d = DotProduct (thread->base->origin, p->plane.normal);
548 if (d > thread->base->radius)
553 //if (d < -p->radius)
554 else if (d < -thread->base->radius)
556 stack.source = prevstack->source;
560 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
561 //FIXME: shouldn't we create a new source origin and radius for fast checks?
567 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
572 if (!prevstack->pass)
573 { // the second leaf can only be blocked if coplanar
575 // mark the portal as visible
576 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
578 RecursiveLeafFlow (p->leaf, thread, &stack);
582 #ifdef SEPERATORCACHE
583 if (stack.numseperators[0])
585 for (n = 0; n < stack.numseperators[0]; n++)
587 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
589 break; // target is not visible
591 if (n < stack.numseperators[0])
596 stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
599 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
604 #ifdef SEPERATORCACHE
605 if (stack.numseperators[1])
607 for (n = 0; n < stack.numseperators[1]; n++)
609 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
611 break; // target is not visible
616 stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
619 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
624 // mark the portal as visible
625 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
627 // flow through it for real
628 RecursiveLeafFlow (p->leaf, thread, &stack);
638 generates the portalvis bit vector
641 void PortalFlow (int portalnum)
649 Sys_Printf("\r%6d", portalnum);
652 p = sorted_portals[portalnum];
656 p->status = stat_done;
660 p->status = stat_working;
662 c_might = CountBits (p->portalflood, numportals*2);
664 memset (&data, 0, sizeof(data));
667 data.pstack_head.portal = p;
668 data.pstack_head.source = p->winding;
669 data.pstack_head.portalplane = p->plane;
670 data.pstack_head.depth = 0;
671 for (i=0 ; i<portallongs ; i++)
672 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
674 RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
676 p->status = stat_done;
678 c_can = CountBits (p->portalvis, numportals*2);
680 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
681 (int)(p - portals), c_might, c_can, data.c_chains);
689 void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
694 passage_t *passage, *nextpassage;
696 long *might, *vis, *prevmight, *cansee, *portalvis, more;
699 leaf = &leafs[portal->leaf];
701 prevstack->next = &stack;
704 stack.depth = prevstack->depth + 1;
706 vis = (long *)thread->base->portalvis;
708 passage = portal->passages;
709 nextpassage = passage;
710 // check all portals for flowing into other leafs
711 for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
713 p = leaf->portals[i];
717 nextpassage = passage->next;
720 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
721 continue; // can't possibly see it
724 // mark the portal as visible
725 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
727 prevmight = (long *)prevstack->mightsee;
728 cansee = (long *)passage->cansee;
729 might = (long *)stack.mightsee;
730 memcpy(might, prevmight, portalbytes);
731 if (p->status == stat_done)
732 portalvis = (long *) p->portalvis;
734 portalvis = (long *) p->portalflood;
736 for (j = 0; j < portallongs; j++)
740 *might &= *cansee++ & *portalvis++;
741 more |= (*might & ~vis[j]);
752 // can't see anything new
756 // flow through it for real
757 RecursivePassageFlow(p, thread, &stack);
768 void PassageFlow (int portalnum)
773 // int c_might, c_can;
776 Sys_Printf("\r%6d", portalnum);
779 p = sorted_portals[portalnum];
783 p->status = stat_done;
787 p->status = stat_working;
789 // c_might = CountBits (p->portalflood, numportals*2);
791 memset (&data, 0, sizeof(data));
794 data.pstack_head.portal = p;
795 data.pstack_head.source = p->winding;
796 data.pstack_head.portalplane = p->plane;
797 data.pstack_head.depth = 0;
798 for (i=0 ; i<portallongs ; i++)
799 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
801 RecursivePassageFlow (p, &data, &data.pstack_head);
803 p->status = stat_done;
806 c_can = CountBits (p->portalvis, numportals*2);
808 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
809 (int)(p - portals), c_might, c_can, data.c_chains);
815 RecursivePassagePortalFlow
818 void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
823 visPlane_t backplane;
824 passage_t *passage, *nextpassage;
826 long *might, *vis, *prevmight, *cansee, *portalvis, more;
829 // thread->c_chains++;
831 leaf = &leafs[portal->leaf];
832 // CheckStack (leaf, thread);
834 prevstack->next = &stack;
839 stack.depth = prevstack->depth + 1;
841 #ifdef SEPERATORCACHE
842 stack.numseperators[0] = 0;
843 stack.numseperators[1] = 0;
846 vis = (long *)thread->base->portalvis;
848 passage = portal->passages;
849 nextpassage = passage;
850 // check all portals for flowing into other leafs
851 for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
853 p = leaf->portals[i];
856 nextpassage = passage->next;
859 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
860 continue; // can't possibly see it
862 prevmight = (long *)prevstack->mightsee;
863 cansee = (long *)passage->cansee;
864 might = (long *)stack.mightsee;
865 memcpy(might, prevmight, portalbytes);
866 if (p->status == stat_done)
867 portalvis = (long *) p->portalvis;
869 portalvis = (long *) p->portalflood;
871 for (j = 0; j < portallongs; j++)
875 *might &= *cansee++ & *portalvis++;
876 more |= (*might & ~vis[j]);
886 if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
887 { // can't see anything new
891 // get plane of portal, point normal into the neighbor leaf
892 stack.portalplane = p->plane;
893 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
894 backplane.dist = -p->plane.dist;
900 stack.freewindings[0] = 1;
901 stack.freewindings[1] = 1;
902 stack.freewindings[2] = 1;
908 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
909 d -= thread->pstack_head.portalplane.dist;
914 else if (d > p->radius)
916 stack.pass = p->winding;
920 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
926 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
936 d = DotProduct (thread->base->origin, p->plane.normal);
940 if (d > thread->base->radius)
945 //if (d < -p->radius)
946 else if (d < -thread->base->radius)
948 stack.source = prevstack->source;
952 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
953 //FIXME: shouldn't we create a new source origin and radius for fast checks?
959 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
964 if (!prevstack->pass)
965 { // the second leaf can only be blocked if coplanar
967 // mark the portal as visible
968 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
970 RecursivePassagePortalFlow (p, thread, &stack);
974 #ifdef SEPERATORCACHE
975 if (stack.numseperators[0])
977 for (n = 0; n < stack.numseperators[0]; n++)
979 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
981 break; // target is not visible
983 if (n < stack.numseperators[0])
988 stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
991 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
996 #ifdef SEPERATORCACHE
997 if (stack.numseperators[1])
999 for (n = 0; n < stack.numseperators[1]; n++)
1001 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
1003 break; // target is not visible
1008 stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
1011 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
1016 // mark the portal as visible
1017 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
1019 // flow through it for real
1020 RecursivePassagePortalFlow(p, thread, &stack);
1031 void PassagePortalFlow (int portalnum)
1036 // int c_might, c_can;
1039 Sys_Printf("\r%6d", portalnum);
1042 p = sorted_portals[portalnum];
1046 p->status = stat_done;
1050 p->status = stat_working;
1052 // c_might = CountBits (p->portalflood, numportals*2);
1054 memset (&data, 0, sizeof(data));
1057 data.pstack_head.portal = p;
1058 data.pstack_head.source = p->winding;
1059 data.pstack_head.portalplane = p->plane;
1060 data.pstack_head.depth = 0;
1061 for (i=0 ; i<portallongs ; i++)
1062 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
1064 RecursivePassagePortalFlow (p, &data, &data.pstack_head);
1066 p->status = stat_done;
1069 c_can = CountBits (p->portalvis, numportals*2);
1071 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
1072 (int)(p - portals), c_might, c_can, data.c_chains);
1076 fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split)
1085 fixedWinding_t *neww;
1087 counts[0] = counts[1] = counts[2] = 0;
1089 // determine sides for each point
1090 for (i=0 ; i<in->numpoints ; i++)
1092 dot = DotProduct (in->points[i], split->normal);
1095 if (dot > ON_EPSILON)
1096 sides[i] = SIDE_FRONT;
1097 else if (dot < -ON_EPSILON)
1098 sides[i] = SIDE_BACK;
1107 return in; // completely on front side
1114 sides[i] = sides[0];
1115 dists[i] = dists[0];
1119 neww->numpoints = 0;
1121 for (i=0 ; i<in->numpoints ; i++)
1125 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1127 return in; // can't chop -- fall back to original
1130 if (sides[i] == SIDE_ON)
1132 VectorCopy (p1, neww->points[neww->numpoints]);
1137 if (sides[i] == SIDE_FRONT)
1139 VectorCopy (p1, neww->points[neww->numpoints]);
1143 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1146 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1148 return in; // can't chop -- fall back to original
1151 // generate a split point
1152 p2 = in->points[(i+1)%in->numpoints];
1154 dot = dists[i] / (dists[i]-dists[i+1]);
1155 for (j=0 ; j<3 ; j++)
1156 { // avoid round off error when possible
1157 if (split->normal[j] == 1)
1158 mid[j] = split->dist;
1159 else if (split->normal[j] == -1)
1160 mid[j] = -split->dist;
1162 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1165 VectorCopy (mid, neww->points[neww->numpoints]);
1177 int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators)
1184 int counts[3], numseperators;
1188 // check all combinations
1189 for (i=0 ; i<source->numpoints ; i++)
1191 l = (i+1)%source->numpoints;
1192 VectorSubtract (source->points[l] , source->points[i], v1);
1194 // find a vertex of pass that makes a plane that puts all of the
1195 // vertexes of pass on the front side and all of the vertexes of
1196 // source on the back side
1197 for (j=0 ; j<pass->numpoints ; j++)
1199 VectorSubtract (pass->points[j], source->points[i], v2);
1201 plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
1202 plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
1203 plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
1205 // if points don't make a valid plane, skip it
1207 length = plane.normal[0] * plane.normal[0]
1208 + plane.normal[1] * plane.normal[1]
1209 + plane.normal[2] * plane.normal[2];
1211 if (length < ON_EPSILON)
1214 length = 1/sqrt(length);
1216 plane.normal[0] *= length;
1217 plane.normal[1] *= length;
1218 plane.normal[2] *= length;
1220 plane.dist = DotProduct (pass->points[j], plane.normal);
1223 // find out which side of the generated seperating plane has the
1228 for (k=0 ; k<source->numpoints ; k++)
1230 if (k == i || k == l)
1232 d = DotProduct (source->points[k], plane.normal) - plane.dist;
1233 if (d < -ON_EPSILON)
1234 { // source is on the negative side, so we want all
1235 // pass and target on the positive side
1239 else if (d > ON_EPSILON)
1240 { // source is on the positive side, so we want all
1241 // pass and target on the negative side
1246 if (k == source->numpoints)
1247 continue; // planar with source portal
1249 fliptest = flipclip;
1252 // flip the normal if the source portal is backwards
1256 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1257 plane.dist = -plane.dist;
1261 // if all of the pass portal points are now on the positive side,
1262 // this is the seperating plane
1264 counts[0] = counts[1] = counts[2] = 0;
1265 for (k=0 ; k<pass->numpoints ; k++)
1269 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1270 if (d < -ON_EPSILON)
1272 else if (d > ON_EPSILON)
1277 if (k != pass->numpoints)
1278 continue; // points on negative side, not a seperating plane
1281 continue; // planar with seperating plane
1283 k = (j+1)%pass->numpoints;
1284 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1285 if (d < -ON_EPSILON)
1287 k = (j+pass->numpoints-1)%pass->numpoints;
1288 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1289 if (d < -ON_EPSILON)
1293 // flip the normal if we want the back side
1297 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1298 plane.dist = -plane.dist;
1301 if (numseperators >= maxseperators)
1302 Error("max seperators");
1303 seperators[numseperators] = plane;
1308 return numseperators;
1315 MrE: create passages from one portal to all the portals in the leaf the portal leads to
1316 every passage has a cansee bit string with all the portals that can be
1317 seen through the passage
1320 void CreatePassages(int portalnum)
1322 int i, j, k, n, numseperators, numsee;
1324 vportal_t *portal, *p, *target;
1326 passage_t *passage, *lastpassage;
1327 visPlane_t seperators[MAX_SEPERATORS*2];
1329 fixedWinding_t in, out, *res;
1333 Sys_Printf("\r%6d", portalnum);
1336 portal = sorted_portals[portalnum];
1338 if (portal->removed)
1340 portal->status = stat_done;
1345 leaf = &leafs[portal->leaf];
1346 for (i = 0; i < leaf->numportals; i++)
1348 target = leaf->portals[i];
1349 if (target->removed)
1352 passage = (passage_t *) safe_malloc(sizeof(passage_t) + portalbytes);
1353 memset(passage, 0, sizeof(passage_t) + portalbytes);
1354 numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
1355 numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
1357 passage->next = NULL;
1359 lastpassage->next = passage;
1361 portal->passages = passage;
1362 lastpassage = passage;
1365 //create the passage->cansee
1366 for (j = 0; j < numportals * 2; j++)
1371 if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
1373 if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
1375 for (k = 0; k < numseperators; k++)
1378 d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
1379 //if completely at the back of the seperator plane
1380 if (d < -p->radius + ON_EPSILON)
1383 for (n = 0; n < w->numpoints; n++)
1385 d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
1386 //if at the front of the seperator
1390 //if no points are at the front of the seperator
1391 if (n >= w->numpoints)
1394 if (k < numseperators)
1397 /* explitive deleted */
1400 /* ydnar: prefer correctness to stack overflow */
1401 //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1402 if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING )
1403 memcpy( &in, p->winding, (int) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) );
1405 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1408 for( k = 0; k < numseperators; k++ )
1410 /* ydnar: this is a shitty crutch */
1411 if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING )
1413 //% Sys_Printf( "[%d]", p->winding->numpoints );
1414 in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1417 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1419 memcpy( &in, &out, sizeof( fixedWinding_t ) );
1425 if (k < numseperators)
1427 passage->cansee[j >> 3] |= (1<<(j&7));
1433 void PassageMemory(void)
1435 int i, j, totalmem, totalportals;
1436 vportal_t *portal, *target;
1441 for (i = 0; i < numportals; i++)
1443 portal = sorted_portals[i];
1444 if (portal->removed)
1446 leaf = &leafs[portal->leaf];
1447 for (j = 0; j < leaf->numportals; j++)
1449 target = leaf->portals[j];
1450 if (target->removed)
1452 totalmem += sizeof(passage_t) + portalbytes;
1456 Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals);
1457 Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
1461 ===============================================================================
1463 This is a rough first-order aproximation that is used to trivially reject some
1464 of the final calculations.
1467 Calculates portalfront and portalflood bit vectors
1471 typedef struct passage_s
1473 struct passage_s *next;
1474 struct portal_s *to;
1475 stryct sep_s *seperators;
1479 typedef struct portal_s
1481 struct passage_s *passages;
1482 int leaf; // leaf portal faces into
1490 calc portal visibility
1496 for a portal to be visible to a passage, it must be on the front of
1497 all seperating planes, and both portals must be behind the new portal
1499 ===============================================================================
1511 void SimpleFlood (vportal_t *srcportal, int leafnum)
1518 leaf = &leafs[leafnum];
1520 for (i=0 ; i<leaf->numportals ; i++)
1522 p = leaf->portals[i];
1526 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
1529 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
1532 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
1534 SimpleFlood (srcportal, p->leaf);
1543 void BasePortalVis( int portalnum )
1552 p = portals+portalnum;
1557 p->portalfront = safe_malloc (portalbytes);
1558 memset (p->portalfront, 0, portalbytes);
1560 p->portalflood = safe_malloc (portalbytes);
1561 memset (p->portalflood, 0, portalbytes);
1563 p->portalvis = safe_malloc (portalbytes);
1564 memset (p->portalvis, 0, portalbytes);
1566 for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
1568 if( j == portalnum )
1573 /* ydnar: this is old farplane vis code from mre */
1575 if (farplanedist >= 0)
1578 VectorSubtract(p->origin, tp->origin, dir);
1579 if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1584 /* ydnar: this is known-to-be-working farplane code */
1585 if( farPlaneDist > 0.0f )
1587 VectorSubtract( p->origin, tp->origin, dir );
1588 if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist )
1594 for (k=0 ; k<w->numpoints ; k++)
1596 d = DotProduct (w->points[k], p->plane.normal)
1601 if (k == w->numpoints)
1602 continue; // no points on front
1605 for (k=0 ; k<w->numpoints ; k++)
1607 d = DotProduct (w->points[k], tp->plane.normal)
1609 if (d < -ON_EPSILON)
1612 if (k == w->numpoints)
1613 continue; // no points on front
1615 p->portalfront[j>>3] |= (1<<(j&7));
1618 SimpleFlood (p, p->leaf);
1620 p->nummightsee = CountBits (p->portalflood, numportals*2);
1621 // Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1622 c_flood += p->nummightsee;
1630 ===============================================================================
1632 This is a second order aproximation
1634 Calculates portalvis bit vector
1638 ===============================================================================
1643 RecursiveLeafBitFlow
1647 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
1654 byte newmight[MAX_PORTALS/8];
1656 leaf = &leafs[leafnum];
1658 // check all portals for flowing into other leafs
1659 for (i=0 ; i<leaf->numportals ; i++)
1661 p = leaf->portals[i];
1666 // if some previous portal can't see it, skip
1667 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
1670 // if this portal can see some portals we mightsee, recurse
1672 for (j=0 ; j<portallongs ; j++)
1674 ((long *)newmight)[j] = ((long *)mightsee)[j]
1675 & ((long *)p->portalflood)[j];
1676 more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
1680 continue; // can't see anything new
1682 cansee[pnum>>3] |= (1<<(pnum&7));
1684 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
1693 void BetterPortalVis (int portalnum)
1697 p = portals+portalnum;
1702 RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
1704 // build leaf vis information
1705 p->nummightsee = CountBits (p->portalvis, numportals*2);
1706 c_vis += p->nummightsee;