[HN Gopher] Implementing Marching Squares
       ___________________________________________________________________
        
       Implementing Marching Squares
        
       Author : thecedarprince
       Score  : 42 points
       Date   : 2021-12-22 22:39 UTC (1 days ago)
        
 (HTM) web link (jacobzelko.com)
 (TXT) w3m dump (jacobzelko.com)
        
       | slig wrote:
       | Related video from Reducible
       | https://www.youtube.com/watch?v=6oMZb3yP_H8&t=1153s
        
       | user-the-name wrote:
       | 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.
        
         | phkahler wrote:
         | >> 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.
        
         | convolvatron wrote:
         | you can also use the original field to produce normals that
         | look a lot better (for cubes)
        
       | onos wrote:
       | 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 wrote:
         | 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.
        
       | vegetablepotpie wrote:
       | 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.
        
       | lloeki wrote:
       | Going 3D, marching cubes (and tetrahedrons) make for very
       | interesting landscape generation.
       | 
       | https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...
        
       | liversage wrote:
       | 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 naive 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...
       | 
       | https://martinliversage.blob.core.windows.net/publications/1...
        
         | phkahler wrote:
         | >> 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.
        
       ___________________________________________________________________
       (page generated 2021-12-23 23:02 UTC)