home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / bsp / qbsp3 / csg.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-18  |  11.4 KB  |  615 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4. /*
  5.  
  6. tag all brushes with original contents
  7. brushes may contain multiple contents
  8. there will be no brush overlap after csg phase
  9.  
  10.  
  11.  
  12.  
  13. each side has a count of the other sides it splits
  14.  
  15. the best split will be the one that minimizes the total split counts
  16. of all remaining sides
  17.  
  18. precalc side on plane table
  19.  
  20. evaluate split side
  21. {
  22. cost = 0
  23. for all sides
  24.     for all sides
  25.         get 
  26.         if side splits side and splitside is on same child
  27.             cost++;
  28. }
  29.  
  30.  
  31.   */
  32.  
  33. void SplitBrush2 (bspbrush_t *brush, int planenum,
  34.     bspbrush_t **front, bspbrush_t **back)
  35. {
  36.     SplitBrush (brush, planenum, front, back);
  37. #if 0
  38.     if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)
  39.         (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo;    // not -1
  40.     if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)
  41.         (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo;    // not -1
  42. #endif
  43. }
  44.  
  45. /*
  46. ===============
  47. SubtractBrush
  48.  
  49. Returns a list of brushes that remain after B is subtracted from A.
  50. May by empty if A is contained inside B.
  51.  
  52. The originals are undisturbed.
  53. ===============
  54. */
  55. bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
  56. {    // a - b = out (list)
  57.     int        i;
  58.     bspbrush_t    *front, *back;
  59.     bspbrush_t    *out, *in;
  60.  
  61.     in = a;
  62.     out = NULL;
  63.     for (i=0 ; i<b->numsides && in ; i++)
  64.     {
  65.         SplitBrush2 (in, b->sides[i].planenum, &front, &back);
  66.         if (in != a)
  67.             FreeBrush (in);
  68.         if (front)
  69.         {    // add to list
  70.             front->next = out;
  71.             out = front;
  72.         }
  73.         in = back;
  74.     }
  75.     if (in)
  76.         FreeBrush (in);
  77.     else
  78.     {    // didn't really intersect
  79.         FreeBrushList (out);
  80.         return a;
  81.     }
  82.     return out;
  83. }
  84.  
  85. /*
  86. ===============
  87. IntersectBrush
  88.  
  89. Returns a single brush made up by the intersection of the
  90. two provided brushes, or NULL if they are disjoint.
  91.  
  92. The originals are undisturbed.
  93. ===============
  94. */
  95. bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)
  96. {
  97.     int        i;
  98.     bspbrush_t    *front, *back;
  99.     bspbrush_t    *in;
  100.  
  101.     in = a;
  102.     for (i=0 ; i<b->numsides && in ; i++)
  103.     {
  104.         SplitBrush2 (in, b->sides[i].planenum, &front, &back);
  105.         if (in != a)
  106.             FreeBrush (in);
  107.         if (front)
  108.             FreeBrush (front);
  109.         in = back;
  110.     }
  111.  
  112.     if (in == a)
  113.         return NULL;
  114.  
  115.     in->next = NULL;
  116.     return in;
  117. }
  118.  
  119.  
  120. /*
  121. ===============
  122. BrushesDisjoint
  123.  
  124. Returns true if the two brushes definately do not intersect.
  125. There will be false negatives for some non-axial combinations.
  126. ===============
  127. */
  128. qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)
  129. {
  130.     int        i, j;
  131.  
  132.     // check bounding boxes
  133.     for (i=0 ; i<3 ; i++)
  134.         if (a->mins[i] >= b->maxs[i]
  135.         || a->maxs[i] <= b->mins[i])
  136.             return true;    // bounding boxes don't overlap
  137.  
  138.     // check for opposing planes
  139.     for (i=0 ; i<a->numsides ; i++)
  140.     {
  141.         for (j=0 ; j<b->numsides ; j++)
  142.         {
  143.             if (a->sides[i].planenum ==
  144.             (b->sides[j].planenum^1) )
  145.                 return true;    // opposite planes, so not touching
  146.         }
  147.     }
  148.  
  149.     return false;    // might intersect
  150. }
  151.  
  152. /*
  153. ===============
  154. IntersectionContents
  155.  
  156. Returns a content word for the intersection of two brushes.
  157. Some combinations will generate a combination (water + clip),
  158. but most will be the stronger of the two contents.
  159. ===============
  160. */
  161. int    IntersectionContents (int c1, int c2)
  162. {
  163.     int        out;
  164.  
  165.     out = c1 | c2;
  166.  
  167.     if (out & CONTENTS_SOLID)
  168.         out = CONTENTS_SOLID;
  169.  
  170.     return out;
  171. }
  172.  
  173.  
  174. int        minplanenums[3];
  175. int        maxplanenums[3];
  176.  
  177. /*
  178. ===============
  179. ClipBrushToBox
  180.  
  181. Any planes shared with the box edge will be set to no texinfo
  182. ===============
  183. */
  184. bspbrush_t    *ClipBrushToBox (bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)
  185. {
  186.     int        i, j;
  187.     bspbrush_t    *front,    *back;
  188.     int        p;
  189.  
  190.     for (j=0 ; j<2 ; j++)
  191.     {
  192.         if (brush->maxs[j] > clipmaxs[j])
  193.         {
  194.             SplitBrush (brush, maxplanenums[j], &front, &back);
  195.             if (front)
  196.                 FreeBrush (front);
  197.             brush = back;
  198.             if (!brush)
  199.                 return NULL;
  200.         }
  201.         if (brush->mins[j] < clipmins[j])
  202.         {
  203.             SplitBrush (brush, minplanenums[j], &front, &back);
  204.             if (back)
  205.                 FreeBrush (back);
  206.             brush = front;
  207.             if (!brush)
  208.                 return NULL;
  209.         }
  210.     }
  211.  
  212.     // remove any colinear faces
  213.  
  214.     for (i=0 ; i<brush->numsides ; i++)
  215.     {
  216.         p = brush->sides[i].planenum & ~1;
  217.         if (p == maxplanenums[0] || p == maxplanenums[1] 
  218.             || p == minplanenums[0] || p == minplanenums[1])
  219.         {
  220.             brush->sides[i].texinfo = TEXINFO_NODE;
  221.             brush->sides[i].visible = false;
  222.         }
  223.     }
  224.     return brush;
  225. }
  226.  
  227. /*
  228. ===============
  229. MakeBspBrushList 
  230. ===============
  231. */
  232. bspbrush_t *MakeBspBrushList (int startbrush, int endbrush,
  233.         vec3_t clipmins, vec3_t clipmaxs)
  234. {
  235.     mapbrush_t    *mb;
  236.     bspbrush_t    *brushlist, *newbrush;
  237.     int            i, j;
  238.     int            c_faces;
  239.     int            c_brushes;
  240.     int            numsides;
  241.     int            vis;
  242.     vec3_t        normal;
  243.     float        dist;
  244.  
  245.     for (i=0 ; i<2 ; i++)
  246.     {
  247.         VectorClear (normal);
  248.         normal[i] = 1;
  249.         dist = clipmaxs[i];
  250.         maxplanenums[i] = FindFloatPlane (normal, dist);
  251.         dist = clipmins[i];
  252.         minplanenums[i] = FindFloatPlane (normal, dist);
  253.     }
  254.  
  255.     brushlist = NULL;
  256.     c_faces = 0;
  257.     c_brushes = 0;
  258.  
  259.     for (i=startbrush ; i<endbrush ; i++)
  260.     {
  261.         mb = &mapbrushes[i];
  262.  
  263.         numsides = mb->numsides;
  264.         if (!numsides)
  265.             continue;
  266.         // make sure the brush has at least one face showing
  267.         vis = 0;
  268.         for (j=0 ; j<numsides ; j++)
  269.             if (mb->original_sides[j].visible && mb->original_sides[j].winding)
  270.                 vis++;
  271. #if 0
  272.         if (!vis)
  273.             continue;    // no faces at all
  274. #endif
  275.         // if the brush is outside the clip area, skip it
  276.         for (j=0 ; j<3 ; j++)
  277.             if (mb->mins[j] >= clipmaxs[j]
  278.             || mb->maxs[j] <= clipmins[j])
  279.             break;
  280.         if (j != 3)
  281.             continue;
  282.  
  283.         //
  284.         // make a copy of the brush
  285.         //
  286.         newbrush = AllocBrush (mb->numsides);
  287.         newbrush->original = mb;
  288.         newbrush->numsides = mb->numsides;
  289.         memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));
  290.         for (j=0 ; j<numsides ; j++)
  291.         {
  292.             if (newbrush->sides[j].winding)
  293.                 newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding);
  294.             if (newbrush->sides[j].surf & SURF_HINT)
  295.                 newbrush->sides[j].visible = true;    // hints are always visible
  296.         }
  297.         VectorCopy (mb->mins, newbrush->mins);
  298.         VectorCopy (mb->maxs, newbrush->maxs);
  299.  
  300.         //
  301.         // carve off anything outside the clip box
  302.         //
  303.         newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
  304.         if (!newbrush)
  305.             continue;
  306.  
  307.         c_faces += vis;
  308.         c_brushes++;
  309.  
  310.         newbrush->next = brushlist;
  311.         brushlist = newbrush;
  312.     }
  313.  
  314.     return brushlist;
  315. }
  316.  
  317. /*
  318. ===============
  319. AddBspBrushListToTail
  320. ===============
  321. */
  322. bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)
  323. {
  324.     bspbrush_t    *walk, *next;
  325.  
  326.     for (walk=list ; walk ; walk=next)
  327.     {    // add to end of list
  328.         next = walk->next;
  329.         walk->next = NULL;
  330.         tail->next = walk;
  331.         tail = walk;
  332.     }
  333.  
  334.     return tail;
  335. }
  336.  
  337. /*
  338. ===========
  339. CullList
  340.  
  341. Builds a new list that doesn't hold the given brush
  342. ===========
  343. */
  344. bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1)
  345. {
  346.     bspbrush_t    *newlist;
  347.     bspbrush_t    *next;
  348.  
  349.     newlist = NULL;
  350.  
  351.     for ( ; list ; list = next)
  352.     {
  353.         next = list->next;
  354.         if (list == skip1)
  355.         {
  356.             FreeBrush (list);
  357.             continue;
  358.         }
  359.         list->next = newlist;
  360.         newlist = list;
  361.     }
  362.     return newlist;
  363. }
  364.  
  365.  
  366. /*
  367. ==================
  368. WriteBrushMap
  369. ==================
  370. */
  371. void WriteBrushMap (char *name, bspbrush_t *list)
  372. {
  373.     FILE    *f;
  374.     side_t    *s;
  375.     int        i;
  376.     winding_t    *w;
  377.  
  378.     printf ("writing %s\n", name);
  379.     f = fopen (name, "wb");
  380.     if (!f)
  381.         Error ("Can't write %s\b", name);
  382.  
  383.     fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
  384.  
  385.     for ( ; list ; list=list->next )
  386.     {
  387.         fprintf (f, "{\n");
  388.         for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
  389.         {
  390.             w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
  391.  
  392.             fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
  393.             fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
  394.             fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
  395.  
  396.             fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
  397.             FreeWinding (w);
  398.         }
  399.         fprintf (f, "}\n");
  400.     }
  401.     fprintf (f, "}\n");
  402.  
  403.     fclose (f);
  404.  
  405. }
  406.  
  407. /*
  408. ==================
  409. BrushGE
  410.  
  411. Returns true if b1 is allowed to bite b2
  412. ==================
  413. */
  414. qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
  415. {
  416.     // detail brushes never bite structural brushes
  417.     if ( (b1->original->contents & CONTENTS_DETAIL) 
  418.         && !(b2->original->contents & CONTENTS_DETAIL) )
  419.         return false;
  420.     if (b1->original->contents & CONTENTS_SOLID)
  421.         return true;
  422.     return false;
  423. }
  424.  
  425. /*
  426. =================
  427. ChopBrushes
  428.  
  429. Carves any intersecting solid brushes into the minimum number
  430. of non-intersecting brushes. 
  431. =================
  432. */
  433. bspbrush_t *ChopBrushes (bspbrush_t *head)
  434. {
  435.     bspbrush_t    *b1, *b2, *next;
  436.     bspbrush_t    *tail;
  437.     bspbrush_t    *keep;
  438.     bspbrush_t    *sub, *sub2;
  439.     int            c1, c2;
  440.  
  441.     qprintf ("---- ChopBrushes ----\n");
  442.     qprintf ("original brushes: %i\n", CountBrushList (head));
  443.  
  444. #if 0
  445.     if (startbrush == 0)
  446.         WriteBrushList ("before.gl", head, false);
  447. #endif
  448.     keep = NULL;
  449.  
  450. newlist:
  451.     // find tail
  452.     if (!head)
  453.         return NULL;
  454.     for (tail=head ; tail->next ; tail=tail->next)
  455.     ;
  456.  
  457.     for (b1=head ; b1 ; b1=next)
  458.     {
  459.         next = b1->next;
  460.         for (b2=b1->next ; b2 ; b2 = b2->next)
  461.         {
  462.             if (BrushesDisjoint (b1, b2))
  463.                 continue;
  464.  
  465.             sub = NULL;
  466.             sub2 = NULL;
  467.             c1 = 999999;
  468.             c2 = 999999;
  469.  
  470.             if ( BrushGE (b2, b1) )
  471.             {
  472.                 sub = SubtractBrush (b1, b2);
  473.                 if (sub == b1)
  474.                     continue;        // didn't really intersect
  475.                 if (!sub)
  476.                 {    // b1 is swallowed by b2
  477.                     head = CullList (b1, b1);
  478.                     goto newlist;
  479.                 }
  480.                 c1 = CountBrushList (sub);
  481.             }
  482.  
  483.             if ( BrushGE (b1, b2) )
  484.             {
  485.                 sub2 = SubtractBrush (b2, b1);
  486.                 if (sub2 == b2)
  487.                     continue;        // didn't really intersect
  488.                 if (!sub2)
  489.                 {    // b2 is swallowed by b1
  490.                     FreeBrushList (sub);
  491.                     head = CullList (b1, b2);
  492.                     goto newlist;
  493.                 }
  494.                 c2 = CountBrushList (sub2);
  495.             }
  496.  
  497.             if (!sub && !sub2)
  498.                 continue;        // neither one can bite
  499.  
  500.             // only accept if it didn't fragment
  501.             // (commening this out allows full fragmentation)
  502.             if (c1 > 1 && c2 > 1)
  503.             {
  504.                 if (sub2)
  505.                     FreeBrushList (sub2);
  506.                 if (sub)
  507.                     FreeBrushList (sub);
  508.                 continue;
  509.             }
  510.  
  511.             if (c1 < c2)
  512.             {
  513.                 if (sub2)
  514.                     FreeBrushList (sub2);
  515.                 tail = AddBrushListToTail (sub, tail);
  516.                 head = CullList (b1, b1);
  517.                 goto newlist;
  518.             }
  519.             else
  520.             {
  521.                 if (sub)
  522.                     FreeBrushList (sub);
  523.                 tail = AddBrushListToTail (sub2, tail);
  524.                 head = CullList (b1, b2);
  525.                 goto newlist;
  526.             }
  527.         }
  528.  
  529.         if (!b2)
  530.         {    // b1 is no longer intersecting anything, so keep it
  531.             b1->next = keep;
  532.             keep = b1;
  533.         }
  534.     }
  535.  
  536.     qprintf ("output brushes: %i\n", CountBrushList (keep));
  537. #if 0
  538.     {
  539.         WriteBrushList ("after.gl", keep, false);
  540.         WriteBrushMap ("after.map", keep);
  541.     }
  542. #endif
  543.     return keep;
  544. }
  545.  
  546.  
  547. /*
  548. =================
  549. InitialBrushList
  550. =================
  551. */
  552. bspbrush_t *InitialBrushList (bspbrush_t *list)
  553. {
  554.     bspbrush_t *b;
  555.     bspbrush_t    *out, *newb;
  556.     int            i;
  557.  
  558.     // only return brushes that have visible faces
  559.     out = NULL;
  560.     for (b=list ; b ; b=b->next)
  561.     {
  562. #if 0
  563.         for (i=0 ; i<b->numsides ; i++)
  564.             if (b->sides[i].visible)
  565.                 break;
  566.         if (i == b->numsides)
  567.             continue;
  568. #endif
  569.         newb = CopyBrush (b);
  570.         newb->next = out;
  571.         out = newb;
  572.  
  573.         // clear visible, so it must be set by MarkVisibleFaces_r
  574.         // to be used in the optimized list
  575.         for (i=0 ; i<b->numsides ; i++)
  576.         {
  577.             newb->sides[i].original = &b->sides[i];
  578. //            newb->sides[i].visible = true;
  579.             b->sides[i].visible = false;
  580.         }
  581.     }
  582.  
  583.     return out;
  584. }
  585.  
  586. /*
  587. =================
  588. OptimizedBrushList
  589. =================
  590. */
  591. bspbrush_t *OptimizedBrushList (bspbrush_t *list)
  592. {
  593.     bspbrush_t *b;
  594.     bspbrush_t    *out, *newb;
  595.     int            i;
  596.  
  597.     // only return brushes that have visible faces
  598.     out = NULL;
  599.     for (b=list ; b ; b=b->next)
  600.     {
  601.         for (i=0 ; i<b->numsides ; i++)
  602.             if (b->sides[i].visible)
  603.                 break;
  604.         if (i == b->numsides)
  605.             continue;
  606.         newb = CopyBrush (b);
  607.         newb->next = out;
  608.         out = newb;
  609.     }
  610.  
  611. //    WriteBrushList ("vis.gl", out, true);
  612.  
  613.     return out;
  614. }
  615.