2 ===========================================================================
3 Copyright (C) 1997-2006 Id Software, Inc.
5 This file is part of Quake 2 Tools source code.
7 Quake 2 Tools source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
12 Quake 2 Tools source code is distributed in the hope that it will be
13 useful, 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 Quake 2 Tools source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
26 each portal will have a list of all possible to see from first portal
28 if (!thread->portalmightsee[portalnum])
32 for p2 = all other portals in leaf
34 for all portals that might be seen by p2
35 mark as unseen if not present in seperating plane
36 flood fill a new mightsee
37 save as passagemightsee
40 void CalcMightSee (leaf_t *leaf,
43 int CountBits (byte *bits, int numbits)
49 for (i=0 ; i<numbits ; i++)
50 if (bits[i>>3] & (1<<(i&7)) )
57 int c_portalskip, c_leafskip;
58 int c_vistest, c_mighttest;
64 void CheckStack (leaf_t *leaf, threaddata_t *thread)
68 for (p=thread->pstack_head.next ; p ; p=p->next)
72 Error ("CheckStack: leaf recursion");
73 for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
74 if (p2->leaf == p->leaf)
75 Error ("CheckStack: late leaf recursion");
81 winding_t *AllocStackWinding (pstack_t *stack)
87 if (stack->freewindings[i])
89 stack->freewindings[i] = 0;
90 return &stack->windings[i];
94 Error ("AllocStackWinding: failed");
99 void FreeStackWinding (winding_t *w, pstack_t *stack)
103 i = w - stack->windings;
106 return; // not from local
108 if (stack->freewindings[i])
109 Error ("FreeStackWinding: allready free");
110 stack->freewindings[i] = 1;
119 winding_t *ChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
130 counts[0] = counts[1] = counts[2] = 0;
132 // determine sides for each point
133 for (i=0 ; i<in->numpoints ; i++)
135 dot = DotProduct (in->points[i], split->normal);
138 if (dot > ON_EPSILON)
139 sides[i] = SIDE_FRONT;
140 else if (dot < -ON_EPSILON)
141 sides[i] = SIDE_BACK;
150 return in; // completely on front side
154 FreeStackWinding (in, stack);
161 neww = AllocStackWinding (stack);
165 for (i=0 ; i<in->numpoints ; i++)
169 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
171 FreeStackWinding (neww, stack);
172 return in; // can't chop -- fall back to original
175 if (sides[i] == SIDE_ON)
177 VectorCopy (p1, neww->points[neww->numpoints]);
182 if (sides[i] == SIDE_FRONT)
184 VectorCopy (p1, neww->points[neww->numpoints]);
188 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
191 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
193 FreeStackWinding (neww, stack);
194 return in; // can't chop -- fall back to original
197 // generate a split point
198 p2 = in->points[(i+1)%in->numpoints];
200 dot = dists[i] / (dists[i]-dists[i+1]);
201 for (j=0 ; j<3 ; j++)
202 { // avoid round off error when possible
203 if (split->normal[j] == 1)
204 mid[j] = split->dist;
205 else if (split->normal[j] == -1)
206 mid[j] = -split->dist;
208 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
211 VectorCopy (mid, neww->points[neww->numpoints]);
215 // free the original winding
216 FreeStackWinding (in, stack);
226 Source, pass, and target are an ordering of portals.
228 Generates seperating planes canidates by taking two points from source and one
229 point from pass, and clips target by them.
231 If target is totally clipped away, that portal can not be seen through.
233 Normal clip keeps target on the same side as pass, which is correct if the
234 order goes source, pass, target. If the order goes pass, source, target then
235 flipclip should be set.
238 winding_t *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
248 // check all combinations
249 for (i=0 ; i<source->numpoints ; i++)
251 l = (i+1)%source->numpoints;
252 VectorSubtract (source->points[l] , source->points[i], v1);
254 // fing a vertex of pass that makes a plane that puts all of the
255 // vertexes of pass on the front side and all of the vertexes of
256 // source on the back side
257 for (j=0 ; j<pass->numpoints ; j++)
259 VectorSubtract (pass->points[j], source->points[i], v2);
261 plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
262 plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
263 plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
265 // if points don't make a valid plane, skip it
267 length = plane.normal[0] * plane.normal[0]
268 + plane.normal[1] * plane.normal[1]
269 + plane.normal[2] * plane.normal[2];
271 if (length < ON_EPSILON)
274 length = 1/sqrt(length);
276 plane.normal[0] *= length;
277 plane.normal[1] *= length;
278 plane.normal[2] *= length;
280 plane.dist = DotProduct (pass->points[j], plane.normal);
283 // find out which side of the generated seperating plane has the
288 for (k=0 ; k<source->numpoints ; k++)
290 if (k == i || k == l)
292 d = DotProduct (source->points[k], plane.normal) - plane.dist;
294 { // source is on the negative side, so we want all
295 // pass and target on the positive side
299 else if (d > ON_EPSILON)
300 { // source is on the positive side, so we want all
301 // pass and target on the negative side
306 if (k == source->numpoints)
307 continue; // planar with source portal
312 // flip the normal if the source portal is backwards
316 VectorSubtract (vec3_origin, plane.normal, plane.normal);
317 plane.dist = -plane.dist;
321 // if all of the pass portal points are now on the positive side,
322 // this is the seperating plane
324 counts[0] = counts[1] = counts[2] = 0;
325 for (k=0 ; k<pass->numpoints ; k++)
329 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
332 else if (d > ON_EPSILON)
337 if (k != pass->numpoints)
338 continue; // points on negative side, not a seperating plane
341 continue; // planar with seperating plane
343 k = (j+1)%pass->numpoints;
344 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
347 k = (j+pass->numpoints-1)%pass->numpoints;
348 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
353 // flip the normal if we want the back side
357 VectorSubtract (vec3_origin, plane.normal, plane.normal);
358 plane.dist = -plane.dist;
362 // clip target by the seperating plane
364 target = ChopWinding (target, stack, &plane);
366 return NULL; // target is not visible
379 Flood fill through the leafs
380 If src_portal is NULL, this is the originating leaf
383 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
390 long *test, *might, *vis, more;
395 leaf = &leafs[leafnum];
396 // CheckStack (leaf, thread);
398 prevstack->next = &stack;
404 might = (long *)stack.mightsee;
405 vis = (long *)thread->base->portalvis;
407 // check all portals for flowing into other leafs
408 for (i=0 ; i<leaf->numportals ; i++)
410 p = leaf->portals[i];
413 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
415 continue; // can't possibly see it
418 // if the portal can't see anything we haven't allready seen, skip it
419 if (p->status == stat_done)
421 test = (long *)p->portalvis;
425 test = (long *)p->portalflood;
429 for (j=0 ; j<portallongs ; j++)
431 might[j] = ((long *)prevstack->mightsee)[j] & test[j];
432 more |= (might[j] & ~vis[j]);
436 (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
437 { // can't see anything new
441 // get plane of portal, point normal into the neighbor leaf
442 stack.portalplane = p->plane;
443 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
444 backplane.dist = -p->plane.dist;
450 stack.freewindings[0] = 1;
451 stack.freewindings[1] = 1;
452 stack.freewindings[2] = 1;
458 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
459 d -= thread->pstack_head.portalplane.dist;
464 else if (d > p->radius)
466 stack.pass = p->winding;
470 stack.pass = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
476 stack.pass = ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
486 d = DotProduct (thread->base->origin, p->plane.normal);
492 else if (d < -p->radius)
494 stack.source = prevstack->source;
498 stack.source = ChopWinding (prevstack->source, &stack, &backplane);
504 stack.source = ChopWinding (prevstack->source, &stack, &backplane);
509 if (!prevstack->pass)
510 { // the second leaf can only be blocked if coplanar
512 // mark the portal as visible
513 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
515 RecursiveLeafFlow (p->leaf, thread, &stack);
519 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);
523 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);
527 // mark the portal as visible
528 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
530 // flow through it for real
531 RecursiveLeafFlow (p->leaf, thread, &stack);
540 generates the portalvis bit vector
543 void PortalFlow (int portalnum)
550 p = sorted_portals[portalnum];
551 p->status = stat_working;
553 c_might = CountBits (p->portalflood, numportals*2);
555 memset (&data, 0, sizeof(data));
558 data.pstack_head.portal = p;
559 data.pstack_head.source = p->winding;
560 data.pstack_head.portalplane = p->plane;
561 for (i=0 ; i<portallongs ; i++)
562 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
563 RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
565 p->status = stat_done;
567 c_can = CountBits (p->portalvis, numportals*2);
569 qprintf ("portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
570 (int)(p - portals), c_might, c_can, data.c_chains);
575 ===============================================================================
577 This is a rough first-order aproximation that is used to trivially reject some
578 of the final calculations.
581 Calculates portalfront and portalflood bit vectors
585 typedef struct passage_s
587 struct passage_s *next;
589 stryct sep_s *seperators;
593 typedef struct portal_s
595 struct passage_s *passages;
596 int leaf; // leaf portal faces into
604 calc portal visibility
610 for a portal to be visible to a passage, it must be on the front of
611 all seperating planes, and both portals must be behind the mew portal
613 ===============================================================================
625 void SimpleFlood (portal_t *srcportal, int leafnum)
632 leaf = &leafs[leafnum];
634 for (i=0 ; i<leaf->numportals ; i++)
636 p = leaf->portals[i];
638 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
641 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
644 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
646 SimpleFlood (srcportal, p->leaf);
655 void BasePortalVis (int portalnum)
662 p = portals+portalnum;
664 p->portalfront = malloc (portalbytes);
665 memset (p->portalfront, 0, portalbytes);
667 p->portalflood = malloc (portalbytes);
668 memset (p->portalflood, 0, portalbytes);
670 p->portalvis = malloc (portalbytes);
671 memset (p->portalvis, 0, portalbytes);
673 for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
678 for (k=0 ; k<w->numpoints ; k++)
680 d = DotProduct (w->points[k], p->plane.normal)
685 if (k == w->numpoints)
686 continue; // no points on front
689 for (k=0 ; k<w->numpoints ; k++)
691 d = DotProduct (w->points[k], tp->plane.normal)
696 if (k == w->numpoints)
697 continue; // no points on front
699 p->portalfront[j>>3] |= (1<<(j&7));
702 SimpleFlood (p, p->leaf);
704 p->nummightsee = CountBits (p->portalflood, numportals*2);
705 // printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
706 c_flood += p->nummightsee;
714 ===============================================================================
716 This is a second order aproximation
718 Calculates portalvis bit vector
722 ===============================================================================
731 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
738 byte newmight[MAX_PORTALS/8];
740 leaf = &leafs[leafnum];
742 // check all portals for flowing into other leafs
743 for (i=0 ; i<leaf->numportals ; i++)
745 p = leaf->portals[i];
748 // if some previous portal can't see it, skip
749 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
752 // if this portal can see some portals we mightsee, recurse
754 for (j=0 ; j<portallongs ; j++)
756 ((long *)newmight)[j] = ((long *)mightsee)[j]
757 & ((long *)p->portalflood)[j];
758 more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
762 continue; // can't see anything new
764 cansee[pnum>>3] |= (1<<(pnum&7));
766 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
775 void BetterPortalVis (int portalnum)
779 p = portals+portalnum;
781 RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
783 // build leaf vis information
784 p->nummightsee = CountBits (p->portalvis, numportals*2);
785 c_vis += p->nummightsee;