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)
67 for (i=0 ; i<numbits ; i++)
68 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)
86 for (p=thread->pstack_head.next ; p ; p=p->next)
90 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");
99 fixedWinding_t *AllocStackWinding (pstack_t *stack)
103 for (i=0 ; i<3 ; i++)
105 if (stack->freewindings[i])
107 stack->freewindings[i] = 0;
108 return &stack->windings[i];
112 Error ("AllocStackWinding: failed");
117 void FreeStackWinding (fixedWinding_t *w, pstack_t *stack)
121 i = w - stack->windings;
124 return; // not from local
126 if (stack->freewindings[i])
127 Error ("FreeStackWinding: allready free");
128 stack->freewindings[i] = 1;
137 fixedWinding_t *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_t *split)
146 fixedWinding_t *neww;
148 counts[0] = counts[1] = counts[2] = 0;
150 // determine sides for each point
151 for (i=0 ; i<in->numpoints ; i++)
153 dot = DotProduct (in->points[i], split->normal);
156 if (dot > ON_EPSILON)
157 sides[i] = SIDE_FRONT;
158 else if (dot < -ON_EPSILON)
159 sides[i] = SIDE_BACK;
168 return in; // completely on front side
172 FreeStackWinding (in, stack);
179 neww = AllocStackWinding (stack);
183 for (i=0 ; i<in->numpoints ; i++)
187 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)
195 VectorCopy (p1, neww->points[neww->numpoints]);
200 if (sides[i] == SIDE_FRONT)
202 VectorCopy (p1, neww->points[neww->numpoints]);
206 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
209 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
211 FreeStackWinding (neww, stack);
212 return in; // can't chop -- fall back to original
215 // generate a split point
216 p2 = in->points[(i+1)%in->numpoints];
218 dot = dists[i] / (dists[i]-dists[i+1]);
219 for (j=0 ; j<3 ; j++)
220 { // avoid round off error when possible
221 if (split->normal[j] == 1)
222 mid[j] = split->dist;
223 else if (split->normal[j] == -1)
224 mid[j] = -split->dist;
226 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
229 VectorCopy (mid, neww->points[neww->numpoints]);
233 // free the original winding
234 FreeStackWinding (in, stack);
243 Source, pass, and target are an ordering of portals.
245 Generates seperating planes canidates by taking two points from source and one
246 point from pass, and clips target by them.
248 If target is totally clipped away, that portal can not be seen through.
250 Normal clip keeps target on the same side as pass, which is correct if the
251 order goes source, pass, target. If the order goes pass, source, target then
252 flipclip should be set.
255 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)
291 length = 1/sqrt(length);
293 plane.normal[0] *= length;
294 plane.normal[1] *= length;
295 plane.normal[2] *= length;
297 plane.dist = DotProduct (pass->points[j], plane.normal);
300 // find out which side of the generated seperating plane has the
305 for (k=0 ; k<source->numpoints ; k++)
307 if (k == i || k == l)
309 d = DotProduct (source->points[k], plane.normal) - plane.dist;
311 { // source is on the negative side, so we want all
312 // pass and target on the positive side
316 else if (d > ON_EPSILON)
317 { // 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
329 // 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++)
346 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
349 else if (d > ON_EPSILON)
354 if (k != pass->numpoints)
355 continue; // points on negative side, not a seperating plane
358 continue; // planar with seperating plane
360 k = (j+1)%pass->numpoints;
361 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
364 k = (j+pass->numpoints-1)%pass->numpoints;
365 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
370 // flip the normal if we want the back side
374 VectorSubtract (vec3_origin, plane.normal, plane.normal);
375 plane.dist = -plane.dist;
378 #ifdef SEPERATORCACHE
379 stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
380 if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
381 Error("MAX_SEPERATORS");
383 //MrE: fast check first
384 d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
385 //if completely at the back of the seperator plane
386 if (d < -stack->portal->radius)
388 //if completely on the front of the seperator plane
389 if (d > stack->portal->radius)
393 // clip target by the seperating plane
395 target = VisChopWinding (target, stack, &plane);
397 return NULL; // target is not visible
399 break; // optimization by Antony Suter
410 Flood fill through the leafs
411 If src_portal is NULL, this is the originating leaf
414 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
418 visPlane_t backplane;
421 long *test, *might, *prevmight, *vis, more;
426 leaf = &leafs[leafnum];
427 // CheckStack (leaf, thread);
429 prevstack->next = &stack;
434 stack.depth = prevstack->depth + 1;
436 #ifdef SEPERATORCACHE
437 stack.numseperators[0] = 0;
438 stack.numseperators[1] = 0;
441 might = (long *)stack.mightsee;
442 vis = (long *)thread->base->portalvis;
444 // check all portals for flowing into other leafs
445 for (i = 0; i < leaf->numportals; i++)
447 p = leaf->portals[i];
452 /* MrE: portal trace debug code
454 int portaltrace[] = {13, 16, 17, 37};
457 s = &thread->pstack_head;
458 for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
460 if (s->portal->num != portaltrace[j])
463 if (j >= sizeof(portaltrace)/sizeof(int) - 1)
465 if (p->num == portaltrace[j])
466 n = 0; //traced through all the portals
471 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
473 continue; // can't possibly see it
476 // if the portal can't see anything we haven't allready seen, skip it
477 if (p->status == stat_done)
479 test = (long *)p->portalvis;
483 test = (long *)p->portalflood;
487 prevmight = (long *)prevstack->mightsee;
488 for (j=0 ; j<portallongs ; j++)
490 might[j] = prevmight[j] & test[j];
491 more |= (might[j] & ~vis[j]);
495 (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
496 { // can't see anything new
500 // get plane of portal, point normal into the neighbor leaf
501 stack.portalplane = p->plane;
502 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
503 backplane.dist = -p->plane.dist;
509 stack.freewindings[0] = 1;
510 stack.freewindings[1] = 1;
511 stack.freewindings[2] = 1;
517 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
518 d -= thread->pstack_head.portalplane.dist;
523 else if (d > p->radius)
525 stack.pass = p->winding;
529 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
535 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
545 d = DotProduct (thread->base->origin, p->plane.normal);
549 if (d > thread->base->radius)
554 //if (d < -p->radius)
555 else if (d < -thread->base->radius)
557 stack.source = prevstack->source;
561 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
562 //FIXME: shouldn't we create a new source origin and radius for fast checks?
568 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
573 if (!prevstack->pass)
574 { // the second leaf can only be blocked if coplanar
576 // mark the portal as visible
577 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
579 RecursiveLeafFlow (p->leaf, thread, &stack);
583 #ifdef SEPERATORCACHE
584 if (stack.numseperators[0])
586 for (n = 0; n < stack.numseperators[0]; n++)
588 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
590 break; // target is not visible
592 if (n < stack.numseperators[0])
597 stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
600 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
605 #ifdef SEPERATORCACHE
606 if (stack.numseperators[1])
608 for (n = 0; n < stack.numseperators[1]; n++)
610 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
612 break; // target is not visible
617 stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
620 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
625 // mark the portal as visible
626 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
628 // flow through it for real
629 RecursiveLeafFlow (p->leaf, thread, &stack);
639 generates the portalvis bit vector
642 void PortalFlow (int portalnum)
650 Sys_Printf("\r%6d", portalnum);
653 p = sorted_portals[portalnum];
657 p->status = stat_done;
661 p->status = stat_working;
663 c_might = CountBits (p->portalflood, numportals*2);
665 memset (&data, 0, sizeof(data));
668 data.pstack_head.portal = p;
669 data.pstack_head.source = p->winding;
670 data.pstack_head.portalplane = p->plane;
671 data.pstack_head.depth = 0;
672 for (i=0 ; i<portallongs ; i++)
673 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
675 RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
677 p->status = stat_done;
679 c_can = CountBits (p->portalvis, numportals*2);
681 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
682 (int)(p - portals), c_might, c_can, data.c_chains);
690 void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
695 passage_t *passage, *nextpassage;
697 long *might, *vis, *prevmight, *cansee, *portalvis, more;
700 leaf = &leafs[portal->leaf];
702 prevstack->next = &stack;
705 stack.depth = prevstack->depth + 1;
707 vis = (long *)thread->base->portalvis;
709 passage = portal->passages;
710 nextpassage = passage;
711 // check all portals for flowing into other leafs
712 for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
714 p = leaf->portals[i];
718 nextpassage = passage->next;
721 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
722 continue; // can't possibly see it
725 // mark the portal as visible
726 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
728 prevmight = (long *)prevstack->mightsee;
729 cansee = (long *)passage->cansee;
730 might = (long *)stack.mightsee;
731 memcpy(might, prevmight, portalbytes);
732 if (p->status == stat_done)
733 portalvis = (long *) p->portalvis;
735 portalvis = (long *) p->portalflood;
737 for (j = 0; j < portallongs; j++)
741 *might &= *cansee++ & *portalvis++;
742 more |= (*might & ~vis[j]);
753 // can't see anything new
757 // flow through it for real
758 RecursivePassageFlow(p, thread, &stack);
769 void PassageFlow (int portalnum)
774 // int c_might, c_can;
777 Sys_Printf("\r%6d", portalnum);
780 p = sorted_portals[portalnum];
784 p->status = stat_done;
788 p->status = stat_working;
790 // c_might = CountBits (p->portalflood, numportals*2);
792 memset (&data, 0, sizeof(data));
795 data.pstack_head.portal = p;
796 data.pstack_head.source = p->winding;
797 data.pstack_head.portalplane = p->plane;
798 data.pstack_head.depth = 0;
799 for (i=0 ; i<portallongs ; i++)
800 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
802 RecursivePassageFlow (p, &data, &data.pstack_head);
804 p->status = stat_done;
807 c_can = CountBits (p->portalvis, numportals*2);
809 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
810 (int)(p - portals), c_might, c_can, data.c_chains);
816 RecursivePassagePortalFlow
819 void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
824 visPlane_t backplane;
825 passage_t *passage, *nextpassage;
827 long *might, *vis, *prevmight, *cansee, *portalvis, more;
830 // thread->c_chains++;
832 leaf = &leafs[portal->leaf];
833 // CheckStack (leaf, thread);
835 prevstack->next = &stack;
840 stack.depth = prevstack->depth + 1;
842 #ifdef SEPERATORCACHE
843 stack.numseperators[0] = 0;
844 stack.numseperators[1] = 0;
847 vis = (long *)thread->base->portalvis;
849 passage = portal->passages;
850 nextpassage = passage;
851 // check all portals for flowing into other leafs
852 for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
854 p = leaf->portals[i];
857 nextpassage = passage->next;
860 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
861 continue; // can't possibly see it
863 prevmight = (long *)prevstack->mightsee;
864 cansee = (long *)passage->cansee;
865 might = (long *)stack.mightsee;
866 memcpy(might, prevmight, portalbytes);
867 if (p->status == stat_done)
868 portalvis = (long *) p->portalvis;
870 portalvis = (long *) p->portalflood;
872 for (j = 0; j < portallongs; j++)
876 *might &= *cansee++ & *portalvis++;
877 more |= (*might & ~vis[j]);
887 if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
888 { // can't see anything new
892 // get plane of portal, point normal into the neighbor leaf
893 stack.portalplane = p->plane;
894 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
895 backplane.dist = -p->plane.dist;
901 stack.freewindings[0] = 1;
902 stack.freewindings[1] = 1;
903 stack.freewindings[2] = 1;
909 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
910 d -= thread->pstack_head.portalplane.dist;
915 else if (d > p->radius)
917 stack.pass = p->winding;
921 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
927 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
937 d = DotProduct (thread->base->origin, p->plane.normal);
941 if (d > thread->base->radius)
946 //if (d < -p->radius)
947 else if (d < -thread->base->radius)
949 stack.source = prevstack->source;
953 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
954 //FIXME: shouldn't we create a new source origin and radius for fast checks?
960 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
965 if (!prevstack->pass)
966 { // the second leaf can only be blocked if coplanar
968 // mark the portal as visible
969 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
971 RecursivePassagePortalFlow (p, thread, &stack);
975 #ifdef SEPERATORCACHE
976 if (stack.numseperators[0])
978 for (n = 0; n < stack.numseperators[0]; n++)
980 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
982 break; // target is not visible
984 if (n < stack.numseperators[0])
989 stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
992 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
997 #ifdef SEPERATORCACHE
998 if (stack.numseperators[1])
1000 for (n = 0; n < stack.numseperators[1]; n++)
1002 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
1004 break; // target is not visible
1009 stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
1012 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
1017 // mark the portal as visible
1018 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
1020 // flow through it for real
1021 RecursivePassagePortalFlow(p, thread, &stack);
1032 void PassagePortalFlow (int portalnum)
1037 // int c_might, c_can;
1040 Sys_Printf("\r%6d", portalnum);
1043 p = sorted_portals[portalnum];
1047 p->status = stat_done;
1051 p->status = stat_working;
1053 // c_might = CountBits (p->portalflood, numportals*2);
1055 memset (&data, 0, sizeof(data));
1058 data.pstack_head.portal = p;
1059 data.pstack_head.source = p->winding;
1060 data.pstack_head.portalplane = p->plane;
1061 data.pstack_head.depth = 0;
1062 for (i=0 ; i<portallongs ; i++)
1063 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
1065 RecursivePassagePortalFlow (p, &data, &data.pstack_head);
1067 p->status = stat_done;
1070 c_can = CountBits (p->portalvis, numportals*2);
1072 Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
1073 (int)(p - portals), c_might, c_can, data.c_chains);
1077 fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split)
1086 fixedWinding_t *neww;
1088 counts[0] = counts[1] = counts[2] = 0;
1090 // determine sides for each point
1091 for (i=0 ; i<in->numpoints ; i++)
1093 dot = DotProduct (in->points[i], split->normal);
1096 if (dot > ON_EPSILON)
1097 sides[i] = SIDE_FRONT;
1098 else if (dot < -ON_EPSILON)
1099 sides[i] = SIDE_BACK;
1108 return in; // completely on front side
1115 sides[i] = sides[0];
1116 dists[i] = dists[0];
1120 neww->numpoints = 0;
1122 for (i=0 ; i<in->numpoints ; i++)
1126 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1128 return in; // can't chop -- fall back to original
1131 if (sides[i] == SIDE_ON)
1133 VectorCopy (p1, neww->points[neww->numpoints]);
1138 if (sides[i] == SIDE_FRONT)
1140 VectorCopy (p1, neww->points[neww->numpoints]);
1144 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
1147 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
1149 return in; // can't chop -- fall back to original
1152 // generate a split point
1153 p2 = in->points[(i+1)%in->numpoints];
1155 dot = dists[i] / (dists[i]-dists[i+1]);
1156 for (j=0 ; j<3 ; j++)
1157 { // avoid round off error when possible
1158 if (split->normal[j] == 1)
1159 mid[j] = split->dist;
1160 else if (split->normal[j] == -1)
1161 mid[j] = -split->dist;
1163 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
1166 VectorCopy (mid, neww->points[neww->numpoints]);
1178 int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators)
1185 int counts[3], numseperators;
1189 // check all combinations
1190 for (i=0 ; i<source->numpoints ; i++)
1192 l = (i+1)%source->numpoints;
1193 VectorSubtract (source->points[l] , source->points[i], v1);
1195 // find a vertex of pass that makes a plane that puts all of the
1196 // vertexes of pass on the front side and all of the vertexes of
1197 // source on the back side
1198 for (j=0 ; j<pass->numpoints ; j++)
1200 VectorSubtract (pass->points[j], source->points[i], v2);
1202 plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
1203 plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
1204 plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
1206 // if points don't make a valid plane, skip it
1208 length = plane.normal[0] * plane.normal[0]
1209 + plane.normal[1] * plane.normal[1]
1210 + plane.normal[2] * plane.normal[2];
1212 if (length < ON_EPSILON)
1215 length = 1/sqrt(length);
1217 plane.normal[0] *= length;
1218 plane.normal[1] *= length;
1219 plane.normal[2] *= length;
1221 plane.dist = DotProduct (pass->points[j], plane.normal);
1224 // find out which side of the generated seperating plane has the
1229 for (k=0 ; k<source->numpoints ; k++)
1231 if (k == i || k == l)
1233 d = DotProduct (source->points[k], plane.normal) - plane.dist;
1234 if (d < -ON_EPSILON)
1235 { // source is on the negative side, so we want all
1236 // pass and target on the positive side
1240 else if (d > ON_EPSILON)
1241 { // source is on the positive side, so we want all
1242 // pass and target on the negative side
1247 if (k == source->numpoints)
1248 continue; // planar with source portal
1250 fliptest = flipclip;
1253 // flip the normal if the source portal is backwards
1257 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1258 plane.dist = -plane.dist;
1262 // if all of the pass portal points are now on the positive side,
1263 // this is the seperating plane
1265 counts[0] = counts[1] = counts[2] = 0;
1266 for (k=0 ; k<pass->numpoints ; k++)
1270 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1271 if (d < -ON_EPSILON)
1273 else if (d > ON_EPSILON)
1278 if (k != pass->numpoints)
1279 continue; // points on negative side, not a seperating plane
1282 continue; // planar with seperating plane
1284 k = (j+1)%pass->numpoints;
1285 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1286 if (d < -ON_EPSILON)
1288 k = (j+pass->numpoints-1)%pass->numpoints;
1289 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
1290 if (d < -ON_EPSILON)
1294 // flip the normal if we want the back side
1298 VectorSubtract (vec3_origin, plane.normal, plane.normal);
1299 plane.dist = -plane.dist;
1302 if (numseperators >= maxseperators)
1303 Error("max seperators");
1304 seperators[numseperators] = plane;
1309 return numseperators;
1316 MrE: create passages from one portal to all the portals in the leaf the portal leads to
1317 every passage has a cansee bit string with all the portals that can be
1318 seen through the passage
1321 void CreatePassages(int portalnum)
1323 int i, j, k, n, numseperators, numsee;
1325 vportal_t *portal, *p, *target;
1327 passage_t *passage, *lastpassage;
1328 visPlane_t seperators[MAX_SEPERATORS*2];
1330 fixedWinding_t in, out, *res;
1334 Sys_Printf("\r%6d", portalnum);
1337 portal = sorted_portals[portalnum];
1339 if (portal->removed)
1341 portal->status = stat_done;
1346 leaf = &leafs[portal->leaf];
1347 for (i = 0; i < leaf->numportals; i++)
1349 target = leaf->portals[i];
1350 if (target->removed)
1353 passage = (passage_t *) safe_malloc(sizeof(passage_t) + portalbytes);
1354 memset(passage, 0, sizeof(passage_t) + portalbytes);
1355 numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
1356 numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
1358 passage->next = NULL;
1360 lastpassage->next = passage;
1362 portal->passages = passage;
1363 lastpassage = passage;
1366 //create the passage->cansee
1367 for (j = 0; j < numportals * 2; j++)
1372 if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
1374 if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
1376 for (k = 0; k < numseperators; k++)
1379 d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
1380 //if completely at the back of the seperator plane
1381 if (d < -p->radius + ON_EPSILON)
1384 for (n = 0; n < w->numpoints; n++)
1386 d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
1387 //if at the front of the seperator
1391 //if no points are at the front of the seperator
1392 if (n >= w->numpoints)
1395 if (k < numseperators)
1398 /* explitive deleted */
1401 /* ydnar: prefer correctness to stack overflow */
1402 //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
1403 if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING )
1404 memcpy( &in, p->winding, (size_t) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) );
1406 memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
1409 for( k = 0; k < numseperators; k++ )
1411 /* ydnar: this is a shitty crutch */
1412 if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING )
1414 //% Sys_Printf( "[%d]", p->winding->numpoints );
1415 in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
1418 res = PassageChopWinding( &in, &out, &seperators[ k ] );
1420 memcpy( &in, &out, sizeof( fixedWinding_t ) );
1426 if (k < numseperators)
1428 passage->cansee[j >> 3] |= (1<<(j&7));
1434 void PassageMemory(void)
1436 int i, j, totalmem, totalportals;
1437 vportal_t *portal, *target;
1442 for (i = 0; i < numportals; i++)
1444 portal = sorted_portals[i];
1445 if (portal->removed)
1447 leaf = &leafs[portal->leaf];
1448 for (j = 0; j < leaf->numportals; j++)
1450 target = leaf->portals[j];
1451 if (target->removed)
1453 totalmem += sizeof(passage_t) + portalbytes;
1457 Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals);
1458 Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
1462 ===============================================================================
1464 This is a rough first-order aproximation that is used to trivially reject some
1465 of the final calculations.
1468 Calculates portalfront and portalflood bit vectors
1472 typedef struct passage_s
1474 struct passage_s *next;
1475 struct portal_s *to;
1476 stryct sep_s *seperators;
1480 typedef struct portal_s
1482 struct passage_s *passages;
1483 int leaf; // leaf portal faces into
1491 calc portal visibility
1497 for a portal to be visible to a passage, it must be on the front of
1498 all seperating planes, and both portals must be behind the new portal
1500 ===============================================================================
1512 void SimpleFlood (vportal_t *srcportal, int leafnum)
1519 leaf = &leafs[leafnum];
1521 for (i=0 ; i<leaf->numportals ; i++)
1523 p = leaf->portals[i];
1527 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
1530 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
1533 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
1535 SimpleFlood (srcportal, p->leaf);
1544 void BasePortalVis( int portalnum )
1553 p = portals+portalnum;
1558 p->portalfront = safe_malloc (portalbytes);
1559 memset (p->portalfront, 0, portalbytes);
1561 p->portalflood = safe_malloc (portalbytes);
1562 memset (p->portalflood, 0, portalbytes);
1564 p->portalvis = safe_malloc (portalbytes);
1565 memset (p->portalvis, 0, portalbytes);
1567 for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
1569 if( j == portalnum )
1574 /* ydnar: this is old farplane vis code from mre */
1576 if (farplanedist >= 0)
1579 VectorSubtract(p->origin, tp->origin, dir);
1580 if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
1585 /* ydnar: this is known-to-be-working farplane code */
1586 if( farPlaneDist > 0.0f )
1588 VectorSubtract( p->origin, tp->origin, dir );
1589 if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist )
1595 for (k=0 ; k<w->numpoints ; k++)
1597 d = DotProduct (w->points[k], p->plane.normal)
1602 if (k == w->numpoints)
1603 continue; // no points on front
1606 for (k=0 ; k<w->numpoints ; k++)
1608 d = DotProduct (w->points[k], tp->plane.normal)
1610 if (d < -ON_EPSILON)
1613 if (k == w->numpoints)
1614 continue; // no points on front
1616 p->portalfront[j>>3] |= (1<<(j&7));
1619 SimpleFlood (p, p->leaf);
1621 p->nummightsee = CountBits (p->portalflood, numportals*2);
1622 // Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
1623 c_flood += p->nummightsee;
1631 ===============================================================================
1633 This is a second order aproximation
1635 Calculates portalvis bit vector
1639 ===============================================================================
1644 RecursiveLeafBitFlow
1648 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
1655 byte newmight[MAX_PORTALS/8];
1657 leaf = &leafs[leafnum];
1659 // check all portals for flowing into other leafs
1660 for (i=0 ; i<leaf->numportals ; i++)
1662 p = leaf->portals[i];
1667 // if some previous portal can't see it, skip
1668 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
1671 // if this portal can see some portals we mightsee, recurse
1673 for (j=0 ; j<portallongs ; j++)
1675 ((long *)newmight)[j] = ((long *)mightsee)[j]
1676 & ((long *)p->portalflood)[j];
1677 more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
1681 continue; // can't see anything new
1683 cansee[pnum>>3] |= (1<<(pnum&7));
1685 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
1694 void BetterPortalVis (int portalnum)
1698 p = portals+portalnum;
1703 RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
1705 // build leaf vis information
1706 p->nummightsee = CountBits (p->portalvis, numportals*2);
1707 c_vis += p->nummightsee;