Marching Cubes, Part 2 : Implementation Details

Hello again,

I thought a second post explaining a little more about my implementation of the marching squares algorithm.  As basic as it is, it could still be a resource to other people out there.  I know personally it took me quite some time to figure out how it all works, and then longer to understand a way to implement that in code form.

At its simplest, the marching squares algorithm really is very simple.  There are steps required.

1) Create a grid.
2) For each square in this grid, See if any object intersect with its corners.
3) For each of these intersected corners, draw the line contours according to the rules.

Okay, so on their own, those points don’t make much sense, so let me explain it in the context of my little example.

Create a Grid

So I’ve said that the first step is to create a grid, and it really is.  For my example I used a 2d array.  Currently it’s a purely logical grid, and doesn’t store any data, in future versions however it will combine with our ‘spatial grid’, which only does calculations for relevent squares ( more on which squares are relevent in the next section ).  And that’s section one.  Now, obviously the scale of your grid is dramatically going to affect your performance ( 800×600 may look pretty, but that’s a *lot* of calculations ), however all I want out of my grid are some coordinates, the detail I plan on adding later – as long as I have the bounding coordinates, All is good.

Checking Intersections

This is where things start to get interesting.  Let me first talk about my particles, They’ve got two properties that matter.  The Radius, and the ‘energy’. 

Blue Circle represents the blob, the Grey ring - the 'energy'

Anatomy of a Blob

 This ‘energy ring’ is the important part.  In the blob examples, we’ve called it our ‘threshold’, that is, the distance particles want to be away from other particles.  And so I figured I would use the same concept for this example.  When the blobs are placed on the grid, They look like this : 

Blob on Grid

Blob on Grid

As you can see, with a blob placed directly in the centre of a grid square, the energy radius neatly fits around the whole particle.  I’ve made the grid size relative to the particle radius.  Obviously if you changed this, you would get different results, possibly with particles not even registering at all – but you can get some interesting effects.

From here, I check every grid square to see how many of the corners are within the energy threshold.  ( This is a simple point to point distance check – nothing fancy as of yet ).  

Blob with Marked Corners

Blob with Marked Corners

So in the above example, there were 9 squares to check.  The First one ( top left ), had only one corner in, the next ( top middle ), had its bottom points, the next ( top right ), only it’s bottom left point.  etc etc.  Move the blob slightly, and the dot change accordingly 

 

Blob in a slightly different position

Blob in a slightly different position

Each of the squares has to be calculated individually ( though I just realised an idea that could potentially save a lot of time ).  As I said, my version is very very basic – and so, my implementation is very simple.

ANYWAY moving on, this is where this little table will come in handy : 

 

Marching Squares Cases

Marching Squares Cases, image from here

 

Now you see why we calculated those corners ? Note case 5, and case 10 have 2 different possibilities, I’ve gone with the non-red versions for all of my particles.  I think it wll give a ‘goopier’ feel once it’s been properly implemented.

Drawing Lines

The next step in the implementation is to calculate which case is relevent for what square.  Draw the lines, and voila – you’ve got : 

 

omg lines

lines!

Two Blobs

Two Blobs

And you get the picture. I told you it was fundamentally simple.  Now, I believe I am cheating a little.  ‘true’ marching squares traverses surface lines ( or so some resources lead me to believe – though others, didn’t ).  I’m merely drawing lines with flash’s inbuilt this.graphics.moveTo / lineTo methods.

This is just a very basic post to explain how my current iteration works.  Though since making that original version I’ve made various changes to the implementation to speed it up a bit.  Snookle is working on bitwise operations to help speed up the square search, and I’m going to work on a faster searching method tonight ( one that doesn’t do calculations twice, as mine currently does ).

I hope this explained something to those out there who are still confused, It might be a little disjointed – it’s something like 38 degrees in here at the moment – But yes.

 – Anthony.

Advertisements

About aA

I'm a 28 year old Designer from Brisbane, Australia. I've got a keen interest in Motion Graphics, Illustration, and Game Design. View all posts by aA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: