Marching Squares!

Jan 15, 2011 at 4:00 AM

Hi everyone! Here is some quick snap shots of a new feature being developed for Farseer 3.3!

Marching Squares is a neat algorithm for finding the surface of an area recursively. It can find holes without fail and is blazing fast (in 2D).

The above images show the rough non-combined squares found by the algorithm. The finished product will return fully decomposed polygons not larger then a given size. Much like the bottom part of the third image.

Some benefits to using this method instead of using the Texture->Polygon method is speed and the ability to reconstruct parts of the mesh in real-time, like for say a destructible terrain. Only the parts of the terrain that are modified have to be reconstructed.

A demo of how to use this for the destructible terrain purpose will be included in Farseer 3.3!

Jan 15, 2011 at 3:40 PM

It looks amazing Matt.

Be sure to add the test you have to the testbed. Would really like to play around with this.

Jan 15, 2011 at 3:57 PM

Too cool, look forward to using it.

Jan 15, 2011 at 6:17 PM

when can we get our hands on this? I could use it right now!

Jan 15, 2011 at 6:28 PM

It's still in alpha and not ready yet for public consumption.

I still have to combine all the found squares into polygons.

Jan 15, 2011 at 6:42 PM

ahh, still cool though... does the final product perform better then if you were to decompose an object using the old texture to fixture algorithm? I have been finding that the decompisition systems slow down significantly when you do it multiple times or subtract from the body and do it again. There begins to be hundreds of polys which tends to be harsh on the system, especially on the wp7. Does the fact that you seperate the figure into boxes speed up the final product?

Jan 15, 2011 at 7:13 PM

Marching Squares fixes that problem by allowing small subsets of polygons to be removed and recalculated quickly. The decomposition will only be needed for a few chunks and should be fast even on WP7.

Also, I will include a method of Marching Squares that receives a function to evaluate whether or not a point is inside or outside the mesh. This will allow end users to create meshes based on math functions.

Jan 17, 2011 at 10:03 PM

This is exactly what I've needed for a while - I originally tried to create deformable terrain by hybridising Farseer's poly collision engine with my own bitmap collision routines, but it's a poor solution involving some complex calculations. Rather than duplicate your functionality I'm going to resume work on other parts of my engine, so I'll be extremely interested to what what you come up with here. Sounds awesome so far.

Jan 17, 2011 at 10:49 PM

@MrCochese: I've seen a bunch of people that needed support for deformable terrain. I can assure you that Matthew is working hard on the algorithm, he is currently creating an algorithm to combine the rectangles into larger polygons in an efficient way.

I've seen the prototype and it looks promising. As far as I can tell, the marching squares algorithm is working fine; it should be finished in the near future.

Mar 13, 2011 at 5:39 PM


Any new news on when this will be ready?
Really want it :) 

Mar 13, 2011 at 9:27 PM
No, I don't know. But, I don't work on Farseer Physics. I just use it. LOL. I really want it too. I think its gooling to be released in 3.2.

From: VoSSer
Sent: Sunday, March 13, 2011 1:39 PM
Subject: Re: Marching Squares! [FarseerPhysics:241875]

From: VoSSer


Any new news on when this will be ready?
Really want it :)

Mar 13, 2011 at 9:45 PM

I really want it too! Is it ready in source? if so is the source workable into a production game yet if we don't use some of the other features?

Mar 24, 2011 at 7:56 PM


Just saw that 3.3 is out (woho!) and noticed that marching squares was part of the release (even more yay!).

I could not see any examples in sample project though.

So i'm looking for some guidance as to how to use it properly. I have generated a 2D array (3000x1000) of my terrain, where 1 is ground and 0 is empty space.
Ive used this array to generate a bitmap aswell, but im not sure what I should do with it now.



Mar 25, 2011 at 12:46 AM

The testbed project contains a sample called DestructibleTerrainMSTest.

May 23, 2012 at 11:40 AM
Edited May 23, 2012 at 11:42 AM

Just wanted to show a working implementation using the Marching Squares code from the testbed.

The post is about alpha mapping but shows a teaser video where he is using Farseer and Marching squares to destroy terrain.