The previous implementation of the marching squares [Link] generates a lot of vertices because each segment line is defined by its own starting and ending points however all these line segments are interconnected - forming a polyline - and this is not taken into account in the implementation. Here is a new version to reduce the number of vertices.
1. Remove doubles
 |
| Fig.1: Test 5x5 image. |
Note: To use this image, go to Image > Adjust > Size..., set the width and height to 5 and choose a Bilinear interpolation mode.
If we calculate the isocontoured line of the test image of Fig. 1 using the basic implementation [Link] at a threshold value of 220 and a square size of 1, 20 vertices are generated as shown below but 10 are duplicates.
v 2 0.7083333333333334 0 #1
v 1.7426470588235294 1 0 #2
v 2.2573529411764706 1 0 #3
v 2 0.7083333333333334 0 #4 same as #1
v 1 1.7426470588235294 0 #5
v 0.7426470588235294 2 0 #6
v 1.7426470588235294 1 0 #7 same as #2
v 1 1.7426470588235294 0 #8 same as #5
v 2.2573529411764706 1 0 #9 same as #3
v 2.673076923076923 2 0 #10
v 0.7426470588235294 2 0 #11 same as #6
v 1 2.2023121387283235 0 #12
v 1.7976878612716762 3 0 #13
v 1 2.2023121387283235 0 #14 same as #12
v 2.6730769230769234 2 0 #15 same as #10
v 2.2 3 0 #16
v 1.7976878612716765 3 0 #17 same as #13
v 2 3.2 0 #18
v 2.2 3 0 #19 same as #16
v 2 3.2 0 #20 same as #18
Because of the interconnected nature of the isocontoured lines, a vertex in edge e1 is also shared in the edge e3 of the next marching square and similarly between edge e2 and e0 of the square below as shown in Fig. 2.
 |
| Fig.2: Duplicated vertices created from adjacent marching squares. The black and white colors correspond to outside and inside pixels, respectively. |
In the Marching Squares, the image is scanned from left to right and top to bottom. Thus, the vertex of edge e3 was already calculated in the edge e1 of the previous marching square and similarly for edge e0 and edge e2 of the square above. To find the previous vertices, we have to store one row of marching squares to retrieve the already calculated vertices along the common edges.
In the example of Fig. 3, the marching square #5 has a segment line between e0 and e3. The vertex of e0 was already calculated from the marching square #2 (point D) and those of e3 comes from the previous marching square #4 (point F).
 |
| Fig.3: The vertices named from 'A' to 'F' are calculated in this isocontour as symbolized by the dot ends of the red segment lines. In each marching square, only edges e1 and e2 (black lines) are evaluated, the vertices of edges e0 and e3 (dotted black lines) are extracted from previous marching squares. |
Now, if we run the new script, we get the following OBJ file only containing 10 vertices ...
v 2 0.7083333333333334 0
v 1.7426470588235294 1 0
v 2.2573529411764706 1 0
v 1 1.7426470588235294 0
v 0.7426470588235294 2 0
v 2.673076923076923 2 0
v 1 2.2023121387283235 0
v 1.7976878612716762 3 0
v 2.2 3 0
v 2 3.2 0
f 1 2
f 3 1
f 4 5
f 2 4
f 3 6
f 5 7
f 8 7
f 6 9
f 8 10
f 9 10
What about the code ? I modified the code to add some Object-Oriented Programming (OOP) techniques and that's the subject of the next post.
No comments:
Post a Comment