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+

"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.

arching ants are a colloquial term for the animated dotted-line that indicates a selected item or area by image-editing programs such as Adobe Photoshop and the GIMP. Traditionally, marching ants are implemented as a 1-pixel line. "Fat" marching ants (> 1 pixel wide) have a lot of visual appeal especially in 3D scenes, but are surprisingly difficult to implement correctly. I couldn't find a single reference to a "fat" marching ants algorithm. Fat marching ants could be used in 3D design and modeling programs to mark selected objects. The standard marching ants are not appropriate for this purpose because in 3D programs you often change your view (camera position) of the scene and expect the objects to be rendered according to the new view.

In this article I will present several algorithms to draw "fat" marching ants with arbitrary line widths and a nice 3D look. Each algorithm has its own trade-offs regarding performance, accuracy, and control. The demo code uses C#/GDI+. Some of the algorithms are completely generic and can be implemented easily in any programming language on any graphic system. Other algorithms rely on certain GDI+ facilities that may or may not be available elsewhere.

Traditional Marching Ants Algorithm
There are multiple ways to implement the traditional marching ants algorithm. One way is to use a slightly modified Bresenham line drawing algorithm. Bresenham's algorithm generates the line pixel by pixel. If a pixel belongs to an ant it is drawn otherwise the algorithm continues to the next pixel. The following code demonstrates how to determine if a given pixel should be drawn or not.

... int quotient = (i+offset+m_antLength+m_antGap) % (m_antLength+m_antGap); if (quotient <= m_antLength) { ... }

That's about it. In order to achieve the animated effect the dotted-line is rendered in incremental offsets every timer tick. The important thing about marching ants is that they don't march along a single line but multiple joined lines (see Figure 1). This raises the question of drawing partial ants at the ends of line segments. Consider an ant of length 10 pixels and a gap (between ants) of 5 pixels. If the last ant along a line segment had room for only 3 pixels (i.e. a line length of 33 pixels, including two full ants, 2 gaps, and one partial ant) then its remaining 7 pixels should be drawn at the beginning of the next line segment (see circled area in Figure 2).

Figure 1. This is the traditional look of marching ants: thin and two dimensional.
Figure 2. The total number of pixels in an ant, even when split between two line segments, remains constant.

Requirements for Fat Marching Ants

Figure 3. A fat ant has a very distinct geometry with two parallel line segments and two parallel arcs at either end, creating a direction-centric capsule shape.
Visually arresting "fat" marching ants are difficult. If you want to dazzle your sweetheart with a polished, elegant algorithm you will have to sweat it. Here are my requirements:
  • The lines should be thick (duh!)
  • The ants should have a 3D look
  • The ants should turn corners gracefully (joined lines)
  • The direction of the march should be obvious
  • The motion should be smooth
You can see a close-up of a fat ant in Figure 3. Before moving on to the algorithms themselves let me introduce a quick TLA (Three Letter Acronym): FMA, which stands for Fat Marching Ants.

Comment and Contribute








