I’ve been pretty busy this week working on a CSG algorithm for indoor level creation. The idea is to be able to create hollow spaces for rooms using a “substractive brush” approach. So far I’ve got the first part of a reasonably robust algorithm working on 2 axis aligned boxes. I suspect it will work fairly well on any pair of convex solids but I haven’t tested that yet.

        public IEnumerable<Polygon> Subtract(ConvexSolid solid)
        {
            List<Polygon> polygonList = new List<Polygon>();

            foreach (Polygon polygon in Polygons)
            {
                bool wasSplit = false;
                Polygon polygonToSplit = polygon;

                foreach (Polygon otherPolygon in solid.Polygons)
                {
                    Plane splittingPlane = otherPolygon.Plane;
                    Polygon.PlaneClassification classification = otherPolygon.ClassifyTo(polygonToSplit.Plane);

                    if (classification == Polygon.PlaneClassification.Behind || classification == Polygon.PlaneClassification.Straddling) 
                    {   
                        Polygon.SplitResult splitResult = polygonToSplit.Split(splittingPlane);

                        if (splitResult != null)
                        {
                            if(splitResult.FrontPolygon != null)
                                wasSplit = true;

                            if (splitResult.BackPolygon != null)
                                polygonList.Add(splitResult.BackPolygon);

                            if (splitResult.FrontPolygon != null)
                                polygonToSplit = splitResult.FrontPolygon;
                        }
                    }
                }

                if (!wasSplit)
                    polygonList.Add(polygon);
            }

            return polygonList;
        }

It might be a little hard to tell whats going on in these screenshots but I figure a picture speaks louder than words. There is one degenerate case that I haven’t been able to solve when the cutting face is in front of the face to be cut. This shows up only when the solids overlap and one of the faces is coplanar with another as seen in the last screenshot. If anyone can spot a way to fix this I’d be greatly appreciated :)

I’ve gone over the alorithm many times with a fine tooth comb and written unit tests. Unforunately I don’t think I’m going to be able to solve the remaining bug without a big refactor. Probably by keeping all of the split polygons and having a second pass to remove any that are inside the solids.