Implementing Marching Squares(jacobzelko.com)
jacobzelko.com
Implementing Marching Squares
http://jacobzelko.com/marching-squares/
6 comments
>> 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.
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.
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.
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.
>> 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.
He does mention interpolation but doesn't go into it. That can also be used to resolve the ambiguity in cases 5 and 10.
you can also use the original field to produce normals that look a lot better (for cubes)
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!
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.
Now I am wondering if you could use the alternative for case 5 or 10, but not both.
Going 3D, marching cubes (and tetrahedrons) make for very interesting landscape generation.
https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...
https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...
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.
Related video from Reducible https://www.youtube.com/watch?v=6oMZb3yP_H8&t=1153s
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...
https://martinliversage.blob.core.windows.net/publications/1...