Implementing Marching Squares

48 10 5 years ago

I like how the article shows written descriptions of the algorithm, code, and visual aids to show the input data and output data. This accommodates many different learning styles and gives readers the option to either skim or go into detail. If my college text books were written this way, I would have learned much more fluently.

onos• 5 years ago

This was fun and simpler than I was anticipating: After first reading the problem statement I assumed we’d need to do some sort of search to get the connected clusters, but we see here the line to draw at any point is determined completely by local info. Neat!

mannykannot• 5 years ago

It is deterministic, though I am not sure if it gives one unique solution. In the example shown, there are many squares with white dots on one diagonal and black dots on the other; in these cases, it always seems to separate the white dots. (These are the cases liversage points out are ambiguous.) I guess that if you reversed the coloring, or used the alternatives for cases 5 and 10, the resulting partitioning would join the previously-white dots together.

Now I am wondering if you could use the alternative for case 5 or 10, but not both.

slig• 5 years ago

Related video from Reducible https://www.youtube.com/watch?v=6oMZb3yP_H8&t=1153s

user-the-name• 5 years ago

This is missing out an important step when using marching squares to visualise fields like the original example: You should not just apply a threshold to the input data, but instead you should keep the original values around, and use them to figure out where along an edge the intersection point should be placed. This gives you contours that follow the actual isolines much more closely.

For instance, if you are plotting the line where the field crosses zero, and one point is at 9 and its neighbour at -1, you should place the intersection point at 90% of the distance from the first to the second.

convolvatron• 5 years ago

you can also use the original field to produce normals that look a lot better (for cubes)

phkahler2• 5 years ago

> For instance, if you are plotting the line where the field crosses zero, and one point is at 9 and its neighbour at -1, you should place the intersection point at 90% of the distance from the first to the second.

He does mention interpolation but doesn't go into it. That can also be used to resolve the ambiguity in cases 5 and 10.

liversage• 5 years ago

Cases 5 and 10 in the article are actually ambiguous. In each case there are two ways to draw lines to separate the high and low points and a naïve algorithm will just hardcode one of each like it's done in the article. This isn't a serious problem in the two dimensional marching squares algorithm but the same problem can lead to holes in the surface generated by the three dimensional marching cubes algorithm.

During a visit to Washington University I had the opportunity to work with this flaw in the algorithm and I ended up publishing a scientific paper about the subject. I then went on to write my thesis (in Danish) where I worked more rigorously on how to deal with this. It's so long ago that I almost forgot so reading about marching squares again was a nice trip down memory lane.

https://martinliversage.blob.core.windows.net/publications/1...

phkahler2• 5 years ago

> Cases 5 and 10 in the article are actually ambiguous.

They are. He does mention using interpolation to make better boundaries. For example if you're using a threshold value and flag points as above/below that value, you can position the end-point of a line based on that threshold. When the lines don't exactly split a squares edge then cases 5 and 10 can be made less ambiguous by selecting the lines that minimize total line-length within a square. Or some similar heuristic.

lloeki• 5 years ago

Going 3D, marching cubes (and tetrahedrons) make for very interesting landscape generation.

https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...

Implementing Marching Squares

Related Stories