Implementing 2D CSG (for collision shapes)?

Question

Are there any simple (or well documented) algorithms for basic CSG operations on 2D polygons?

I'm looking for a way to 'add' a number of overlapping 2D collision shapes. These may be convex or concave, but will be closed shapes, defined as a set of line segments, with no self-intersections.

The use of this would be to construct a clean set of collision edges, for use with a 2D physics engine, from a scene consisting of many arbitrarily placed (and frequently overlapping) objects, each with their own collision shape.

To begin with, I only need to 'add' shapes, but the ability to 'subtract', to create holes, may also be useful.

Answer 1

Is this for level designer, or for the engine?

For the level designer - you'll need that code to e.g. combine static objects. Research vector graphic APIs for the solution, the task sounds pretty common for SVG, PostScript, WMF, etc.. First try using CombineRgn Win32 API :-)

For the game engine - I'd suggest you don't do what you want.. You'll spend enormous amount of CPU combining your objects together. You'll spend enormous count of branch mispredictions checking the border conditions, testing whether 2 segments intersect or not, etc.. And, this process must be repeated every frame for the visible portion of your map.

Just do bounding box checks, then collide individual objects. If your object shapes are too complex - simplify them while exporting data into the engine, and use different shapes for collision and drawing.

Update: see my C# GDI+ code that does what you want. You can easily write the same in C++: the GraphicsPath class is merely a thin wrapper over the corresponding gdiplus.dll functions.

static class GraphicsPathExt
{
    [DllImport( @"gdiplus.dll" )]
    static extern int GdipWindingModeOutline( HandleRef path, IntPtr matrix, float flatness );

    static HandleRef getPathHandle( GraphicsPath p )
    {
        return new HandleRef( p, (IntPtr)p.GetType().GetField( "nativePath", BindingFlags.NonPublic | BindingFlags.Instance ).GetValue( p ) );
    }

    public static void FlattenPath( this GraphicsPath p )
    {
        HandleRef h = getPathHandle( p );
        int status = GdipWindingModeOutline( h, IntPtr.Zero, 0.25F );
        // TODO: see http://msdn.microsoft.com/en-us/library/ms534175(VS.85).aspx and throw a correct exception.
        if( 0 != status )
            throw new ApplicationException( "GDI+ error " + status.ToString() );
    }
}

class Program
{

    static void Main( string[] args )
    {
        PointF[] fig1 = 
        {
            new PointF(-50, 0),
            new PointF(0, 50),
            new PointF(50, 0),
        };

        PointF[] fig2 = 
        {
            new PointF(-50, 25),
            new PointF(50, 25),
            new PointF(0, -25),
        };

        GraphicsPath path1 = new GraphicsPath();
        path1.AddLines( fig1 );
        path1.CloseAllFigures();

        GraphicsPath path2 = new GraphicsPath();
        path2.AddLines( fig2 );
        path2.CloseAllFigures();

        GraphicsPath combined = new GraphicsPath();
        combined.AddPath( path1, true );
        combined.AddPath( path2, true );
        combined.FlattenPath();

        foreach (var p in combined.PathPoints)
        {
            Console.WriteLine( "<{0}, {1}>", p.X, p.Y );
        }
    }
}

Answer 2

I wrote a little proof of concept that used CSG to make scorched earth/worms style game play. I implemented it with gluTessellate. I then mapped the tessellated triangles onto Box2D polygons. I could both add and subtract dirt from the simulation as well as make and fill holes.

The largest problem I found using gluTessallate is that it has no problem returning degenerate triangles. I had to filter those out before moving the tessellated triangles into the physics engine.

One of the nice things about gluTessallate is that it is possible determine adjacency from the callback information. I never took it further but in theory you could use the adjacency and SCC to accurately detect islanding.