实现2D CSG(用于碰撞形状)?

是否有任何简单的(或有据可查的)在2D多边形上进行基本CSG操作的algorithm?

我正在寻找一种方法来“添加”一些重叠的2D碰撞形状。 这些可以是凸的或凹的,但是将是闭合的形状,被定义为一组线段,没有自交点。

使用这种方法将构建一个干净的一组碰撞边,用于2D物理引擎,从包含许多任意放置(并且频繁重叠)的对象组成的场景中,每个对象都有自己的碰撞形状。

首先,我只需要“添加”形状,但“减”的能力,以创建漏洞,也可能是有用的。

这是关卡devise师,还是引擎?

对于关卡devise师来说,你需要这个代码来组合静态对象。 研究解决scheme的vectorgraphicsAPI,这个任务对于SVG,PostScript,WMF等听起来很常见。首先尝试使用CombineRgn Win32 API 🙂

对于游戏引擎 – 我建议你不要做你想做的事情。你会花费大量的CPU结合你的对象。 你会花费大量的分支预测错误来检查边界条件,testing两个分段是否相交等。而且,这个过程必须在地图可见部分的每一帧中重复。

只是做边界框检查,然后碰撞单个对象。 如果对象形状太复杂 – 在将数据导出到引擎时简化它们,并使用不同的形状进行碰撞和绘制。

更新 :看看我的C#GDI +代码,做你想做的。 你可以很容易地在C ++中编写相同的代码:GraphicsPath类仅仅是相应的gdiplus.dll函数的一个简单的包装器。

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}>", pX, pY ); } } } 

我写了一个使用CSG来制作焦土/蠕虫风格游戏的概念certificate。 我用gluTessellate实现了它。 然后,我将棋盘格三角形映射到Box2D多边形上。 我可以从模拟中添加和减去污垢以及填充和填充孔。

我发现使用gluTessallate最大的问题是返回退化三角形没有问题。 在将棋盘格三角形移动到物理引擎之前,我必须将其过滤掉。

关于gluTessallate的好处之一是可以从callback信息中确定邻接关系。 我从来没有更进一步,但理论上你可以使用邻接和SCC来准确检测孤岛。

自己添加一个答案 – 正如我最终使用这个: http : //sourceforge.net/projects/polyclipping/ – 而不是尝试从头开始实施。

到目前为止,它的工作非常好,而且它非常容易使用(使用C#)

一旦我开始使用正确的术语进行search,维基百科已经链接了一小段关于这个主题的信息: http : //en.wikipedia.org/wiki/Boolean_operations_on_polygons

这是一个梦幻般的3D CSG的JavaScript实现。 这对于你的问题来说肯定是过分的,但是代码很小,很干净并且有很好的文档,所以你可以通过研究来学习。