-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-\r
-----------------------------------------------------------------------------------\r
-\r
-This code has been altered significantly from its original form, to support\r
-several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
-\r
-------------------------------------------------------------------------------- */\r
-\r
-\r
-\r
-/* marker */\r
-#define VISFLOW_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-\r
-/*\r
-\r
- each portal will have a list of all possible to see from first portal\r
-\r
- if (!thread->portalmightsee[portalnum])\r
-\r
- portal mightsee\r
-\r
- for p2 = all other portals in leaf\r
- get sperating planes\r
- for all portals that might be seen by p2\r
- mark as unseen if not present in seperating plane\r
- flood fill a new mightsee\r
- save as passagemightsee\r
-\r
-\r
- void CalcMightSee (leaf_t *leaf, \r
-*/\r
-\r
-int CountBits (byte *bits, int numbits)\r
-{\r
- int i;\r
- int c;\r
-\r
- c = 0;\r
- for (i=0 ; i<numbits ; i++)\r
- if (bits[i>>3] & (1<<(i&7)) )\r
- c++;\r
-\r
- return c;\r
-}\r
-\r
-int c_fullskip;\r
-int c_portalskip, c_leafskip;\r
-int c_vistest, c_mighttest;\r
-\r
-int c_chop, c_nochop;\r
-\r
-int active;\r
-\r
-void CheckStack (leaf_t *leaf, threaddata_t *thread)\r
-{\r
- pstack_t *p, *p2;\r
-\r
- for (p=thread->pstack_head.next ; p ; p=p->next)\r
- {\r
-// Sys_Printf ("=");\r
- if (p->leaf == leaf)\r
- Error ("CheckStack: leaf recursion");\r
- for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)\r
- if (p2->leaf == p->leaf)\r
- Error ("CheckStack: late leaf recursion");\r
- }\r
-// Sys_Printf ("\n");\r
-}\r
-\r
-\r
-fixedWinding_t *AllocStackWinding (pstack_t *stack)\r
-{\r
- int i;\r
-\r
- for (i=0 ; i<3 ; i++)\r
- {\r
- if (stack->freewindings[i])\r
- {\r
- stack->freewindings[i] = 0;\r
- return &stack->windings[i];\r
- }\r
- }\r
-\r
- Error ("AllocStackWinding: failed");\r
-\r
- return NULL;\r
-}\r
-\r
-void FreeStackWinding (fixedWinding_t *w, pstack_t *stack)\r
-{\r
- int i;\r
-\r
- i = w - stack->windings;\r
-\r
- if (i<0 || i>2)\r
- return; // not from local\r
-\r
- if (stack->freewindings[i])\r
- Error ("FreeStackWinding: allready free");\r
- stack->freewindings[i] = 1;\r
-}\r
-\r
-/*\r
-==============\r
-VisChopWinding\r
-\r
-==============\r
-*/\r
-fixedWinding_t *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_t *split)\r
-{\r
- vec_t dists[128];\r
- int sides[128];\r
- int counts[3];\r
- vec_t dot;\r
- int i, j;\r
- vec_t *p1, *p2;\r
- vec3_t mid;\r
- fixedWinding_t *neww;\r
-\r
- counts[0] = counts[1] = counts[2] = 0;\r
-\r
- // determine sides for each point\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- dot = DotProduct (in->points[i], split->normal);\r
- dot -= split->dist;\r
- dists[i] = dot;\r
- if (dot > ON_EPSILON)\r
- sides[i] = SIDE_FRONT;\r
- else if (dot < -ON_EPSILON)\r
- sides[i] = SIDE_BACK;\r
- else\r
- {\r
- sides[i] = SIDE_ON;\r
- }\r
- counts[sides[i]]++;\r
- }\r
-\r
- if (!counts[1])\r
- return in; // completely on front side\r
- \r
- if (!counts[0])\r
- {\r
- FreeStackWinding (in, stack);\r
- return NULL;\r
- }\r
-\r
- sides[i] = sides[0];\r
- dists[i] = dists[0];\r
- \r
- neww = AllocStackWinding (stack);\r
-\r
- neww->numpoints = 0;\r
-\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- p1 = in->points[i];\r
-\r
- if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
- {\r
- FreeStackWinding (neww, stack);\r
- return in; // can't chop -- fall back to original\r
- }\r
-\r
- if (sides[i] == SIDE_ON)\r
- {\r
- VectorCopy (p1, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- continue;\r
- }\r
- \r
- if (sides[i] == SIDE_FRONT)\r
- {\r
- VectorCopy (p1, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- }\r
- \r
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
- continue;\r
- \r
- if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
- {\r
- FreeStackWinding (neww, stack);\r
- return in; // can't chop -- fall back to original\r
- }\r
-\r
- // generate a split point\r
- p2 = in->points[(i+1)%in->numpoints];\r
- \r
- dot = dists[i] / (dists[i]-dists[i+1]);\r
- for (j=0 ; j<3 ; j++)\r
- { // avoid round off error when possible\r
- if (split->normal[j] == 1)\r
- mid[j] = split->dist;\r
- else if (split->normal[j] == -1)\r
- mid[j] = -split->dist;\r
- else\r
- mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
- }\r
- \r
- VectorCopy (mid, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- }\r
- \r
- // free the original winding\r
- FreeStackWinding (in, stack);\r
- \r
- return neww;\r
-}\r
-\r
-/*\r
-==============\r
-ClipToSeperators\r
-\r
-Source, pass, and target are an ordering of portals.\r
-\r
-Generates seperating planes canidates by taking two points from source and one\r
-point from pass, and clips target by them.\r
-\r
-If target is totally clipped away, that portal can not be seen through.\r
-\r
-Normal clip keeps target on the same side as pass, which is correct if the\r
-order goes source, pass, target. If the order goes pass, source, target then\r
-flipclip should be set.\r
-==============\r
-*/\r
-fixedWinding_t *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack)\r
-{\r
- int i, j, k, l;\r
- visPlane_t plane;\r
- vec3_t v1, v2;\r
- float d;\r
- vec_t length;\r
- int counts[3];\r
- qboolean fliptest;\r
-\r
- // check all combinations \r
- for (i=0 ; i<source->numpoints ; i++)\r
- {\r
- l = (i+1)%source->numpoints;\r
- VectorSubtract (source->points[l] , source->points[i], v1);\r
-\r
- // find a vertex of pass that makes a plane that puts all of the\r
- // vertexes of pass on the front side and all of the vertexes of\r
- // source on the back side\r
- for (j=0 ; j<pass->numpoints ; j++)\r
- {\r
- VectorSubtract (pass->points[j], source->points[i], v2);\r
-\r
- plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];\r
- plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];\r
- plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];\r
- \r
- // if points don't make a valid plane, skip it\r
-\r
- length = plane.normal[0] * plane.normal[0]\r
- + plane.normal[1] * plane.normal[1]\r
- + plane.normal[2] * plane.normal[2];\r
- \r
- if (length < ON_EPSILON)\r
- continue;\r
-\r
- length = 1/sqrt(length);\r
- \r
- plane.normal[0] *= length;\r
- plane.normal[1] *= length;\r
- plane.normal[2] *= length;\r
-\r
- plane.dist = DotProduct (pass->points[j], plane.normal);\r
-\r
- //\r
- // find out which side of the generated seperating plane has the\r
- // source portal\r
- //\r
-#if 1\r
- fliptest = qfalse;\r
- for (k=0 ; k<source->numpoints ; k++)\r
- {\r
- if (k == i || k == l)\r
- continue;\r
- d = DotProduct (source->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- { // source is on the negative side, so we want all\r
- // pass and target on the positive side\r
- fliptest = qfalse;\r
- break;\r
- }\r
- else if (d > ON_EPSILON)\r
- { // source is on the positive side, so we want all\r
- // pass and target on the negative side\r
- fliptest = qtrue;\r
- break;\r
- }\r
- }\r
- if (k == source->numpoints)\r
- continue; // planar with source portal\r
-#else\r
- fliptest = flipclip;\r
-#endif\r
- //\r
- // flip the normal if the source portal is backwards\r
- //\r
- if (fliptest)\r
- {\r
- VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
- plane.dist = -plane.dist;\r
- }\r
-#if 1\r
- //\r
- // if all of the pass portal points are now on the positive side,\r
- // this is the seperating plane\r
- //\r
- counts[0] = counts[1] = counts[2] = 0;\r
- for (k=0 ; k<pass->numpoints ; k++)\r
- {\r
- if (k==j)\r
- continue;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- break;\r
- else if (d > ON_EPSILON)\r
- counts[0]++;\r
- else\r
- counts[2]++;\r
- }\r
- if (k != pass->numpoints)\r
- continue; // points on negative side, not a seperating plane\r
- \r
- if (!counts[0])\r
- continue; // planar with seperating plane\r
-#else\r
- k = (j+1)%pass->numpoints;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- continue;\r
- k = (j+pass->numpoints-1)%pass->numpoints;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- continue; \r
-#endif\r
- //\r
- // flip the normal if we want the back side\r
- //\r
- if (flipclip)\r
- {\r
- VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
- plane.dist = -plane.dist;\r
- }\r
-\r
-#ifdef SEPERATORCACHE\r
- stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;\r
- if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)\r
- Error("MAX_SEPERATORS");\r
-#endif\r
- //MrE: fast check first\r
- d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;\r
- //if completely at the back of the seperator plane\r
- if (d < -stack->portal->radius)\r
- return NULL;\r
- //if completely on the front of the seperator plane\r
- if (d > stack->portal->radius)\r
- break;\r
-\r
- //\r
- // clip target by the seperating plane\r
- //\r
- target = VisChopWinding (target, stack, &plane);\r
- if (!target)\r
- return NULL; // target is not visible\r
-\r
- break; // optimization by Antony Suter\r
- }\r
- }\r
- \r
- return target;\r
-}\r
-\r
-/*\r
-==================\r
-RecursiveLeafFlow\r
-\r
-Flood fill through the leafs\r
-If src_portal is NULL, this is the originating leaf\r
-==================\r
-*/\r
-void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)\r
-{\r
- pstack_t stack;\r
- vportal_t *p;\r
- visPlane_t backplane;\r
- leaf_t *leaf;\r
- int i, j, n;\r
- long *test, *might, *prevmight, *vis, more;\r
- int pnum;\r
-\r
- thread->c_chains++;\r
-\r
- leaf = &leafs[leafnum];\r
-// CheckStack (leaf, thread);\r
-\r
- prevstack->next = &stack;\r
-\r
- stack.next = NULL;\r
- stack.leaf = leaf;\r
- stack.portal = NULL;\r
- stack.depth = prevstack->depth + 1;\r
-\r
-#ifdef SEPERATORCACHE\r
- stack.numseperators[0] = 0;\r
- stack.numseperators[1] = 0;\r
-#endif\r
-\r
- might = (long *)stack.mightsee;\r
- vis = (long *)thread->base->portalvis;\r
- \r
- // check all portals for flowing into other leafs \r
- for (i = 0; i < leaf->numportals; i++)\r
- {\r
- p = leaf->portals[i];\r
- if (p->removed)\r
- continue;\r
- pnum = p - portals;\r
-\r
- /* MrE: portal trace debug code\r
- {\r
- int portaltrace[] = {13, 16, 17, 37};\r
- pstack_t *s;\r
-\r
- s = &thread->pstack_head;\r
- for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)\r
- {\r
- if (s->portal->num != portaltrace[j])\r
- break;\r
- }\r
- if (j >= sizeof(portaltrace)/sizeof(int) - 1)\r
- {\r
- if (p->num == portaltrace[j])\r
- n = 0; //traced through all the portals\r
- }\r
- }\r
- */\r
-\r
- if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )\r
- {\r
- continue; // can't possibly see it\r
- }\r
-\r
- // if the portal can't see anything we haven't allready seen, skip it\r
- if (p->status == stat_done)\r
- {\r
- test = (long *)p->portalvis;\r
- }\r
- else\r
- {\r
- test = (long *)p->portalflood;\r
- }\r
-\r
- more = 0;\r
- prevmight = (long *)prevstack->mightsee;\r
- for (j=0 ; j<portallongs ; j++)\r
- {\r
- might[j] = prevmight[j] & test[j];\r
- more |= (might[j] & ~vis[j]);\r
- }\r
- \r
- if (!more && \r
- (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )\r
- { // can't see anything new\r
- continue;\r
- }\r
-\r
- // get plane of portal, point normal into the neighbor leaf\r
- stack.portalplane = p->plane;\r
- VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);\r
- backplane.dist = -p->plane.dist;\r
- \r
-// c_portalcheck++;\r
- \r
- stack.portal = p;\r
- stack.next = NULL;\r
- stack.freewindings[0] = 1;\r
- stack.freewindings[1] = 1;\r
- stack.freewindings[2] = 1;\r
- \r
-#if 1\r
- {\r
- float d;\r
-\r
- d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);\r
- d -= thread->pstack_head.portalplane.dist;\r
- if (d < -p->radius)\r
- {\r
- continue;\r
- }\r
- else if (d > p->radius)\r
- {\r
- stack.pass = p->winding;\r
- }\r
- else \r
- {\r
- stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
- if (!stack.pass)\r
- continue;\r
- }\r
- }\r
-#else\r
- stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
- if (!stack.pass)\r
- continue;\r
-#endif\r
-\r
- \r
-#if 1\r
- {\r
- float d;\r
-\r
- d = DotProduct (thread->base->origin, p->plane.normal);\r
- d -= p->plane.dist;\r
- //MrE: vis-bug fix\r
- //if (d > p->radius)\r
- if (d > thread->base->radius)\r
- {\r
- continue;\r
- }\r
- //MrE: vis-bug fix\r
- //if (d < -p->radius)\r
- else if (d < -thread->base->radius)\r
- {\r
- stack.source = prevstack->source;\r
- }\r
- else \r
- {\r
- stack.source = VisChopWinding (prevstack->source, &stack, &backplane);\r
- //FIXME: shouldn't we create a new source origin and radius for fast checks?\r
- if (!stack.source)\r
- continue;\r
- }\r
- }\r
-#else\r
- stack.source = VisChopWinding (prevstack->source, &stack, &backplane);\r
- if (!stack.source)\r
- continue;\r
-#endif\r
-\r
- if (!prevstack->pass)\r
- { // the second leaf can only be blocked if coplanar\r
-\r
- // mark the portal as visible\r
- thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
-\r
- RecursiveLeafFlow (p->leaf, thread, &stack);\r
- continue;\r
- }\r
-\r
-#ifdef SEPERATORCACHE\r
- if (stack.numseperators[0])\r
- {\r
- for (n = 0; n < stack.numseperators[0]; n++)\r
- {\r
- stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);\r
- if (!stack.pass)\r
- break; // target is not visible\r
- }\r
- if (n < stack.numseperators[0])\r
- continue;\r
- }\r
- else\r
- {\r
- stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);\r
- }\r
-#else\r
- stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);\r
-#endif\r
- if (!stack.pass)\r
- continue;\r
-\r
-#ifdef SEPERATORCACHE\r
- if (stack.numseperators[1])\r
- {\r
- for (n = 0; n < stack.numseperators[1]; n++)\r
- {\r
- stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);\r
- if (!stack.pass)\r
- break; // target is not visible\r
- }\r
- }\r
- else\r
- {\r
- stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);\r
- }\r
-#else\r
- stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);\r
-#endif\r
- if (!stack.pass)\r
- continue;\r
-\r
- // mark the portal as visible\r
- thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
-\r
- // flow through it for real\r
- RecursiveLeafFlow (p->leaf, thread, &stack);\r
- //\r
- stack.next = NULL;\r
- } \r
-}\r
-\r
-/*\r
-===============\r
-PortalFlow\r
-\r
-generates the portalvis bit vector\r
-===============\r
-*/\r
-void PortalFlow (int portalnum)\r
-{\r
- threaddata_t data;\r
- int i;\r
- vportal_t *p;\r
- int c_might, c_can;\r
-\r
-#ifdef MREDEBUG\r
- Sys_Printf("\r%6d", portalnum);\r
-#endif\r
-\r
- p = sorted_portals[portalnum];\r
-\r
- if (p->removed)\r
- {\r
- p->status = stat_done;\r
- return;\r
- }\r
-\r
- p->status = stat_working;\r
-\r
- c_might = CountBits (p->portalflood, numportals*2);\r
-\r
- memset (&data, 0, sizeof(data));\r
- data.base = p;\r
- \r
- data.pstack_head.portal = p;\r
- data.pstack_head.source = p->winding;\r
- data.pstack_head.portalplane = p->plane;\r
- data.pstack_head.depth = 0;\r
- for (i=0 ; i<portallongs ; i++)\r
- ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];\r
-\r
- RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);\r
-\r
- p->status = stat_done;\r
-\r
- c_can = CountBits (p->portalvis, numportals*2);\r
-\r
- Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", \r
- (int)(p - portals), c_might, c_can, data.c_chains);\r
-}\r
-\r
-/*\r
-==================\r
-RecursivePassageFlow\r
-==================\r
-*/\r
-void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)\r
-{\r
- pstack_t stack;\r
- vportal_t *p;\r
- leaf_t *leaf;\r
- passage_t *passage, *nextpassage;\r
- int i, j;\r
- long *might, *vis, *prevmight, *cansee, *portalvis, more;\r
- int pnum;\r
-\r
- leaf = &leafs[portal->leaf];\r
-\r
- prevstack->next = &stack;\r
-\r
- stack.next = NULL;\r
- stack.depth = prevstack->depth + 1;\r
-\r
- vis = (long *)thread->base->portalvis;\r
-\r
- passage = portal->passages;\r
- nextpassage = passage;\r
- // check all portals for flowing into other leafs \r
- for (i = 0; i < leaf->numportals; i++, passage = nextpassage)\r
- {\r
- p = leaf->portals[i];\r
- if ( p->removed ) {\r
- continue;\r
- }\r
- nextpassage = passage->next;\r
- pnum = p - portals;\r
-\r
- if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {\r
- continue; // can't possibly see it\r
- }\r
-\r
- // mark the portal as visible\r
- thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
-\r
- prevmight = (long *)prevstack->mightsee;\r
- cansee = (long *)passage->cansee;\r
- might = (long *)stack.mightsee;\r
- memcpy(might, prevmight, portalbytes);\r
- if (p->status == stat_done)\r
- portalvis = (long *) p->portalvis;\r
- else\r
- portalvis = (long *) p->portalflood;\r
- more = 0;\r
- for (j = 0; j < portallongs; j++)\r
- {\r
- if (*might)\r
- {\r
- *might &= *cansee++ & *portalvis++;\r
- more |= (*might & ~vis[j]);\r
- }\r
- else\r
- {\r
- cansee++;\r
- portalvis++;\r
- }\r
- might++;\r
- }\r
-\r
- if ( !more ) {\r
- // can't see anything new\r
- continue;\r
- }\r
-\r
- // flow through it for real\r
- RecursivePassageFlow(p, thread, &stack);\r
-\r
- stack.next = NULL;\r
- }\r
-}\r
-\r
-/*\r
-===============\r
-PassageFlow\r
-===============\r
-*/\r
-void PassageFlow (int portalnum)\r
-{\r
- threaddata_t data;\r
- int i;\r
- vportal_t *p;\r
-// int c_might, c_can;\r
-\r
-#ifdef MREDEBUG\r
- Sys_Printf("\r%6d", portalnum);\r
-#endif\r
-\r
- p = sorted_portals[portalnum];\r
-\r
- if (p->removed)\r
- {\r
- p->status = stat_done;\r
- return;\r
- }\r
-\r
- p->status = stat_working;\r
-\r
-// c_might = CountBits (p->portalflood, numportals*2);\r
-\r
- memset (&data, 0, sizeof(data));\r
- data.base = p;\r
- \r
- data.pstack_head.portal = p;\r
- data.pstack_head.source = p->winding;\r
- data.pstack_head.portalplane = p->plane;\r
- data.pstack_head.depth = 0;\r
- for (i=0 ; i<portallongs ; i++)\r
- ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];\r
-\r
- RecursivePassageFlow (p, &data, &data.pstack_head);\r
-\r
- p->status = stat_done;\r
-\r
- /*\r
- c_can = CountBits (p->portalvis, numportals*2);\r
-\r
- Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", \r
- (int)(p - portals), c_might, c_can, data.c_chains);\r
- */\r
-}\r
-\r
-/*\r
-==================\r
-RecursivePassagePortalFlow\r
-==================\r
-*/\r
-void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)\r
-{\r
- pstack_t stack;\r
- vportal_t *p;\r
- leaf_t *leaf;\r
- visPlane_t backplane;\r
- passage_t *passage, *nextpassage;\r
- int i, j, n;\r
- long *might, *vis, *prevmight, *cansee, *portalvis, more;\r
- int pnum;\r
-\r
-// thread->c_chains++;\r
-\r
- leaf = &leafs[portal->leaf];\r
-// CheckStack (leaf, thread);\r
-\r
- prevstack->next = &stack;\r
-\r
- stack.next = NULL;\r
- stack.leaf = leaf;\r
- stack.portal = NULL;\r
- stack.depth = prevstack->depth + 1;\r
-\r
-#ifdef SEPERATORCACHE\r
- stack.numseperators[0] = 0;\r
- stack.numseperators[1] = 0;\r
-#endif\r
-\r
- vis = (long *)thread->base->portalvis;\r
-\r
- passage = portal->passages;\r
- nextpassage = passage;\r
- // check all portals for flowing into other leafs \r
- for (i = 0; i < leaf->numportals; i++, passage = nextpassage)\r
- {\r
- p = leaf->portals[i];\r
- if (p->removed)\r
- continue;\r
- nextpassage = passage->next;\r
- pnum = p - portals;\r
-\r
- if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )\r
- continue; // can't possibly see it\r
-\r
- prevmight = (long *)prevstack->mightsee;\r
- cansee = (long *)passage->cansee;\r
- might = (long *)stack.mightsee;\r
- memcpy(might, prevmight, portalbytes);\r
- if (p->status == stat_done)\r
- portalvis = (long *) p->portalvis;\r
- else\r
- portalvis = (long *) p->portalflood;\r
- more = 0;\r
- for (j = 0; j < portallongs; j++)\r
- {\r
- if (*might)\r
- {\r
- *might &= *cansee++ & *portalvis++;\r
- more |= (*might & ~vis[j]);\r
- }\r
- else\r
- {\r
- cansee++;\r
- portalvis++;\r
- }\r
- might++;\r
- }\r
-\r
- if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )\r
- { // can't see anything new\r
- continue;\r
- }\r
-\r
- // get plane of portal, point normal into the neighbor leaf\r
- stack.portalplane = p->plane;\r
- VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);\r
- backplane.dist = -p->plane.dist;\r
- \r
-// c_portalcheck++;\r
- \r
- stack.portal = p;\r
- stack.next = NULL;\r
- stack.freewindings[0] = 1;\r
- stack.freewindings[1] = 1;\r
- stack.freewindings[2] = 1;\r
-\r
-#if 1\r
- {\r
- float d;\r
-\r
- d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);\r
- d -= thread->pstack_head.portalplane.dist;\r
- if (d < -p->radius)\r
- {\r
- continue;\r
- }\r
- else if (d > p->radius)\r
- {\r
- stack.pass = p->winding;\r
- }\r
- else \r
- {\r
- stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
- if (!stack.pass)\r
- continue;\r
- }\r
- }\r
-#else\r
- stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);\r
- if (!stack.pass)\r
- continue;\r
-#endif\r
-\r
- \r
-#if 1\r
- {\r
- float d;\r
-\r
- d = DotProduct (thread->base->origin, p->plane.normal);\r
- d -= p->plane.dist;\r
- //MrE: vis-bug fix\r
- //if (d > p->radius)\r
- if (d > thread->base->radius)\r
- {\r
- continue;\r
- }\r
- //MrE: vis-bug fix\r
- //if (d < -p->radius)\r
- else if (d < -thread->base->radius)\r
- {\r
- stack.source = prevstack->source;\r
- }\r
- else \r
- {\r
- stack.source = VisChopWinding (prevstack->source, &stack, &backplane);\r
- //FIXME: shouldn't we create a new source origin and radius for fast checks?\r
- if (!stack.source)\r
- continue;\r
- }\r
- }\r
-#else\r
- stack.source = VisChopWinding (prevstack->source, &stack, &backplane);\r
- if (!stack.source)\r
- continue;\r
-#endif\r
-\r
- if (!prevstack->pass)\r
- { // the second leaf can only be blocked if coplanar\r
-\r
- // mark the portal as visible\r
- thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
-\r
- RecursivePassagePortalFlow (p, thread, &stack);\r
- continue;\r
- }\r
-\r
-#ifdef SEPERATORCACHE\r
- if (stack.numseperators[0])\r
- {\r
- for (n = 0; n < stack.numseperators[0]; n++)\r
- {\r
- stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);\r
- if (!stack.pass)\r
- break; // target is not visible\r
- }\r
- if (n < stack.numseperators[0])\r
- continue;\r
- }\r
- else\r
- {\r
- stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);\r
- }\r
-#else\r
- stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);\r
-#endif\r
- if (!stack.pass)\r
- continue;\r
-\r
-#ifdef SEPERATORCACHE\r
- if (stack.numseperators[1])\r
- {\r
- for (n = 0; n < stack.numseperators[1]; n++)\r
- {\r
- stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);\r
- if (!stack.pass)\r
- break; // target is not visible\r
- }\r
- }\r
- else\r
- {\r
- stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);\r
- }\r
-#else\r
- stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);\r
-#endif\r
- if (!stack.pass)\r
- continue;\r
-\r
- // mark the portal as visible\r
- thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));\r
-\r
- // flow through it for real\r
- RecursivePassagePortalFlow(p, thread, &stack);\r
- //\r
- stack.next = NULL;\r
- }\r
-}\r
-\r
-/*\r
-===============\r
-PassagePortalFlow\r
-===============\r
-*/\r
-void PassagePortalFlow (int portalnum)\r
-{\r
- threaddata_t data;\r
- int i;\r
- vportal_t *p;\r
-// int c_might, c_can;\r
-\r
-#ifdef MREDEBUG\r
- Sys_Printf("\r%6d", portalnum);\r
-#endif\r
-\r
- p = sorted_portals[portalnum];\r
-\r
- if (p->removed)\r
- {\r
- p->status = stat_done;\r
- return;\r
- }\r
-\r
- p->status = stat_working;\r
-\r
-// c_might = CountBits (p->portalflood, numportals*2);\r
-\r
- memset (&data, 0, sizeof(data));\r
- data.base = p;\r
- \r
- data.pstack_head.portal = p;\r
- data.pstack_head.source = p->winding;\r
- data.pstack_head.portalplane = p->plane;\r
- data.pstack_head.depth = 0;\r
- for (i=0 ; i<portallongs ; i++)\r
- ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];\r
-\r
- RecursivePassagePortalFlow (p, &data, &data.pstack_head);\r
-\r
- p->status = stat_done;\r
-\r
- /*\r
- c_can = CountBits (p->portalvis, numportals*2);\r
-\r
- Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n", \r
- (int)(p - portals), c_might, c_can, data.c_chains);\r
- */\r
-}\r
-\r
-fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split)\r
-{\r
- vec_t dists[128];\r
- int sides[128];\r
- int counts[3];\r
- vec_t dot;\r
- int i, j;\r
- vec_t *p1, *p2;\r
- vec3_t mid;\r
- fixedWinding_t *neww;\r
-\r
- counts[0] = counts[1] = counts[2] = 0;\r
-\r
- // determine sides for each point\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- dot = DotProduct (in->points[i], split->normal);\r
- dot -= split->dist;\r
- dists[i] = dot;\r
- if (dot > ON_EPSILON)\r
- sides[i] = SIDE_FRONT;\r
- else if (dot < -ON_EPSILON)\r
- sides[i] = SIDE_BACK;\r
- else\r
- {\r
- sides[i] = SIDE_ON;\r
- }\r
- counts[sides[i]]++;\r
- }\r
-\r
- if (!counts[1])\r
- return in; // completely on front side\r
- \r
- if (!counts[0])\r
- {\r
- return NULL;\r
- }\r
-\r
- sides[i] = sides[0];\r
- dists[i] = dists[0];\r
- \r
- neww = out;\r
-\r
- neww->numpoints = 0;\r
-\r
- for (i=0 ; i<in->numpoints ; i++)\r
- {\r
- p1 = in->points[i];\r
-\r
- if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
- {\r
- return in; // can't chop -- fall back to original\r
- }\r
-\r
- if (sides[i] == SIDE_ON)\r
- {\r
- VectorCopy (p1, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- continue;\r
- }\r
- \r
- if (sides[i] == SIDE_FRONT)\r
- {\r
- VectorCopy (p1, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- }\r
- \r
- if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])\r
- continue;\r
- \r
- if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)\r
- {\r
- return in; // can't chop -- fall back to original\r
- }\r
-\r
- // generate a split point\r
- p2 = in->points[(i+1)%in->numpoints];\r
- \r
- dot = dists[i] / (dists[i]-dists[i+1]);\r
- for (j=0 ; j<3 ; j++)\r
- { // avoid round off error when possible\r
- if (split->normal[j] == 1)\r
- mid[j] = split->dist;\r
- else if (split->normal[j] == -1)\r
- mid[j] = -split->dist;\r
- else\r
- mid[j] = p1[j] + dot*(p2[j]-p1[j]);\r
- }\r
- \r
- VectorCopy (mid, neww->points[neww->numpoints]);\r
- neww->numpoints++;\r
- }\r
- \r
- return neww;\r
-}\r
-\r
-/*\r
-===============\r
-AddSeperators\r
-===============\r
-*/\r
-int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators)\r
-{\r
- int i, j, k, l;\r
- visPlane_t plane;\r
- vec3_t v1, v2;\r
- float d;\r
- vec_t length;\r
- int counts[3], numseperators;\r
- qboolean fliptest;\r
-\r
- numseperators = 0;\r
- // check all combinations \r
- for (i=0 ; i<source->numpoints ; i++)\r
- {\r
- l = (i+1)%source->numpoints;\r
- VectorSubtract (source->points[l] , source->points[i], v1);\r
-\r
- // find a vertex of pass that makes a plane that puts all of the\r
- // vertexes of pass on the front side and all of the vertexes of\r
- // source on the back side\r
- for (j=0 ; j<pass->numpoints ; j++)\r
- {\r
- VectorSubtract (pass->points[j], source->points[i], v2);\r
-\r
- plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];\r
- plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];\r
- plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];\r
- \r
- // if points don't make a valid plane, skip it\r
-\r
- length = plane.normal[0] * plane.normal[0]\r
- + plane.normal[1] * plane.normal[1]\r
- + plane.normal[2] * plane.normal[2];\r
- \r
- if (length < ON_EPSILON)\r
- continue;\r
-\r
- length = 1/sqrt(length);\r
- \r
- plane.normal[0] *= length;\r
- plane.normal[1] *= length;\r
- plane.normal[2] *= length;\r
-\r
- plane.dist = DotProduct (pass->points[j], plane.normal);\r
-\r
- //\r
- // find out which side of the generated seperating plane has the\r
- // source portal\r
- //\r
-#if 1\r
- fliptest = qfalse;\r
- for (k=0 ; k<source->numpoints ; k++)\r
- {\r
- if (k == i || k == l)\r
- continue;\r
- d = DotProduct (source->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- { // source is on the negative side, so we want all\r
- // pass and target on the positive side\r
- fliptest = qfalse;\r
- break;\r
- }\r
- else if (d > ON_EPSILON)\r
- { // source is on the positive side, so we want all\r
- // pass and target on the negative side\r
- fliptest = qtrue;\r
- break;\r
- }\r
- }\r
- if (k == source->numpoints)\r
- continue; // planar with source portal\r
-#else\r
- fliptest = flipclip;\r
-#endif\r
- //\r
- // flip the normal if the source portal is backwards\r
- //\r
- if (fliptest)\r
- {\r
- VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
- plane.dist = -plane.dist;\r
- }\r
-#if 1\r
- //\r
- // if all of the pass portal points are now on the positive side,\r
- // this is the seperating plane\r
- //\r
- counts[0] = counts[1] = counts[2] = 0;\r
- for (k=0 ; k<pass->numpoints ; k++)\r
- {\r
- if (k==j)\r
- continue;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- break;\r
- else if (d > ON_EPSILON)\r
- counts[0]++;\r
- else\r
- counts[2]++;\r
- }\r
- if (k != pass->numpoints)\r
- continue; // points on negative side, not a seperating plane\r
- \r
- if (!counts[0])\r
- continue; // planar with seperating plane\r
-#else\r
- k = (j+1)%pass->numpoints;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- continue;\r
- k = (j+pass->numpoints-1)%pass->numpoints;\r
- d = DotProduct (pass->points[k], plane.normal) - plane.dist;\r
- if (d < -ON_EPSILON)\r
- continue; \r
-#endif\r
- //\r
- // flip the normal if we want the back side\r
- //\r
- if (flipclip)\r
- {\r
- VectorSubtract (vec3_origin, plane.normal, plane.normal);\r
- plane.dist = -plane.dist;\r
- }\r
-\r
- if (numseperators >= maxseperators)\r
- Error("max seperators");\r
- seperators[numseperators] = plane;\r
- numseperators++;\r
- break;\r
- }\r
- }\r
- return numseperators;\r
-}\r
-\r
-/*\r
-===============\r
-CreatePassages\r
-\r
-MrE: create passages from one portal to all the portals in the leaf the portal leads to\r
- every passage has a cansee bit string with all the portals that can be\r
- seen through the passage\r
-===============\r
-*/\r
-void CreatePassages(int portalnum)\r
-{\r
- int i, j, k, n, numseperators, numsee;\r
- float d;\r
- vportal_t *portal, *p, *target;\r
- leaf_t *leaf;\r
- passage_t *passage, *lastpassage;\r
- visPlane_t seperators[MAX_SEPERATORS*2];\r
- fixedWinding_t *w;\r
- fixedWinding_t in, out, *res;\r
- \r
- \r
-#ifdef MREDEBUG\r
- Sys_Printf("\r%6d", portalnum);\r
-#endif\r
-\r
- portal = sorted_portals[portalnum];\r
-\r
- if (portal->removed)\r
- {\r
- portal->status = stat_done;\r
- return;\r
- }\r
-\r
- lastpassage = NULL;\r
- leaf = &leafs[portal->leaf];\r
- for (i = 0; i < leaf->numportals; i++)\r
- {\r
- target = leaf->portals[i];\r
- if (target->removed)\r
- continue;\r
-\r
- passage = (passage_t *) safe_malloc(sizeof(passage_t) + portalbytes);\r
- memset(passage, 0, sizeof(passage_t) + portalbytes);\r
- numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);\r
- numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);\r
-\r
- passage->next = NULL;\r
- if (lastpassage)\r
- lastpassage->next = passage;\r
- else\r
- portal->passages = passage;\r
- lastpassage = passage;\r
-\r
- numsee = 0;\r
- //create the passage->cansee\r
- for (j = 0; j < numportals * 2; j++)\r
- {\r
- p = &portals[j];\r
- if (p->removed)\r
- continue;\r
- if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )\r
- continue;\r
- if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )\r
- continue;\r
- for (k = 0; k < numseperators; k++)\r
- {\r
- //\r
- d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;\r
- //if completely at the back of the seperator plane\r
- if (d < -p->radius + ON_EPSILON)\r
- break;\r
- w = p->winding;\r
- for (n = 0; n < w->numpoints; n++)\r
- {\r
- d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;\r
- //if at the front of the seperator\r
- if (d > ON_EPSILON)\r
- break;\r
- }\r
- //if no points are at the front of the seperator\r
- if (n >= w->numpoints)\r
- break;\r
- }\r
- if (k < numseperators)\r
- continue;\r
- \r
- /* explitive deleted */\r
- \r
- \r
- /* ydnar: prefer correctness to stack overflow */\r
- //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );\r
- if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING )\r
- memcpy( &in, p->winding, (int) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) );\r
- else\r
- memcpy( &in, p->winding, sizeof( fixedWinding_t ) );\r
- \r
- \r
- for( k = 0; k < numseperators; k++ )\r
- {\r
- /* ydnar: this is a shitty crutch */\r
- if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING )\r
- {\r
- //% Sys_Printf( "[%d]", p->winding->numpoints );\r
- in.numpoints = MAX_POINTS_ON_FIXED_WINDING;\r
- }\r
- \r
- res = PassageChopWinding( &in, &out, &seperators[ k ] );\r
- if( res == &out )\r
- memcpy( &in, &out, sizeof( fixedWinding_t ) );\r
-\r
- \r
- if( res == NULL )\r
- break;\r
- }\r
- if (k < numseperators)\r
- continue;\r
- passage->cansee[j >> 3] |= (1<<(j&7));\r
- numsee++;\r
- }\r
- }\r
-}\r
-\r
-void PassageMemory(void)\r
-{\r
- int i, j, totalmem, totalportals;\r
- vportal_t *portal, *target;\r
- leaf_t *leaf;\r
-\r
- totalmem = 0;\r
- totalportals = 0;\r
- for (i = 0; i < numportals; i++)\r
- {\r
- portal = sorted_portals[i];\r
- if (portal->removed)\r
- continue;\r
- leaf = &leafs[portal->leaf];\r
- for (j = 0; j < leaf->numportals; j++)\r
- {\r
- target = leaf->portals[j];\r
- if (target->removed)\r
- continue;\r
- totalmem += sizeof(passage_t) + portalbytes;\r
- totalportals++;\r
- }\r
- }\r
- Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals);\r
- Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);\r
-}\r
-\r
-/*\r
-===============================================================================\r
-\r
-This is a rough first-order aproximation that is used to trivially reject some\r
-of the final calculations.\r
-\r
-\r
-Calculates portalfront and portalflood bit vectors\r
-\r
-thinking about:\r
-\r
-typedef struct passage_s\r
-{\r
- struct passage_s *next;\r
- struct portal_s *to;\r
- stryct sep_s *seperators;\r
- byte *mightsee;\r
-} passage_t;\r
-\r
-typedef struct portal_s\r
-{\r
- struct passage_s *passages;\r
- int leaf; // leaf portal faces into\r
-} portal_s;\r
-\r
-leaf = portal->leaf\r
-clear \r
-for all portals\r
-\r
-\r
-calc portal visibility\r
- clear bit vector\r
- for all passages\r
- passage visibility\r
-\r
-\r
-for a portal to be visible to a passage, it must be on the front of\r
-all seperating planes, and both portals must be behind the new portal\r
-\r
-===============================================================================\r
-*/\r
-\r
-int c_flood, c_vis;\r
-\r
-\r
-/*\r
-==================\r
-SimpleFlood\r
-\r
-==================\r
-*/\r
-void SimpleFlood (vportal_t *srcportal, int leafnum)\r
-{\r
- int i;\r
- leaf_t *leaf;\r
- vportal_t *p;\r
- int pnum;\r
-\r
- leaf = &leafs[leafnum];\r
- \r
- for (i=0 ; i<leaf->numportals ; i++)\r
- {\r
- p = leaf->portals[i];\r
- if (p->removed)\r
- continue;\r
- pnum = p - portals;\r
- if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )\r
- continue;\r
-\r
- if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )\r
- continue;\r
-\r
- srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));\r
- \r
- SimpleFlood (srcportal, p->leaf);\r
- }\r
-}\r
-\r
-/*\r
-==============\r
-BasePortalVis\r
-==============\r
-*/\r
-void BasePortalVis( int portalnum )\r
-{\r
- int j, k;\r
- vportal_t *tp, *p;\r
- float d;\r
- fixedWinding_t *w;\r
- vec3_t dir;\r
- \r
-\r
- p = portals+portalnum;\r
-\r
- if (p->removed)\r
- return;\r
-\r
- p->portalfront = safe_malloc (portalbytes);\r
- memset (p->portalfront, 0, portalbytes);\r
-\r
- p->portalflood = safe_malloc (portalbytes);\r
- memset (p->portalflood, 0, portalbytes);\r
- \r
- p->portalvis = safe_malloc (portalbytes);\r
- memset (p->portalvis, 0, portalbytes);\r
- \r
- for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)\r
- {\r
- if( j == portalnum )\r
- continue;\r
- if( tp->removed )\r
- continue;\r
-\r
- /* ydnar: this is old farplane vis code from mre */\r
- /*\r
- if (farplanedist >= 0)\r
- {\r
- vec3_t dir;\r
- VectorSubtract(p->origin, tp->origin, dir);\r
- if (VectorLength(dir) > farplanedist - p->radius - tp->radius)\r
- continue;\r
- }\r
- */\r
- \r
- /* ydnar: this is known-to-be-working farplane code */\r
- if( farPlaneDist > 0.0f )\r
- {\r
- VectorSubtract( p->origin, tp->origin, dir );\r
- if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist )\r
- continue;\r
- }\r
- \r
- \r
- w = tp->winding;\r
- for (k=0 ; k<w->numpoints ; k++)\r
- {\r
- d = DotProduct (w->points[k], p->plane.normal)\r
- - p->plane.dist;\r
- if (d > ON_EPSILON)\r
- break;\r
- }\r
- if (k == w->numpoints)\r
- continue; // no points on front\r
-\r
- w = p->winding;\r
- for (k=0 ; k<w->numpoints ; k++)\r
- {\r
- d = DotProduct (w->points[k], tp->plane.normal)\r
- - tp->plane.dist;\r
- if (d < -ON_EPSILON)\r
- break;\r
- }\r
- if (k == w->numpoints)\r
- continue; // no points on front\r
-\r
- p->portalfront[j>>3] |= (1<<(j&7));\r
- }\r
- \r
- SimpleFlood (p, p->leaf);\r
-\r
- p->nummightsee = CountBits (p->portalflood, numportals*2);\r
-// Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);\r
- c_flood += p->nummightsee;\r
-}\r
-\r
-\r
-\r
-\r
-\r
-/*\r
-===============================================================================\r
-\r
-This is a second order aproximation \r
-\r
-Calculates portalvis bit vector\r
-\r
-WAAAAAAY too slow.\r
-\r
-===============================================================================\r
-*/\r
-\r
-/*\r
-==================\r
-RecursiveLeafBitFlow\r
-\r
-==================\r
-*/\r
-void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)\r
-{\r
- vportal_t *p;\r
- leaf_t *leaf;\r
- int i, j;\r
- long more;\r
- int pnum;\r
- byte newmight[MAX_PORTALS/8];\r
-\r
- leaf = &leafs[leafnum];\r
- \r
- // check all portals for flowing into other leafs\r
- for (i=0 ; i<leaf->numportals ; i++)\r
- {\r
- p = leaf->portals[i];\r
- if (p->removed)\r
- continue;\r
- pnum = p - portals;\r
-\r
- // if some previous portal can't see it, skip\r
- if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )\r
- continue;\r
-\r
- // if this portal can see some portals we mightsee, recurse\r
- more = 0;\r
- for (j=0 ; j<portallongs ; j++)\r
- {\r
- ((long *)newmight)[j] = ((long *)mightsee)[j] \r
- & ((long *)p->portalflood)[j];\r
- more |= ((long *)newmight)[j] & ~((long *)cansee)[j];\r
- }\r
-\r
- if (!more)\r
- continue; // can't see anything new\r
-\r
- cansee[pnum>>3] |= (1<<(pnum&7));\r
-\r
- RecursiveLeafBitFlow (p->leaf, newmight, cansee);\r
- } \r
-}\r
-\r
-/*\r
-==============\r
-BetterPortalVis\r
-==============\r
-*/\r
-void BetterPortalVis (int portalnum)\r
-{\r
- vportal_t *p;\r
-\r
- p = portals+portalnum;\r
-\r
- if (p->removed)\r
- return;\r
-\r
- RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);\r
-\r
- // build leaf vis information\r
- p->nummightsee = CountBits (p->portalvis, numportals*2);\r
- c_vis += p->nummightsee;\r
-}\r
-\r
-\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+----------------------------------------------------------------------------------
+
+This code has been altered significantly from its original form, to support
+several games based on the Quake III Arena engine, in the form of "Q3Map2."
+
+------------------------------------------------------------------------------- */
+
+
+
+/* marker */
+#define VISFLOW_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+
+/*
+
+ each portal will have a list of all possible to see from first portal
+
+ if (!thread->portalmightsee[portalnum])
+
+ portal mightsee
+
+ for p2 = all other portals in leaf
+ get sperating planes
+ for all portals that might be seen by p2
+ mark as unseen if not present in seperating plane
+ flood fill a new mightsee
+ save as passagemightsee
+
+
+ void CalcMightSee (leaf_t *leaf,
+*/
+
+int CountBits (byte *bits, int numbits)
+{
+ int i;
+ int c;
+
+ c = 0;
+ for (i=0 ; i<numbits ; i++)
+ if (bits[i>>3] & (1<<(i&7)) )
+ c++;
+
+ return c;
+}
+
+int c_fullskip;
+int c_portalskip, c_leafskip;
+int c_vistest, c_mighttest;
+
+int c_chop, c_nochop;
+
+int active;
+
+void CheckStack (leaf_t *leaf, threaddata_t *thread)
+{
+ pstack_t *p, *p2;
+
+ for (p=thread->pstack_head.next ; p ; p=p->next)
+ {
+// Sys_Printf ("=");
+ if (p->leaf == leaf)
+ Error ("CheckStack: leaf recursion");
+ for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
+ if (p2->leaf == p->leaf)
+ Error ("CheckStack: late leaf recursion");
+ }
+// Sys_Printf ("\n");
+}
+
+
+fixedWinding_t *AllocStackWinding (pstack_t *stack)
+{
+ int i;
+
+ for (i=0 ; i<3 ; i++)
+ {
+ if (stack->freewindings[i])
+ {
+ stack->freewindings[i] = 0;
+ return &stack->windings[i];
+ }
+ }
+
+ Error ("AllocStackWinding: failed");
+
+ return NULL;
+}
+
+void FreeStackWinding (fixedWinding_t *w, pstack_t *stack)
+{
+ int i;
+
+ i = w - stack->windings;
+
+ if (i<0 || i>2)
+ return; // not from local
+
+ if (stack->freewindings[i])
+ Error ("FreeStackWinding: allready free");
+ stack->freewindings[i] = 1;
+}
+
+/*
+==============
+VisChopWinding
+
+==============
+*/
+fixedWinding_t *VisChopWinding (fixedWinding_t *in, pstack_t *stack, visPlane_t *split)
+{
+ vec_t dists[128];
+ int sides[128];
+ int counts[3];
+ vec_t dot;
+ int i, j;
+ vec_t *p1, *p2;
+ vec3_t mid;
+ fixedWinding_t *neww;
+
+ counts[0] = counts[1] = counts[2] = 0;
+
+ // determine sides for each point
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ dot = DotProduct (in->points[i], split->normal);
+ dot -= split->dist;
+ dists[i] = dot;
+ if (dot > ON_EPSILON)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -ON_EPSILON)
+ sides[i] = SIDE_BACK;
+ else
+ {
+ sides[i] = SIDE_ON;
+ }
+ counts[sides[i]]++;
+ }
+
+ if (!counts[1])
+ return in; // completely on front side
+
+ if (!counts[0])
+ {
+ FreeStackWinding (in, stack);
+ return NULL;
+ }
+
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ neww = AllocStackWinding (stack);
+
+ neww->numpoints = 0;
+
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ p1 = in->points[i];
+
+ if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+ {
+ FreeStackWinding (neww, stack);
+ return in; // can't chop -- fall back to original
+ }
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+ {
+ FreeStackWinding (neww, stack);
+ return in; // can't chop -- fall back to original
+ }
+
+ // generate a split point
+ p2 = in->points[(i+1)%in->numpoints];
+
+ dot = dists[i] / (dists[i]-dists[i+1]);
+ for (j=0 ; j<3 ; j++)
+ { // avoid round off error when possible
+ if (split->normal[j] == 1)
+ mid[j] = split->dist;
+ else if (split->normal[j] == -1)
+ mid[j] = -split->dist;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ }
+
+ // free the original winding
+ FreeStackWinding (in, stack);
+
+ return neww;
+}
+
+/*
+==============
+ClipToSeperators
+
+Source, pass, and target are an ordering of portals.
+
+Generates seperating planes canidates by taking two points from source and one
+point from pass, and clips target by them.
+
+If target is totally clipped away, that portal can not be seen through.
+
+Normal clip keeps target on the same side as pass, which is correct if the
+order goes source, pass, target. If the order goes pass, source, target then
+flipclip should be set.
+==============
+*/
+fixedWinding_t *ClipToSeperators (fixedWinding_t *source, fixedWinding_t *pass, fixedWinding_t *target, qboolean flipclip, pstack_t *stack)
+{
+ int i, j, k, l;
+ visPlane_t plane;
+ vec3_t v1, v2;
+ float d;
+ vec_t length;
+ int counts[3];
+ qboolean fliptest;
+
+ // check all combinations
+ for (i=0 ; i<source->numpoints ; i++)
+ {
+ l = (i+1)%source->numpoints;
+ VectorSubtract (source->points[l] , source->points[i], v1);
+
+ // find a vertex of pass that makes a plane that puts all of the
+ // vertexes of pass on the front side and all of the vertexes of
+ // source on the back side
+ for (j=0 ; j<pass->numpoints ; j++)
+ {
+ VectorSubtract (pass->points[j], source->points[i], v2);
+
+ plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
+ plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
+ plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
+
+ // if points don't make a valid plane, skip it
+
+ length = plane.normal[0] * plane.normal[0]
+ + plane.normal[1] * plane.normal[1]
+ + plane.normal[2] * plane.normal[2];
+
+ if (length < ON_EPSILON)
+ continue;
+
+ length = 1/sqrt(length);
+
+ plane.normal[0] *= length;
+ plane.normal[1] *= length;
+ plane.normal[2] *= length;
+
+ plane.dist = DotProduct (pass->points[j], plane.normal);
+
+ //
+ // find out which side of the generated seperating plane has the
+ // source portal
+ //
+#if 1
+ fliptest = qfalse;
+ for (k=0 ; k<source->numpoints ; k++)
+ {
+ if (k == i || k == l)
+ continue;
+ d = DotProduct (source->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ { // source is on the negative side, so we want all
+ // pass and target on the positive side
+ fliptest = qfalse;
+ break;
+ }
+ else if (d > ON_EPSILON)
+ { // source is on the positive side, so we want all
+ // pass and target on the negative side
+ fliptest = qtrue;
+ break;
+ }
+ }
+ if (k == source->numpoints)
+ continue; // planar with source portal
+#else
+ fliptest = flipclip;
+#endif
+ //
+ // flip the normal if the source portal is backwards
+ //
+ if (fliptest)
+ {
+ VectorSubtract (vec3_origin, plane.normal, plane.normal);
+ plane.dist = -plane.dist;
+ }
+#if 1
+ //
+ // if all of the pass portal points are now on the positive side,
+ // this is the seperating plane
+ //
+ counts[0] = counts[1] = counts[2] = 0;
+ for (k=0 ; k<pass->numpoints ; k++)
+ {
+ if (k==j)
+ continue;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ break;
+ else if (d > ON_EPSILON)
+ counts[0]++;
+ else
+ counts[2]++;
+ }
+ if (k != pass->numpoints)
+ continue; // points on negative side, not a seperating plane
+
+ if (!counts[0])
+ continue; // planar with seperating plane
+#else
+ k = (j+1)%pass->numpoints;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ continue;
+ k = (j+pass->numpoints-1)%pass->numpoints;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ continue;
+#endif
+ //
+ // flip the normal if we want the back side
+ //
+ if (flipclip)
+ {
+ VectorSubtract (vec3_origin, plane.normal, plane.normal);
+ plane.dist = -plane.dist;
+ }
+
+#ifdef SEPERATORCACHE
+ stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
+ if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
+ Error("MAX_SEPERATORS");
+#endif
+ //MrE: fast check first
+ d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
+ //if completely at the back of the seperator plane
+ if (d < -stack->portal->radius)
+ return NULL;
+ //if completely on the front of the seperator plane
+ if (d > stack->portal->radius)
+ break;
+
+ //
+ // clip target by the seperating plane
+ //
+ target = VisChopWinding (target, stack, &plane);
+ if (!target)
+ return NULL; // target is not visible
+
+ break; // optimization by Antony Suter
+ }
+ }
+
+ return target;
+}
+
+/*
+==================
+RecursiveLeafFlow
+
+Flood fill through the leafs
+If src_portal is NULL, this is the originating leaf
+==================
+*/
+void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
+{
+ pstack_t stack;
+ vportal_t *p;
+ visPlane_t backplane;
+ leaf_t *leaf;
+ int i, j, n;
+ long *test, *might, *prevmight, *vis, more;
+ int pnum;
+
+ thread->c_chains++;
+
+ leaf = &leafs[leafnum];
+// CheckStack (leaf, thread);
+
+ prevstack->next = &stack;
+
+ stack.next = NULL;
+ stack.leaf = leaf;
+ stack.portal = NULL;
+ stack.depth = prevstack->depth + 1;
+
+#ifdef SEPERATORCACHE
+ stack.numseperators[0] = 0;
+ stack.numseperators[1] = 0;
+#endif
+
+ might = (long *)stack.mightsee;
+ vis = (long *)thread->base->portalvis;
+
+ // check all portals for flowing into other leafs
+ for (i = 0; i < leaf->numportals; i++)
+ {
+ p = leaf->portals[i];
+ if (p->removed)
+ continue;
+ pnum = p - portals;
+
+ /* MrE: portal trace debug code
+ {
+ int portaltrace[] = {13, 16, 17, 37};
+ pstack_t *s;
+
+ s = &thread->pstack_head;
+ for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
+ {
+ if (s->portal->num != portaltrace[j])
+ break;
+ }
+ if (j >= sizeof(portaltrace)/sizeof(int) - 1)
+ {
+ if (p->num == portaltrace[j])
+ n = 0; //traced through all the portals
+ }
+ }
+ */
+
+ if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
+ {
+ continue; // can't possibly see it
+ }
+
+ // if the portal can't see anything we haven't allready seen, skip it
+ if (p->status == stat_done)
+ {
+ test = (long *)p->portalvis;
+ }
+ else
+ {
+ test = (long *)p->portalflood;
+ }
+
+ more = 0;
+ prevmight = (long *)prevstack->mightsee;
+ for (j=0 ; j<portallongs ; j++)
+ {
+ might[j] = prevmight[j] & test[j];
+ more |= (might[j] & ~vis[j]);
+ }
+
+ if (!more &&
+ (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
+ { // can't see anything new
+ continue;
+ }
+
+ // get plane of portal, point normal into the neighbor leaf
+ stack.portalplane = p->plane;
+ VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
+ backplane.dist = -p->plane.dist;
+
+// c_portalcheck++;
+
+ stack.portal = p;
+ stack.next = NULL;
+ stack.freewindings[0] = 1;
+ stack.freewindings[1] = 1;
+ stack.freewindings[2] = 1;
+
+#if 1
+ {
+ float d;
+
+ d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
+ d -= thread->pstack_head.portalplane.dist;
+ if (d < -p->radius)
+ {
+ continue;
+ }
+ else if (d > p->radius)
+ {
+ stack.pass = p->winding;
+ }
+ else
+ {
+ stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+ if (!stack.pass)
+ continue;
+ }
+ }
+#else
+ stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+ if (!stack.pass)
+ continue;
+#endif
+
+
+#if 1
+ {
+ float d;
+
+ d = DotProduct (thread->base->origin, p->plane.normal);
+ d -= p->plane.dist;
+ //MrE: vis-bug fix
+ //if (d > p->radius)
+ if (d > thread->base->radius)
+ {
+ continue;
+ }
+ //MrE: vis-bug fix
+ //if (d < -p->radius)
+ else if (d < -thread->base->radius)
+ {
+ stack.source = prevstack->source;
+ }
+ else
+ {
+ stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+ //FIXME: shouldn't we create a new source origin and radius for fast checks?
+ if (!stack.source)
+ continue;
+ }
+ }
+#else
+ stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+ if (!stack.source)
+ continue;
+#endif
+
+ if (!prevstack->pass)
+ { // the second leaf can only be blocked if coplanar
+
+ // mark the portal as visible
+ thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+ RecursiveLeafFlow (p->leaf, thread, &stack);
+ continue;
+ }
+
+#ifdef SEPERATORCACHE
+ if (stack.numseperators[0])
+ {
+ for (n = 0; n < stack.numseperators[0]; n++)
+ {
+ stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
+ if (!stack.pass)
+ break; // target is not visible
+ }
+ if (n < stack.numseperators[0])
+ continue;
+ }
+ else
+ {
+ stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
+ }
+#else
+ stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
+#endif
+ if (!stack.pass)
+ continue;
+
+#ifdef SEPERATORCACHE
+ if (stack.numseperators[1])
+ {
+ for (n = 0; n < stack.numseperators[1]; n++)
+ {
+ stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
+ if (!stack.pass)
+ break; // target is not visible
+ }
+ }
+ else
+ {
+ stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
+ }
+#else
+ stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
+#endif
+ if (!stack.pass)
+ continue;
+
+ // mark the portal as visible
+ thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+ // flow through it for real
+ RecursiveLeafFlow (p->leaf, thread, &stack);
+ //
+ stack.next = NULL;
+ }
+}
+
+/*
+===============
+PortalFlow
+
+generates the portalvis bit vector
+===============
+*/
+void PortalFlow (int portalnum)
+{
+ threaddata_t data;
+ int i;
+ vportal_t *p;
+ int c_might, c_can;
+
+#ifdef MREDEBUG
+ Sys_Printf("\r%6d", portalnum);
+#endif
+
+ p = sorted_portals[portalnum];
+
+ if (p->removed)
+ {
+ p->status = stat_done;
+ return;
+ }
+
+ p->status = stat_working;
+
+ c_might = CountBits (p->portalflood, numportals*2);
+
+ memset (&data, 0, sizeof(data));
+ data.base = p;
+
+ data.pstack_head.portal = p;
+ data.pstack_head.source = p->winding;
+ data.pstack_head.portalplane = p->plane;
+ data.pstack_head.depth = 0;
+ for (i=0 ; i<portallongs ; i++)
+ ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+ RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
+
+ p->status = stat_done;
+
+ c_can = CountBits (p->portalvis, numportals*2);
+
+ Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
+ (int)(p - portals), c_might, c_can, data.c_chains);
+}
+
+/*
+==================
+RecursivePassageFlow
+==================
+*/
+void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
+{
+ pstack_t stack;
+ vportal_t *p;
+ leaf_t *leaf;
+ passage_t *passage, *nextpassage;
+ int i, j;
+ long *might, *vis, *prevmight, *cansee, *portalvis, more;
+ int pnum;
+
+ leaf = &leafs[portal->leaf];
+
+ prevstack->next = &stack;
+
+ stack.next = NULL;
+ stack.depth = prevstack->depth + 1;
+
+ vis = (long *)thread->base->portalvis;
+
+ passage = portal->passages;
+ nextpassage = passage;
+ // check all portals for flowing into other leafs
+ for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
+ {
+ p = leaf->portals[i];
+ if ( p->removed ) {
+ continue;
+ }
+ nextpassage = passage->next;
+ pnum = p - portals;
+
+ if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
+ continue; // can't possibly see it
+ }
+
+ // mark the portal as visible
+ thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+ prevmight = (long *)prevstack->mightsee;
+ cansee = (long *)passage->cansee;
+ might = (long *)stack.mightsee;
+ memcpy(might, prevmight, portalbytes);
+ if (p->status == stat_done)
+ portalvis = (long *) p->portalvis;
+ else
+ portalvis = (long *) p->portalflood;
+ more = 0;
+ for (j = 0; j < portallongs; j++)
+ {
+ if (*might)
+ {
+ *might &= *cansee++ & *portalvis++;
+ more |= (*might & ~vis[j]);
+ }
+ else
+ {
+ cansee++;
+ portalvis++;
+ }
+ might++;
+ }
+
+ if ( !more ) {
+ // can't see anything new
+ continue;
+ }
+
+ // flow through it for real
+ RecursivePassageFlow(p, thread, &stack);
+
+ stack.next = NULL;
+ }
+}
+
+/*
+===============
+PassageFlow
+===============
+*/
+void PassageFlow (int portalnum)
+{
+ threaddata_t data;
+ int i;
+ vportal_t *p;
+// int c_might, c_can;
+
+#ifdef MREDEBUG
+ Sys_Printf("\r%6d", portalnum);
+#endif
+
+ p = sorted_portals[portalnum];
+
+ if (p->removed)
+ {
+ p->status = stat_done;
+ return;
+ }
+
+ p->status = stat_working;
+
+// c_might = CountBits (p->portalflood, numportals*2);
+
+ memset (&data, 0, sizeof(data));
+ data.base = p;
+
+ data.pstack_head.portal = p;
+ data.pstack_head.source = p->winding;
+ data.pstack_head.portalplane = p->plane;
+ data.pstack_head.depth = 0;
+ for (i=0 ; i<portallongs ; i++)
+ ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+ RecursivePassageFlow (p, &data, &data.pstack_head);
+
+ p->status = stat_done;
+
+ /*
+ c_can = CountBits (p->portalvis, numportals*2);
+
+ Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
+ (int)(p - portals), c_might, c_can, data.c_chains);
+ */
+}
+
+/*
+==================
+RecursivePassagePortalFlow
+==================
+*/
+void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
+{
+ pstack_t stack;
+ vportal_t *p;
+ leaf_t *leaf;
+ visPlane_t backplane;
+ passage_t *passage, *nextpassage;
+ int i, j, n;
+ long *might, *vis, *prevmight, *cansee, *portalvis, more;
+ int pnum;
+
+// thread->c_chains++;
+
+ leaf = &leafs[portal->leaf];
+// CheckStack (leaf, thread);
+
+ prevstack->next = &stack;
+
+ stack.next = NULL;
+ stack.leaf = leaf;
+ stack.portal = NULL;
+ stack.depth = prevstack->depth + 1;
+
+#ifdef SEPERATORCACHE
+ stack.numseperators[0] = 0;
+ stack.numseperators[1] = 0;
+#endif
+
+ vis = (long *)thread->base->portalvis;
+
+ passage = portal->passages;
+ nextpassage = passage;
+ // check all portals for flowing into other leafs
+ for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
+ {
+ p = leaf->portals[i];
+ if (p->removed)
+ continue;
+ nextpassage = passage->next;
+ pnum = p - portals;
+
+ if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
+ continue; // can't possibly see it
+
+ prevmight = (long *)prevstack->mightsee;
+ cansee = (long *)passage->cansee;
+ might = (long *)stack.mightsee;
+ memcpy(might, prevmight, portalbytes);
+ if (p->status == stat_done)
+ portalvis = (long *) p->portalvis;
+ else
+ portalvis = (long *) p->portalflood;
+ more = 0;
+ for (j = 0; j < portallongs; j++)
+ {
+ if (*might)
+ {
+ *might &= *cansee++ & *portalvis++;
+ more |= (*might & ~vis[j]);
+ }
+ else
+ {
+ cansee++;
+ portalvis++;
+ }
+ might++;
+ }
+
+ if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
+ { // can't see anything new
+ continue;
+ }
+
+ // get plane of portal, point normal into the neighbor leaf
+ stack.portalplane = p->plane;
+ VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
+ backplane.dist = -p->plane.dist;
+
+// c_portalcheck++;
+
+ stack.portal = p;
+ stack.next = NULL;
+ stack.freewindings[0] = 1;
+ stack.freewindings[1] = 1;
+ stack.freewindings[2] = 1;
+
+#if 1
+ {
+ float d;
+
+ d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
+ d -= thread->pstack_head.portalplane.dist;
+ if (d < -p->radius)
+ {
+ continue;
+ }
+ else if (d > p->radius)
+ {
+ stack.pass = p->winding;
+ }
+ else
+ {
+ stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+ if (!stack.pass)
+ continue;
+ }
+ }
+#else
+ stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
+ if (!stack.pass)
+ continue;
+#endif
+
+
+#if 1
+ {
+ float d;
+
+ d = DotProduct (thread->base->origin, p->plane.normal);
+ d -= p->plane.dist;
+ //MrE: vis-bug fix
+ //if (d > p->radius)
+ if (d > thread->base->radius)
+ {
+ continue;
+ }
+ //MrE: vis-bug fix
+ //if (d < -p->radius)
+ else if (d < -thread->base->radius)
+ {
+ stack.source = prevstack->source;
+ }
+ else
+ {
+ stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+ //FIXME: shouldn't we create a new source origin and radius for fast checks?
+ if (!stack.source)
+ continue;
+ }
+ }
+#else
+ stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
+ if (!stack.source)
+ continue;
+#endif
+
+ if (!prevstack->pass)
+ { // the second leaf can only be blocked if coplanar
+
+ // mark the portal as visible
+ thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+ RecursivePassagePortalFlow (p, thread, &stack);
+ continue;
+ }
+
+#ifdef SEPERATORCACHE
+ if (stack.numseperators[0])
+ {
+ for (n = 0; n < stack.numseperators[0]; n++)
+ {
+ stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
+ if (!stack.pass)
+ break; // target is not visible
+ }
+ if (n < stack.numseperators[0])
+ continue;
+ }
+ else
+ {
+ stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
+ }
+#else
+ stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
+#endif
+ if (!stack.pass)
+ continue;
+
+#ifdef SEPERATORCACHE
+ if (stack.numseperators[1])
+ {
+ for (n = 0; n < stack.numseperators[1]; n++)
+ {
+ stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
+ if (!stack.pass)
+ break; // target is not visible
+ }
+ }
+ else
+ {
+ stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
+ }
+#else
+ stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
+#endif
+ if (!stack.pass)
+ continue;
+
+ // mark the portal as visible
+ thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
+
+ // flow through it for real
+ RecursivePassagePortalFlow(p, thread, &stack);
+ //
+ stack.next = NULL;
+ }
+}
+
+/*
+===============
+PassagePortalFlow
+===============
+*/
+void PassagePortalFlow (int portalnum)
+{
+ threaddata_t data;
+ int i;
+ vportal_t *p;
+// int c_might, c_can;
+
+#ifdef MREDEBUG
+ Sys_Printf("\r%6d", portalnum);
+#endif
+
+ p = sorted_portals[portalnum];
+
+ if (p->removed)
+ {
+ p->status = stat_done;
+ return;
+ }
+
+ p->status = stat_working;
+
+// c_might = CountBits (p->portalflood, numportals*2);
+
+ memset (&data, 0, sizeof(data));
+ data.base = p;
+
+ data.pstack_head.portal = p;
+ data.pstack_head.source = p->winding;
+ data.pstack_head.portalplane = p->plane;
+ data.pstack_head.depth = 0;
+ for (i=0 ; i<portallongs ; i++)
+ ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
+
+ RecursivePassagePortalFlow (p, &data, &data.pstack_head);
+
+ p->status = stat_done;
+
+ /*
+ c_can = CountBits (p->portalvis, numportals*2);
+
+ Sys_FPrintf (SYS_VRB,"portal:%4i mightsee:%4i cansee:%4i (%i chains)\n",
+ (int)(p - portals), c_might, c_can, data.c_chains);
+ */
+}
+
+fixedWinding_t *PassageChopWinding (fixedWinding_t *in, fixedWinding_t *out, visPlane_t *split)
+{
+ vec_t dists[128];
+ int sides[128];
+ int counts[3];
+ vec_t dot;
+ int i, j;
+ vec_t *p1, *p2;
+ vec3_t mid;
+ fixedWinding_t *neww;
+
+ counts[0] = counts[1] = counts[2] = 0;
+
+ // determine sides for each point
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ dot = DotProduct (in->points[i], split->normal);
+ dot -= split->dist;
+ dists[i] = dot;
+ if (dot > ON_EPSILON)
+ sides[i] = SIDE_FRONT;
+ else if (dot < -ON_EPSILON)
+ sides[i] = SIDE_BACK;
+ else
+ {
+ sides[i] = SIDE_ON;
+ }
+ counts[sides[i]]++;
+ }
+
+ if (!counts[1])
+ return in; // completely on front side
+
+ if (!counts[0])
+ {
+ return NULL;
+ }
+
+ sides[i] = sides[0];
+ dists[i] = dists[0];
+
+ neww = out;
+
+ neww->numpoints = 0;
+
+ for (i=0 ; i<in->numpoints ; i++)
+ {
+ p1 = in->points[i];
+
+ if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+ {
+ return in; // can't chop -- fall back to original
+ }
+
+ if (sides[i] == SIDE_ON)
+ {
+ VectorCopy (p1, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ continue;
+ }
+
+ if (sides[i] == SIDE_FRONT)
+ {
+ VectorCopy (p1, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ }
+
+ if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
+ continue;
+
+ if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
+ {
+ return in; // can't chop -- fall back to original
+ }
+
+ // generate a split point
+ p2 = in->points[(i+1)%in->numpoints];
+
+ dot = dists[i] / (dists[i]-dists[i+1]);
+ for (j=0 ; j<3 ; j++)
+ { // avoid round off error when possible
+ if (split->normal[j] == 1)
+ mid[j] = split->dist;
+ else if (split->normal[j] == -1)
+ mid[j] = -split->dist;
+ else
+ mid[j] = p1[j] + dot*(p2[j]-p1[j]);
+ }
+
+ VectorCopy (mid, neww->points[neww->numpoints]);
+ neww->numpoints++;
+ }
+
+ return neww;
+}
+
+/*
+===============
+AddSeperators
+===============
+*/
+int AddSeperators (fixedWinding_t *source, fixedWinding_t *pass, qboolean flipclip, visPlane_t *seperators, int maxseperators)
+{
+ int i, j, k, l;
+ visPlane_t plane;
+ vec3_t v1, v2;
+ float d;
+ vec_t length;
+ int counts[3], numseperators;
+ qboolean fliptest;
+
+ numseperators = 0;
+ // check all combinations
+ for (i=0 ; i<source->numpoints ; i++)
+ {
+ l = (i+1)%source->numpoints;
+ VectorSubtract (source->points[l] , source->points[i], v1);
+
+ // find a vertex of pass that makes a plane that puts all of the
+ // vertexes of pass on the front side and all of the vertexes of
+ // source on the back side
+ for (j=0 ; j<pass->numpoints ; j++)
+ {
+ VectorSubtract (pass->points[j], source->points[i], v2);
+
+ plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
+ plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
+ plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
+
+ // if points don't make a valid plane, skip it
+
+ length = plane.normal[0] * plane.normal[0]
+ + plane.normal[1] * plane.normal[1]
+ + plane.normal[2] * plane.normal[2];
+
+ if (length < ON_EPSILON)
+ continue;
+
+ length = 1/sqrt(length);
+
+ plane.normal[0] *= length;
+ plane.normal[1] *= length;
+ plane.normal[2] *= length;
+
+ plane.dist = DotProduct (pass->points[j], plane.normal);
+
+ //
+ // find out which side of the generated seperating plane has the
+ // source portal
+ //
+#if 1
+ fliptest = qfalse;
+ for (k=0 ; k<source->numpoints ; k++)
+ {
+ if (k == i || k == l)
+ continue;
+ d = DotProduct (source->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ { // source is on the negative side, so we want all
+ // pass and target on the positive side
+ fliptest = qfalse;
+ break;
+ }
+ else if (d > ON_EPSILON)
+ { // source is on the positive side, so we want all
+ // pass and target on the negative side
+ fliptest = qtrue;
+ break;
+ }
+ }
+ if (k == source->numpoints)
+ continue; // planar with source portal
+#else
+ fliptest = flipclip;
+#endif
+ //
+ // flip the normal if the source portal is backwards
+ //
+ if (fliptest)
+ {
+ VectorSubtract (vec3_origin, plane.normal, plane.normal);
+ plane.dist = -plane.dist;
+ }
+#if 1
+ //
+ // if all of the pass portal points are now on the positive side,
+ // this is the seperating plane
+ //
+ counts[0] = counts[1] = counts[2] = 0;
+ for (k=0 ; k<pass->numpoints ; k++)
+ {
+ if (k==j)
+ continue;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ break;
+ else if (d > ON_EPSILON)
+ counts[0]++;
+ else
+ counts[2]++;
+ }
+ if (k != pass->numpoints)
+ continue; // points on negative side, not a seperating plane
+
+ if (!counts[0])
+ continue; // planar with seperating plane
+#else
+ k = (j+1)%pass->numpoints;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ continue;
+ k = (j+pass->numpoints-1)%pass->numpoints;
+ d = DotProduct (pass->points[k], plane.normal) - plane.dist;
+ if (d < -ON_EPSILON)
+ continue;
+#endif
+ //
+ // flip the normal if we want the back side
+ //
+ if (flipclip)
+ {
+ VectorSubtract (vec3_origin, plane.normal, plane.normal);
+ plane.dist = -plane.dist;
+ }
+
+ if (numseperators >= maxseperators)
+ Error("max seperators");
+ seperators[numseperators] = plane;
+ numseperators++;
+ break;
+ }
+ }
+ return numseperators;
+}
+
+/*
+===============
+CreatePassages
+
+MrE: create passages from one portal to all the portals in the leaf the portal leads to
+ every passage has a cansee bit string with all the portals that can be
+ seen through the passage
+===============
+*/
+void CreatePassages(int portalnum)
+{
+ int i, j, k, n, numseperators, numsee;
+ float d;
+ vportal_t *portal, *p, *target;
+ leaf_t *leaf;
+ passage_t *passage, *lastpassage;
+ visPlane_t seperators[MAX_SEPERATORS*2];
+ fixedWinding_t *w;
+ fixedWinding_t in, out, *res;
+
+
+#ifdef MREDEBUG
+ Sys_Printf("\r%6d", portalnum);
+#endif
+
+ portal = sorted_portals[portalnum];
+
+ if (portal->removed)
+ {
+ portal->status = stat_done;
+ return;
+ }
+
+ lastpassage = NULL;
+ leaf = &leafs[portal->leaf];
+ for (i = 0; i < leaf->numportals; i++)
+ {
+ target = leaf->portals[i];
+ if (target->removed)
+ continue;
+
+ passage = (passage_t *) safe_malloc(sizeof(passage_t) + portalbytes);
+ memset(passage, 0, sizeof(passage_t) + portalbytes);
+ numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
+ numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
+
+ passage->next = NULL;
+ if (lastpassage)
+ lastpassage->next = passage;
+ else
+ portal->passages = passage;
+ lastpassage = passage;
+
+ numsee = 0;
+ //create the passage->cansee
+ for (j = 0; j < numportals * 2; j++)
+ {
+ p = &portals[j];
+ if (p->removed)
+ continue;
+ if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
+ continue;
+ if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
+ continue;
+ for (k = 0; k < numseperators; k++)
+ {
+ //
+ d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
+ //if completely at the back of the seperator plane
+ if (d < -p->radius + ON_EPSILON)
+ break;
+ w = p->winding;
+ for (n = 0; n < w->numpoints; n++)
+ {
+ d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
+ //if at the front of the seperator
+ if (d > ON_EPSILON)
+ break;
+ }
+ //if no points are at the front of the seperator
+ if (n >= w->numpoints)
+ break;
+ }
+ if (k < numseperators)
+ continue;
+
+ /* explitive deleted */
+
+
+ /* ydnar: prefer correctness to stack overflow */
+ //% memcpy( &in, p->winding, (int)((fixedWinding_t *)0)->points[p->winding->numpoints] );
+ if( p->winding->numpoints <= MAX_POINTS_ON_FIXED_WINDING )
+ memcpy( &in, p->winding, (int) &(((fixedWinding_t*) 0)->points[ p->winding->numpoints ]) );
+ else
+ memcpy( &in, p->winding, sizeof( fixedWinding_t ) );
+
+
+ for( k = 0; k < numseperators; k++ )
+ {
+ /* ydnar: this is a shitty crutch */
+ if( in.numpoints > MAX_POINTS_ON_FIXED_WINDING )
+ {
+ //% Sys_Printf( "[%d]", p->winding->numpoints );
+ in.numpoints = MAX_POINTS_ON_FIXED_WINDING;
+ }
+
+ res = PassageChopWinding( &in, &out, &seperators[ k ] );
+ if( res == &out )
+ memcpy( &in, &out, sizeof( fixedWinding_t ) );
+
+
+ if( res == NULL )
+ break;
+ }
+ if (k < numseperators)
+ continue;
+ passage->cansee[j >> 3] |= (1<<(j&7));
+ numsee++;
+ }
+ }
+}
+
+void PassageMemory(void)
+{
+ int i, j, totalmem, totalportals;
+ vportal_t *portal, *target;
+ leaf_t *leaf;
+
+ totalmem = 0;
+ totalportals = 0;
+ for (i = 0; i < numportals; i++)
+ {
+ portal = sorted_portals[i];
+ if (portal->removed)
+ continue;
+ leaf = &leafs[portal->leaf];
+ for (j = 0; j < leaf->numportals; j++)
+ {
+ target = leaf->portals[j];
+ if (target->removed)
+ continue;
+ totalmem += sizeof(passage_t) + portalbytes;
+ totalportals++;
+ }
+ }
+ Sys_Printf("%7i average number of passages per leaf\n", totalportals / numportals);
+ Sys_Printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
+}
+
+/*
+===============================================================================
+
+This is a rough first-order aproximation that is used to trivially reject some
+of the final calculations.
+
+
+Calculates portalfront and portalflood bit vectors
+
+thinking about:
+
+typedef struct passage_s
+{
+ struct passage_s *next;
+ struct portal_s *to;
+ stryct sep_s *seperators;
+ byte *mightsee;
+} passage_t;
+
+typedef struct portal_s
+{
+ struct passage_s *passages;
+ int leaf; // leaf portal faces into
+} portal_s;
+
+leaf = portal->leaf
+clear
+for all portals
+
+
+calc portal visibility
+ clear bit vector
+ for all passages
+ passage visibility
+
+
+for a portal to be visible to a passage, it must be on the front of
+all seperating planes, and both portals must be behind the new portal
+
+===============================================================================
+*/
+
+int c_flood, c_vis;
+
+
+/*
+==================
+SimpleFlood
+
+==================
+*/
+void SimpleFlood (vportal_t *srcportal, int leafnum)
+{
+ int i;
+ leaf_t *leaf;
+ vportal_t *p;
+ int pnum;
+
+ leaf = &leafs[leafnum];
+
+ for (i=0 ; i<leaf->numportals ; i++)
+ {
+ p = leaf->portals[i];
+ if (p->removed)
+ continue;
+ pnum = p - portals;
+ if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
+ continue;
+
+ if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
+ continue;
+
+ srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
+
+ SimpleFlood (srcportal, p->leaf);
+ }
+}
+
+/*
+==============
+BasePortalVis
+==============
+*/
+void BasePortalVis( int portalnum )
+{
+ int j, k;
+ vportal_t *tp, *p;
+ float d;
+ fixedWinding_t *w;
+ vec3_t dir;
+
+
+ p = portals+portalnum;
+
+ if (p->removed)
+ return;
+
+ p->portalfront = safe_malloc (portalbytes);
+ memset (p->portalfront, 0, portalbytes);
+
+ p->portalflood = safe_malloc (portalbytes);
+ memset (p->portalflood, 0, portalbytes);
+
+ p->portalvis = safe_malloc (portalbytes);
+ memset (p->portalvis, 0, portalbytes);
+
+ for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
+ {
+ if( j == portalnum )
+ continue;
+ if( tp->removed )
+ continue;
+
+ /* ydnar: this is old farplane vis code from mre */
+ /*
+ if (farplanedist >= 0)
+ {
+ vec3_t dir;
+ VectorSubtract(p->origin, tp->origin, dir);
+ if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
+ continue;
+ }
+ */
+
+ /* ydnar: this is known-to-be-working farplane code */
+ if( farPlaneDist > 0.0f )
+ {
+ VectorSubtract( p->origin, tp->origin, dir );
+ if( VectorLength( dir ) - p->radius - tp->radius > farPlaneDist )
+ continue;
+ }
+
+
+ w = tp->winding;
+ for (k=0 ; k<w->numpoints ; k++)
+ {
+ d = DotProduct (w->points[k], p->plane.normal)
+ - p->plane.dist;
+ if (d > ON_EPSILON)
+ break;
+ }
+ if (k == w->numpoints)
+ continue; // no points on front
+
+ w = p->winding;
+ for (k=0 ; k<w->numpoints ; k++)
+ {
+ d = DotProduct (w->points[k], tp->plane.normal)
+ - tp->plane.dist;
+ if (d < -ON_EPSILON)
+ break;
+ }
+ if (k == w->numpoints)
+ continue; // no points on front
+
+ p->portalfront[j>>3] |= (1<<(j&7));
+ }
+
+ SimpleFlood (p, p->leaf);
+
+ p->nummightsee = CountBits (p->portalflood, numportals*2);
+// Sys_Printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
+ c_flood += p->nummightsee;
+}
+
+
+
+
+
+/*
+===============================================================================
+
+This is a second order aproximation
+
+Calculates portalvis bit vector
+
+WAAAAAAY too slow.
+
+===============================================================================
+*/
+
+/*
+==================
+RecursiveLeafBitFlow
+
+==================
+*/
+void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
+{
+ vportal_t *p;
+ leaf_t *leaf;
+ int i, j;
+ long more;
+ int pnum;
+ byte newmight[MAX_PORTALS/8];
+
+ leaf = &leafs[leafnum];
+
+ // check all portals for flowing into other leafs
+ for (i=0 ; i<leaf->numportals ; i++)
+ {
+ p = leaf->portals[i];
+ if (p->removed)
+ continue;
+ pnum = p - portals;
+
+ // if some previous portal can't see it, skip
+ if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
+ continue;
+
+ // if this portal can see some portals we mightsee, recurse
+ more = 0;
+ for (j=0 ; j<portallongs ; j++)
+ {
+ ((long *)newmight)[j] = ((long *)mightsee)[j]
+ & ((long *)p->portalflood)[j];
+ more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
+ }
+
+ if (!more)
+ continue; // can't see anything new
+
+ cansee[pnum>>3] |= (1<<(pnum&7));
+
+ RecursiveLeafBitFlow (p->leaf, newmight, cansee);
+ }
+}
+
+/*
+==============
+BetterPortalVis
+==============
+*/
+void BetterPortalVis (int portalnum)
+{
+ vportal_t *p;
+
+ p = portals+portalnum;
+
+ if (p->removed)
+ return;
+
+ RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
+
+ // build leaf vis information
+ p->nummightsee = CountBits (p->portalvis, numportals*2);
+ c_vis += p->nummightsee;
+}
+
+
projects / xonotic / netradiant.git / blobdiff