CSG Tutorial

By Alan Baylis 21/03/2003
My Homepage   Message Board   Email





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 theMAP 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
http://folk.uio.no/stefanha/mapfiles.pdf

Gerald Filimonov
http://www.3dtechdev/tutorials/illegalgeometry/illegalgeometrytut.html

Dan Royer
http://www.cfxweb.net/~aggrav8d/tutorials/csg.html



(Alan Baylis a.k.a. TheGoodAlien)
My Homepage

Email


Add Me!