2 Copyright (C) 1999-2006 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
25 each portal will have a list of all possible to see from first portal
27 if (!thread->portalmightsee[portalnum])
31 for p2 = all other portals in leaf
33 for all portals that might be seen by p2
34 mark as unseen if not present in seperating plane
35 flood fill a new mightsee
36 save as passagemightsee
39 void CalcMightSee (leaf_t *leaf,
42 int CountBits (byte *bits, int numbits)
48 for (i=0 ; i<numbits ; i++)
49 if (bits[i>>3] & (1<<(i&7)) )
56 int c_portalskip, c_leafskip;
57 int c_vistest, c_mighttest;
63 void CheckStack (leaf_t *leaf, threaddata_t *thread)
67 for (p=thread->pstack_head.next ; p ; p=p->next)
71 Error ("CheckStack: leaf recursion");
72 for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
73 if (p2->leaf == p->leaf)
74 Error ("CheckStack: late leaf recursion");
80 winding_t *AllocStackWinding (pstack_t *stack)
86 if (stack->freewindings[i])
88 stack->freewindings[i] = 0;
89 return &stack->windings[i];
93 Error ("AllocStackWinding: failed");
98 void FreeStackWinding (winding_t *w, pstack_t *stack)
102 i = w - stack->windings;
105 return; // not from local
107 if (stack->freewindings[i])
108 Error ("FreeStackWinding: allready free");
109 stack->freewindings[i] = 1;
118 winding_t *Vis_ChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
129 counts[0] = counts[1] = counts[2] = 0;
131 // determine sides for each point
132 for (i=0 ; i<in->numpoints ; i++)
134 dot = DotProduct (in->points[i], split->normal);
137 if (dot > ON_EPSILON)
138 sides[i] = SIDE_FRONT;
139 else if (dot < -ON_EPSILON)
140 sides[i] = SIDE_BACK;
149 return in; // completely on front side
153 FreeStackWinding (in, stack);
160 neww = AllocStackWinding (stack);
164 for (i=0 ; i<in->numpoints ; i++)
168 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
170 FreeStackWinding (neww, stack);
171 return in; // can't chop -- fall back to original
174 if (sides[i] == SIDE_ON)
176 VectorCopy (p1, neww->points[neww->numpoints]);
181 if (sides[i] == SIDE_FRONT)
183 VectorCopy (p1, neww->points[neww->numpoints]);
187 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
190 if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
192 FreeStackWinding (neww, stack);
193 return in; // can't chop -- fall back to original
196 // generate a split point
197 p2 = in->points[(i+1)%in->numpoints];
199 dot = dists[i] / (dists[i]-dists[i+1]);
200 for (j=0 ; j<3 ; j++)
201 { // avoid round off error when possible
202 if (split->normal[j] == 1)
203 mid[j] = split->dist;
204 else if (split->normal[j] == -1)
205 mid[j] = -split->dist;
207 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
210 VectorCopy (mid, neww->points[neww->numpoints]);
214 // free the original winding
215 FreeStackWinding (in, stack);
225 Source, pass, and target are an ordering of portals.
227 Generates seperating planes canidates by taking two points from source and one
228 point from pass, and clips target by them.
230 If target is totally clipped away, that portal can not be seen through.
232 Normal clip keeps target on the same side as pass, which is correct if the
233 order goes source, pass, target. If the order goes pass, source, target then
234 flipclip should be set.
237 winding_t *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
247 // check all combinations
248 for (i=0 ; i<source->numpoints ; i++)
250 l = (i+1)%source->numpoints;
251 VectorSubtract (source->points[l] , source->points[i], v1);
253 // fing a vertex of pass that makes a plane that puts all of the
254 // vertexes of pass on the front side and all of the vertexes of
255 // source on the back side
256 for (j=0 ; j<pass->numpoints ; j++)
258 VectorSubtract (pass->points[j], source->points[i], v2);
260 plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
261 plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
262 plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
264 // if points don't make a valid plane, skip it
266 length = plane.normal[0] * plane.normal[0]
267 + plane.normal[1] * plane.normal[1]
268 + plane.normal[2] * plane.normal[2];
270 if (length < ON_EPSILON)
273 length = 1/sqrt(length);
275 plane.normal[0] *= length;
276 plane.normal[1] *= length;
277 plane.normal[2] *= length;
279 plane.dist = DotProduct (pass->points[j], plane.normal);
282 // find out which side of the generated seperating plane has the
287 for (k=0 ; k<source->numpoints ; k++)
289 if (k == i || k == l)
291 d = DotProduct (source->points[k], plane.normal) - plane.dist;
293 { // source is on the negative side, so we want all
294 // pass and target on the positive side
298 else if (d > ON_EPSILON)
299 { // source is on the positive side, so we want all
300 // pass and target on the negative side
305 if (k == source->numpoints)
306 continue; // planar with source portal
311 // flip the normal if the source portal is backwards
315 VectorSubtract (vec3_origin, plane.normal, plane.normal);
316 plane.dist = -plane.dist;
320 // if all of the pass portal points are now on the positive side,
321 // this is the seperating plane
323 counts[0] = counts[1] = counts[2] = 0;
324 for (k=0 ; k<pass->numpoints ; k++)
328 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
331 else if (d > ON_EPSILON)
336 if (k != pass->numpoints)
337 continue; // points on negative side, not a seperating plane
340 continue; // planar with seperating plane
342 k = (j+1)%pass->numpoints;
343 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
346 k = (j+pass->numpoints-1)%pass->numpoints;
347 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
352 // flip the normal if we want the back side
356 VectorSubtract (vec3_origin, plane.normal, plane.normal);
357 plane.dist = -plane.dist;
361 // clip target by the seperating plane
363 target = Vis_ChopWinding (target, stack, &plane);
365 return NULL; // target is not visible
378 Flood fill through the leafs
379 If src_portal is NULL, this is the originating leaf
382 void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
389 long *test, *might, *vis, more;
394 leaf = &leafs[leafnum];
395 // CheckStack (leaf, thread);
397 prevstack->next = &stack;
403 might = (long *)stack.mightsee;
404 vis = (long *)thread->base->portalvis;
406 // check all portals for flowing into other leafs
407 for (i=0 ; i<leaf->numportals ; i++)
409 p = leaf->portals[i];
412 if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
414 continue; // can't possibly see it
417 // if the portal can't see anything we haven't allready seen, skip it
418 if (p->status == stat_done)
420 test = (long *)p->portalvis;
424 test = (long *)p->portalflood;
428 for (j=0 ; j<portallongs ; j++)
430 might[j] = ((long *)prevstack->mightsee)[j] & test[j];
431 more |= (might[j] & ~vis[j]);
435 (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
436 { // can't see anything new
440 // get plane of portal, point normal into the neighbor leaf
441 stack.portalplane = p->plane;
442 VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
443 backplane.dist = -p->plane.dist;
449 stack.freewindings[0] = 1;
450 stack.freewindings[1] = 1;
451 stack.freewindings[2] = 1;
457 d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
458 d -= thread->pstack_head.portalplane.dist;
463 else if (d > p->radius)
465 stack.pass = p->winding;
469 stack.pass = Vis_ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
475 stack.pass = Vis_ChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
485 d = DotProduct (thread->base->origin, p->plane.normal);
491 else if (d < -p->radius)
493 stack.source = prevstack->source;
497 stack.source = Vis_ChopWinding (prevstack->source, &stack, &backplane);
503 stack.source = Vis_ChopWinding (prevstack->source, &stack, &backplane);
508 if (!prevstack->pass)
509 { // the second leaf can only be blocked if coplanar
511 // mark the portal as visible
512 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
514 RecursiveLeafFlow (p->leaf, thread, &stack);
518 stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, false, &stack);
522 stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, true, &stack);
526 // mark the portal as visible
527 thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
529 // flow through it for real
530 RecursiveLeafFlow (p->leaf, thread, &stack);
539 generates the portalvis bit vector
542 void PortalFlow (int portalnum)
549 p = sorted_portals[portalnum];
550 p->status = stat_working;
552 c_might = CountBits (p->portalflood, numportals*2);
554 memset (&data, 0, sizeof(data));
557 data.pstack_head.portal = p;
558 data.pstack_head.source = p->winding;
559 data.pstack_head.portalplane = p->plane;
560 for (i=0 ; i<portallongs ; i++)
561 ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
562 RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
564 p->status = stat_done;
566 c_can = CountBits (p->portalvis, numportals*2);
568 Sys_FPrintf ( SYS_VRB, "portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
569 (int)(p - portals), c_might, c_can, data.c_chains);
574 ===============================================================================
576 This is a rough first-order aproximation that is used to trivially reject some
577 of the final calculations.
580 Calculates portalfront and portalflood bit vectors
584 typedef struct passage_s
586 struct passage_s *next;
588 stryct sep_s *seperators;
592 typedef struct portal_s
594 struct passage_s *passages;
595 int leaf; // leaf portal faces into
603 calc portal visibility
609 for a portal to be visible to a passage, it must be on the front of
610 all seperating planes, and both portals must be behind the mew portal
612 ===============================================================================
624 void SimpleFlood (portal_t *srcportal, int leafnum)
631 leaf = &leafs[leafnum];
633 for (i=0 ; i<leaf->numportals ; i++)
635 p = leaf->portals[i];
637 if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
640 if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
643 srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
645 SimpleFlood (srcportal, p->leaf);
654 void BasePortalVis (int portalnum)
661 p = portals+portalnum;
663 p->portalfront = malloc (portalbytes);
664 memset (p->portalfront, 0, portalbytes);
666 p->portalflood = malloc (portalbytes);
667 memset (p->portalflood, 0, portalbytes);
669 p->portalvis = malloc (portalbytes);
670 memset (p->portalvis, 0, portalbytes);
672 for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
677 for (k=0 ; k<w->numpoints ; k++)
679 d = DotProduct (w->points[k], p->plane.normal)
684 if (k == w->numpoints)
685 continue; // no points on front
688 for (k=0 ; k<w->numpoints ; k++)
690 d = DotProduct (w->points[k], tp->plane.normal)
695 if (k == w->numpoints)
696 continue; // no points on front
698 p->portalfront[j>>3] |= (1<<(j&7));
701 SimpleFlood (p, p->leaf);
703 p->nummightsee = CountBits (p->portalflood, numportals*2);
704 // printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
705 c_flood += p->nummightsee;
713 ===============================================================================
715 This is a second order aproximation
717 Calculates portalvis bit vector
721 ===============================================================================
730 void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
737 byte newmight[MAX_PORTALS/8];
739 leaf = &leafs[leafnum];
741 // check all portals for flowing into other leafs
742 for (i=0 ; i<leaf->numportals ; i++)
744 p = leaf->portals[i];
747 // if some previous portal can't see it, skip
748 if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
751 // if this portal can see some portals we mightsee, recurse
753 for (j=0 ; j<portallongs ; j++)
755 ((long *)newmight)[j] = ((long *)mightsee)[j]
756 & ((long *)p->portalflood)[j];
757 more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
761 continue; // can't see anything new
763 cansee[pnum>>3] |= (1<<(pnum&7));
765 RecursiveLeafBitFlow (p->leaf, newmight, cansee);
774 void BetterPortalVis (int portalnum)
778 p = portals+portalnum;
780 RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
782 // build leaf vis information
783 p->nummightsee = CountBits (p->portalvis, numportals*2);
784 c_vis += p->nummightsee;