Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


"Fat" Marching Ants: An Algorithmic Experimentation Using GDI+ : Page 2

"Marching ants" are a common UI feature in image editing programs but giving the ants a little more visual texture is a harder problem than you'd ever dream. This article discusses four different algorithms for making elegant, 3D ants with varying levels of performance, accuracy, and control.

Algorithm No. 1: Arc-based FMA
This algorithm piggybacks on the traditional algorithm. Whenever the traditional algorithm draws a pixel, the fat algorithm will draw a crescent perpendicular to the actual line (see Figure 4). When an ant turns a corner (line join) there is an unpleasant effect. The ant seems broken (see Figure 5). An elegant solution is to make the turn smoother by injecting more points along the ant's trail (spline-like), but I didn't want to modify the points that define the line. Instead, I simply draw a filled circle, a.k.a. "The Knee," while an ant is turning a corner (see Figure 6).

Figure 4. These experimental ants are made of parallel crescents.
Figure 5. Ants that 'go around the corner' in this algorithm end up badly broken.

Another issue that came up is the consistency of the ant. Remember that the ant is not a cohesive shape, but a bunch of adjacent crescents. These crescents, when drawn along a diagonal line, don't always adhere to their neighbors due to approximation errors when moving from the ideal coordinate system to the pixelated screen (see Figure 7). One solution is to draw two crescents for each point: One crescent at (x,y) and another at (previous x,y). Another solution is to draw two-pixel wide arcs using the DrawArc() function.

Figure 6. A smooth "knee" joint helps this ant turn the corner more elegantly.
Figure 7. Non-uniform ant rendering is a result of approximation errors that occur when the ants are rendered on a pixelated screen.

Another issue with this algorithm is that the contour of the ant is jagged (aliasing) since the contour is created implicitly by the end points of multiple arcs. Anti-aliasing works on explicit lines and curves only so we have a problem, Houston.

Algorithm No. 2: Line-based FMA
This algorithm takes a different view of the problem. Instead of creating the ant from a sequence of arcs perpendicular to the central line it draws multiple lines parallel to the central line (see Figure 8).

Figure 8. These ants were made with a different algorithm that relies on a series of parallel lines.
Assuming that an ant is longer than it is wide rendering it using lines along its long dimension will result in fewer steps in the inner loop. For example if an ant is 25 pixels long and 8 pixels wide then rendering it using arcs will require 25 arcs while rendering it using lines will require just 8 lines. This approach also solves the aliasing problem since the lines that comprise an ant (possibly just the two extreme lines) can now take advantage of anti-aliasing.

This algorithm also builds on the traditional algorithm, however instead of drawing each ant incrementally it just remembers the start and end points of each ant along the Bresenham line (note that an ant may be split between several consecutive line segments). When the end point of an ant is reached it is time to draw lines from each point along the imaginary arc at the rear end of the ant to the corresponding point at its head. That means somehow we have to figure out the points along these arcs.

Bresenham was kind enough to come up with a circle algorithm as well as a line algorithm. Arcs (being the partial circles they are) can be calculated using Bresenham's circle algorithm. However, this is not a straight forward affair. Bresenham's circle algorithm capitalizes on the fact that circle are completely symmetric. The algorithm calculates directly only 1/8 of the circle and completes the rest by way of symmetry. For every calculated point x,y on the circle circumference (assuming the center is 0,0) the following points will also be on the circle's circumference: (x,-y), (-x,y), (-x,-y), (y,x), (-y,x), (y, -x) and (-y, -x). Unfortunately, this calculation method makes it difficult to figure out what points belong to some arbitrary arc.

What I needed is to sort all the points of a circle in a certain direction (e.g. clock-wise) and, given an arc identified by a start angle A and a sweep S, just take all the points between points corresponding to A and A+S. This required a modicum of post processing of Bresenham's algorithm. Here is the arc calculation algorithm:

  • Calculate the start point (SP) and end point (EP) on the circle
  • Run standard Bresenham's circle algorithm and store the points (1/8 circle only)
  • Rearrange the points in continuous manner (put the symmetric points in the right place)
  • Scan the points and find the indices of the points that are closest to SP and EP
  • Return all the points between SP and EP
I definitely calculate and massage a bunch of points I don't need (especially for arcs with a big radius and small sweep). However, this algorithm works and because for each line segment I calculate this arc only once it doesn't seem worthwhile to optimize it further. Of course, your mileage may vary. I'll talk about performance later.

Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



Thanks for your registration, follow us on our social networks to keep up-to-date