Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Help understanding marching squares algorithm

Tags:

c++

algorithm

In my game, I want to layout squares along the edges of a monochrome image: enter image description here

So I found this algorithm which should solve the issue. http://en.wikipedia.org/wiki/Marching_squares

It does not seem that hard to implement, I just think I do not understand exactly what Wiki is saying. I think I have to break the image up into cells where each cell represents 2x2 pixels on the image? Is that correct? I'm then lost by this instruction:

For each cell in the contouring grid:

1.Compose the 4 bits at the corners of the cell to build a binary index: walk around the cell in a clockwise direction appending the bit to the index, using bitwise OR and left-shift, from most significant bit at the top left, to least significant bit at the bottom left. The resulting 4-bit index can have 16 possible values in the range 0-15.

I'm not sure how to appending the bit.

Thanks

like image 691
jmasterx Avatar asked May 12 '11 20:05

jmasterx


1 Answers

After you create the 2x2 cells, for each one you compute a number like this:

  • set the number to 0
  • if the top left point is above the threshold, add 8
  • if the top right point is above, add 4
  • if the lower right point is above, add 2
  • if the lower left point is above the threshold, add 1.

Edited formatting.

like image 183
Andrei Avatar answered Nov 08 '22 10:11

Andrei