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