Ripping apart Glue Editor

This week I’ve been busy gearing up for an iteration on Glue Editor. The plan is to implement the constructive solid geometry (CSG) features into the editor for building levels.

It’s been a while since I worked on Glue Editor so I had to get familiar with the code again. The engine code has changed a lot since the last time it was used in the editor so the first step was to get them working in harmony. This was a pretty big refactor and as I ploughed through I stripped the code back to basics. I’ve dropped many of the features that don’t fit our current direction with a plan to rebuild the editor from a more solid base. At this stage I think it’s best to keep the two code bases separate so that the old version remains as is.

There’s still a lot to do but here’s a screenshot of very basic CSG in action. Very much a hacked up prototype just to get my head around the problem at this stage. Over the next month I hope to complete a working alpha version. Once that happens I’ll start doing periodic releases for testing and feedback.

Level creation with subtractive CSG

Yesterday I mentioned breifly that I was working on a CSG algorithm for level creation. Today I thought I’d share a few screenshots from a prototype level that I created using only a few lines of code. The level you see here is constructed from only a few axis aligned boxes that form the inside of the room. When they are placed next to each other they “cut” the space out making it more interesting.

You’ll also notice in the wireframe that each of the walls are created from “grids”. This is not required but produces better dynamic lighting. An alternative approach is to apply a second pass to remove t-junctions and apply static light maps. Many first person games use an approach like this with BSP based levels.

Working on a Constructive Solid Geometry (CSG) algoritm

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.