CSG Tutorial
By Alan Baylis 21/03/2003
Download the Demo with Source
Constructive Solid Geometry (CSG) is used in game editors
to construct the world geometry by adding or subtracting brushes (primitive convex
shapes) from one another. It is also used to remove illegal geometry from existing
world data files as described by
Gerald Filimonov, so unless we are going to use
an existing world loader we will have to know how to do a bit of CSG programming.
I found that the best place to start learning about CSG was to download the MAP
file tutorial by
Stefan Hajnoczi who describes the process very
well. Another source of info was the tutorial
Dan Royer My final process is mix of these tutorials
and the source code presented by
Gerald Filimonov and works well for CSG addition
of multiple brushes. I will work towards making the other CSG operations such
as subtraction, intersection and difference later on.
Stefan, Gerald and Dan have already done a good job of explaining how the splitting
of polygons is performed and many of the other details so in this tutorial I will
just give you my heavily commented source code and take it that you have already
read their tutorials.
To begin with we need a polygon class that supports n-sided polygons which you
will find in polygon.h/cpp of the demo source code, I have used a standard array
for the vertices of the polygons to avoid a lot of dynamic memory handling but
a polygon with 20 vertices will be fine for this demo. The main function for splitting
polygons is also in polygon.cpp. We also need a brush class, which is basically
just a collection of polygons, which you will find in brush.h/cpp. The main CSG
functions used below can be found in csg.cpp. In order to handle the polygons
and brushes in a dynamic list I have also added new pointers and member functions
to the polygon and brush classes.
You may have another way of handling your polygons and brushes in a list so you
will need a function to add them to a list compatible with the following code.
My method for doing this, which assumes there is a global array of brushes and
a brush pointer called BrushSet, is as follows.
void CreateBrushSet()
{
for (int loop = 0; loop < numBrushes; loop++)
{
BRUSH* newBrush = new BRUSH;
*newBrush = Brush[loop];
if (BrushSet)
BrushSet->AddBrush(newBrush);
else
BrushSet = newBrush;
}
}
CSGAddition loops through the brushes in the brush set and
performs a csg addition between each brush in the list with every other brush
in the list. There are a few things to Note:
* When copying a polygon from a list that may be inserted in a new list you must
set the NextPoly pointer to NULL.
* The clip flag which is passed to CSGClipPolygon is used to decide whether or
not to keep coplanar polygons.
* After each operation only the remaining fragments are clipped by following brushes,
this is done by copying the remaining fragments back to the working polygon list
before continuing.
int CSGAddition()
{
// Clip flag is sent to CSGClipPolygon to determine whether or not to keep
// coplanar polygons.
int clip;
// Temporary lists of polygons and brushes.
POLYGON* polylist1 = NULL;
POLYGON* polylist2 = NULL;
POLYGON* polylist3 = NULL;
POLYGON* looppoly = NULL;
POLYGON* frags = NULL;
POLYGON* poly = NULL;
BRUSH* brush1 = NULL;
BRUSH* brush2 = NULL;
// Loop through each of the brushes and set the temporary pointer brush1.
for (brush1 = BrushSet; brush1; brush1 = brush1->GetNext())
{
// Clear the clip flag for each new brush to be clipped.
clip = false;
// Copy the polygons from brush1 to polylist1
for (int loop = 0; loop < brush1->numPolygons; loop++)
{
POLYGON* newPolygon = new POLYGON;
*newPolygon = brush1->Polygon[loop];
if (polylist1)
polylist1->AddPolygon(newPolygon);
else
polylist1 = newPolygon;
}
// Loop through each of the brushes and set the temporary pointer brush2.
for (brush2 = BrushSet; brush2; brush2 = brush2->GetNext())
{
// If brush1 is the same as brush2 then we are halfway through
// clipping the brushes against each other so we set the clip
// flag for further operations and continue.
if (brush1 == brush2)
{
clip = true;
continue;
}
// I didn't need to do an intersection test for the sake of this
// demo but one should be added here in a finished program
// to speed up the routine.
// Copy the polygons from brush2 to polylist2
for (int loop = 0; loop < brush2->numPolygons; loop++)
{
POLYGON* newPolygon = new POLYGON;
*newPolygon = brush2->Polygon[loop];
if (polylist2)
polylist2->AddPolygon(newPolygon);
else
polylist2 = newPolygon;
}
// Loop through each polygon in polylist1 and clip it against the
// polygons in polylist2.
for (looppoly = polylist1; looppoly; looppoly = looppoly->GetNext())
{
// Make a copy of the original polygon.
poly = new POLYGON;
*poly = *looppoly;
// Clear the NextPoly pointer before adding the polygon to
// another list.
poly->NextPoly = NULL;
// Clip the polygon against polylist2.
frags = CSGClipPolygon(poly, polylist2, clip);
// Add the fragments returned to polylist3.
if (polylist3)
polylist3->AddPolygon(frags);
else
polylist3 = frags;
// If the fragment returned is not the original polygon then
// delete the original polygon.
if (!(frags == poly))
delete poly;
}
// Copy the list of fragments over to polylist1 to be clipped by
// further brushes.
DeleteList(polylist1);
polylist1 = polylist3->CopyList();
// Delete the temporary polygon lists.
DeleteList(polylist2);
polylist2 = NULL;
DeleteList(polylist3);
polylist3 = NULL;
}
}
// Copy the final polygon list out to an array
Brush[0].numPolygons = 0;
for (looppoly = polylist1; looppoly; looppoly = looppoly->GetNext())
{
Brush[0].Polygon[Brush[0].numPolygons] = *looppoly;
Brush[0].Polygon[Brush[0].numPolygons++].NextPoly = NULL;
}
// Delete the now copied list
DeleteList(polylist1);
polylist1 = NULL;
// Set a state flag to show that a CSG operation was performed.
CSGflag = 0;
return 1;
}
CSGClipPolygon takes a polygon and
recursively clips it against a list of plane polygons. The resulting fragments
are linked together and returned after each recursion.
POLYGON* CSGClipPolygon (POLYGON* poly, POLYGON* planepoly, int clip)
{
// Temporary polygon lists.
POLYGON* retfrags = NULL;
POLYGON* frontfrag = NULL;
POLYGON* backfrag = NULL;
// Classify the polygon against the plane.
int result = ClassifyPolygon(poly, *planepoly);
switch (result)
{
case Front:
// If the polygon is in front of the plane then return it whole.
return poly;
break;
case Back:
// If the polygon is behind the plane and there are more planes
// in the plane list then clip it against the next plane.
if (planepoly->GetNext())
{
retfrags = CSGClipPolygon(poly, planepoly->GetNext(), clip);
return retfrags;
}
// Otherwise return NULL.
else
return NULL;
break;
case PolygonWasSplit:
// If the polygon intersects the plane then it needs splitting.
frontfrag = new POLYGON;
backfrag = new POLYGON;
SplitPolygon(poly, *planepoly, frontfrag, backfrag);
// If there are more planes in the list then continue to
//clip the back fragment.
if (planepoly->GetNext())
{
retfrags = CSGClipPolygon(backfrag, planepoly->GetNext(), clip);
// If the returned fragment is not the same as the original back
// fragment then delete the back fragment and add the returned
// fragment to the front fragment before returning all.
if (!(retfrags == backfrag))
{
delete backfrag;
frontfrag->AddPolygon(retfrags);
return frontfrag;
}
// If the returned fragment is the same as the original back
// fragment then it survived further clipping and we can just
// return the original polygon.
else
{
delete frontfrag;
delete backfrag;
return poly;
}
}
// There were no more planes to check the back fragment against so
// we only keep the front fragment.
else
{
delete backfrag;
return frontfrag;
}
break;
case OnPartition:
// The polygon was coplanar with the plane so we check the polygons
// normal to see if it is in front of the plane, if it is we know
// that the polygon is facing the same way as the plane. If so, and
// the clip flag hasn't been set, then we can return the polygon.
if (ClassifyPoint(poly->Vertex[0].normal, planepoly->Vertex[0].coords,
planepoly->Vertex[0].normal) == 1)
if (!clip)
return poly;
// If the program gets to here then either the polygon faced the
// opposite way to the plane or the clip flag was set, in which case
// we continue to clip it with any other planes in the list or return
// NULL if there are no more planes.
if (planepoly->GetNext())
retfrags = CSGClipPolygon(poly, planepoly->GetNext(), clip);
else
return NULL;
break;
}
// If a coplanar polygon gets split by other planes then we return the
// fragments here.
return retfrags;
}
Hopefully this source code combined with the tutorials mentioned
will make it easier for you to perform CSG, it is a difficult subject so give
yourself a lot of time to let the ideas become clear. This has been my first experiment
with CSG and I will keep working on it in future demos. I hope it helps you to
construct your own worlds. If you have any suggestions, problems or error reports
then send me an email.
Al.
References:
Stefan Hajnoczi
Gerald Filimonov
Dan Royer
Above Content Copyright © 1998 - 2005 Alan Baylis, All Rights Reserved
