Graphics Reference
In-Depth Information
lower vertex coming first, so a vertex on the segment from
(
1, 2
)
to
(
1, 3
)
would have a name
(
1, 2, 1, 3
)
.
• We can process the grid of squares one at a time. For each square, we do
the following.
-
Find the isocurve vertex associated to it.
-
If the vertex is new (we can use a hash table with the name as an index
to check this in
O
(
1
)
time), we assign a new index to the vertex name,
and add this index to our vertex table; if it's old, we do nothing with it.
-
For each new vertex, we use the values at the ends of the associated
edge to determine its exact location, and record this in the vertex table.
-
Examine the pattern of plusses and minuses to figure out what edges
must be added (we can do this with a lookup table in which the four
plusses and minuses serve as a 4-bit binary index); then we add these
edges to the edge table.
• The resultant set of isocurves has the property that every vertex (except
those on the very boundary of the grid) is shared by exactly two edges;
hence the resultant isocurves are all simple closed curves or polylines.
The square-at-a-time property will extend to 3D as well; because that 3D
algorithm is called “marching cubes,” this 2D algorithm can be called
marching
squares.
In practice, it may make sense to process a whole row of squares at once
to favor cache coherency.
Let us now return to the assumptions made at the start of our discussion of
marching squares.
We assumed that no grid vertex had the value 0. If a vertex has value 0, but
none of its neighbors do, we can adjust the value slightly (to, say, .001 times the
next smallest vertex value adjacent to it). We then proceed with the rest of the
algorithm, but at the very end, we adjust the positions of isocurve vertices that
lie on edges leaving this grid vertex so that they are all this single vertex. This
means that up to four different isocurve vertices may be at the same location so
that the isocurve no longer necessarily consists of disjoint simple closed curves
and polylines. Often, however, just two vertices get moved to sit at the grid vertex,
and the edge between them ends up with zero length (see Figure 24.11), while the
closed-curves-and-arcs property continues to hold. If four vertices all collapse to
a single grid vertex, the property no longer holds.
2
3
2
2
2
2
2
3
2
2
2
2
2
3
2
2
2
2
0
2
2
0
3
2
2
0.1
3
2
2
3
2
2
2
4
2
2
2
4
2
2
2
4
Figure 24.11: One grid vertex has value
0
; we adjust the value slightly and compute the
isocurve (which passes near the grid vertex), and then, at the end, we move the two nearby
vertices to the grid vertex so that the edge between them shrinks to nothing.
