home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / CSG.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  16.4 KB  |  661 lines
  1.  
  2. #include "stdafx.h"
  3. #include "qe3.h"
  4. #include "winding.h"
  5.  
  6.  
  7. /*
  8. =============
  9. CSG_MakeHollow
  10. =============
  11. */
  12.  
  13. void Brush_Scale(brush_t* b)
  14. {
  15.   for (face_t* f = b->brush_faces ; f ; f=f->next)
  16.   {
  17.       for (int i=0 ; i<3 ; i++)
  18.     {
  19.       VectorScale (f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i]);
  20.     }
  21.   }
  22. }
  23.  
  24. void CSG_MakeHollow (void)
  25. {
  26.     brush_t        *b, *front, *back, *next;
  27.     face_t        *f;
  28.     face_t        split;
  29.     vec3_t        move;
  30.     int            i;
  31.  
  32.     for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
  33.     {
  34.         next = b->next;
  35.  
  36.     if (b->owner->eclass->fixedsize || b->patchBrush || b->hiddenBrush)
  37.           continue;
  38.  
  39.         for (f = b->brush_faces ; f ; f=f->next)
  40.         {
  41.             split = *f;
  42.             VectorScale (f->plane.normal, g_qeglobals.d_gridsize, move);
  43.             for (i=0 ; i<3 ; i++)
  44.                 VectorSubtract (split.planepts[i], move, split.planepts[i]);
  45.  
  46.             Brush_SplitBrushByFace (b, &split, &front, &back);
  47.             if (back)
  48.                 Brush_Free (back);
  49.             if (front)
  50.                 Brush_AddToList (front, &selected_brushes);
  51.         }
  52.         Brush_Free (b);
  53.     }
  54.     Sys_UpdateWindows (W_ALL);
  55. }
  56.  
  57. /*
  58. =============
  59. Brush_Merge
  60.  
  61.  Returns a new brush that is created by merging brush1 and brush2.
  62.  May return NULL if brush1 and brush2 do not create a convex brush when merged.
  63.  The input brushes brush1 and brush2 stay intact.
  64.  
  65.  if onlyshape is true then the merge is allowed based on the shape only
  66.  otherwise the texture/shader references of faces in the same plane have to
  67.  be the same as well.
  68. =============
  69. */
  70. brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)
  71. {
  72.     int i, shared;
  73.     brush_t *newbrush;
  74.     face_t *face1, *face2, *newface, *f;
  75.  
  76.     // check for bounding box overlapp
  77.     for (i = 0; i < 3; i++)
  78.     {
  79.         if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
  80.                 || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)
  81.         {
  82.             // never merge if the brushes overlap
  83.             return NULL;
  84.         }
  85.     }
  86.     //
  87.     shared = 0;
  88.     // check if the new brush would be convex... flipped planes make a brush non-convex
  89.     for (face1 = brush1->brush_faces; face1; face1 = face1->next)
  90.     {
  91.         // don't check the faces of brush 1 and 2 touching each other
  92.         for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  93.         {
  94.             if (Plane_Equal(&face1->plane, &face2->plane, true))
  95.             {
  96.                 shared++;
  97.                 // there may only be ONE shared side
  98.                 if (shared > 1)
  99.                     return NULL;
  100.                 break;
  101.             }
  102.         }
  103.         // if this face plane is shared
  104.         if (face2) continue;
  105.         //
  106.         for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  107.         {
  108.             // don't check the faces of brush 1 and 2 touching each other
  109.             for (f = brush1->brush_faces; f; f = f->next)
  110.             {
  111.                 if (Plane_Equal(&face2->plane, &f->plane, true)) break;
  112.             }
  113.             if (f)
  114.                 continue;
  115.             //
  116.             if (Plane_Equal(&face1->plane, &face2->plane, false))
  117.             {
  118.                 //if the texture/shader references should be the same but are not
  119.                 if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0) return NULL;
  120.                 continue;
  121.             }
  122.             //
  123.             if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
  124.                                     face1->plane.normal, face2->plane.normal,
  125.                                     face1->plane.dist, face2->plane.dist))
  126.             {
  127.                 return NULL;
  128.             } //end if
  129.         } //end for
  130.     } //end for
  131.     //
  132.     newbrush = Brush_Alloc();
  133.     //
  134.     for (face1 = brush1->brush_faces; face1; face1 = face1->next)
  135.     {
  136.         // don't add the faces of brush 1 and 2 touching each other
  137.         for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  138.         {
  139.             if (Plane_Equal(&face1->plane, &face2->plane, true))
  140.                 break;
  141.         }
  142.         if (face2)
  143.             continue;
  144.         // don't add faces with the same plane twice
  145.         for (f = newbrush->brush_faces; f; f = f->next)
  146.         {
  147.             if (Plane_Equal(&face1->plane, &f->plane, false))
  148.                 break;
  149.             if (Plane_Equal(&face1->plane, &f->plane, true))
  150.                 break;
  151.         }
  152.         if (f)
  153.             continue;
  154.         //
  155.         newface = Face_Alloc();
  156.         newface->texdef = face1->texdef;
  157.         VectorCopy(face1->planepts[0], newface->planepts[0]);
  158.         VectorCopy(face1->planepts[1], newface->planepts[1]);
  159.         VectorCopy(face1->planepts[2], newface->planepts[2]);
  160.         newface->plane = face1->plane;
  161.         newface->next = newbrush->brush_faces;
  162.         newbrush->brush_faces = newface;
  163.     }
  164.     //
  165.     for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  166.     {
  167.         // don't add the faces of brush 1 and 2 touching each other
  168.         for (face1 = brush1->brush_faces; face1; face1 = face1->next)
  169.         {
  170.             if (Plane_Equal(&face2->plane, &face1->plane, true))
  171.                 break;
  172.         }
  173.         if (face1)
  174.             continue;
  175.         // don't add faces with the same plane twice
  176.         for (f = newbrush->brush_faces; f; f = f->next)
  177.         {
  178.             if (Plane_Equal(&face2->plane, &f->plane, false))
  179.                 break;
  180.             if (Plane_Equal(&face2->plane, &f->plane, true))
  181.                 break;
  182.         }
  183.         if (f)
  184.             continue;
  185.         //
  186.         newface = Face_Alloc();
  187.         newface->texdef = face2->texdef;
  188.         VectorCopy(face2->planepts[0], newface->planepts[0]);
  189.         VectorCopy(face2->planepts[1], newface->planepts[1]);
  190.         VectorCopy(face2->planepts[2], newface->planepts[2]);
  191.         newface->plane = face2->plane;
  192.         newface->next = newbrush->brush_faces;
  193.         newbrush->brush_faces = newface;
  194.     }
  195.     // link the new brush to an entity
  196.     Entity_LinkBrush (brush1->owner, newbrush);
  197.     // build windings for the faces
  198.     Brush_BuildWindings( newbrush, false);
  199.     return newbrush;
  200. }
  201.  
  202. /*
  203. =============
  204. Brush_MergeListPairs
  205.  
  206.   Returns a list with merged brushes.
  207.   Tries to merge brushes pair wise.
  208.   The input list is destroyed.
  209.   Input and output should be a single linked list using .next
  210. =============
  211. */
  212. brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)
  213. {
  214.     int nummerges, merged;
  215.     brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
  216.     brush_t *lastb2;
  217.  
  218.     if (!brushlist) return NULL;
  219.  
  220.     nummerges = 0;
  221.     do
  222.     {
  223.         for (tail = brushlist; tail; tail = tail->next)
  224.         {
  225.             if (!tail->next) break;
  226.         }
  227.         merged = 0;
  228.         newbrushlist = NULL;
  229.         for (b1 = brushlist; b1; b1 = brushlist)
  230.         {
  231.             lastb2 = b1;
  232.             for (b2 = b1->next; b2; b2 = b2->next)
  233.             {
  234.                 newbrush = Brush_Merge(b1, b2, onlyshape);
  235.                 if (newbrush)
  236.                 {
  237.                     tail->next = newbrush;
  238.                     lastb2->next = b2->next;
  239.                     brushlist = brushlist->next;
  240.                     b1->next = b1->prev = NULL;
  241.                     b2->next = b2->prev = NULL;
  242.                     Brush_Free(b1);
  243.                     Brush_Free(b2);
  244.                     for (tail = brushlist; tail; tail = tail->next)
  245.                     {
  246.                         if (!tail->next) break;
  247.                     } //end for
  248.                     merged++;
  249.                     nummerges++;
  250.                     break;
  251.                 }
  252.                 lastb2 = b2;
  253.             }
  254.             //if b1 can't be merged with any of the other brushes
  255.             if (!b2)
  256.             {
  257.                 brushlist = brushlist->next;
  258.                 //keep b1
  259.                 b1->next = newbrushlist;
  260.                 newbrushlist = b1;
  261.             }
  262.         }
  263.         brushlist = newbrushlist;
  264.     } while(merged);
  265.     return newbrushlist;
  266. }
  267.  
  268. /*
  269. =============
  270. Brush_MergeList
  271.  
  272.  Tries to merge all brushes in the list into one new brush.
  273.  The input brush list stays intact.
  274.  Returns NULL if no merged brush can be created.
  275.  To create a new brush the brushes in the list may not overlap and
  276.  the outer faces of the brushes together should make a new convex brush.
  277.  
  278.  if onlyshape is true then the merge is allowed based on the shape only
  279.  otherwise the texture/shader references of faces in the same plane have to
  280.  be the same as well.
  281. =============
  282. */
  283. brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)
  284. {
  285.     brush_t *brush1, *brush2, *brush3, *newbrush;
  286.     face_t *face1, *face2, *face3, *newface, *f;
  287.  
  288.     if (!brushlist) return NULL;
  289.     for (brush1 = brushlist; brush1; brush1 = brush1->next)
  290.     {
  291.         // check if the new brush would be convex... flipped planes make a brush concave
  292.         for (face1 = brush1->brush_faces; face1; face1 = face1->next)
  293.         {
  294.             // don't check face1 if it touches another brush
  295.             for (brush2 = brushlist; brush2; brush2 = brush2->next)
  296.             {
  297.                 if (brush2 == brush1) continue;
  298.                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  299.                 {
  300.                     if (Plane_Equal(&face1->plane, &face2->plane, true))
  301.                     {
  302.                         break;
  303.                     }
  304.                 }
  305.                 if (face2) break;
  306.             }
  307.             // if face1 touches another brush
  308.             if (brush2) continue;
  309.             //
  310.             for (brush2 = brush1->next; brush2; brush2 = brush2->next)
  311.             {
  312.                 // don't check the faces of brush 2 touching another brush
  313.                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  314.                 {
  315.                     for (brush3 = brushlist; brush3; brush3 = brush3->next)
  316.                     {
  317.                         if (brush3 == brush2) continue;
  318.                         for (face3 = brush3->brush_faces; face3; face3 = face3->next)
  319.                         {
  320.                             if (Plane_Equal(&face2->plane, &face3->plane, true)) break;
  321.                         }
  322.                         if (face3) break;
  323.                     }
  324.                     // if face2 touches another brush
  325.                     if (brush3) continue;
  326.                     //
  327.                     if (Plane_Equal(&face1->plane, &face2->plane, false))
  328.                     {
  329.                         //if the texture/shader references should be the same but are not
  330.                         if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0) return NULL;
  331.                         continue;
  332.                     }
  333.                     //
  334.                     if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
  335.                                             face1->plane.normal, face2->plane.normal,
  336.                                             face1->plane.dist, face2->plane.dist))
  337.                     {
  338.                         return NULL;
  339.                     }
  340.                 }
  341.             }
  342.         }
  343.     }
  344.     //
  345.     newbrush = Brush_Alloc();
  346.     //
  347.     for (brush1 = brushlist; brush1; brush1 = brush1->next)
  348.     {
  349.         for (face1 = brush1->brush_faces; face1; face1 = face1->next)
  350.         {
  351.             // don't add face1 to the new brush if it touches another brush
  352.             for (brush2 = brushlist; brush2; brush2 = brush2->next)
  353.             {
  354.                 if (brush2 == brush1) continue;
  355.                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
  356.                 {
  357.                     if (Plane_Equal(&face1->plane, &face2->plane, true))
  358.                     {
  359.                         break;
  360.                     }
  361.                 }
  362.                 if (face2) break;
  363.             }
  364.             if (brush2) continue;
  365.             // don't add faces with the same plane twice
  366.             for (f = newbrush->brush_faces; f; f = f->next)
  367.             {
  368.                 if (Plane_Equal(&face1->plane, &f->plane, false))
  369.                     break;
  370.                 if (Plane_Equal(&face1->plane, &f->plane, true))
  371.                     break;
  372.             }
  373.             if (f)
  374.                 continue;
  375.             //
  376.             newface = Face_Alloc();
  377.             newface->texdef = face1->texdef;
  378.             VectorCopy(face1->planepts[0], newface->planepts[0]);
  379.             VectorCopy(face1->planepts[1], newface->planepts[1]);
  380.             VectorCopy(face1->planepts[2], newface->planepts[2]);
  381.             newface->plane = face1->plane;
  382.             newface->next = newbrush->brush_faces;
  383.             newbrush->brush_faces = newface;
  384.         }
  385.     }
  386.     // link the new brush to an entity
  387.     Entity_LinkBrush (brushlist->owner, newbrush);
  388.     // build windings for the faces
  389.     Brush_BuildWindings( newbrush, false);
  390.     return newbrush;
  391. }
  392.  
  393. /*
  394. =============
  395. Brush_Subtract
  396.  
  397.  Returns a list of brushes that remain after B is subtracted from A.
  398.  May by empty if A is contained inside B.
  399.  The originals are undisturbed.
  400. =============
  401. */
  402. brush_t *Brush_Subtract(brush_t *a, brush_t *b)
  403. {
  404.     // a - b = out (list)
  405.     brush_t *front, *back;
  406.     brush_t *in, *out, *next;
  407.     face_t *f;
  408.  
  409.     in = a;
  410.     out = NULL;
  411.     for (f = b->brush_faces; f && in; f = f->next)
  412.     {
  413.         Brush_SplitBrushByFace(in, f, &front, &back);
  414.         if (in != a) Brush_Free(in);
  415.         if (front)
  416.         {    // add to list
  417.             front->next = out;
  418.             out = front;
  419.         }
  420.         in = back;
  421.     }
  422.     //NOTE: in != a just in case brush b has no faces
  423.     if (in && in != a)
  424.     {
  425.         Brush_Free(in);
  426.     }
  427.     else
  428.     {    //didn't really intersect
  429.         for (b = out; b; b = next)
  430.         {
  431.             next = b->next;
  432.             b->next = b->prev = NULL;
  433.             Brush_Free(b);
  434.         }
  435.         return a;
  436.     }
  437.     return out;
  438. }
  439.  
  440. /*
  441. =============
  442. CSG_Subtract
  443. =============
  444. */
  445. void CSG_Subtract (void)
  446. {
  447.     brush_t        *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
  448.     brush_t        fragmentlist;
  449.     int            i, numfragments, numbrushes;
  450.  
  451.     Sys_Printf ("Subtracting...\n");
  452.  
  453.     if (selected_brushes.next == &selected_brushes)
  454.     {
  455.         Sys_Printf("No brushes selected.\n");
  456.         return;
  457.     }
  458.  
  459.     fragmentlist.next = &fragmentlist;
  460.     fragmentlist.prev = &fragmentlist;
  461.  
  462.     numfragments = 0;
  463.     numbrushes = 0;
  464.     for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
  465.     {
  466.         next = b->next;
  467.  
  468.         if (b->owner->eclass->fixedsize)
  469.             continue;    // can't use texture from a fixed entity, so don't subtract
  470.  
  471.         // chop all fragments further up
  472.         for (s = fragmentlist.next; s != &fragmentlist; s = snext)
  473.         {
  474.             snext = s->next;
  475.  
  476.             for (i=0 ; i<3 ; i++)
  477.                 if (b->mins[i] >= s->maxs[i] - ON_EPSILON 
  478.                 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
  479.                     break;
  480.             if (i != 3)
  481.                 continue;    // definately don't touch
  482.             fragments = Brush_Subtract(s, b);
  483.             // if the brushes did not really intersect
  484.             if (fragments == s)
  485.                 continue;
  486.             // try to merge fragments
  487.             fragments = Brush_MergeListPairs(fragments, true);
  488.             // add the fragments to the list
  489.             for (frag = fragments; frag; frag = nextfragment)
  490.             {
  491.                 nextfragment = frag->next;
  492.                 frag->next = NULL;
  493.                 frag->owner = s->owner;
  494.                 Brush_AddToList(frag, &fragmentlist);
  495.             }
  496.             // free the original brush
  497.             Brush_Free(s);
  498.         }
  499.  
  500.         // chop any active brushes up
  501.         for (s = active_brushes.next; s != &active_brushes; s = snext)
  502.         {
  503.             snext = s->next;
  504.  
  505.             if (s->owner->eclass->fixedsize || s->patchBrush || s->hiddenBrush)
  506.                 continue;
  507.  
  508.             //face_t *pFace = s->brush_faces;
  509.             if (s->brush_faces->d_texture->bFromShader && (s->brush_faces->d_texture->nShaderFlags & QER_NOCARVE))
  510.             {
  511.                 continue;
  512.             }
  513.  
  514.             for (i=0 ; i<3 ; i++)
  515.                 if (b->mins[i] >= s->maxs[i] - ON_EPSILON 
  516.                 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
  517.                     break;
  518.             if (i != 3)
  519.                 continue;    // definately don't touch
  520.  
  521.             fragments = Brush_Subtract(s, b);
  522.             // if the brushes did not really intersect
  523.             if (fragments == s)
  524.                 continue;
  525.             //
  526.             Undo_AddBrush(s);
  527.             // one extra brush chopped up
  528.             numbrushes++;
  529.             // try to merge fragments
  530.             fragments = Brush_MergeListPairs(fragments, true);
  531.             // add the fragments to the list
  532.             for (frag = fragments; frag; frag = nextfragment)
  533.             {
  534.                 nextfragment = frag->next;
  535.                 frag->next = NULL;
  536.                 frag->owner = s->owner;
  537.                 Brush_AddToList(frag, &fragmentlist);
  538.             }
  539.             // free the original brush
  540.             Brush_Free(s);
  541.         }
  542.     }
  543.  
  544.     // move all fragments to the active brush list
  545.     for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)
  546.     {
  547.         nextfragment = frag->next;
  548.         numfragments++;
  549.         Brush_RemoveFromList(frag);
  550.         Brush_AddToList(frag, &active_brushes);
  551.         Undo_EndBrush(frag);
  552.     }
  553.  
  554.     if (numfragments == 0)
  555.     {
  556.         Sys_Printf("Selected brush%s did not intersect with any other brushes.\n",
  557.                     (selected_brushes.next->next == &selected_brushes) ? "":"es");
  558.         return;
  559.     }
  560.     Sys_Printf("done. (created %d fragment%s out of %d brush%s)\n", numfragments, (numfragments == 1)?"":"s",
  561.                             numbrushes, (numbrushes == 1)?"":"es");
  562.     Sys_UpdateWindows(W_ALL);
  563. }
  564.  
  565. /*
  566. =============
  567. CSG_Merge
  568. =============
  569. */
  570. void CSG_Merge(void)
  571. {
  572.     brush_t *b, *next, *newlist, *newbrush;
  573.     struct entity_s    *owner;
  574.  
  575.     Sys_Printf ("Merging...\n");
  576.  
  577.     if (selected_brushes.next == &selected_brushes)
  578.     {
  579.         Sys_Printf("No brushes selected.\n");
  580.         return;
  581.     }
  582.  
  583.     if (selected_brushes.next->next == &selected_brushes)
  584.     {
  585.         Sys_Printf("At least two brushes have to be selected.\n");
  586.         return;
  587.     }
  588.  
  589.     owner = selected_brushes.next->owner;
  590.  
  591.     for (b = selected_brushes.next; b != &selected_brushes; b = next)
  592.     {
  593.         next = b->next;
  594.  
  595.         if (b->owner->eclass->fixedsize)
  596.         {
  597.             // can't use texture from a fixed entity, so don't subtract
  598.             Sys_Printf("Cannot add fixed size entities.\n");
  599.             return;
  600.         }
  601.  
  602.         if (b->patchBrush)
  603.         {
  604.             Sys_Printf("Cannot add patches.\n");
  605.             return;
  606.         }
  607.  
  608.         if (b->brush_faces->d_texture->bFromShader && (b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE))
  609.         {
  610.             Sys_Printf("Cannot add brushes using shaders that don't allows CSG operations.\n");
  611.             return;
  612.         }
  613.  
  614.         if (b->owner != owner)
  615.         {
  616.             Sys_Printf("Cannot add brushes from different entities.\n");
  617.             return;
  618.         }
  619.  
  620.     }
  621.  
  622.     newlist = NULL;
  623.     for (b = selected_brushes.next; b != &selected_brushes; b = next)
  624.     {
  625.         next = b->next;
  626.  
  627.         Brush_RemoveFromList(b);
  628.         b->next = newlist;
  629.         b->prev = NULL;
  630.         newlist = b;
  631.     }
  632.  
  633.     newbrush = Brush_MergeList(newlist, true);
  634.     // if the new brush would not be convex
  635.     if (!newbrush)
  636.     {
  637.         // add the brushes back into the selection
  638.         for (b = newlist; b; b = next)
  639.         {
  640.             next = b->next;
  641.             b->next = NULL;
  642.             b->prev = NULL;
  643.             Brush_AddToList(b, &selected_brushes);
  644.         }
  645.         Sys_Printf("Cannot add a set of brushes with a concave hull.\n");
  646.         return;
  647.     }
  648.     // free the original brushes
  649.     for (b = newlist; b; b = next)
  650.     {
  651.         next = b->next;
  652.         b->next = NULL;
  653.         b->prev = NULL;
  654.         Brush_Free(b);
  655.     }
  656.     Brush_AddToList(newbrush, &selected_brushes);
  657.  
  658.     Sys_Printf ("done.\n");
  659.     Sys_UpdateWindows (W_ALL);
  660. }
  661.