# Implementing 2D CSG (for collision shapes)?

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.

• Adding an answer myself - as I ended up using this: sourceforge.net/projects/polyclipping - rather than attempting an implementation from scratch. So far it's doing the job quite nicely, and it was very easy to use (with C#) Wikipedia has links to a fair bit of information on the subject, once I started searching using the right terminology: en.wikipedia.org/wiki/Boolean_operations_on_polygons – bluescrn Jan 8 '11 at 19:27
• Here is a fantastic javascript implementation of 3D CSG. This is certainly overkill for your problem, but the code is small, clean and well-documented, so you can learn a great deal by studying it. – DaleyPaley Apr 17 '13 at 11:23

## 2 Answers

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 );
}
}
}


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.

• Interesting, I will have to read up on that. However, I'm trying to stay away from triangle meshes - and deal purely with outline edges (as for collision purposes, any interior/enclosed edges attached to a vertex on the outline can cause unwanted collisions). But maybe a triangle mesh as an intermediate step, before filtering out interior edges, is a possible approach? – bluescrn Nov 15 '10 at 16:01
• gluTessellate has an outline only mode as well GLU_TESS_BOUNDRY_ONLY. The link I provide has a short section specifically about CSG. – deft_code Nov 15 '10 at 17:41
• Wow, that looks surprisingly powerful, I'd never realised that glu contained that functionality. It looks like it's an option (despite my tool being D3D-based), but I'm still quite curious about the algorithms that would be involved in a DIY solution – bluescrn Nov 15 '10 at 18:58
• There isn't really anything novel in OpenGL's tessellator. I imagine any advanced tessellator could do similar things. Also DirectX11 features hardware tessellation, I don't know if it has the advanced features needed for CSG but it would be worth a look. – deft_code Nov 15 '10 at 19:30