home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / vis / flow.c next >
C/C++ Source or Header  |  1996-09-12  |  10KB  |  476 lines
  1. #include "vis.h"
  2.  
  3. int        c_chains;
  4. int        c_portalskip, c_leafskip;
  5. int        c_vistest, c_mighttest;
  6.  
  7. int        active;
  8.  
  9. void CheckStack (leaf_t *leaf, threaddata_t *thread)
  10. {
  11.     pstack_t    *p;
  12.  
  13.     for (p=thread->pstack_head.next ; p ; p=p->next)
  14.         if (p->leaf == leaf)
  15.             Error ("CheckStack: leaf recursion");
  16. }
  17.  
  18.  
  19. /*
  20. ==============
  21. ClipToSeperators
  22.  
  23. Source, pass, and target are an ordering of portals.
  24.  
  25. Generates seperating planes canidates by taking two points from source and one
  26. point from pass, and clips target by them.
  27.  
  28. If target is totally clipped away, that portal can not be seen through.
  29.  
  30. Normal clip keeps target on the same side as pass, which is correct if the
  31. order goes source, pass, target.  If the order goes pass, source, target then
  32. flipclip should be set.
  33. ==============
  34. */
  35. winding_t    *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip)
  36. {
  37.     int            i, j, k, l;
  38.     plane_t        plane;
  39.     vec3_t        v1, v2;
  40.     float        d;
  41.     vec_t        length;
  42.     int            counts[3];
  43.     qboolean        fliptest;
  44.  
  45. // check all combinations    
  46.     for (i=0 ; i<source->numpoints ; i++)
  47.     {
  48.         l = (i+1)%source->numpoints;
  49.         VectorSubtract (source->points[l] , source->points[i], v1);
  50.  
  51.     // fing a vertex of pass that makes a plane that puts all of the
  52.     // vertexes of pass on the front side and all of the vertexes of
  53.     // source on the back side
  54.         for (j=0 ; j<pass->numpoints ; j++)
  55.         {
  56.             VectorSubtract (pass->points[j], source->points[i], v2);
  57.  
  58.             plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
  59.             plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
  60.             plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
  61.             
  62.         // if points don't make a valid plane, skip it
  63.  
  64.             length = plane.normal[0] * plane.normal[0]
  65.             + plane.normal[1] * plane.normal[1]
  66.             + plane.normal[2] * plane.normal[2];
  67.             
  68.             if (length < ON_EPSILON)
  69.                 continue;
  70.  
  71.             length = 1/sqrt(length);
  72.             
  73.             plane.normal[0] *= length;
  74.             plane.normal[1] *= length;
  75.             plane.normal[2] *= length;
  76.  
  77.             plane.dist = DotProduct (pass->points[j], plane.normal);
  78.  
  79.         //
  80.         // find out which side of the generated seperating plane has the
  81.         // source portal
  82.         //
  83.             fliptest = false;
  84.             for (k=0 ; k<source->numpoints ; k++)
  85.             {
  86.                 if (k == i || k == l)
  87.                     continue;
  88.                 d = DotProduct (source->points[k], plane.normal) - plane.dist;
  89.                 if (d < -ON_EPSILON)
  90.                 {    // source is on the negative side, so we want all
  91.                     // pass and target on the positive side
  92.                     fliptest = false;
  93.                     break;
  94.                 }
  95.                 else if (d > ON_EPSILON)
  96.                 {    // source is on the positive side, so we want all
  97.                     // pass and target on the negative side
  98.                     fliptest = true;
  99.                     break;
  100.                 }
  101.             }
  102.             if (k == source->numpoints)
  103.                 continue;        // planar with source portal
  104.  
  105.         //
  106.         // flip the normal if the source portal is backwards
  107.         //
  108.             if (fliptest)
  109.             {
  110.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  111.                 plane.dist = -plane.dist;
  112.             }
  113.             
  114.         //
  115.         // if all of the pass portal points are now on the positive side,
  116.         // this is the seperating plane
  117.         //
  118.             counts[0] = counts[1] = counts[2] = 0;
  119.             for (k=0 ; k<pass->numpoints ; k++)
  120.             {
  121.                 if (k==j)
  122.                     continue;
  123.                 d = DotProduct (pass->points[k], plane.normal) - plane.dist;
  124.                 if (d < -ON_EPSILON)
  125.                     break;
  126.                 else if (d > ON_EPSILON)
  127.                     counts[0]++;
  128.                 else
  129.                     counts[2]++;
  130.             }
  131.             if (k != pass->numpoints)
  132.                 continue;    // points on negative side, not a seperating plane
  133.                 
  134.             if (!counts[0])
  135.             {
  136.                 continue;    // planar with seperating plane
  137.             }
  138.         
  139.         //
  140.         // flip the normal if we want the back side
  141.         //
  142.             if (flipclip)
  143.             {
  144.                 VectorSubtract (vec3_origin, plane.normal, plane.normal);
  145.                 plane.dist = -plane.dist;
  146.             }
  147.             
  148.         //
  149.         // clip target by the seperating plane
  150.         //
  151.             target = ClipWinding (target, &plane, false);
  152.             if (!target)
  153.                 return NULL;        // target is not visible
  154.         }
  155.     }
  156.     
  157.     return target;
  158. }
  159.  
  160.  
  161.  
  162. /*
  163. ==================
  164. RecursiveLeafFlow
  165.  
  166. Flood fill through the leafs
  167. If src_portal is NULL, this is the originating leaf
  168. ==================
  169. */
  170. void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
  171. {
  172.     pstack_t    stack;
  173.     portal_t    *p;
  174.     plane_t        backplane;
  175.     winding_t    *source, *target;
  176.     leaf_t         *leaf;
  177.     int            i, j;
  178.     long        *test, *might, *vis;
  179.     qboolean        more;
  180.     
  181.     c_chains++;
  182.  
  183.     leaf = &leafs[leafnum];
  184.     CheckStack (leaf, thread);
  185.     
  186. // mark the leaf as visible
  187.     if (! (thread->leafvis[leafnum>>3] & (1<<(leafnum&7)) ) )
  188.     {
  189.         thread->leafvis[leafnum>>3] |= 1<<(leafnum&7);
  190.         thread->base->numcansee++;
  191.     }
  192.     
  193.     prevstack->next = &stack;
  194.     stack.next = NULL;
  195.     stack.leaf = leaf;
  196.     stack.portal = NULL;
  197.     stack.mightsee = malloc(bitbytes);
  198.     might = (long *)stack.mightsee;
  199.     vis = (long *)thread->leafvis;
  200.     
  201. // check all portals for flowing into other leafs    
  202.     for (i=0 ; i<leaf->numportals ; i++)
  203.     {
  204.         p = leaf->portals[i];
  205.  
  206.         if ( ! (prevstack->mightsee[p->leaf>>3] & (1<<(p->leaf&7)) ) )
  207.         {
  208.             c_leafskip++;
  209.             continue;    // can't possibly see it
  210.         }
  211.  
  212.     // if the portal can't see anything we haven't allready seen, skip it
  213.         if (p->status == stat_done)
  214.         {
  215.             c_vistest++;
  216.             test = (long *)p->visbits;
  217.         }
  218.         else
  219.         {
  220.             c_mighttest++;
  221.             test = (long *)p->mightsee;
  222.         }
  223.         more = false;
  224.         for (j=0 ; j<bitlongs ; j++)
  225.         {
  226.             might[j] = ((long *)prevstack->mightsee)[j] & test[j];
  227.             if (might[j] & ~vis[j])
  228.                 more = true;
  229.         }
  230.         
  231.         if (!more)
  232.         {    // can't see anything new
  233.             c_portalskip++;
  234.             continue;
  235.         }
  236.         
  237. // get plane of portal, point normal into the neighbor leaf
  238.         stack.portalplane = p->plane;
  239.         VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
  240.         backplane.dist = -p->plane.dist;
  241.             
  242.         if (VectorCompare (prevstack->portalplane.normal, backplane.normal) )
  243.             continue;    // can't go out a coplanar face
  244.     
  245.         c_portalcheck++;
  246.         
  247.         stack.portal = p;
  248.         stack.next = NULL;
  249.         
  250.         target = ClipWinding (p->winding, &thread->pstack_head.portalplane, false);
  251.         if (!target)
  252.             continue;
  253.             
  254.         if (!prevstack->pass)
  255.         {    // the second leaf can only be blocked if coplanar
  256.         
  257.             stack.source = prevstack->source;
  258.             stack.pass = target;
  259.             RecursiveLeafFlow (p->leaf, thread, &stack);
  260.             FreeWinding (target);
  261.             continue;
  262.         }
  263.  
  264.         target = ClipWinding (target, &prevstack->portalplane, false);
  265.         if (!target)
  266.             continue;
  267.         
  268.         source = CopyWinding (prevstack->source);
  269.  
  270.         source = ClipWinding (source, &backplane, false);
  271.         if (!source)
  272.         {
  273.             FreeWinding (target);
  274.             continue;
  275.         }
  276.  
  277.         c_portaltest++;
  278.  
  279.         if (testlevel > 0)
  280.         {
  281.             target = ClipToSeperators (source, prevstack->pass, target, false);
  282.             if (!target)
  283.             {
  284.                 FreeWinding (source);
  285.                 continue;
  286.             }
  287.         }
  288.         
  289.         if (testlevel > 1)
  290.         {
  291.             target = ClipToSeperators (prevstack->pass, source, target, true);
  292.             if (!target)
  293.             {
  294.                 FreeWinding (source);
  295.                 continue;
  296.             }
  297.         }
  298.         
  299.         if (testlevel > 2)
  300.         {
  301.             source = ClipToSeperators (target, prevstack->pass, source, false);
  302.             if (!source)
  303.             {
  304.                 FreeWinding (target);
  305.                 continue;
  306.             }
  307.         }
  308.         
  309.         if (testlevel > 3)
  310.         {
  311.             source = ClipToSeperators (prevstack->pass, target, source, true);
  312.             if (!source)
  313.             {
  314.                 FreeWinding (target);
  315.                 continue;
  316.             }
  317.         }
  318.  
  319.         stack.source = source;
  320.         stack.pass = target;
  321.  
  322.         c_portalpass++;
  323.     
  324.     // flow through it for real
  325.         RecursiveLeafFlow (p->leaf, thread, &stack);
  326.         
  327.         FreeWinding (source);
  328.         FreeWinding (target);
  329.     }
  330.     
  331.     free (stack.mightsee);
  332. }
  333.  
  334.  
  335. /*
  336. ===============
  337. PortalFlow
  338.  
  339. ===============
  340. */
  341. void PortalFlow (portal_t *p)
  342. {
  343.     threaddata_t    data;
  344.  
  345.     if (p->status != stat_working)
  346.         Error ("PortalFlow: reflowed");
  347.     p->status = stat_working;
  348.     
  349.     p->visbits = malloc (bitbytes);
  350.     memset (p->visbits, 0, bitbytes);
  351.  
  352.     memset (&data, 0, sizeof(data));
  353.     data.leafvis = p->visbits;
  354.     data.base = p;
  355.     
  356.     data.pstack_head.portal = p;
  357.     data.pstack_head.source = p->winding;
  358.     data.pstack_head.portalplane = p->plane;
  359.     data.pstack_head.mightsee = p->mightsee;
  360.         
  361.     RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);
  362.  
  363.     p->status = stat_done;
  364. }
  365.  
  366.  
  367. /*
  368. ===============================================================================
  369.  
  370. This is a rough first-order aproximation that is used to trivially reject some
  371. of the final calculations.
  372.  
  373. ===============================================================================
  374. */
  375.  
  376. byte    portalsee[MAX_PORTALS];
  377. int        c_leafsee, c_portalsee;
  378.  
  379. void SimpleFlood (portal_t *srcportal, int leafnum)
  380. {
  381.     int        i;
  382.     leaf_t    *leaf;
  383.     portal_t    *p;
  384.     
  385.     if (srcportal->mightsee[leafnum>>3] & (1<<(leafnum&7)) )
  386.         return;
  387.     srcportal->mightsee[leafnum>>3] |= (1<<(leafnum&7));
  388.     c_leafsee++;
  389.     
  390.     leaf = &leafs[leafnum];
  391.     
  392.     for (i=0 ; i<leaf->numportals ; i++)
  393.     {
  394.         p = leaf->portals[i];
  395.         if ( !portalsee[ p - portals ] )
  396.             continue;
  397.         SimpleFlood (srcportal, p->leaf);
  398.     }
  399. }
  400.  
  401.  
  402. /*
  403. ==============
  404. BasePortalVis
  405. ==============
  406. */
  407. void BasePortalVis (void)
  408. {
  409.     int            i, j, k;
  410.     portal_t    *tp, *p;
  411.     float        d;
  412.     winding_t    *w;
  413.     
  414.     for (i=0, p = portals ; i<numportals*2 ; i++, p++)
  415.     {
  416.         p->mightsee = malloc (bitbytes);
  417.         memset (p->mightsee, 0, bitbytes);
  418.         
  419.         c_portalsee = 0;
  420.         memset (portalsee, 0, numportals*2);
  421.  
  422.         for (j=0, tp = portals ; j<numportals*2 ; j++, tp++)
  423.         {
  424.             if (j == i)
  425.                 continue;
  426.             w = tp->winding;
  427.             for (k=0 ; k<w->numpoints ; k++)
  428.             {
  429.                 d = DotProduct (w->points[k], p->plane.normal)
  430.                     - p->plane.dist;
  431.                 if (d > ON_EPSILON)
  432.                     break;
  433.             }
  434.             if (k == w->numpoints)
  435.                 continue;    // no points on front
  436.                 
  437.             
  438.             w = p->winding;
  439.             for (k=0 ; k<w->numpoints ; k++)
  440.             {
  441.                 d = DotProduct (w->points[k], tp->plane.normal)
  442.                     - tp->plane.dist;
  443.                 if (d < -ON_EPSILON)
  444.                     break;
  445.             }
  446.             if (k == w->numpoints)
  447.                 continue;    // no points on front
  448.  
  449.             portalsee[j] = 1;        
  450.             c_portalsee++;
  451.             
  452.         }
  453.         
  454.         c_leafsee = 0;
  455.         SimpleFlood (p, p->leaf);
  456.         p->nummightsee = c_leafsee;
  457. //        printf ("portal:%4i  c_leafsee:%4i \n", i, c_leafsee);
  458.     
  459.     }
  460.  
  461. }
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.