home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / visflow.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  36.1 KB  |  1,641 lines
  1. #include "vis.h"
  2.  
  3. /*
  4.  
  5.   each portal will have a list of all possible to see from first portal
  6.  
  7.   if (!thread->portalmightsee[portalnum])
  8.  
  9.   portal mightsee
  10.  
  11.   for p2 = all other portals in leaf
  12.     get sperating planes
  13.     for all portals that might be seen by p2
  14.         mark as unseen if not present in seperating plane
  15.     flood fill a new mightsee
  16.     save as passagemightsee
  17.  
  18.  
  19.   void CalcMightSee (leaf_t *leaf, 
  20. */
  21.  
  22. int CountBits (byte *bits, int numbits)
  23. {
  24.     int        i;
  25.     int        c;
  26.  
  27.     c = 0;
  28.     for (i=0 ; i<numbits ; i++)
  29.         if (bits[i>>3] & (1<<(i&7)) )
  30.             c++;
  31.  
  32.     return c;
  33. }
  34.  
  35. int        c_fullskip;
  36. int        c_portalskip, c_leafskip;
  37. int        c_vistest, c_mighttest;
  38.  
  39. int        c_chop, c_nochop;
  40.  
  41. int        active;
  42.  
  43. void CheckStack (leaf_t *leaf, threaddata_t *thread)
  44. {
  45.     pstack_t    *p, *p2;
  46.  
  47.     for (p=thread->pstack_head.next ; p ; p=p->next)
  48.     {
  49. //        _printf ("=");
  50.         if (p->leaf == leaf)
  51.             Error ("CheckStack: leaf recursion");
  52.         for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
  53.             if (p2->leaf == p->leaf)
  54.                 Error ("CheckStack: late leaf recursion");
  55.     }
  56. //    _printf ("\n");
  57. }
  58.  
  59.  
  60. winding_t *AllocStackWinding (pstack_t *stack)
  61. {
  62.     int        i;
  63.  
  64.     for (i=0 ; i<3 ; i++)
  65.     {
  66.         if (stack->freewindings[i])
  67.         {
  68.             stack->freewindings[i] = 0;
  69.             return &stack->windings[i];
  70.         }
  71.     }
  72.  
  73.     Error ("AllocStackWinding: failed");
  74.  
  75.     return NULL;
  76. }
  77.  
  78. void FreeStackWinding (winding_t *w, pstack_t *stack)
  79. {
  80.     int        i;
  81.  
  82.     i = w - stack->windings;
  83.  
  84.     if (i<0 || i>2)
  85.         return;        // not from local
  86.  
  87.     if (stack->freewindings[i])
  88.         Error ("FreeStackWinding: allready free");
  89.     stack->freewindings[i] = 1;
  90. }
  91.  
  92. /*
  93. ==============
  94. VisChopWinding
  95.  
  96. ==============
  97. */
  98. winding_t    *VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
  99. {
  100.     vec_t    dists[128];
  101.     int        sides[128];
  102.     int        counts[3];
  103.     vec_t    dot;
  104.     int        i, j;
  105.     vec_t    *p1, *p2;
  106.     vec3_t    mid;
  107.     winding_t    *neww;
  108.  
  109.     counts[0] = counts[1] = counts[2] = 0;
  110.  
  111.     // determine sides for each point
  112.     for (i=0 ; i<in->numpoints ; i++)
  113.     {
  114.         dot = DotProduct (in->points[i], split->normal);
  115.         dot -= split->dist;
  116.         dists[i] = dot;
  117.         if (dot > ON_EPSILON)
  118.             sides[i] = SIDE_FRONT;
  119.         else if (dot < -ON_EPSILON)
  120.             sides[i] = SIDE_BACK;
  121.         else
  122.         {
  123.             sides[i] = SIDE_ON;
  124.         }
  125.         counts[sides[i]]++;
  126.     }
  127.  
  128.     if (!counts[1])
  129.         return in;        // completely on front side
  130.     
  131.     if (!counts[0])
  132.     {
  133.         FreeStackWinding (in, stack);
  134.         return NULL;
  135.     }
  136.  
  137.     sides[i] = sides[0];
  138.     dists[i] = dists[0];
  139.     
  140.     neww = AllocStackWinding (stack);
  141.  
  142.     neww->numpoints = 0;
  143.  
  144.     for (i=0 ; i<in->numpoints ; i++)
  145.     {
  146.         p1 = in->points[i];
  147.  
  148.         if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
  149.         {
  150.             FreeStackWinding (neww, stack);
  151.             return in;        // can't chop -- fall back to original
  152.         }
  153.  
  154.         if (sides[i] == SIDE_ON)
  155.         {
  156.             VectorCopy (p1, neww->points[neww->numpoints]);
  157.             neww->numpoints++;
  158.             continue;
  159.         }
  160.     
  161.         if (sides[i] == SIDE_FRONT)
  162.         {
  163.             VectorCopy (p1, neww->points[neww->numpoints]);
  164.             neww->numpoints++;
  165.         }
  166.         
  167.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  168.             continue;
  169.             
  170.         if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
  171.         {
  172.             FreeStackWinding (neww, stack);
  173.             return in;        // can't chop -- fall back to original
  174.         }
  175.  
  176.         // generate a split point
  177.         p2 = in->points[(i+1)%in->numpoints];
  178.         
  179.         dot = dists[i] / (dists[i]-dists[i+1]);
  180.         for (j=0 ; j<3 ; j++)
  181.         {    // avoid round off error when possible
  182.             if (split->normal[j] == 1)
  183.                 mid[j] = split->dist;
  184.             else if (split->normal[j] == -1)
  185.                 mid[j] = -split->dist;
  186.             else
  187.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  188.         }
  189.             
  190.         VectorCopy (mid, neww->points[neww->numpoints]);
  191.         neww->numpoints++;
  192.     }
  193.     
  194.     // free the original winding
  195.     FreeStackWinding (in, stack);
  196.     
  197.     return neww;
  198. }
  199.  
  200. /*
  201. ==============
  202. ClipToSeperators
  203.  
  204. Source, pass, and target are an ordering of portals.
  205.  
  206. Generates seperating planes canidates by taking two points from source and one
  207. point from pass, and clips target by them.
  208.  
  209. If target is totally clipped away, that portal can not be seen through.
  210.  
  211. Normal clip keeps target on the same side as pass, which is correct if the
  212. order goes source, pass, target.  If the order goes pass, source, target then
  213. flipclip should be set.
  214. ==============
  215. */
  216. winding_t    *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
  217. {
  218.     int            i, j, k, l;
  219.     plane_t        plane;
  220.     vec3_t        v1, v2;
  221.     float        d;
  222.     vec_t        length;
  223.     int            counts[3];
  224.     qboolean        fliptest;
  225.  
  226.     // check all combinations    
  227.     for (i=0 ; i<source->numpoints ; i++)
  228.     {
  229.         l = (i+1)%source->numpoints;
  230.         VectorSubtract (source->points[l] , source->points[i], v1);
  231.  
  232.         // find a vertex of pass that makes a plane that puts all of the
  233.         // vertexes of pass on the front side and all of the vertexes of
  234.         // source on the back side
  235.         for (j=0 ; j<pass->numpoints ; j++)
  236.         {
  237.             VectorSubtract (pass->points[j], source->points[i], v2);
  238.  
  239.             plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
  240.             plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
  241.             plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
  242.             
  243.             // if points don't make a valid plane, skip it
  244.  
  245.             length = plane.normal[0] * plane.normal[0]
  246.             + plane.normal[1] * plane.normal[1]
  247.             + plane.normal[2] * plane.normal[2];
  248.             
  249.             if (length < ON_EPSILON)
  250.                 continue;
  251.  
  252.             length = 1/sqrt(length);
  253.             
  254.             plane.normal[0] *= length;
  255.             plane.normal[1] *= length;
  256.             plane.normal[2] *= length;
  257.  
  258.             plane.dist = DotProduct (pass->points[j], plane.normal);
  259.  
  260.             //
  261.             // find out which side of the generated seperating plane has the
  262.             // source portal
  263.             //
  264. #if 1
  265.             fliptest = qfalse;
  266.             for (k=0 ; k<source->numpoints ; k++)
  267.             {
  268.                 if (k == i || k == l)
  269.                     continue;
  270.                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
  271.                 if (d < -ON_EPSILON)
  272.                 {    // source is on the negative side, so we want all
  273.                     // pass and target on the positive side
  274.                     fliptest = qfalse;
  275.                     break;
  276.                 }
  277.                 else if (d > ON_EPSILON)
  278.                 {    // source is on the positive side, so we want all
  279.                     // pass and target on the negative side
  280.                     fliptest = qtrue;
  281.                     break;
  282.                 }
  283.             }
  284.             if (k == source->numpoints)
  285.                 continue;        // planar with source portal
  286. #else
  287.             fliptest = flipclip;
  288. #endif
  289.             //
  290.             // flip the normal if the source portal is backwards
  291.             //
  292.             if (fliptest)
  293.             {
  294.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  295.                 plane.dist = -plane.dist;
  296.             }
  297. #if 1
  298.             //
  299.             // if all of the pass portal points are now on the positive side,
  300.             // this is the seperating plane
  301.             //
  302.             counts[0] = counts[1] = counts[2] = 0;
  303.             for (k=0 ; k<pass->numpoints ; k++)
  304.             {
  305.                 if (k==j)
  306.                     continue;
  307.                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  308.                 if (d < -ON_EPSILON)
  309.                     break;
  310.                 else if (d > ON_EPSILON)
  311.                     counts[0]++;
  312.                 else
  313.                     counts[2]++;
  314.             }
  315.             if (k != pass->numpoints)
  316.                 continue;    // points on negative side, not a seperating plane
  317.                 
  318.             if (!counts[0])
  319.                 continue;    // planar with seperating plane
  320. #else
  321.             k = (j+1)%pass->numpoints;
  322.             d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  323.             if (d < -ON_EPSILON)
  324.                 continue;
  325.             k = (j+pass->numpoints-1)%pass->numpoints;
  326.             d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  327.             if (d < -ON_EPSILON)
  328.                 continue;            
  329. #endif
  330.             //
  331.             // flip the normal if we want the back side
  332.             //
  333.             if (flipclip)
  334.             {
  335.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  336.                 plane.dist = -plane.dist;
  337.             }
  338.  
  339. #ifdef SEPERATORCACHE
  340.             stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
  341.             if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
  342.                 Error("MAX_SEPERATORS");
  343. #endif
  344.             //MrE: fast check first
  345.             d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
  346.             //if completely at the back of the seperator plane
  347.             if (d < -stack->portal->radius)
  348.                 return NULL;
  349.             //if completely on the front of the seperator plane
  350.             if (d > stack->portal->radius)
  351.                 break;
  352.  
  353.             //
  354.             // clip target by the seperating plane
  355.             //
  356.             target = VisChopWinding (target, stack, &plane);
  357.             if (!target)
  358.                 return NULL;        // target is not visible
  359.  
  360.             break;        // optimization by Antony Suter
  361.         }
  362.     }
  363.     
  364.     return target;
  365. }
  366.  
  367. /*
  368. ==================
  369. RecursiveLeafFlow
  370.  
  371. Flood fill through the leafs
  372. If src_portal is NULL, this is the originating leaf
  373. ==================
  374. */
  375. void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
  376. {
  377.     pstack_t    stack;
  378.     vportal_t    *p;
  379.     plane_t        backplane;
  380.     leaf_t         *leaf;
  381.     int            i, j, n;
  382.     long        *test, *might, *prevmight, *vis, more;
  383.     int            pnum;
  384.  
  385.     thread->c_chains++;
  386.  
  387.     leaf = &leafs[leafnum];
  388. //    CheckStack (leaf, thread);
  389.  
  390.     prevstack->next = &stack;
  391.  
  392.     stack.next = NULL;
  393.     stack.leaf = leaf;
  394.     stack.portal = NULL;
  395.     stack.depth = prevstack->depth + 1;
  396.  
  397. #ifdef SEPERATORCACHE
  398.     stack.numseperators[0] = 0;
  399.     stack.numseperators[1] = 0;
  400. #endif
  401.  
  402.     might = (long *)stack.mightsee;
  403.     vis = (long *)thread->base->portalvis;
  404.     
  405.     // check all portals for flowing into other leafs    
  406.     for (i = 0; i < leaf->numportals; i++)
  407.     {
  408.         p = leaf->portals[i];
  409.         if (p->removed)
  410.             continue;
  411.         pnum = p - portals;
  412.  
  413.         /* MrE: portal trace debug code
  414.         {
  415.             int portaltrace[] = {13, 16, 17, 37};
  416.             pstack_t *s;
  417.  
  418.             s = &thread->pstack_head;
  419.             for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
  420.             {
  421.                 if (s->portal->num != portaltrace[j])
  422.                     break;
  423.             }
  424.             if (j >= sizeof(portaltrace)/sizeof(int) - 1)
  425.             {
  426.                 if (p->num == portaltrace[j])
  427.                     n = 0; //traced through all the portals
  428.             }
  429.         }
  430.         */
  431.  
  432.         if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
  433.         {
  434.             continue;    // can't possibly see it
  435.         }
  436.  
  437.         // if the portal can't see anything we haven't allready seen, skip it
  438.         if (p->status == stat_done)
  439.         {
  440.             test = (long *)p->portalvis;
  441.         }
  442.         else
  443.         {
  444.             test = (long *)p->portalflood;
  445.         }
  446.  
  447.         more = 0;
  448.         prevmight = (long *)prevstack->mightsee;
  449.         for (j=0 ; j<portallongs ; j++)
  450.         {
  451.             might[j] = prevmight[j] & test[j];
  452.             more |= (might[j] & ~vis[j]);
  453.         }
  454.         
  455.         if (!more && 
  456.             (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
  457.         {    // can't see anything new
  458.             continue;
  459.         }
  460.  
  461.         // get plane of portal, point normal into the neighbor leaf
  462.         stack.portalplane = p->plane;
  463.         VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
  464.         backplane.dist = -p->plane.dist;
  465.         
  466. //        c_portalcheck++;
  467.         
  468.         stack.portal = p;
  469.         stack.next = NULL;
  470.         stack.freewindings[0] = 1;
  471.         stack.freewindings[1] = 1;
  472.         stack.freewindings[2] = 1;
  473.         
  474. #if 1
  475.         {
  476.             float d;
  477.  
  478.             d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
  479.             d -= thread->pstack_head.portalplane.dist;
  480.             if (d < -p->radius)
  481.             {
  482.                 continue;
  483.             }
  484.             else if (d > p->radius)
  485.             {
  486.                 stack.pass = p->winding;
  487.             }
  488.             else    
  489.             {
  490.                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
  491.                 if (!stack.pass)
  492.                     continue;
  493.             }
  494.         }
  495. #else
  496.         stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
  497.         if (!stack.pass)
  498.             continue;
  499. #endif
  500.  
  501.     
  502. #if 1
  503.         {
  504.             float d;
  505.  
  506.             d = DotProduct (thread->base->origin, p->plane.normal);
  507.             d -= p->plane.dist;
  508.             //MrE: vis-bug fix
  509.             //if (d > p->radius)
  510.             if (d > thread->base->radius)
  511.             {
  512.                 continue;
  513.             }
  514.             //MrE: vis-bug fix
  515.             //if (d < -p->radius)
  516.             else if (d < -thread->base->radius)
  517.             {
  518.                 stack.source = prevstack->source;
  519.             }
  520.             else    
  521.             {
  522.                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
  523.                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
  524.                 if (!stack.source)
  525.                     continue;
  526.             }
  527.         }
  528. #else
  529.         stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
  530.         if (!stack.source)
  531.             continue;
  532. #endif
  533.  
  534.         if (!prevstack->pass)
  535.         {    // the second leaf can only be blocked if coplanar
  536.  
  537.             // mark the portal as visible
  538.             thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
  539.  
  540.             RecursiveLeafFlow (p->leaf, thread, &stack);
  541.             continue;
  542.         }
  543.  
  544. #ifdef SEPERATORCACHE
  545.         if (stack.numseperators[0])
  546.         {
  547.             for (n = 0; n < stack.numseperators[0]; n++)
  548.             {
  549.                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
  550.                 if (!stack.pass)
  551.                     break;        // target is not visible
  552.             }
  553.             if (n < stack.numseperators[0])
  554.                 continue;
  555.         }
  556.         else
  557.         {
  558.             stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
  559.         }
  560. #else
  561.         stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
  562. #endif
  563.         if (!stack.pass)
  564.             continue;
  565.  
  566. #ifdef SEPERATORCACHE
  567.         if (stack.numseperators[1])
  568.         {
  569.             for (n = 0; n < stack.numseperators[1]; n++)
  570.             {
  571.                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
  572.                 if (!stack.pass)
  573.                     break;        // target is not visible
  574.             }
  575.         }
  576.         else
  577.         {
  578.             stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
  579.         }
  580. #else
  581.         stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
  582. #endif
  583.         if (!stack.pass)
  584.             continue;
  585.  
  586.         // mark the portal as visible
  587.         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
  588.  
  589.         // flow through it for real
  590.         RecursiveLeafFlow (p->leaf, thread, &stack);
  591.         //
  592.         stack.next = NULL;
  593.     }    
  594. }
  595.  
  596. /*
  597. ===============
  598. PortalFlow
  599.  
  600. generates the portalvis bit vector
  601. ===============
  602. */
  603. void PortalFlow (int portalnum)
  604. {
  605.     threaddata_t    data;
  606.     int                i;
  607.     vportal_t        *p;
  608.     int                c_might, c_can;
  609.  
  610. #ifdef MREDEBUG
  611.     _printf("\r%6d", portalnum);
  612. #endif
  613.  
  614.     p = sorted_portals[portalnum];
  615.  
  616.     if (p->removed)
  617.     {
  618.         p->status = stat_done;
  619.         return;
  620.     }
  621.  
  622.     p->status = stat_working;
  623.  
  624.     c_might = CountBits (p->portalflood, numportals*2);
  625.  
  626.     memset (&data, 0, sizeof(data));
  627.     data.base = p;
  628.     
  629.     data.pstack_head.portal = p;
  630.     data.pstack_head.source = p->winding;
  631.     data.pstack_head.portalplane = p->plane;
  632.     data.pstack_head.depth = 0;
  633.     for (i=0 ; i<portallongs ; i++)
  634.         ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
  635.  
  636.     RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
  637.  
  638.     p->status = stat_done;
  639.  
  640.     c_can = CountBits (p->portalvis, numportals*2);
  641.  
  642.     qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
  643.         (int)(p - portals),    c_might, c_can, data.c_chains);
  644. }
  645.  
  646. /*
  647. ==================
  648. RecursivePassageFlow
  649. ==================
  650. */
  651. void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
  652. {
  653.     pstack_t    stack;
  654.     vportal_t    *p;
  655.     leaf_t         *leaf;
  656.     passage_t    *passage, *nextpassage;
  657.     int            i, j;
  658.     long        *might, *vis, *prevmight, *cansee, *portalvis, more;
  659.     int            pnum;
  660.  
  661. //    thread->c_chains++;
  662.  
  663.     leaf = &leafs[portal->leaf];
  664. //    CheckStack (leaf, thread);
  665.  
  666.     prevstack->next = &stack;
  667.  
  668.     stack.next = NULL;
  669. //    stack.leaf = leaf;
  670. //    stack.portal = NULL;
  671.     stack.depth = prevstack->depth + 1;
  672.  
  673.     vis = (long *)thread->base->portalvis;
  674.  
  675.     passage = portal->passages;
  676.     nextpassage = passage;
  677.     // check all portals for flowing into other leafs    
  678.     for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
  679.     {
  680.         p = leaf->portals[i];
  681.         if (p->removed)
  682.             continue;
  683.         nextpassage = passage->next;
  684.         pnum = p - portals;
  685.  
  686.         if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
  687.             continue;    // can't possibly see it
  688.  
  689.         prevmight = (long *)prevstack->mightsee;
  690.         cansee = (long *)passage->cansee;
  691.         might = (long *)stack.mightsee;
  692.         memcpy(might, prevmight, portalbytes);
  693.         if (p->status == stat_done)
  694.             portalvis = (long *) p->portalvis;
  695.         else
  696.             portalvis = (long *) p->portalflood;
  697.         more = 0;
  698.         for (j = 0; j < portallongs; j++)
  699.         {
  700.             if (*might)
  701.             {
  702.                 *might &= *cansee++ & *portalvis++;
  703.                 more |= (*might & ~vis[j]);
  704.             }
  705.             else
  706.             {
  707.                 cansee++;
  708.                 portalvis++;
  709.             }
  710.             might++;
  711.         }
  712.  
  713.         if (!more &&
  714.             (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
  715.         {    // can't see anything new
  716.             continue;
  717.         }
  718.  
  719. //        stack.portal = p;
  720.         // mark the portal as visible
  721.         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
  722.         // flow through it for real
  723.         RecursivePassageFlow(p, thread, &stack);
  724.         //
  725.         stack.next = NULL;
  726.     }
  727. }
  728.  
  729. /*
  730. ===============
  731. PassageFlow
  732. ===============
  733. */
  734. void PassageFlow (int portalnum)
  735. {
  736.     threaddata_t    data;
  737.     int                i;
  738.     vportal_t        *p;
  739. //    int                c_might, c_can;
  740.  
  741. #ifdef MREDEBUG
  742.     _printf("\r%6d", portalnum);
  743. #endif
  744.  
  745.     p = sorted_portals[portalnum];
  746.  
  747.     if (p->removed)
  748.     {
  749.         p->status = stat_done;
  750.         return;
  751.     }
  752.  
  753.     p->status = stat_working;
  754.  
  755. //    c_might = CountBits (p->portalflood, numportals*2);
  756.  
  757.     memset (&data, 0, sizeof(data));
  758.     data.base = p;
  759.     
  760.     data.pstack_head.portal = p;
  761.     data.pstack_head.source = p->winding;
  762.     data.pstack_head.portalplane = p->plane;
  763.     data.pstack_head.depth = 0;
  764.     for (i=0 ; i<portallongs ; i++)
  765.         ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
  766.  
  767.     RecursivePassageFlow (p, &data, &data.pstack_head);
  768.  
  769.     p->status = stat_done;
  770.  
  771.     /*
  772.     c_can = CountBits (p->portalvis, numportals*2);
  773.  
  774.     qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
  775.         (int)(p - portals),    c_might, c_can, data.c_chains);
  776.     */
  777. }
  778.  
  779. /*
  780. ==================
  781. RecursivePassagePortalFlow
  782. ==================
  783. */
  784. void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
  785. {
  786.     pstack_t    stack;
  787.     vportal_t    *p;
  788.     leaf_t         *leaf;
  789.     plane_t        backplane;
  790.     passage_t    *passage, *nextpassage;
  791.     int            i, j, n;
  792.     long        *might, *vis, *prevmight, *cansee, *portalvis, more;
  793.     int            pnum;
  794.  
  795. //    thread->c_chains++;
  796.  
  797.     leaf = &leafs[portal->leaf];
  798. //    CheckStack (leaf, thread);
  799.  
  800.     prevstack->next = &stack;
  801.  
  802.     stack.next = NULL;
  803.     stack.leaf = leaf;
  804.     stack.portal = NULL;
  805.     stack.depth = prevstack->depth + 1;
  806.  
  807. #ifdef SEPERATORCACHE
  808.     stack.numseperators[0] = 0;
  809.     stack.numseperators[1] = 0;
  810. #endif
  811.  
  812.     vis = (long *)thread->base->portalvis;
  813.  
  814.     passage = portal->passages;
  815.     nextpassage = passage;
  816.     // check all portals for flowing into other leafs    
  817.     for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
  818.     {
  819.         p = leaf->portals[i];
  820.         if (p->removed)
  821.             continue;
  822.         nextpassage = passage->next;
  823.         pnum = p - portals;
  824.  
  825.         if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
  826.             continue;    // can't possibly see it
  827.  
  828.         prevmight = (long *)prevstack->mightsee;
  829.         cansee = (long *)passage->cansee;
  830.         might = (long *)stack.mightsee;
  831.         memcpy(might, prevmight, portalbytes);
  832.         if (p->status == stat_done)
  833.             portalvis = (long *) p->portalvis;
  834.         else
  835.             portalvis = (long *) p->portalflood;
  836.         more = 0;
  837.         for (j = 0; j < portallongs; j++)
  838.         {
  839.             if (*might)
  840.             {
  841.                 *might &= *cansee++ & *portalvis++;
  842.                 more |= (*might & ~vis[j]);
  843.             }
  844.             else
  845.             {
  846.                 cansee++;
  847.                 portalvis++;
  848.             }
  849.             might++;
  850.         }
  851.  
  852.         if (!more &&
  853.             (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
  854.         {    // can't see anything new
  855.             continue;
  856.         }
  857.  
  858.         // get plane of portal, point normal into the neighbor leaf
  859.         stack.portalplane = p->plane;
  860.         VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
  861.         backplane.dist = -p->plane.dist;
  862.         
  863. //        c_portalcheck++;
  864.         
  865.         stack.portal = p;
  866.         stack.next = NULL;
  867.         stack.freewindings[0] = 1;
  868.         stack.freewindings[1] = 1;
  869.         stack.freewindings[2] = 1;
  870.  
  871. #if 1
  872.         {
  873.             float d;
  874.  
  875.             d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
  876.             d -= thread->pstack_head.portalplane.dist;
  877.             if (d < -p->radius)
  878.             {
  879.                 continue;
  880.             }
  881.             else if (d > p->radius)
  882.             {
  883.                 stack.pass = p->winding;
  884.             }
  885.             else    
  886.             {
  887.                 stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
  888.                 if (!stack.pass)
  889.                     continue;
  890.             }
  891.         }
  892. #else
  893.         stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
  894.         if (!stack.pass)
  895.             continue;
  896. #endif
  897.  
  898.     
  899. #if 1
  900.         {
  901.             float d;
  902.  
  903.             d = DotProduct (thread->base->origin, p->plane.normal);
  904.             d -= p->plane.dist;
  905.             //MrE: vis-bug fix
  906.             //if (d > p->radius)
  907.             if (d > thread->base->radius)
  908.             {
  909.                 continue;
  910.             }
  911.             //MrE: vis-bug fix
  912.             //if (d < -p->radius)
  913.             else if (d < -thread->base->radius)
  914.             {
  915.                 stack.source = prevstack->source;
  916.             }
  917.             else    
  918.             {
  919.                 stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
  920.                 //FIXME: shouldn't we create a new source origin and radius for fast checks?
  921.                 if (!stack.source)
  922.                     continue;
  923.             }
  924.         }
  925. #else
  926.         stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
  927.         if (!stack.source)
  928.             continue;
  929. #endif
  930.  
  931.         if (!prevstack->pass)
  932.         {    // the second leaf can only be blocked if coplanar
  933.  
  934.             // mark the portal as visible
  935.             thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
  936.  
  937.             RecursivePassagePortalFlow (p, thread, &stack);
  938.             continue;
  939.         }
  940.  
  941. #ifdef SEPERATORCACHE
  942.         if (stack.numseperators[0])
  943.         {
  944.             for (n = 0; n < stack.numseperators[0]; n++)
  945.             {
  946.                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
  947.                 if (!stack.pass)
  948.                     break;        // target is not visible
  949.             }
  950.             if (n < stack.numseperators[0])
  951.                 continue;
  952.         }
  953.         else
  954.         {
  955.             stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
  956.         }
  957. #else
  958.         stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
  959. #endif
  960.         if (!stack.pass)
  961.             continue;
  962.  
  963. #ifdef SEPERATORCACHE
  964.         if (stack.numseperators[1])
  965.         {
  966.             for (n = 0; n < stack.numseperators[1]; n++)
  967.             {
  968.                 stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
  969.                 if (!stack.pass)
  970.                     break;        // target is not visible
  971.             }
  972.         }
  973.         else
  974.         {
  975.             stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
  976.         }
  977. #else
  978.         stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
  979. #endif
  980.         if (!stack.pass)
  981.             continue;
  982.  
  983.         // mark the portal as visible
  984.         thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));
  985.         // flow through it for real
  986.         RecursivePassagePortalFlow(p, thread, &stack);
  987.         //
  988.         stack.next = NULL;
  989.     }
  990. }
  991.  
  992. /*
  993. ===============
  994. PassagePortalFlow
  995. ===============
  996. */
  997. void PassagePortalFlow (int portalnum)
  998. {
  999.     threaddata_t    data;
  1000.     int                i;
  1001.     vportal_t        *p;
  1002. //    int                c_might, c_can;
  1003.  
  1004. #ifdef MREDEBUG
  1005.     _printf("\r%6d", portalnum);
  1006. #endif
  1007.  
  1008.     p = sorted_portals[portalnum];
  1009.  
  1010.     if (p->removed)
  1011.     {
  1012.         p->status = stat_done;
  1013.         return;
  1014.     }
  1015.  
  1016.     p->status = stat_working;
  1017.  
  1018. //    c_might = CountBits (p->portalflood, numportals*2);
  1019.  
  1020.     memset (&data, 0, sizeof(data));
  1021.     data.base = p;
  1022.     
  1023.     data.pstack_head.portal = p;
  1024.     data.pstack_head.source = p->winding;
  1025.     data.pstack_head.portalplane = p->plane;
  1026.     data.pstack_head.depth = 0;
  1027.     for (i=0 ; i<portallongs ; i++)
  1028.         ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];
  1029.  
  1030.     RecursivePassagePortalFlow (p, &data, &data.pstack_head);
  1031.  
  1032.     p->status = stat_done;
  1033.  
  1034.     /*
  1035.     c_can = CountBits (p->portalvis, numportals*2);
  1036.  
  1037.     qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
  1038.         (int)(p - portals),    c_might, c_can, data.c_chains);
  1039.     */
  1040. }
  1041.  
  1042. winding_t *PassageChopWinding (winding_t *in, winding_t *out, plane_t *split)
  1043. {
  1044.     vec_t    dists[128];
  1045.     int        sides[128];
  1046.     int        counts[3];
  1047.     vec_t    dot;
  1048.     int        i, j;
  1049.     vec_t    *p1, *p2;
  1050.     vec3_t    mid;
  1051.     winding_t    *neww;
  1052.  
  1053.     counts[0] = counts[1] = counts[2] = 0;
  1054.  
  1055.     // determine sides for each point
  1056.     for (i=0 ; i<in->numpoints ; i++)
  1057.     {
  1058.         dot = DotProduct (in->points[i], split->normal);
  1059.         dot -= split->dist;
  1060.         dists[i] = dot;
  1061.         if (dot > ON_EPSILON)
  1062.             sides[i] = SIDE_FRONT;
  1063.         else if (dot < -ON_EPSILON)
  1064.             sides[i] = SIDE_BACK;
  1065.         else
  1066.         {
  1067.             sides[i] = SIDE_ON;
  1068.         }
  1069.         counts[sides[i]]++;
  1070.     }
  1071.  
  1072.     if (!counts[1])
  1073.         return in;        // completely on front side
  1074.     
  1075.     if (!counts[0])
  1076.     {
  1077.         return NULL;
  1078.     }
  1079.  
  1080.     sides[i] = sides[0];
  1081.     dists[i] = dists[0];
  1082.     
  1083.     neww = out;
  1084.  
  1085.     neww->numpoints = 0;
  1086.  
  1087.     for (i=0 ; i<in->numpoints ; i++)
  1088.     {
  1089.         p1 = in->points[i];
  1090.  
  1091.         if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
  1092.         {
  1093.             return in;        // can't chop -- fall back to original
  1094.         }
  1095.  
  1096.         if (sides[i] == SIDE_ON)
  1097.         {
  1098.             VectorCopy (p1, neww->points[neww->numpoints]);
  1099.             neww->numpoints++;
  1100.             continue;
  1101.         }
  1102.     
  1103.         if (sides[i] == SIDE_FRONT)
  1104.         {
  1105.             VectorCopy (p1, neww->points[neww->numpoints]);
  1106.             neww->numpoints++;
  1107.         }
  1108.         
  1109.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  1110.             continue;
  1111.             
  1112.         if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
  1113.         {
  1114.             return in;        // can't chop -- fall back to original
  1115.         }
  1116.  
  1117.         // generate a split point
  1118.         p2 = in->points[(i+1)%in->numpoints];
  1119.         
  1120.         dot = dists[i] / (dists[i]-dists[i+1]);
  1121.         for (j=0 ; j<3 ; j++)
  1122.         {    // avoid round off error when possible
  1123.             if (split->normal[j] == 1)
  1124.                 mid[j] = split->dist;
  1125.             else if (split->normal[j] == -1)
  1126.                 mid[j] = -split->dist;
  1127.             else
  1128.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  1129.         }
  1130.             
  1131.         VectorCopy (mid, neww->points[neww->numpoints]);
  1132.         neww->numpoints++;
  1133.     }
  1134.     
  1135.     return neww;
  1136. }
  1137.  
  1138. /*
  1139. ===============
  1140. AddSeperators
  1141. ===============
  1142. */
  1143. int AddSeperators (winding_t *source, winding_t *pass, qboolean flipclip, plane_t *seperators, int maxseperators)
  1144. {
  1145.     int            i, j, k, l;
  1146.     plane_t        plane;
  1147.     vec3_t        v1, v2;
  1148.     float        d;
  1149.     vec_t        length;
  1150.     int            counts[3], numseperators;
  1151.     qboolean    fliptest;
  1152.  
  1153.     numseperators = 0;
  1154.     // check all combinations    
  1155.     for (i=0 ; i<source->numpoints ; i++)
  1156.     {
  1157.         l = (i+1)%source->numpoints;
  1158.         VectorSubtract (source->points[l] , source->points[i], v1);
  1159.  
  1160.         // find a vertex of pass that makes a plane that puts all of the
  1161.         // vertexes of pass on the front side and all of the vertexes of
  1162.         // source on the back side
  1163.         for (j=0 ; j<pass->numpoints ; j++)
  1164.         {
  1165.             VectorSubtract (pass->points[j], source->points[i], v2);
  1166.  
  1167.             plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
  1168.             plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
  1169.             plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
  1170.             
  1171.             // if points don't make a valid plane, skip it
  1172.  
  1173.             length = plane.normal[0] * plane.normal[0]
  1174.             + plane.normal[1] * plane.normal[1]
  1175.             + plane.normal[2] * plane.normal[2];
  1176.             
  1177.             if (length < ON_EPSILON)
  1178.                 continue;
  1179.  
  1180.             length = 1/sqrt(length);
  1181.             
  1182.             plane.normal[0] *= length;
  1183.             plane.normal[1] *= length;
  1184.             plane.normal[2] *= length;
  1185.  
  1186.             plane.dist = DotProduct (pass->points[j], plane.normal);
  1187.  
  1188.             //
  1189.             // find out which side of the generated seperating plane has the
  1190.             // source portal
  1191.             //
  1192. #if 1
  1193.             fliptest = qfalse;
  1194.             for (k=0 ; k<source->numpoints ; k++)
  1195.             {
  1196.                 if (k == i || k == l)
  1197.                     continue;
  1198.                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
  1199.                 if (d < -ON_EPSILON)
  1200.                 {    // source is on the negative side, so we want all
  1201.                     // pass and target on the positive side
  1202.                     fliptest = qfalse;
  1203.                     break;
  1204.                 }
  1205.                 else if (d > ON_EPSILON)
  1206.                 {    // source is on the positive side, so we want all
  1207.                     // pass and target on the negative side
  1208.                     fliptest = qtrue;
  1209.                     break;
  1210.                 }
  1211.             }
  1212.             if (k == source->numpoints)
  1213.                 continue;        // planar with source portal
  1214. #else
  1215.             fliptest = flipclip;
  1216. #endif
  1217.             //
  1218.             // flip the normal if the source portal is backwards
  1219.             //
  1220.             if (fliptest)
  1221.             {
  1222.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  1223.                 plane.dist = -plane.dist;
  1224.             }
  1225. #if 1
  1226.             //
  1227.             // if all of the pass portal points are now on the positive side,
  1228.             // this is the seperating plane
  1229.             //
  1230.             counts[0] = counts[1] = counts[2] = 0;
  1231.             for (k=0 ; k<pass->numpoints ; k++)
  1232.             {
  1233.                 if (k==j)
  1234.                     continue;
  1235.                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  1236.                 if (d < -ON_EPSILON)
  1237.                     break;
  1238.                 else if (d > ON_EPSILON)
  1239.                     counts[0]++;
  1240.                 else
  1241.                     counts[2]++;
  1242.             }
  1243.             if (k != pass->numpoints)
  1244.                 continue;    // points on negative side, not a seperating plane
  1245.                 
  1246.             if (!counts[0])
  1247.                 continue;    // planar with seperating plane
  1248. #else
  1249.             k = (j+1)%pass->numpoints;
  1250.             d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  1251.             if (d < -ON_EPSILON)
  1252.                 continue;
  1253.             k = (j+pass->numpoints-1)%pass->numpoints;
  1254.             d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  1255.             if (d < -ON_EPSILON)
  1256.                 continue;            
  1257. #endif
  1258.             //
  1259.             // flip the normal if we want the back side
  1260.             //
  1261.             if (flipclip)
  1262.             {
  1263.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  1264.                 plane.dist = -plane.dist;
  1265.             }
  1266.  
  1267.             if (numseperators >= maxseperators)
  1268.                 Error("max seperators");
  1269.             seperators[numseperators] = plane;
  1270.             numseperators++;
  1271.             break;
  1272.         }
  1273.     }
  1274.     return numseperators;
  1275. }
  1276.  
  1277. /*
  1278. ===============
  1279. CreatePassages
  1280.  
  1281. MrE: create passages from one portal to all the portals in the leaf the portal leads to
  1282.      every passage has a cansee bit string with all the portals that can be
  1283.      seen through the passage
  1284. ===============
  1285. */
  1286. void CreatePassages(int portalnum)
  1287. {
  1288.     int i, j, k, n, numseperators, numsee;
  1289.     float d;
  1290.     vportal_t *portal, *p, *target;
  1291.     leaf_t *leaf;
  1292.     passage_t    *passage, *lastpassage;
  1293.     plane_t seperators[MAX_SEPERATORS*2];
  1294.     winding_t *w;
  1295.     winding_t in, out, *res;
  1296.  
  1297. #ifdef MREDEBUG
  1298.     _printf("\r%6d", portalnum);
  1299. #endif
  1300.  
  1301.     portal = sorted_portals[portalnum];
  1302.  
  1303.     if (portal->removed)
  1304.     {
  1305.         portal->status = stat_done;
  1306.         return;
  1307.     }
  1308.  
  1309.     lastpassage = NULL;
  1310.     leaf = &leafs[portal->leaf];
  1311.     for (i = 0; i < leaf->numportals; i++)
  1312.     {
  1313.         target = leaf->portals[i];
  1314.         if (target->removed)
  1315.             continue;
  1316.  
  1317.         passage = (passage_t *) malloc(sizeof(passage_t) + portalbytes);
  1318.         memset(passage, 0, sizeof(passage_t) + portalbytes);
  1319.         numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
  1320.         numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);
  1321.  
  1322.         passage->next = NULL;
  1323.         if (lastpassage)
  1324.             lastpassage->next = passage;
  1325.         else
  1326.             portal->passages = passage;
  1327.         lastpassage = passage;
  1328.  
  1329.         numsee = 0;
  1330.         //create the passage->cansee
  1331.         for (j = 0; j < numportals * 2; j++)
  1332.         {
  1333.             p = &portals[j];
  1334.             if (p->removed)
  1335.                 continue;
  1336.             if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
  1337.                 continue;
  1338.             if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
  1339.                 continue;
  1340.             for (k = 0; k < numseperators; k++)
  1341.             {
  1342.                 //
  1343.                 d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
  1344.                 //if completely at the back of the seperator plane
  1345.                 if (d < -p->radius + ON_EPSILON)
  1346.                     break;
  1347.                 w = p->winding;
  1348.                 for (n = 0; n < w->numpoints; n++)
  1349.                 {
  1350.                     d = DotProduct (w->points[n], seperators[k].normal) - seperators[k].dist;
  1351.                     //if at the front of the seperator
  1352.                     if (d > ON_EPSILON)
  1353.                         break;
  1354.                 }
  1355.                 //if no points are at the front of the seperator
  1356.                 if (n >= w->numpoints)
  1357.                     break;
  1358.             }
  1359.             if (k < numseperators)
  1360.                 continue;
  1361.             memcpy(&in, p->winding, sizeof(winding_t));
  1362.             for (k = 0; k < numseperators; k++)
  1363.             {
  1364.                 res = PassageChopWinding(&in, &out, &seperators[k]);
  1365.                 if (res == &out)
  1366.                     memcpy(&in, &out, sizeof(winding_t));
  1367.                 if (res == NULL)
  1368.                     break;
  1369.             }
  1370.             if (k < numseperators)
  1371.                 continue;
  1372.             passage->cansee[j >> 3] |= (1<<(j&7));
  1373.             numsee++;
  1374.         }
  1375.     }
  1376. }
  1377.  
  1378. void PassageMemory(void)
  1379. {
  1380.     int i, j, totalmem, totalportals;
  1381.     vportal_t *portal, *target;
  1382.     leaf_t *leaf;
  1383.  
  1384.     totalmem = 0;
  1385.     totalportals = 0;
  1386.     for (i = 0; i < numportals; i++)
  1387.     {
  1388.         portal = sorted_portals[i];
  1389.         if (portal->removed)
  1390.             continue;
  1391.         leaf = &leafs[portal->leaf];
  1392.         for (j = 0; j < leaf->numportals; j++)
  1393.         {
  1394.             target = leaf->portals[j];
  1395.             if (target->removed)
  1396.                 continue;
  1397.             totalmem += sizeof(passage_t) + portalbytes;
  1398.             totalportals++;
  1399.         }
  1400.     }
  1401.     _printf("%7i average number of passages per leaf\n", totalportals / numportals);
  1402.     _printf("%7i MB required passage memory\n", totalmem >> 10 >> 10);
  1403. }
  1404.  
  1405. /*
  1406. ===============================================================================
  1407.  
  1408. This is a rough first-order aproximation that is used to trivially reject some
  1409. of the final calculations.
  1410.  
  1411.  
  1412. Calculates portalfront and portalflood bit vectors
  1413.  
  1414. thinking about:
  1415.  
  1416. typedef struct passage_s
  1417. {
  1418.     struct passage_s    *next;
  1419.     struct portal_s        *to;
  1420.     stryct sep_s        *seperators;
  1421.     byte                *mightsee;
  1422. } passage_t;
  1423.  
  1424. typedef struct portal_s
  1425. {
  1426.     struct passage_s    *passages;
  1427.     int                    leaf;        // leaf portal faces into
  1428. } portal_s;
  1429.  
  1430. leaf = portal->leaf
  1431. clear 
  1432. for all portals
  1433.  
  1434.  
  1435. calc portal visibility
  1436.     clear bit vector
  1437.     for all passages
  1438.         passage visibility
  1439.  
  1440.  
  1441. for a portal to be visible to a passage, it must be on the front of
  1442. all seperating planes, and both portals must be behind the new portal
  1443.  
  1444. ===============================================================================
  1445. */
  1446.  
  1447. int        c_flood, c_vis;
  1448.  
  1449.  
  1450. /*
  1451. ==================
  1452. SimpleFlood
  1453.  
  1454. ==================
  1455. */
  1456. void SimpleFlood (vportal_t *srcportal, int leafnum)
  1457. {
  1458.     int        i;
  1459.     leaf_t    *leaf;
  1460.     vportal_t    *p;
  1461.     int        pnum;
  1462.  
  1463.     leaf = &leafs[leafnum];
  1464.     
  1465.     for (i=0 ; i<leaf->numportals ; i++)
  1466.     {
  1467.         p = leaf->portals[i];
  1468.         if (p->removed)
  1469.             continue;
  1470.         pnum = p - portals;
  1471.         if ( ! (srcportal->portalfront[pnum>>3] & (1<<(pnum&7)) ) )
  1472.             continue;
  1473.  
  1474.         if (srcportal->portalflood[pnum>>3] & (1<<(pnum&7)) )
  1475.             continue;
  1476.  
  1477.         srcportal->portalflood[pnum>>3] |= (1<<(pnum&7));
  1478.         
  1479.         SimpleFlood (srcportal, p->leaf);
  1480.     }
  1481. }
  1482.  
  1483. /*
  1484. ==============
  1485. BasePortalVis
  1486. ==============
  1487. */
  1488. void BasePortalVis (int portalnum)
  1489. {
  1490.     int            j, k;
  1491.     vportal_t    *tp, *p;
  1492.     float        d;
  1493.     winding_t    *w;
  1494.  
  1495.     p = portals+portalnum;
  1496.  
  1497.     if (p->removed)
  1498.         return;
  1499.  
  1500.     p->portalfront = malloc (portalbytes);
  1501.     memset (p->portalfront, 0, portalbytes);
  1502.  
  1503.     p->portalflood = malloc (portalbytes);
  1504.     memset (p->portalflood, 0, portalbytes);
  1505.     
  1506.     p->portalvis = malloc (portalbytes);
  1507.     memset (p->portalvis, 0, portalbytes);
  1508.     
  1509.     for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
  1510.     {
  1511.         if (j == portalnum)
  1512.             continue;
  1513.         if (tp->removed)
  1514.             continue;
  1515.         /*
  1516.         if (farplanedist >= 0)
  1517.         {
  1518.             vec3_t dir;
  1519.             VectorSubtract(p->origin, tp->origin, dir);
  1520.             if (VectorLength(dir) > farplanedist - p->radius - tp->radius)
  1521.                 continue;
  1522.         }
  1523.         */
  1524.         w = tp->winding;
  1525.         for (k=0 ; k<w->numpoints ; k++)
  1526.         {
  1527.             d = DotProduct (w->points[k], p->plane.normal)
  1528.                 - p->plane.dist;
  1529.             if (d > ON_EPSILON)
  1530.                 break;
  1531.         }
  1532.         if (k == w->numpoints)
  1533.             continue;    // no points on front
  1534.  
  1535.         w = p->winding;
  1536.         for (k=0 ; k<w->numpoints ; k++)
  1537.         {
  1538.             d = DotProduct (w->points[k], tp->plane.normal)
  1539.                 - tp->plane.dist;
  1540.             if (d < -ON_EPSILON)
  1541.                 break;
  1542.         }
  1543.         if (k == w->numpoints)
  1544.             continue;    // no points on front
  1545.  
  1546.         p->portalfront[j>>3] |= (1<<(j&7));
  1547.     }
  1548.     
  1549.     SimpleFlood (p, p->leaf);
  1550.  
  1551.     p->nummightsee = CountBits (p->portalflood, numportals*2);
  1552. //    _printf ("portal %i: %i mightsee\n", portalnum, p->nummightsee);
  1553.     c_flood += p->nummightsee;
  1554. }
  1555.  
  1556.  
  1557.  
  1558.  
  1559.  
  1560. /*
  1561. ===============================================================================
  1562.  
  1563. This is a second order aproximation 
  1564.  
  1565. Calculates portalvis bit vector
  1566.  
  1567. WAAAAAAY too slow.
  1568.  
  1569. ===============================================================================
  1570. */
  1571.  
  1572. /*
  1573. ==================
  1574. RecursiveLeafBitFlow
  1575.  
  1576. ==================
  1577. */
  1578. void RecursiveLeafBitFlow (int leafnum, byte *mightsee, byte *cansee)
  1579. {
  1580.     vportal_t    *p;
  1581.     leaf_t         *leaf;
  1582.     int            i, j;
  1583.     long        more;
  1584.     int            pnum;
  1585.     byte        newmight[MAX_PORTALS/8];
  1586.  
  1587.     leaf = &leafs[leafnum];
  1588.     
  1589.     // check all portals for flowing into other leafs
  1590.     for (i=0 ; i<leaf->numportals ; i++)
  1591.     {
  1592.         p = leaf->portals[i];
  1593.         if (p->removed)
  1594.             continue;
  1595.         pnum = p - portals;
  1596.  
  1597.         // if some previous portal can't see it, skip
  1598.         if (! (mightsee[pnum>>3] & (1<<(pnum&7)) ) )
  1599.             continue;
  1600.  
  1601.         // if this portal can see some portals we mightsee, recurse
  1602.         more = 0;
  1603.         for (j=0 ; j<portallongs ; j++)
  1604.         {
  1605.             ((long *)newmight)[j] = ((long *)mightsee)[j] 
  1606.                 & ((long *)p->portalflood)[j];
  1607.             more |= ((long *)newmight)[j] & ~((long *)cansee)[j];
  1608.         }
  1609.  
  1610.         if (!more)
  1611.             continue;    // can't see anything new
  1612.  
  1613.         cansee[pnum>>3] |= (1<<(pnum&7));
  1614.  
  1615.         RecursiveLeafBitFlow (p->leaf, newmight, cansee);
  1616.     }    
  1617. }
  1618.  
  1619. /*
  1620. ==============
  1621. BetterPortalVis
  1622. ==============
  1623. */
  1624. void BetterPortalVis (int portalnum)
  1625. {
  1626.     vportal_t    *p;
  1627.  
  1628.     p = portals+portalnum;
  1629.  
  1630.     if (p->removed)
  1631.         return;
  1632.  
  1633.     RecursiveLeafBitFlow (p->leaf, p->portalflood, p->portalvis);
  1634.  
  1635.     // build leaf vis information
  1636.     p->nummightsee = CountBits (p->portalvis, numportals*2);
  1637.     c_vis += p->nummightsee;
  1638. }
  1639.  
  1640.  
  1641.