Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members  

csg.cpp

Go to the documentation of this file.
00001 // CSG functions
00002 // Based on the work of Gerald Filimonov and Dan Royer.
00003 // By Alan Baylis 2003
00004 
00005 #include <windows.h>
00006 #include "csg.h"
00007 #include "polygon.h"
00008 #include "vector.h"
00009 #include "vertex.h"
00010 #include "brush.h"
00011 #include "collision.h"
00012 #include "bsp.h"
00013 #include "mmgr.h"
00014 
00015 extern int numBrushes;
00016 extern POLYGON* brushPolygons;
00017 extern BRUSH* BrushSet;
00018 extern BRUSH* Brush;
00019 extern VERTEX* vertex1;
00020 extern VERTEX* vertex2;
00021 extern VERTEX* vertex3;
00022 extern bool Texturing;
00023 extern bool CSGflag;
00024 extern bool CSGcullface;
00025 
00026 // CSGClipPolygon takes a polygon and recursively clips it against a list of
00027 // plane polygons.
00028 POLYGON* CSGClipPolygon (POLYGON* poly, POLYGON* planepoly, int clip)
00029 {
00030     // Temporary polygon lists.
00031     POLYGON* retfrags = NULL;
00032     POLYGON* frontfrag = NULL;
00033     POLYGON* backfrag = NULL;
00034 
00035     // Classify the polygon against the plane.
00036     int result = ClassifyPolygon(poly, *planepoly);
00037 
00038     switch (result)
00039     {
00040         case Front:
00041             // If the polygon is in front of the plane then return it whole.
00042             return poly;
00043         break;
00044 
00045         case Back:
00046             // If the polygon is behind the plane and there are more planes
00047             // in the plane list then clip it against the next plane.
00048             if (planepoly->GetNext())
00049             {
00050                 retfrags = CSGClipPolygon(poly, planepoly->GetNext(), clip);
00051                 return retfrags;
00052             }
00053             // Otherwise return NULL.
00054             else
00055                 return NULL;
00056         break;
00057 
00058         case PolygonWasSplit:
00059             // If the polygon intersects the plane then it needs splitting.
00060             frontfrag = new POLYGON;
00061             backfrag = new POLYGON;
00062 
00063             SplitPolygon(poly, *planepoly, frontfrag, backfrag);
00064 
00065             // If there are more planes in the list then continue to clip the
00066             // back fragment. 
00067             if (planepoly->GetNext())
00068             {
00069                 retfrags = CSGClipPolygon(backfrag, planepoly->GetNext(), clip);
00070                 // If the returned fragment is not the same as the original back
00071                 // fragment then delete the back fragment and add the returned
00072                 // fragment to the front fragment before returning all.
00073                 if (!(retfrags == backfrag))
00074                 {
00075                     delete backfrag;
00076                     frontfrag->AddPolygon(retfrags);
00077                     return frontfrag;
00078                 }
00079                 // If the returned fragment was the same as the original back
00080                 // fragment then it survived further clipping and we can just
00081                 // return the original polygon.
00082                 else
00083                 {
00084                     delete frontfrag;
00085                     delete backfrag;
00086                     return poly;
00087                 }
00088             }
00089             // There were no more planes to check the back fragment against so
00090             // we only keep the front fragment.
00091             else
00092             {
00093                 delete backfrag;
00094                 return frontfrag;
00095             }
00096         break;
00097 
00098           case OnPartition:
00099             // The polygon was coplanar with the plane so we check the polygons
00100             // normal to see if it is in front of the plane, if it is we know
00101             // that the polygon is facing the same way as the plane. If so, and
00102             // the clip flag hasn't been set, then we can return the polygon.
00103             if (ClassifyPoint(poly->Vertex[0].normal, planepoly->Vertex[0].coords, planepoly->Vertex[0].normal) == 1)
00104                 if (!clip)
00105                     return poly;
00106 
00107             // If the program gets to here then either the polygon faced the
00108             // opposite way to the plane or the clip flag was set, in which case
00109             // we continue to clip it with any other planes in the list or return
00110             // NULL if there are no more planes.          
00111             if (planepoly->GetNext())
00112                 retfrags = CSGClipPolygon(poly, planepoly->GetNext(), clip);
00113             else
00114                 return NULL;
00115         break;
00116     }
00117     // If a coplanar polygon gets split by other planes then we return the
00118     // fragments here.
00119     return retfrags;
00120 }
00121 
00122 // CSGAddition loops through a set of brushes and performs CSG addition between
00123 // each brush in the set with every other brush in the set.
00124 int CSGAddition()
00125 {
00126     // Clip flag is sent to CSGClipPolygon to determine whether or not to keep
00127     // coplanar polygons.
00128     int clip;
00129 
00130     // Temporary lists of polygons and brushes.
00131     POLYGON* polylist1 = NULL;
00132     POLYGON* polylist2 = NULL;
00133     POLYGON* polylist3 = NULL;
00134     POLYGON* looppoly = NULL;
00135     POLYGON* frags = NULL;
00136     POLYGON* poly = NULL;
00137     BRUSH* brush1 = NULL;
00138     BRUSH* brush2 = NULL;
00139 
00140     // Loop through each of the brushes and set the temporary pointer brush1.
00141     for (brush1 = BrushSet; brush1; brush1 = brush1->GetNext())
00142     {
00143         // Clear the clip flag for each new brush to be clipped.
00144         clip = false;
00145 
00146         // Copy the polygons from brush1 to polylist1.
00147         for (int loop = 0; loop < brush1->numPolygons; loop++)
00148         {
00149                POLYGON* newPolygon = new POLYGON;
00150             *newPolygon = brush1->Polygon[loop];
00151             if (polylist1)
00152                 polylist1->AddPolygon(newPolygon);            
00153             else
00154                 polylist1 = newPolygon;
00155         }
00156 
00157         // Loop through each of the brushes and set the temporary pointer brush2.
00158         for (brush2 = BrushSet; brush2; brush2 = brush2->GetNext())
00159         {
00160             // If brush1 is the same as brush2 then we are halfway through
00161             // clipping the brushes against each other so we set the clip
00162             // flag for further operations and continue.
00163             if (brush1 == brush2)
00164             {
00165                 clip = true;
00166                 continue;
00167             }
00168 
00169             // I didn't need to do an intersection test for the sake of this
00170             // demo but one should be added here in a finished program
00171             // to speed up the routine.
00172 
00173             // Copy the polygons from brush2 to polylist2.
00174             for (int loop = 0; loop < brush2->numPolygons; loop++)
00175             {
00176                 POLYGON* newPolygon = new POLYGON;
00177                 *newPolygon = brush2->Polygon[loop];
00178                 if (polylist2)
00179                     polylist2->AddPolygon(newPolygon);
00180                 else
00181                     polylist2 = newPolygon;
00182             }
00183 
00184             // Loop through each polygon in polylist1 and clip it against the
00185             // polygons in polylist2. 
00186             for (looppoly = polylist1; looppoly; looppoly = looppoly->GetNext())
00187             {
00188                 // Make a copy of the original polygon.
00189                 poly = new POLYGON;
00190                 *poly = *looppoly;
00191                 // Clear the NextPoly pointer before adding the polygon to
00192                 // another list.
00193                 poly->NextPoly = NULL;
00194 
00195                 // Clip the polygon against polylist2. 
00196                 frags = CSGClipPolygon(poly, polylist2, clip);
00197                 // Add the fragments returned to polylist3. 
00198                 if (polylist3)
00199                     polylist3->AddPolygon(frags);
00200                 else
00201                     polylist3 = frags;
00202                 // If the fragment returned is not the original polygon then
00203                 // delete the original polygon.
00204                 if (!(frags == poly))
00205                     delete poly;
00206             }
00207 
00208             // Copy the list of fragments over to polylist1 to be clipped by
00209             // further brushes.
00210             DeleteList(polylist1);
00211             polylist1 = polylist3->CopyList();
00212             // Delete the temporary polygon lists.
00213             DeleteList(polylist2);
00214             polylist2 = NULL;
00215             DeleteList(polylist3);
00216             polylist3 = NULL;
00217         }
00218     }
00219     // Copy the final polygon list out to an array.
00220     Brush[0].numPolygons = 0;
00221     for (looppoly = polylist1; looppoly; looppoly = looppoly->GetNext())
00222     {
00223         Brush[0].Polygon[Brush[0].numPolygons] = *looppoly;
00224         Brush[0].Polygon[Brush[0].numPolygons++].NextPoly = NULL;    
00225     }
00226     // Delete the now copied list.
00227     DeleteList(polylist1);
00228     polylist1 = NULL;
00229     // Set a state flag to show that a CSG operation was performed.
00230     CSGflag = 0;
00231 
00232     return 1;
00233 }

Generated on Fri Dec 23 05:15:46 2005 for Constructive Solid Geometry by doxygen1.2.15