Talk:Marching squares

not Marching Squares, but a binary raster contour following algorithm

The algorithm described is not Marching Squares, but a binary raster contour following algorithm, the output is a set of cells, not an interpolated contour, and there's no hint how to find the set of all contours when there are many disjoint components.

A true analogy to Marching Cubes would iterate over every square independently, classify the boundary data values, use a look-up table to generate the topology of output contour(s), with data interpolation to get accurate geometric position, then merge this with the existing output structures.

For example, there are descriptions here, including ASCII-art drawings of all distinct cases for squares:

Contour lines: Isoline Slice

Contour bands: Isoband Slice

The implementations are specific to the AVS APIs, but include code in C and Fortran, for planar and non-planar 2D surfaces embedded within 3D regular, irregular and unstructured grids (UCDs).

The original algorithms are credited to Mike French, Evans & Sutherland UK, and variously dated March-June 1992.

The code is in the public domain, as described in the International AVS Center license, and E&S copyright with stipulations that all subsequent distribution is free of charge.

The documentation contains this comment on references: The composite algorithm is original and unpublished by this author, it is very simple and must have been published somewhere before. The marching cubes idea (index and look-up table) was used without referring to any particular paper.

Note that AVS provided an Isosurface implementation of Marching Cubes, and did license the Lorensen & Cline patent which has now expired (I believe they paid GE $100k!).

Mikhailfranco (talk) 08:19, 30 January 2009 (UTC)

I agree, the article as currently written is misleading, and does not describe what is commonly understood to be the Marching Squares / Marching Cubes algorithm. It should be updated. By the way, I believe this 1987 paper by Lorensen & Cline is the original algorithm.

DRE (talk) 05:43, 14 November 2009 (UTC)

I'm not sure if this assessment is correct, but this algorithm did what I expected from a 2D version of Marching Cubes: find an equipotential contour quickly and _without_ having to assess every cell in the grid. The information on this page was very valuable, and is complete enough to implement the algorithm.

ChrisNF (talk) 23:37, 23 February 2009 (UTC)

No doubt the raster contour algorithm is valuable if there is just a single connected data region without holes, and you only want to output the set of cells at the single simple boundary, but that is just a special case for a lower dimensional problem, and it is not analogous to Marching Cubes (MC).

Another difference in the problem statement is that MC applies to data values on vertices of a 3D grid, but the 2D raster problem is posed with values on cells (squares in 2D). To convert the raster problem to a form amenable to Marching Squares, the cell values would have to be localized at cell centres on an offset dual grid with one fewer square in each direction i.e. n x m grid shrinks to dual (n-1) x (m-1) grid.

The MC algorithm generates interpolated surfaces through a volume. The analogy in 2D would be interpolated lines through an area. Where MC can be used to generate 3D volume regions between 3D contour levels the analogy in 2D would be 2D banded contour regions over the area.

The MC algorithm handles the case when there are multiple disjoint regions of data above/below the contour threshold, and any region can have holes, including multiply nested holes. It does this not by trying to handle all the possible global topologies and connectivities, but by ignoring global issues, and reducing the problem to handling cells individually, according to the pattern of values on their vertices. The analogy in 2D is to ignore global 2D topologies and treat each square individually.

The pattern of each cell is independent of the others, but the interpolation step is performed on each 2D cell edge, so the results can be shared by the two neighboring cells (the references linked above mention this, but admit to not implementing this optimization). In MC the linear interpolations are performed on each 3D edge (4 neighboring cells), then connected on each 3D face (2 neighboring cells), and sharing these intermediate steps could be optimizations in building the final 3D output geometry.

--Mikhailfranco (talk) 09:11, 12 August 2009 (UTC)

Replaced the described algorithm by real Marching Squares=

The algorithm on Wikipedia was not the marching-squares algorithm as defined by Lorensen et Al. , and other literature. I replaced the image and whole text to represent the Marching-Squares algorithm from literature. Djexplo (talk) 10:24, 25 February 2011 (UTC)

The previous version was much easier to understand (since it doesn't get bogged down in issues of thresholding or binary representations), and in fact is not just for tracing a contour; it just uses that as the example to make the subject matter more accessible. Also, you misspelled "cells" in your image, which is not a very easily-edited way to present information. 76.21.45.96 (talk) 23:06, 13 March 2011 (UTC)

The values are wrong - you've flipped 4 and 8. Mixed 'true' with 'false' along the example. Altogether this becomes one of the most unclear, misleading and full with errors algorithm description ever to be seen on Wiki. To be deleted. —Preceding unsigned comment added by 46.116.138.85 (talk) 11:07, 31 March 2011 (UTC)

I have update the image to correct those small errors. --130.89.192.63 (talk) 08:13, 5 April 2011 (UTC)

I have moved many of my earlier comments in the discussion page to the main article, introduced the isoline/isoband categories, added new images to explain the many different cases, and given references to the AVS work. I have started a description of performance and optimization, but I realize there is a lot more to add there. I think the existing description is quite good (e.g. it shows how the contour grid is one cell smaller than the data grid), and I have left it in place for now, but it should probably be merged with my isoline description somehow. However, I also notice that 'threshold' is misspelled in the original image. Mikhailfranco (talk) 08:17, 6 May 2011 (UTC)

I have now rewritten the description, and I hope it is clearer now, e.g. remove the equation with undefined b1,b2,b3,b4 and describe bitwise operations. I have also tried to use the terms field/grid/image/cell a bit more consistently and added lots of links such as binary, bit, OR etc. Mikhailfranco (talk) 11:14, 6 May 2011 (UTC)

Previous Article?

The section on saddle points contains this line:

(WARN: In this present article the relation black/white-above/below is the opposite from previous article)

I thus ask: What? --2A02:8388:6281:F080:790B:F9E:F2AC:C790 (talk) 13:13, 24 October 2020 (UTC)