home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / portals.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  16.0 KB  |  823 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. int        c_active_portals;
  6. int        c_peak_portals;
  7. int        c_boundary;
  8. int        c_boundary_sides;
  9.  
  10. /*
  11. ===========
  12. AllocPortal
  13. ===========
  14. */
  15. portal_t *AllocPortal (void)
  16. {
  17.     portal_t    *p;
  18.     
  19.     if (numthreads == 1)
  20.         c_active_portals++;
  21.     if (c_active_portals > c_peak_portals)
  22.         c_peak_portals = c_active_portals;
  23.     
  24.     p = malloc (sizeof(portal_t));
  25.     memset (p, 0, sizeof(portal_t));
  26.     
  27.     return p;
  28. }
  29.  
  30. void FreePortal (portal_t *p)
  31. {
  32.     if (p->winding)
  33.         FreeWinding (p->winding);
  34.     if (numthreads == 1)
  35.         c_active_portals--;
  36.     free (p);
  37. }
  38.  
  39. //==============================================================
  40.  
  41. /*
  42. =============
  43. Portal_Passable
  44.  
  45. Returns true if the portal has non-opaque leafs on both sides
  46. =============
  47. */
  48. qboolean Portal_Passable(portal_t *p) {
  49.     if (!p->onnode) {
  50.         return qfalse;    // to global outsideleaf
  51.     }
  52.  
  53.     if (p->nodes[0]->planenum != PLANENUM_LEAF
  54.         || p->nodes[1]->planenum != PLANENUM_LEAF) {
  55.         Error ("Portal_EntityFlood: not a leaf");
  56.     }
  57.  
  58.     if ( !p->nodes[0]->opaque && !p->nodes[1]->opaque ) {
  59.         return qtrue;
  60.     }
  61.  
  62.     return qfalse;
  63. }
  64.  
  65.  
  66. //=============================================================================
  67.  
  68. int        c_tinyportals;
  69.  
  70. /*
  71. =============
  72. AddPortalToNodes
  73. =============
  74. */
  75. void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
  76. {
  77.     if (p->nodes[0] || p->nodes[1])
  78.         Error ("AddPortalToNode: allready included");
  79.  
  80.     p->nodes[0] = front;
  81.     p->next[0] = front->portals;
  82.     front->portals = p;
  83.     
  84.     p->nodes[1] = back;
  85.     p->next[1] = back->portals;
  86.     back->portals = p;
  87. }
  88.  
  89.  
  90. /*
  91. =============
  92. RemovePortalFromNode
  93. =============
  94. */
  95. void RemovePortalFromNode (portal_t *portal, node_t *l)
  96. {
  97.     portal_t    **pp, *t;
  98.     
  99. // remove reference to the current portal
  100.     pp = &l->portals;
  101.     while (1)
  102.     {
  103.         t = *pp;
  104.         if (!t)
  105.             Error ("RemovePortalFromNode: portal not in leaf");    
  106.  
  107.         if ( t == portal )
  108.             break;
  109.  
  110.         if (t->nodes[0] == l)
  111.             pp = &t->next[0];
  112.         else if (t->nodes[1] == l)
  113.             pp = &t->next[1];
  114.         else
  115.             Error ("RemovePortalFromNode: portal not bounding leaf");
  116.     }
  117.     
  118.     if (portal->nodes[0] == l)
  119.     {
  120.         *pp = portal->next[0];
  121.         portal->nodes[0] = NULL;
  122.     }
  123.     else if (portal->nodes[1] == l)
  124.     {
  125.         *pp = portal->next[1];    
  126.         portal->nodes[1] = NULL;
  127.     }
  128. }
  129.  
  130. //============================================================================
  131.  
  132. void PrintPortal (portal_t *p)
  133. {
  134.     int            i;
  135.     winding_t    *w;
  136.     
  137.     w = p->winding;
  138.     for (i=0 ; i<w->numpoints ; i++)
  139.         _printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
  140.         , w->p[i][1], w->p[i][2]);
  141. }
  142.  
  143. /*
  144. ================
  145. MakeHeadnodePortals
  146.  
  147. The created portals will face the global outside_node
  148. ================
  149. */
  150. #define    SIDESPACE    8
  151. void MakeHeadnodePortals (tree_t *tree)
  152. {
  153.     vec3_t        bounds[2];
  154.     int            i, j, n;
  155.     portal_t    *p, *portals[6];
  156.     plane_t        bplanes[6], *pl;
  157.     node_t *node;
  158.  
  159.     node = tree->headnode;
  160.  
  161. // pad with some space so there will never be null volume leafs
  162.     for (i=0 ; i<3 ; i++)
  163.     {
  164.         bounds[0][i] = tree->mins[i] - SIDESPACE;
  165.         bounds[1][i] = tree->maxs[i] + SIDESPACE;
  166.         if ( bounds[0][i] >= bounds[1][i] ) {
  167.             Error( "Backwards tree volume" );
  168.         }
  169.     }
  170.     
  171.     tree->outside_node.planenum = PLANENUM_LEAF;
  172.     tree->outside_node.brushlist = NULL;
  173.     tree->outside_node.portals = NULL;
  174.     tree->outside_node.opaque = qfalse;
  175.  
  176.     for (i=0 ; i<3 ; i++)
  177.         for (j=0 ; j<2 ; j++)
  178.         {
  179.             n = j*3 + i;
  180.  
  181.             p = AllocPortal ();
  182.             portals[n] = p;
  183.             
  184.             pl = &bplanes[n];
  185.             memset (pl, 0, sizeof(*pl));
  186.             if (j)
  187.             {
  188.                 pl->normal[i] = -1;
  189.                 pl->dist = -bounds[j][i];
  190.             }
  191.             else
  192.             {
  193.                 pl->normal[i] = 1;
  194.                 pl->dist = bounds[j][i];
  195.             }
  196.             p->plane = *pl;
  197.             p->winding = BaseWindingForPlane (pl->normal, pl->dist);
  198.             AddPortalToNodes (p, node, &tree->outside_node);
  199.         }
  200.         
  201. // clip the basewindings by all the other planes
  202.     for (i=0 ; i<6 ; i++)
  203.     {
  204.         for (j=0 ; j<6 ; j++)
  205.         {
  206.             if (j == i)
  207.                 continue;
  208.             ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);
  209.         }
  210.     }
  211. }
  212.  
  213. //===================================================
  214.  
  215.  
  216. /*
  217. ================
  218. BaseWindingForNode
  219. ================
  220. */
  221. #define    BASE_WINDING_EPSILON    0.001
  222. #define    SPLIT_WINDING_EPSILON    0.001
  223.  
  224. winding_t    *BaseWindingForNode (node_t *node)
  225. {
  226.     winding_t    *w;
  227.     node_t        *n;
  228.     plane_t        *plane;
  229.     vec3_t        normal;
  230.     vec_t        dist;
  231.  
  232.     w = BaseWindingForPlane (mapplanes[node->planenum].normal
  233.         , mapplanes[node->planenum].dist);
  234.  
  235.     // clip by all the parents
  236.     for (n=node->parent ; n && w ; )
  237.     {
  238.         plane = &mapplanes[n->planenum];
  239.  
  240.         if (n->children[0] == node)
  241.         {    // take front
  242.             ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);
  243.         }
  244.         else
  245.         {    // take back
  246.             VectorSubtract (vec3_origin, plane->normal, normal);
  247.             dist = -plane->dist;
  248.             ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);
  249.         }
  250.         node = n;
  251.         n = n->parent;
  252.     }
  253.  
  254.     return w;
  255. }
  256.  
  257. //============================================================
  258.  
  259. /*
  260. ==================
  261. MakeNodePortal
  262.  
  263. create the new portal by taking the full plane winding for the cutting plane
  264. and clipping it by all of parents of this node
  265. ==================
  266. */
  267. void MakeNodePortal (node_t *node)
  268. {
  269.     portal_t    *new_portal, *p;
  270.     winding_t    *w;
  271.     vec3_t        normal;
  272.     float        dist;
  273.     int            side;
  274.  
  275.     w = BaseWindingForNode (node);
  276.  
  277.     // clip the portal by all the other portals in the node
  278.     for (p = node->portals ; p && w; p = p->next[side])    
  279.     {
  280.         if (p->nodes[0] == node)
  281.         {
  282.             side = 0;
  283.             VectorCopy (p->plane.normal, normal);
  284.             dist = p->plane.dist;
  285.         }
  286.         else if (p->nodes[1] == node)
  287.         {
  288.             side = 1;
  289.             VectorSubtract (vec3_origin, p->plane.normal, normal);
  290.             dist = -p->plane.dist;
  291.         }
  292.         else
  293.             Error ("CutNodePortals_r: mislinked portal");
  294.  
  295.         ChopWindingInPlace (&w, normal, dist, CLIP_EPSILON);
  296.     }
  297.  
  298.     if (!w)
  299.     {
  300.         return;
  301.     }
  302.  
  303.     if (WindingIsTiny (w))
  304.     {
  305.         c_tinyportals++;
  306.         FreeWinding (w);
  307.         return;
  308.     }
  309.  
  310.     new_portal = AllocPortal ();
  311.     new_portal->plane = mapplanes[node->planenum];
  312.     new_portal->onnode = node;
  313.     new_portal->winding = w;
  314.     new_portal->hint = node->hint;
  315.     AddPortalToNodes (new_portal, node->children[0], node->children[1]);
  316. }
  317.  
  318.  
  319. /*
  320. ==============
  321. SplitNodePortals
  322.  
  323. Move or split the portals that bound node so that the node's
  324. children have portals instead of node.
  325. ==============
  326. */
  327. void SplitNodePortals (node_t *node)
  328. {
  329.     portal_t    *p, *next_portal, *new_portal;
  330.     node_t        *f, *b, *other_node;
  331.     int            side;
  332.     plane_t        *plane;
  333.     winding_t    *frontwinding, *backwinding;
  334.  
  335.     plane = &mapplanes[node->planenum];
  336.     f = node->children[0];
  337.     b = node->children[1];
  338.  
  339.     for (p = node->portals ; p ; p = next_portal)    
  340.     {
  341.         if (p->nodes[0] == node)
  342.             side = 0;
  343.         else if (p->nodes[1] == node)
  344.             side = 1;
  345.         else
  346.             Error ("SplitNodePortals: mislinked portal");
  347.         next_portal = p->next[side];
  348.  
  349.         other_node = p->nodes[!side];
  350.         RemovePortalFromNode (p, p->nodes[0]);
  351.         RemovePortalFromNode (p, p->nodes[1]);
  352.  
  353. //
  354. // cut the portal into two portals, one on each side of the cut plane
  355. //
  356.         ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
  357.             SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
  358.  
  359.         if (frontwinding && WindingIsTiny(frontwinding))
  360.         {
  361.             if (!f->tinyportals)
  362.                 VectorCopy(frontwinding->p[0], f->referencepoint);
  363.             f->tinyportals++;
  364.             if (!other_node->tinyportals)
  365.                 VectorCopy(frontwinding->p[0], other_node->referencepoint);
  366.             other_node->tinyportals++;
  367.  
  368.             FreeWinding (frontwinding);
  369.             frontwinding = NULL;
  370.             c_tinyportals++;
  371.         }
  372.  
  373.         if (backwinding && WindingIsTiny(backwinding))
  374.         {
  375.             if (!b->tinyportals)
  376.                 VectorCopy(backwinding->p[0], b->referencepoint);
  377.             b->tinyportals++;
  378.             if (!other_node->tinyportals)
  379.                 VectorCopy(backwinding->p[0], other_node->referencepoint);
  380.             other_node->tinyportals++;
  381.  
  382.             FreeWinding (backwinding);
  383.             backwinding = NULL;
  384.             c_tinyportals++;
  385.         }
  386.  
  387.         if (!frontwinding && !backwinding)
  388.         {    // tiny windings on both sides
  389.             continue;
  390.         }
  391.  
  392.         if (!frontwinding)
  393.         {
  394.             FreeWinding (backwinding);
  395.             if (side == 0)
  396.                 AddPortalToNodes (p, b, other_node);
  397.             else
  398.                 AddPortalToNodes (p, other_node, b);
  399.             continue;
  400.         }
  401.         if (!backwinding)
  402.         {
  403.             FreeWinding (frontwinding);
  404.             if (side == 0)
  405.                 AddPortalToNodes (p, f, other_node);
  406.             else
  407.                 AddPortalToNodes (p, other_node, f);
  408.             continue;
  409.         }
  410.         
  411.     // the winding is split
  412.         new_portal = AllocPortal ();
  413.         *new_portal = *p;
  414.         new_portal->winding = backwinding;
  415.         FreeWinding (p->winding);
  416.         p->winding = frontwinding;
  417.  
  418.         if (side == 0)
  419.         {
  420.             AddPortalToNodes (p, f, other_node);
  421.             AddPortalToNodes (new_portal, b, other_node);
  422.         }
  423.         else
  424.         {
  425.             AddPortalToNodes (p, other_node, f);
  426.             AddPortalToNodes (new_portal, other_node, b);
  427.         }
  428.     }
  429.  
  430.     node->portals = NULL;
  431. }
  432.  
  433.  
  434. /*
  435. ================
  436. CalcNodeBounds
  437. ================
  438. */
  439. void CalcNodeBounds (node_t *node)
  440. {
  441.     portal_t    *p;
  442.     int            s;
  443.     int            i;
  444.  
  445.     // calc mins/maxs for both leafs and nodes
  446.     ClearBounds (node->mins, node->maxs);
  447.     for (p = node->portals ; p ; p = p->next[s])
  448.     {
  449.         s = (p->nodes[1] == node);
  450.         for (i=0 ; i<p->winding->numpoints ; i++)
  451.             AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
  452.     }
  453. }
  454.  
  455. /*
  456. ==================
  457. MakeTreePortals_r
  458. ==================
  459. */
  460. void MakeTreePortals_r (node_t *node)
  461. {
  462.     int        i;
  463.  
  464.     CalcNodeBounds (node);
  465.     if (node->mins[0] >= node->maxs[0])
  466.     {
  467.         _printf ("WARNING: node without a volume\n");
  468.         _printf("node has %d tiny portals\n", node->tinyportals);
  469.         _printf("node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0],
  470.                                                             node->referencepoint[1],
  471.                                                             node->referencepoint[2]);
  472.     }
  473.  
  474.     for (i=0 ; i<3 ; i++)
  475.     {
  476.         if (node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD)
  477.         {
  478.             _printf ("WARNING: node with unbounded volume\n");
  479.             break;
  480.         }
  481.     }
  482.     if (node->planenum == PLANENUM_LEAF)
  483.         return;
  484.  
  485.     MakeNodePortal (node);
  486.     SplitNodePortals (node);
  487.  
  488.     MakeTreePortals_r (node->children[0]);
  489.     MakeTreePortals_r (node->children[1]);
  490. }
  491.  
  492. /*
  493. ==================
  494. MakeTreePortals
  495. ==================
  496. */
  497. void MakeTreePortals (tree_t *tree)
  498. {
  499.     qprintf( "----- MakeTreePortals -----\n");
  500.     MakeHeadnodePortals (tree);
  501.     MakeTreePortals_r (tree->headnode);
  502.     qprintf("%6d tiny portals\n", c_tinyportals);
  503. }
  504.  
  505. /*
  506. =========================================================
  507.  
  508. FLOOD ENTITIES
  509.  
  510. =========================================================
  511. */
  512.  
  513. int        c_floodedleafs;
  514.  
  515. /*
  516. =============
  517. FloodPortals_r
  518. =============
  519. */
  520. void FloodPortals_r (node_t *node, int dist) {
  521.     portal_t    *p;
  522.     int            s;
  523.  
  524.     if ( node->occupied ) {
  525.         return;
  526.     }
  527.  
  528.     if ( node->opaque ) {
  529.         return;
  530.     }
  531.  
  532.     c_floodedleafs++;
  533.     node->occupied = dist;
  534.  
  535.     for (p=node->portals ; p ; p = p->next[s]) {
  536.         s = (p->nodes[1] == node);
  537.         FloodPortals_r (p->nodes[!s], dist+1);
  538.     }
  539. }
  540.  
  541. /*
  542. =============
  543. PlaceOccupant
  544. =============
  545. */
  546. qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant)
  547. {
  548.     node_t    *node;
  549.     vec_t    d;
  550.     plane_t    *plane;
  551.  
  552.     // find the leaf to start in
  553.     node = headnode;
  554.     while (node->planenum != PLANENUM_LEAF)
  555.     {
  556.         plane = &mapplanes[node->planenum];
  557.         d = DotProduct (origin, plane->normal) - plane->dist;
  558.         if (d >= 0)
  559.             node = node->children[0];
  560.         else
  561.             node = node->children[1];
  562.     }
  563.  
  564.     if ( node->opaque )
  565.         return qfalse;
  566.     node->occupant = occupant;
  567.  
  568.     FloodPortals_r (node, 1);
  569.  
  570.     return qtrue;
  571. }
  572.  
  573. /*
  574. =============
  575. FloodEntities
  576.  
  577. Marks all nodes that can be reached by entites
  578. =============
  579. */
  580. qboolean FloodEntities( tree_t *tree ) {
  581.     int        i;
  582.     vec3_t    origin;
  583.     const char    *cl;
  584.     qboolean    inside;
  585.     node_t *headnode;
  586.  
  587.     headnode = tree->headnode;
  588.     qprintf ("--- FloodEntities ---\n");
  589.     inside = qfalse;
  590.     tree->outside_node.occupied = 0;
  591.  
  592.     c_floodedleafs = 0;
  593.     for (i=1 ; i<num_entities ; i++)
  594.     {
  595.         GetVectorForKey (&entities[i], "origin", origin);
  596.         if (VectorCompare(origin, vec3_origin))
  597.             continue;
  598.  
  599.         cl = ValueForKey (&entities[i], "classname");
  600.  
  601.         origin[2] += 1;    // so objects on floor are ok
  602.  
  603.         if (PlaceOccupant (headnode, origin, &entities[i]))
  604.             inside = qtrue;
  605.     }
  606.  
  607.     qprintf("%5i flooded leafs\n", c_floodedleafs );
  608.  
  609.     if (!inside)
  610.     {
  611.         qprintf ("no entities in open -- no filling\n");
  612.     }
  613.     else if (tree->outside_node.occupied)
  614.     {
  615.         qprintf ("entity reached from outside -- no filling\n");
  616.     }
  617.  
  618.     return (qboolean)(inside && !tree->outside_node.occupied);
  619. }
  620.  
  621. /*
  622. =========================================================
  623.  
  624. FLOOD AREAS
  625.  
  626. =========================================================
  627. */
  628.  
  629. int        c_areas;
  630.  
  631. /*
  632. =============
  633. FloodAreas_r
  634. =============
  635. */
  636. void FloodAreas_r (node_t *node)
  637. {
  638.     portal_t    *p;
  639.     int            s;
  640.     bspbrush_t    *b;
  641.  
  642.     if ( node->areaportal ) {
  643.         //
  644.         if ( node->area == -1 ) {
  645.             node->area = c_areas;
  646.         }
  647.         // this node is part of an area portal brush
  648.         b = node->brushlist->original;
  649.  
  650.         // if the current area has allready touched this
  651.         // portal, we are done
  652.         if (b->portalareas[0] == c_areas || b->portalareas[1] == c_areas)
  653.             return;
  654.  
  655.         // note the current area as bounding the portal
  656.         if (b->portalareas[1] != -1)
  657.         {
  658.             _printf ("WARNING: areaportal brush %i touches > 2 areas\n", b->brushnum );
  659.             return;
  660.         }
  661.         if (b->portalareas[0] != -1) {
  662.             b->portalareas[1] = c_areas;
  663.         } else {
  664.             b->portalareas[0] = c_areas;
  665.         }
  666.  
  667.         return;
  668.     }
  669.  
  670.     if (node->area != -1) {
  671.         return;        // allready got it
  672.     }
  673.     if ( node->cluster == -1 ) {
  674.         return;
  675.     }
  676.  
  677.     node->area = c_areas;
  678.  
  679.     for (p=node->portals ; p ; p = p->next[s])
  680.     {
  681.         s = (p->nodes[1] == node);
  682.  
  683.         if ( !Portal_Passable(p) )
  684.             continue;
  685.  
  686.         FloodAreas_r (p->nodes[!s]);
  687.     }
  688. }
  689.  
  690.  
  691. /*
  692. =============
  693. FindAreas_r
  694.  
  695. Just decend the tree, and for each node that hasn't had an
  696. area set, flood fill out from there
  697. =============
  698. */
  699. void FindAreas_r (node_t *node)
  700. {
  701.     if (node->planenum != PLANENUM_LEAF)
  702.     {
  703.         FindAreas_r (node->children[0]);
  704.         FindAreas_r (node->children[1]);
  705.         return;
  706.     }
  707.  
  708.     if (node->opaque)
  709.         return;
  710.  
  711.     if (node->areaportal)
  712.         return;
  713.  
  714.     if (node->area != -1)
  715.         return;        // allready got it
  716.  
  717.     FloodAreas_r (node);
  718.     c_areas++;
  719. }
  720.  
  721. /*
  722. =============
  723. CheckAreas_r
  724. =============
  725. */
  726. void CheckAreas_r (node_t *node)
  727. {
  728.     bspbrush_t    *b;
  729.  
  730.     if (node->planenum != PLANENUM_LEAF)
  731.     {
  732.         CheckAreas_r (node->children[0]);
  733.         CheckAreas_r (node->children[1]);
  734.         return;
  735.     }
  736.  
  737.     if (node->opaque)
  738.         return;
  739.  
  740.     if (node->cluster != -1)
  741.         if (node->area == -1)
  742.             _printf("WARNING: cluster %d has area set to -1\n", node->cluster);
  743.     if (node->areaportal)
  744.     {
  745.         b = node->brushlist->original;
  746.  
  747.         // check if the areaportal touches two areas
  748.         if (b->portalareas[0] == -1 || b->portalareas[1] == -1)
  749.             _printf ("WARNING: areaportal brush %i doesn't touch two areas\n", b->brushnum);
  750.     }
  751. }
  752.  
  753. /*
  754. =============
  755. FloodAreas
  756.  
  757. Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
  758. =============
  759. */
  760. void FloodAreas (tree_t *tree)
  761. {
  762.     qprintf ("--- FloodAreas ---\n");
  763.     FindAreas_r( tree->headnode );
  764.  
  765.     // check for areaportal brushes that don't touch two areas
  766.     CheckAreas_r( tree->headnode );
  767.  
  768.     qprintf ("%5i areas\n", c_areas);
  769. }
  770.  
  771. //======================================================
  772.  
  773. int        c_outside;
  774. int        c_inside;
  775. int        c_solid;
  776.  
  777. void FillOutside_r (node_t *node)
  778. {
  779.     if (node->planenum != PLANENUM_LEAF)
  780.     {
  781.         FillOutside_r (node->children[0]);
  782.         FillOutside_r (node->children[1]);
  783.         return;
  784.     }
  785.  
  786.     // anything not reachable by an entity
  787.     // can be filled away
  788.     if (!node->occupied) {
  789.         if ( !node->opaque ) {
  790.             c_outside++;
  791.             node->opaque = qtrue;
  792.         } else {
  793.             c_solid++;
  794.         }
  795.     } else {
  796.         c_inside++;
  797.     }
  798.  
  799. }
  800.  
  801. /*
  802. =============
  803. FillOutside
  804.  
  805. Fill all nodes that can't be reached by entities
  806. =============
  807. */
  808. void FillOutside (node_t *headnode)
  809. {
  810.     c_outside = 0;
  811.     c_inside = 0;
  812.     c_solid = 0;
  813.     qprintf ("--- FillOutside ---\n");
  814.     FillOutside_r (headnode);
  815.     qprintf ("%5i solid leafs\n", c_solid);
  816.     qprintf ("%5i leafs filled\n", c_outside);
  817.     qprintf ("%5i inside leafs\n", c_inside);
  818. }
  819.  
  820.  
  821. //==============================================================
  822.  
  823.