Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 3 down vote accepted

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 );
        }
    }
}
share|improve this answer
    
Yes, it's just for the level editor, to build a clean and fairly efficient collision mesh on export. It doesn't need to be real-time, as yes, I expect that would be quite costly :) –  bluescrn Nov 15 '10 at 21:56
    
See my update. BTW I always avoid developing my own code (or evaluating any 3-rd party stuff) for the algorithms already implemented in Windows built-in libraries. –  Soonts Nov 16 '10 at 21:06

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.

share|improve this answer

Adding an answer myself - as I ended up using this: http://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: http://en.wikipedia.org/wiki/Boolean_operations_on_polygons

share|improve this answer

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.