home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 December / PCWKCD1296.iso / sharewar / quake106 / utils / qbsp / solidbsp.c < prev    next >
C/C++ Source or Header  |  1996-09-12  |  14KB  |  755 lines
  1. // solidbsp.c
  2.  
  3. #include "bsp5.h"
  4.  
  5. int        leaffaces;
  6. int        nodefaces;
  7. int        splitnodes;
  8.  
  9. int        c_solid, c_empty, c_water;
  10.  
  11. qboolean        usemidsplit;
  12.  
  13. //============================================================================
  14.  
  15. /*
  16. ==================
  17. FaceSide
  18.  
  19. For BSP hueristic
  20. ==================
  21. */
  22. int FaceSide (face_t *in, plane_t *split)
  23. {
  24.     int        frontcount, backcount;
  25.     vec_t    dot;
  26.     int        i;
  27.     vec_t    *p;
  28.     
  29.     
  30.     frontcount = backcount = 0;
  31.     
  32. // axial planes are fast
  33.     if (split->type < 3)
  34.         for (i=0, p = in->pts[0]+split->type ; i<in->numpoints ; i++, p+=3)
  35.         {
  36.             if (*p > split->dist + ON_EPSILON)
  37.             {
  38.                 if (backcount)
  39.                     return SIDE_ON;
  40.                 frontcount = 1;
  41.             }
  42.             else if (*p < split->dist - ON_EPSILON)
  43.             {
  44.                 if (frontcount)
  45.                     return SIDE_ON;
  46.                 backcount = 1;
  47.             }
  48.         }
  49.     else    
  50. // sloping planes take longer
  51.         for (i=0, p = in->pts[0] ; i<in->numpoints ; i++, p+=3)
  52.         {
  53.             dot = DotProduct (p, split->normal);
  54.             dot -= split->dist;
  55.             if (dot > ON_EPSILON)
  56.             {
  57.                 if (backcount)
  58.                     return SIDE_ON;
  59.                 frontcount = 1;
  60.             }
  61.             else if (dot < -ON_EPSILON)
  62.             {
  63.                 if (frontcount)
  64.                     return SIDE_ON;
  65.                 backcount = 1;
  66.             }
  67.         }
  68.     
  69.     if (!frontcount)
  70.         return SIDE_BACK;
  71.     if (!backcount)
  72.         return SIDE_FRONT;
  73.     
  74.     return SIDE_ON;
  75. }
  76.  
  77. /*
  78. ==================
  79. ChooseMidPlaneFromList
  80.  
  81. The clipping hull BSP doesn't worry about avoiding splits
  82. ==================
  83. */
  84. surface_t *ChooseMidPlaneFromList (surface_t *surfaces, vec3_t mins, vec3_t maxs)
  85. {
  86.     int            j,l;
  87.     surface_t    *p, *bestsurface;
  88.     vec_t        bestvalue, value, dist;
  89.     plane_t        *plane;
  90.  
  91. //
  92. // pick the plane that splits the least
  93. //
  94.     bestvalue = 6*8192*8192;
  95.     bestsurface = NULL;
  96.     
  97.     for (p=surfaces ; p ; p=p->next)
  98.     {
  99.         if (p->onnode)
  100.             continue;
  101.  
  102.         plane = &planes[p->planenum];
  103.         
  104.     // check for axis aligned surfaces
  105.         l = plane->type;
  106.         if (l > PLANE_Z)
  107.             continue;
  108.  
  109.     //
  110.     // calculate the split metric along axis l, smaller values are better
  111.     //
  112.         value = 0;
  113.  
  114.         dist = plane->dist * plane->normal[l];
  115.         for (j=0 ; j<3 ; j++)
  116.         {
  117.             if (j == l)
  118.             {
  119.                 value += (maxs[l]-dist)*(maxs[l]-dist);
  120.                 value += (dist-mins[l])*(dist-mins[l]);
  121.             }
  122.             else
  123.                 value += 2*(maxs[j]-mins[j])*(maxs[j]-mins[j]);
  124.         }
  125.         
  126.         if (value > bestvalue)
  127.             continue;
  128.         
  129.     //
  130.     // currently the best!
  131.     //
  132.         bestvalue = value;
  133.         bestsurface = p;
  134.     }
  135.  
  136.     if (!bestsurface)
  137.     {
  138.         for (p=surfaces ; p ; p=p->next)
  139.             if (!p->onnode)
  140.                 return p;        // first valid surface
  141.         Error ("ChooseMidPlaneFromList: no valid planes");
  142.     }
  143.         
  144.     return bestsurface;
  145. }
  146.  
  147.  
  148.  
  149. /*
  150. ==================
  151. ChoosePlaneFromList
  152.  
  153. The real BSP hueristic
  154. ==================
  155. */
  156. surface_t *ChoosePlaneFromList (surface_t *surfaces, vec3_t mins, vec3_t maxs, qboolean usefloors)
  157. {
  158.     int            j,k,l;
  159.     surface_t    *p, *p2, *bestsurface;
  160.     vec_t        bestvalue, bestdistribution, value, dist;
  161.     plane_t        *plane;
  162.     face_t        *f;
  163.     
  164. //
  165. // pick the plane that splits the least
  166. //
  167.     bestvalue = 99999;
  168.     bestsurface = NULL;
  169.     bestdistribution = 9e30;
  170.     
  171.     for (p=surfaces ; p ; p=p->next)
  172.     {
  173.         if (p->onnode)
  174.             continue;
  175.  
  176.         plane = &planes[p->planenum];
  177.         k = 0;
  178.  
  179.         if (!usefloors && plane->normal[2] == 1)
  180.             continue;
  181.  
  182.         for (p2=surfaces ; p2 ; p2=p2->next)
  183.         {
  184.             if (p2 == p)
  185.                 continue;
  186.             if (p2->onnode)
  187.                 continue;
  188.                 
  189.             for (f=p2->faces ; f ; f=f->next)
  190.             {
  191.                 if (FaceSide (f, plane) == SIDE_ON)
  192.                 {
  193.                     k++;
  194.                     if (k >= bestvalue)
  195.                         break;
  196.                 }
  197.                 
  198.             }
  199.             if (k > bestvalue)
  200.                 break;
  201.         }
  202.  
  203.         if (k > bestvalue)
  204.             continue;
  205.             
  206.     // if equal numbers, axial planes win, then decide on spatial subdivision
  207.     
  208.         if (k < bestvalue || (k == bestvalue && plane->type < PLANE_ANYX) )
  209.         {
  210.         // check for axis aligned surfaces
  211.             l = plane->type;
  212.     
  213.             if (l <= PLANE_Z)
  214.             {    // axial aligned                        
  215.             //
  216.             // calculate the split metric along axis l
  217.             //
  218.                 value = 0;
  219.         
  220.                 for (j=0 ; j<3 ; j++)
  221.                 {
  222.                     if (j == l)
  223.                     {
  224.                         dist = plane->dist * plane->normal[l];
  225.                         value += (maxs[l]-dist)*(maxs[l]-dist);
  226.                         value += (dist-mins[l])*(dist-mins[l]);
  227.                     }
  228.                     else
  229.                         value += 2*(maxs[j]-mins[j])*(maxs[j]-mins[j]);
  230.                 }
  231.                 
  232.                 if (value > bestdistribution && k == bestvalue)
  233.                     continue;
  234.                 bestdistribution = value;
  235.             }
  236.         //
  237.         // currently the best!
  238.         //
  239.             bestvalue = k;
  240.             bestsurface = p;
  241.         }
  242.  
  243.     }
  244.  
  245.  
  246.     return bestsurface;
  247. }
  248.  
  249.  
  250. /*
  251. ==================
  252. SelectPartition
  253.  
  254. Selects a surface from a linked list of surfaces to split the group on
  255. returns NULL if the surface list can not be divided any more (a leaf)
  256. ==================
  257. */
  258. surface_t *SelectPartition (surface_t *surfaces)
  259. {
  260.     int            i,j;
  261.     vec3_t        mins, maxs;
  262.     surface_t    *p, *bestsurface;
  263.  
  264. //
  265. // count onnode surfaces
  266. //
  267.     i = 0;
  268.     bestsurface = NULL;
  269.     for (p=surfaces ; p ; p=p->next)
  270.         if (!p->onnode)
  271.         {
  272.             i++;
  273.             bestsurface = p;
  274.         }
  275.         
  276.     if (i==0)
  277.         return NULL;
  278.         
  279.     if (i==1)
  280.         return bestsurface;    // this is a final split
  281.     
  282. //
  283. // calculate a bounding box of the entire surfaceset
  284. //
  285.     for (i=0 ; i<3 ; i++)
  286.     {
  287.         mins[i] = 99999;
  288.         maxs[i] = -99999;
  289.     }
  290.  
  291.     for (p=surfaces ; p ; p=p->next)
  292.         for (j=0 ; j<3 ; j++)
  293.         {
  294.             if (p->mins[j] < mins[j])
  295.                 mins[j] = p->mins[j];
  296.             if (p->maxs[j] > maxs[j])
  297.                 maxs[j] = p->maxs[j];
  298.         }
  299.  
  300.     if (usemidsplit) // do fast way for clipping hull
  301.         return ChooseMidPlaneFromList (surfaces, mins, maxs);
  302.         
  303. // do slow way to save poly splits for drawing hull
  304. #if 0
  305.     bestsurface = ChoosePlaneFromList (surfaces, mins, maxs, false);
  306.     if (bestsurface)    
  307.         return bestsurface;
  308. #endif        
  309.     return ChoosePlaneFromList (surfaces, mins, maxs, true);
  310. }
  311.  
  312. //============================================================================
  313.  
  314. /*
  315. =================
  316. CalcSurfaceInfo
  317.  
  318. Calculates the bounding box
  319. =================
  320. */
  321. void CalcSurfaceInfo (surface_t *surf)
  322. {
  323.     int        i,j;
  324.     face_t    *f;
  325.     
  326.     if (!surf->faces)
  327.         Error ("CalcSurfaceInfo: surface without a face");
  328.         
  329. //
  330. // calculate a bounding box
  331. //
  332.     for (i=0 ; i<3 ; i++)
  333.     {
  334.         surf->mins[i] = 99999;
  335.         surf->maxs[i] = -99999;
  336.     }
  337.  
  338.     for (f=surf->faces ; f ; f=f->next)
  339.     {
  340. if (f->contents[0] >= 0 || f->contents[1] >= 0)
  341. Error ("Bad contents");
  342.         for (i=0 ; i<f->numpoints ; i++)
  343.             for (j=0 ; j<3 ; j++)
  344.             {
  345.                 if (f->pts[i][j] < surf->mins[j])
  346.                     surf->mins[j] = f->pts[i][j];
  347.                 if (f->pts[i][j] > surf->maxs[j])
  348.                     surf->maxs[j] = f->pts[i][j];
  349.             }
  350.     }
  351. }
  352.  
  353.  
  354.  
  355. /*
  356. ==================
  357. DividePlane
  358. ==================
  359. */
  360. void DividePlane (surface_t *in, plane_t *split, surface_t **front, surface_t **back)
  361. {
  362.     face_t        *facet, *next;
  363.     face_t        *frontlist, *backlist;
  364.     face_t        *frontfrag, *backfrag;
  365.     surface_t    *news;
  366.     plane_t        *inplane;    
  367.     
  368.     inplane = &planes[in->planenum];
  369.     
  370. // parallel case is easy
  371.     if (VectorCompare (inplane->normal, split->normal))
  372.     {
  373. // check for exactly on node
  374.         if (inplane->dist == split->dist)
  375.         {    // divide the facets to the front and back sides
  376.             news = AllocSurface ();
  377.             *news = *in;
  378.  
  379.             facet=in->faces;
  380.             in->faces = NULL;
  381.             news->faces = NULL;
  382.             in->onnode = news->onnode = true;
  383.             
  384.             for ( ; facet ; facet=next)
  385.             {
  386.                 next = facet->next;
  387.                 if (facet->planeside == 1)
  388.                 {
  389.                     facet->next = news->faces;
  390.                     news->faces = facet;
  391.                 }
  392.                 else
  393.                 {
  394.                     facet->next = in->faces;
  395.                     in->faces = facet;
  396.                 }
  397.             }
  398.                 
  399.             if (in->faces)
  400.                 *front = in;
  401.             else
  402.                 *front = NULL;
  403.             if (news->faces)
  404.                 *back = news;
  405.             else
  406.                 *back = NULL;
  407.             return;
  408.         }
  409.         
  410.         if (inplane->dist > split->dist)
  411.         {
  412.             *front = in;
  413.             *back = NULL;
  414.         }
  415.         else
  416.         {
  417.             *front = NULL;
  418.             *back = in;
  419.         }
  420.         return;
  421.     }
  422.     
  423. // do a real split.  may still end up entirely on one side
  424. // OPTIMIZE: use bounding box for fast test
  425.     frontlist = NULL;
  426.     backlist = NULL;
  427.     
  428.     for (facet = in->faces ; facet ; facet = next)
  429.     {
  430.         next = facet->next;
  431.         SplitFace (facet, split, &frontfrag, &backfrag);
  432.         if (frontfrag)
  433.         {
  434.             frontfrag->next = frontlist;
  435.             frontlist = frontfrag;
  436.         }
  437.         if (backfrag)
  438.         {
  439.             backfrag->next = backlist;
  440.             backlist = backfrag;
  441.         }
  442.     }
  443.  
  444. // if nothing actually got split, just move the in plane
  445.     
  446.     if (frontlist == NULL)
  447.     {
  448.         *front = NULL;
  449.         *back = in;
  450.         in->faces = backlist;
  451.         return;
  452.     }
  453.  
  454.     if (backlist == NULL)
  455.     {
  456.         *front = in;
  457.         *back = NULL;
  458.         in->faces = frontlist;
  459.         return;
  460.     }
  461.     
  462.  
  463. // stuff got split, so allocate one new plane and reuse in
  464.     news = AllocSurface ();
  465.     *news = *in;
  466.     news->faces = backlist;
  467.     *back = news;
  468.     
  469.     in->faces = frontlist;
  470.     *front = in;
  471.     
  472. // recalc bboxes and flags
  473.     CalcSurfaceInfo (news);
  474.     CalcSurfaceInfo (in);    
  475. }
  476.  
  477. /*
  478. ==================
  479. DivideNodeBounds
  480. ==================
  481. */
  482. void DivideNodeBounds (node_t *node, plane_t *split)
  483. {
  484.     VectorCopy (node->mins, node->children[0]->mins);
  485.     VectorCopy (node->mins, node->children[1]->mins);
  486.     VectorCopy (node->maxs, node->children[0]->maxs);
  487.     VectorCopy (node->maxs, node->children[1]->maxs);
  488.  
  489. // OPTIMIZE: sloping cuts can give a better bbox than this...
  490.     if (split->type > 2)
  491.         return;
  492.  
  493.     node->children[0]->mins[split->type] =
  494.     node->children[1]->maxs[split->type] = split->dist;
  495. }
  496.  
  497. /*
  498. ==================
  499. LinkConvexFaces
  500.  
  501. Determines the contents of the leaf and creates the final list of
  502. original faces that have some fragment inside this leaf
  503. ==================
  504. */
  505. void LinkConvexFaces (surface_t *planelist, node_t *leafnode)
  506. {
  507.     face_t        *f, *next;
  508.     surface_t    *surf, *pnext;
  509.     int            i, count;
  510.     
  511.     leafnode->faces = NULL;
  512.     leafnode->contents = 0;
  513.     leafnode->planenum = -1;
  514.  
  515.     count = 0;
  516.     for ( surf = planelist ; surf ; surf = surf->next)
  517.     {
  518.         for (f = surf->faces ; f ; f=f->next)
  519.         {
  520.             count++;
  521.             if (!leafnode->contents)
  522.                 leafnode->contents = f->contents[0];
  523.             else if (leafnode->contents != f->contents[0])
  524.                 Error ("Mixed face contents in leafnode");
  525.         }
  526.     }
  527.  
  528.     if (!leafnode->contents)
  529.         leafnode->contents = CONTENTS_SOLID;
  530.         
  531.     switch (leafnode->contents)
  532.     {
  533.     case CONTENTS_EMPTY:
  534.         c_empty++;
  535.         break;
  536.     case CONTENTS_SOLID:
  537.         c_solid++;
  538.         break;
  539.     case CONTENTS_WATER:
  540.     case CONTENTS_SLIME:
  541.     case CONTENTS_LAVA:
  542.     case CONTENTS_SKY:
  543.         c_water++;
  544.         break;
  545.     default:
  546.         Error ("LinkConvexFaces: bad contents number");
  547.     }
  548.  
  549. //
  550. // write the list of faces, and free the originals
  551. //
  552.     leaffaces += count;
  553.     leafnode->markfaces = malloc(sizeof(face_t *)*(count+1));
  554.     i = 0;
  555.     for ( surf = planelist ; surf ; surf = pnext)
  556.     {
  557.         pnext = surf->next;
  558.         for (f = surf->faces ; f ; f=next)
  559.         {
  560.             next = f->next;
  561.             leafnode->markfaces[i] = f->original;
  562.             i++;
  563.             FreeFace (f);
  564.         }
  565.         FreeSurface (surf);
  566.     }
  567.     leafnode->markfaces[i] = NULL;    // sentinal
  568. }
  569.  
  570.  
  571. /*
  572. ==================
  573. LinkNodeFaces
  574.  
  575. Returns a duplicated list of all faces on surface
  576. ==================
  577. */
  578. face_t *LinkNodeFaces (surface_t *surface)
  579. {
  580.     face_t    *f, *new, **prevptr;
  581.     face_t    *list;
  582.     
  583.     list = NULL;
  584.     
  585.     
  586. // subdivide
  587.     prevptr = &surface->faces;
  588.     while (1)
  589.     {
  590.         f = *prevptr;
  591.         if (!f)
  592.             break;
  593.         SubdivideFace (f, prevptr);
  594.         f = *prevptr;
  595.         prevptr = &f->next;
  596.     }
  597.  
  598. // copy
  599.     for (f=surface->faces ; f ; f=f->next)
  600.     {
  601.         nodefaces++;
  602.         new = AllocFace ();
  603.         *new = *f;
  604.         f->original = new;
  605.         new->next = list;
  606.         list = new;
  607.     }
  608.  
  609.     return list;
  610. }
  611.  
  612.  
  613. /*
  614. ==================
  615. PartitionSurfaces
  616. ==================
  617. */
  618. void PartitionSurfaces (surface_t *surfaces, node_t *node)
  619. {
  620.     surface_t    *split, *p, *next;
  621.     surface_t    *frontlist, *backlist;
  622.     surface_t    *frontfrag, *backfrag;
  623.     plane_t        *splitplane;
  624.     
  625.     split = SelectPartition (surfaces);
  626.     if (!split)
  627.     {    // this is a leaf node
  628.         node->planenum = PLANENUM_LEAF;
  629.         LinkConvexFaces (surfaces, node);
  630.         return;
  631.     }
  632.         
  633.     splitnodes++;
  634.     node->faces = LinkNodeFaces (split);
  635.     node->children[0] = AllocNode ();
  636.     node->children[1] = AllocNode ();
  637.     node->planenum = split->planenum;
  638.  
  639.     splitplane = &planes[split->planenum];
  640.     
  641.     DivideNodeBounds (node, splitplane);
  642.  
  643.  
  644. //
  645. // multiple surfaces, so split all the polysurfaces into front and back lists
  646. //
  647.     frontlist = NULL;
  648.     backlist = NULL;
  649.     
  650.     for (p=surfaces ; p ; p=next)
  651.     {
  652.         next = p->next;
  653.         DividePlane (p, splitplane, &frontfrag, &backfrag);
  654.         if (frontfrag && backfrag)
  655.         {
  656.         // the plane was split, which may expose oportunities to merge
  657.         // adjacent faces into a single face
  658. //            MergePlaneFaces (frontfrag);
  659. //            MergePlaneFaces (backfrag);
  660.         }
  661.  
  662.         if (frontfrag)
  663.         {
  664.             if (!frontfrag->faces)
  665.                 Error ("surface with no faces");
  666.             frontfrag->next = frontlist;
  667.             frontlist = frontfrag;
  668.         }
  669.         if (backfrag)
  670.         {
  671.             if (!backfrag->faces)
  672.                 Error ("surface with no faces");
  673.             backfrag->next = backlist;
  674.             backlist = backfrag;
  675.         }
  676.     }
  677.  
  678.     PartitionSurfaces (frontlist, node->children[0]);
  679.     PartitionSurfaces (backlist, node->children[1]);
  680. }
  681.  
  682. /*
  683. ==================
  684. DrawSurface
  685. ==================
  686. */
  687. void DrawSurface (surface_t *surf)
  688. {
  689.     face_t    *f;
  690.     
  691.     for (f=surf->faces ; f ; f=f->next)
  692.         Draw_DrawFace (f);
  693. }
  694.  
  695. /*
  696. ==================
  697. DrawSurfaceList
  698. ==================
  699. */
  700. void DrawSurfaceList (surface_t *surf)
  701. {    
  702.     Draw_ClearWindow ();
  703.     while (surf)
  704.     {
  705.         DrawSurface (surf);
  706.         surf = surf->next;
  707.     }
  708. }
  709.  
  710. /*
  711. ==================
  712. SolidBSP
  713. ==================
  714. */
  715. node_t *SolidBSP (surface_t *surfhead, qboolean midsplit)
  716. {
  717.     int        i;
  718.     node_t    *headnode;
  719.     
  720.     qprintf ("----- SolidBSP -----\n");
  721.  
  722.     headnode = AllocNode ();
  723.     usemidsplit = midsplit;
  724.     
  725. //
  726. // calculate a bounding box for the entire model
  727. //
  728.     for (i=0 ; i<3 ; i++)
  729.     {
  730.         headnode->mins[i] = brushset->mins[i] - SIDESPACE;
  731.         headnode->maxs[i] = brushset->maxs[i] + SIDESPACE;
  732.     }
  733.     
  734. //
  735. // recursively partition everything
  736. //
  737.     Draw_ClearWindow ();
  738.     splitnodes = 0;
  739.     leaffaces = 0;
  740.     nodefaces = 0;
  741.     c_solid = c_empty = c_water = 0;
  742.  
  743.     PartitionSurfaces (surfhead, headnode);
  744.  
  745.     qprintf ("%5i split nodes\n", splitnodes);
  746.     qprintf ("%5i solid leafs\n", c_solid);
  747.     qprintf ("%5i empty leafs\n", c_empty);
  748.     qprintf ("%5i water leafs\n", c_water);    
  749.     qprintf ("%5i leaffaces\n",leaffaces);
  750.     qprintf ("%5i nodefaces\n", nodefaces);
  751.     
  752.     return headnode;
  753. }
  754.  
  755.