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.

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.

Algorithm No. 3: Whole Ant FMA
And now for something completely different. The arc-based and line-based FMA algorithms sliced and diced the poor ant and rendered it piecemeal. This algorithm takes a different approach. It renders a full ant in one swoop. This is impossible of course. At the graphics hardware level everything is rendered pixel-by-pixel by a fancy "Laser" (my homage to Dr. Evil) cannon or some other gadget. What I mean is that at the graphics API level, which is what the code interfaces with, I prepare a whole ant shape and fill it in one call. Admittedly, I use GDI+'s facilities and I don't write everything from scratch. If you want to rough it you can calculate the ant contour (two parallel lines and two "parallel" arcs) and fill the enclosed area (flood fill or multiple Bresenham lines between points with the same Y on the contour).

The whole ant FMA needs to address two issues: how to draw an ant in various orientations and how to handle ants that are split between two line segments. To solve these problems, I prepared an ant shape using GDI+ GraphicsPath facility and for each line segment in a specific orientation I rotate the ant using a transformation matrix. In order to draw seemingly partial ants I use clipping. This means that if an ant is split between two consecutive line segments I actually draw two ants. One ant at the end of the first line segment and another ant at the beginning of the second line segment (with appropriate offsets).

I clip the rendering area so the parts of the ants that should not be rendered will not stick out. Figure 9 shows the whole ant FMA without clipping. Figure 10 shows what it looks like with clipping. In both figures I emphasize in green the clipping region. The effect (with clipping of course) is quite pleasant and there is no need to draw the "knee."

Figure 9. The whole ant FMA without clipping is visually untidy.

?

Figure 10. The whole ant FMA with clipping is tidy and eliminates the need to draw the "knee."

Algorithm No. 4: Dash FMA

Figure 11. The Dash FMA looks pretty good but you can forget about making an ant split between two line segments effectively.

Suppose the graphics API you are using inherently supports rendering of "fat" dashed lines in a given offset. Well, this is the case with GDI+. The algorithm in this case is very simple for each line segment: just draw a line with the proper dash attributes (see Figure 11). There are two issues with this method: It's difficult to control the ant shape and there is no concept of splitting an ant properly between consecutive line segments.

GDI+ Intro
GDI+ is an object-oriented API for 2D graphics programming. It supersedes the old Win32 GDI (Graphics Device Interface). It takes a lot of the drudgery out of doing graphics on Windows due to its object-oriented programming model, which differs from the handle-based programming model of GDI. GDI+ is not a one-to-one mapping of GDI. There is much more functionality. The organization of classes in name spaces and the APIs are superb. Inefficient constructs and functions such as SetPixel and LineDDA were dropped.

GDI+ is implemented as a plain DLL (gdiplus.dll) with a flat C API (some 600 functions), which is bundled with a C++ API (wrapper classes). Microsoft recommends and supports only the C++ API. In addition the .NET framework provides a managed wrapper for GDI+ in the System.Drawing.* namespaces. The most significant drawback of GDI+ is its relatively slow performance. People in the know claim that it is due to a lack of hardware acceleration for GDI+. It should improve in future versions of the .NET framework. Anyway, it should be adequate for most business and UI purposes. Just don't write Doom 4 using GDI+.

I'll quickly introduce the main objects I use in Squigler (the name I gave to my fat marching ant program) and in the GDI+ demo program. There is much more to GDI+ and I encourage you to take the plunge.

?The Graphics Class
The Graphics class is the heart and soul of GDI+; it encapsulates the device context and offers a plethora of properties and methods to control every aspect of rendering such as rendering quality, clipping, and transformations. It also offers a rich variety of DrawXXX methods to draw anything from lines and arcs to text and polygons. Painting shapes is equally easy with the FillXXX methods.

?Coordinate System and Basic Structures
GDI+ uses a coordinate system based on floating point rather than integer units. This may seem strange since eventually you must draw your lines, curves, and shapes on integer pixels (raster graphics, remember?). The reason is that the graphic objects may undergo various transformations and the rounding errors that might be introduced could accumulate and distort the end result. The type of each coordinate is the System.Single ('float' in c#). It is not a System.Double ('double' in C#) because floats have 7 digits of precision (which is more than enough for graphics transformations) and take 32-bit each. Each double has 15 digits of precision but takes a whopping 64-bit. So, it is a very reasonable tradeoff of accuracy vs. space. It is a bit uncomfortable when you need the trigonometric functions (sin, cos, atan, etc.), because they all use 'double' arguments and return values. In these cases, you have to cast between float and double?back and forth.

Most of the methods that require locations or sizes have multiple overloads and accept either integer values or floating point values. The integer values are for convenience and can be used when no transformation is performed on the relevant object. The classes that represent locations, sizes, and areas are Point, PointF, Size, SizeF, Rectangle, and RectangleF. The classes whose names end with 'F' have float fields, while the others have integer fields. The Region class can be used to describe arbitrary complex areas.

?Pens and Brushes
When using the DrawXXX and FillXXX functions, pass as first argument either a pen or a brush. A pen controls every aspect of the drawn line such as color, width, dash style, end points style, and line joins.

pen = new Pen(Color.Crimson, 5);pen.StartCap = LineCap.DiamondAnchor;pen.EndCap = LineCap.ArrowAnchor;g.DrawLine(pen, new Point(5, 10), new Point(20, 30);

The code above demonstrates how to create a pen with a crimson color and a line width of 5 pixels, assign it certain cap styles, and finally draw a line between two points using this pen.

A brush controls how the interior of closed graphic shapes (polygons or graphic paths) will look. There are multiple brush types: solid, hatch, texture, and gradient. Solid brushes are the simplest and just paint an area with a uniform color:

Brush brush = new SolidBrush(Color.OliveDrab);Rectangle rect = new Rectangle(200, 200, 150, 150);g.FillRectangle(brush, rect);

There are multiple constructors for pens and brushes so be sure to choose the one best suited to your needs and enjoy the various defaults without specifying excruciatingly every property.

?Lines and Arcs
Lines and arcs are the Swiss army knife of 2D graphics. They are both very easy to use and allow creating the contours of any shape. You can draw lines and arcs using the overloaded DrawLine and DrawArc methods of the Graphics class passing in a pen:

pen = new Pen(Color.Crimson, 5);pen.StartCap = LineCap.DiamondAnchor;pen.EndCap = LineCap.ArrowAnchor;g.DrawLine(pen, new Point(5, 10), new Point(20, 30);

When drawing an arc the arguments are a rectangle (defined by four integers/floats or two points) an ellipse, a start angle, and a sweep angle. The arc will start at the start angle and continue to "sweep" as far as the sweep angle defines. For a full circle pass 360 as the sweep angle. Note the angles are measured in degrees and not radians.

?GraphicsPath
A graphics path is a rather powerful beast. It allows aggregating multiple figures, lines, arcs, and curves. It even allows a single path to contain multiple disconnected figures. It can easily perform various transformations (see "Transforms," below) on a graphics path by manipulating its Transform attribute. You can render a graphics path by using the DrawPath or FillPath methods of the Graphics class. The code below demonstrate how to create a graphics path, move it a certain distance (using a translation transform), and render it.

Figure 12. GDI+ transformations translate, rotate, and scale turned the version on the left into the version on the right.

// Create a transformation matrixMatrix m = new Matrix();// move 100 pixels to the right and 50 pixels downm.Translate(100, 50);// Create an ant-like graphics pathGraphicsPath p = new GraphicsPath();p.AddLine(0, 0, 50, 0);p.AddArc(50, 0, 20, 20, -90, 180);p.AddLine(50, 20, 0, 20);p.AddArc(-10, 0, 20, 20, 90, -180);// move the graphics path by applying the translation matrixm_path.Transform(m);// Draw the path and fill it toog.FillPath(new SolidBrush(Color.Orange), p);g.DrawPath(new SolidBrush(Color.Black), p);

?Transforms
Transforms are the way to move, rotate, and scale things in GDI+. They can also be used to do interesting things to colors. The basic idea is all these transformations can be represented by matrices. Matrices can be combined by multiplying so multiple effects can be achieved by applying the product of multiple matrix multiplications (the result is a single matrix). Figure 12 presents a bunch of lines, arcs, and a graphics path. The whole enchilada has been rendered twice: once as is and then again after "suffering" three transformations (translate, rotate, and scale).

The code for the entire program is in Listing 1. The Paint event handler of the form calls to methods Draw() and DrawSkewed(). Draw() simply draws all the objects on the screen as seen on the left side of Figure 7. DrawSkewed() creates a combined transformation matrix, applies it to the entire Graphics object and then calls Draw() again. The results can be seen on the right side of Figure 12.

The Squigler Program
Squigler is a program for experimenting with various marching ant algorithms. There are several parameters that control the rendering (some parameters apply only to some algorithms). Squigler boasts a KUI (keyboard user interface) for playing with the parameters. No menu. No mouse. The KUI consists of the following keys:

' ' (Spacebar) - move to next algorithm (cyclic)'+' (Plus)     - Increase thickness of ants '-' (Minus)   - Decrease thickness of ants'p'            - Pause (any key to resume)'s'            - Toggle anti-aliasing'k'            - Toggle "knee" renderingESC (Escape)   - Exit the application 

?Squigler Internals
The architecture is very simple. There is an interface (IMarchingAntRenderer) that multiple concrete renderers implement. The interface has just a single method: Render.

namespace Squigler{       public interface IMarchingAntRenderer       {              void Render(Graphics g,                                    Point[] points,                                    int radius,                                    int offset,                                    int antLength,                                    int antGap,                                    bool renderKnee,                                   Color color);       }}

Each renderer uses a different algorithm for rendering, but they all follow the same high-level flow: The Render() calls a private RenderSegment() for each line Segment. RenderSegment() advances using Bresenham's line algorithm along the line segment and renders the ant incrementally or by calling a private RenderAnt() method. The MainForm creates all the renderers (each one is a singleton that exposes an Instance property) and whenever its timer elapses it calculates the current offset and invalidates the form. The user can easily switch to a different renderer by pressing the 'Spacebar' key or changing the rendering parameters. Any user action invalidates the form (see Listing 2). Invalidating the form triggers a Form_Paint event, which results in a call to the Render() method of the current renderer.

Let's dive into the renderers. There are five different renderers. All except one are based on the Bresenham line algorithm.

?SimpleRenderer
The simple renderer implements the traditional marching ant algorithm (1 pixel wide) I described earlier. Its code is a good way to familiarize yourself with the Bresenham line algorithm. The only interesting thing about it is that it demonstrates how to plot a single pixel using GDI+. The Graphics class has no DrawPixel method. In the olden days of GDI you could call SetPixel() and pass a device context handle. The disappearance of SetPixel() is actually a good thing, since the performance was horrible. The workaround I use to draw a single pixel is to create a 1x1 bitmap, set its only pixel to the desired color and then draw it using the DrawImageUnscaled() method of the Graphics class.

// SetupBitmap  m_bitmap = new Bitmap(1,1);m_bitmap.SetPixel(0, 0, m_color);...// Plot pixel at (x,y)g.DrawImageUnscaled(m_bitmap, x, y);

Another noticeable misfeature of this implementation is horrible aliasing even when the SmoothingMode of the Graphics is set to AntiAlias. The reason is GDI+ can smooth out only lines and curves it draws itself. Here I draw the ants pixel by pixel, so from the point of view of GDI+ there is no line to smooth out. All in all it is a good example of a bad implementation and sets a very low bar for the other renderers. The SimpleRenderer class (below) has a public Render() method that sets up the render parameters, iterates over the line segments, and calls the private RenderSegment() method for each segment. RenderSegment() implements the Bresenham's line algorithm and draws (renders) the 1x1 pixel bitmap for each pixel that belongs to an ant (see Listing 3). The continuation between line segments is handled by keeping track of the offset since the start of the polyline.

public void Render(Graphics g,        Point[] points,        int radius,        int offset,        int antLength,        int antGap,        bool renderKnee,       Color color){                     m_antLength = antLength;       m_antGap = antGap;       m_color = color;       m_bitmap.SetPixel(0, 0, m_color);       int lineCount = points.Length-1;       Debug.Assert(lineCount > 0);       int total = offset;       for (int i = 0; i < lineCount; ++i)              total+= RenderSegment(g, points[i], points[i+1], total);}

?ArcRenderer
The ArcRenderer implements the arc-based FMA. The code is very similar to the SimpleRenderer with two notable exceptions: optional knee rendering and crescent (arc) rendering instead of a single pixel. The ArcRenderer draws the knee as a filled ellipse, if necessary, at the beginning of each segment:

if (renderKnee && offset % (m_antLength+m_antGap) < m_antLength){       int r = m_kneeRadius;       int rr = r * 2;       g.FillEllipse(m_brush, p1.X-r, p1.Y-r, rr, rr);}

Then it iterates over the pixels and calls the RenderCresent() method to actually render each crescent:

void RenderCrescent(Graphics g, Point p, double angle){       double cos = Math.Cos(angle);       double sin = Math.Sin(angle);       float cx = p.X - (float)(cos*m_radius);       float cy = p.Y - (float)(sin*m_radius);       float startAngle = (float)(angle * 180 / Math.PI)-m_halfSweep;       float rr = (float)(2*m_radius);       g.DrawArc(m_pen, (float)(cx-m_radius), (float)(cy-m_radius), rr, rr, startAngle, (float)sweep);}

The center point of the circle, which contains the crescent, is calculated followed by the start angle, which is derived from the line segment's angle. Finally the renderer calls the DrawArc() method of the Graphics class to render the crescent.

?LineRenderer
The LineRenderer implements the line-based FMA. The code doesn't follow the footsteps of the traditional algorithm exactly. The high-level algorithm is the same for each line segment in the polyline: The RenderSegment() method is called, where the algorithm traverses the line segment pixel by pixel. However, the internal mechanics are completely different.

For each line segment an appropriate arc is calculated and stored in the m_arc data member (see Listing 4). For each ant the start point is saved while inching (or rather pixeling) along the Bresenham line. Once an end point is reached (if m_antLength pixels passed since the start point or if the end of a line segment has been reached), the ant is rendered by calling multiple DrawLine() methods from each point along the arc (with start point offset of course) to the corresponding point (with end point offset). This is all done in the RenderAnt() method, which is called once for every ant:

public void RenderAnt(Graphics g, Point p1, Point p2){       for (int i = 0; i < m_arc.Length; ++i)       {              Point p = m_arc[i];              g.DrawLine(m_pen, p1.X+p.X, p1.Y+p.Y, p2.X+p.X, p2.Y+p.Y);       }}

?WholeAntRenderer
The whole ant renderer implements the whole ant FMA. It relies heavily on GDI+ functionality such as GraphicsPath, transforms, and clipping. The basic flow is pretty similar to the LineRenderer. There is the ubiquitous RenderSegment() method, which calculates start and end points along the Bresenham line and calls the RenderAnt() method once it determines an ant should be rendered. The WholeAntRenderer prepares a GraphicsPath that represents an ant when the Render() method is called with a new radius, otherwise it uses the current GraphicsPath data member m_path (see Listing 5).

Because the ant is prepared in advance?in full length?it is not possible to render a partial ant as required when an ant is split between two adjacent line segment. The solution is to draw two full ants with appropriate offsets, but to clip them so they appear as single ant turning the corner. In order to clip the ants I prepared a clipping region around the entire line segment with rounded end points and assigned it to the Clip property of the Graphics class.

// Prepare clip regionint r = m_kneeRadius+1; // make a little buffer for anti-aliasingfloat ox = (float)(r * sina);float oy = (float)(r * -cosa);GraphicsPath clipPath = new GraphicsPath();int sweep = 180;float startAngle = (float)(angle * 180 / Math.PI)-(sweep >> 1);clipPath.AddLine(new PointF(p1.X-ox, p1.Y-oy), new PointF(p2.X-ox, p2.Y-oy));clipPath.AddArc(p2.X-r, p2.Y-r, 2*r, 2*r, startAngle-180, (float)-180);clipPath.AddLine(new PointF(p2.X+ox, p2.Y+oy), new PointF(p1.X+ox, p1.Y+oy));clipPath.AddArc(p1.X-r, p1.Y-r, 2*r, 2*r, startAngle, (float)-180);Region originalClip = g.Clip;g.Clip = new Region(clipPath);

Note that I saved the original clipping region because I needed to restore it before rendering the next line segments to prevent over clipping. Before rendering the ant RenderSegment() also prepares the transform so it corresponds to the current line segment by translating to its origin point and rotating by its angle.

// Prepare the base segment transform matrixfloat a = rad2deg(angle);m_matrix.Reset();int tx = (int)(r * sina);int ty = (int)(r *  -cosa);m_matrix.Translate(tx, ty);m_matrix.Rotate(a);

Note that m_matrix is reset every time. This is necessary to avoid compounding transforms, which is really a bad idea. The algorithm continues merrily along the Bresenham line just like the LineRenderer until an ant needs to be rendered. Then it calls the RenderAnt() method, which works a bit differently. Remember m_matrix already contains the transformations of the current line segment (start point and angle). This means the ant can be rendered as-is, and it will be magically transformed to the proper place. But, there is a catch. The algorithm needs to draw the ant at a certain offset from the beginning of the line segment. This requires you to add another translation transformation on top of m_matrix. Then m_path is transformed and rendered and finally everything is reset to normal before drawing the next ant:

public void RenderAnt(Graphics g, Point p1){       Matrix m = m_antMatrix;       m.Translate(p1.X, p1.Y);       m.Multiply(m_matrix);       m_path.Transform(m);       g.FillPath(m_brush, m_path);       m.Invert();       m_path.Transform(m);       m.Reset();}

?DashRenderer
The DashRenderer implements the Dash FMA. The implementation couldn't have been easier. The Render() method prepares a special pen with a dash style and round line caps (ends of the ant) and calls Graphics.DrawLine() repeatedly for each line segment. Most of the arguments passed to Render() are not even used?there are no data fields and no private methods. (Note that fat dash lines were not available in GDI.) Listing 6 contains the entire DashRenderer class; you can see the actual code in the Render() method is merely seven lines long.

Performance
I didn't conduct a serious performance analysis due to the conceptual and technical difficulties. Instead, I just ran Squigler, switched renderers ('spacebar') while increasing and decreasing the radius parameter ('+' and '-'). Note that I use double buffering of the entire form. The results astonished me. All the renderers except the DashRenderer had the same perceived performance (seemed to run at the same speed). The DashRenderer was much faster then any of the others. This may be explained by the fact that the other renderers are doing a lot of work at the managed code level and have to cross back and forth from the managed to the unmanaged world a lot. Maybe. However, playing with various render parameters such smoothing (anti-aliasing) had no noticeable effect. Changing the radius, however, had a dramatic effect since it increases/decreases the number of pixels that need to be massaged and pushed around. Sad but true: You can never get an idea of how well your code will perform without profiling your production system with production input data.

It is also important to know when NOT to optimize. In this case the usage scenario is an animated outline to some arbitrary shape in a potentially rich graphic scene. Higher performance means the animated line will move faster. Here is an idea for improving the performance of the custom FMAs: I will concentrate on the line-based FMA. The basic idea is to draw only the pixels that need to be drawn without repetitions, calculate offsets only once, and avoid crossing the managed-unmanaged bridge as much as possible. The algorithm:

• Lock the screen buffer and get direct access to the bits
• For each line segment calculate the arc once (just like in the line-based FMA)
• Perform a single Bresenham traversal of the line segment
• For each point along the line belonging to an ant, draw all the pixels at an offset from corresponding points in the base arc
• Unlock the screen buffer when you are done

This is much better (theoretically speaking) then all the other algorithms. No multiple crossing of the managed unmanaged world, direct memory access, and a single Bresenham traversal per line segment.

The Ants Go Marching On
In this article I attacked a novel algorithmic problem of rendering fat marching ants. My approach was to start from a solution to a close problem (standard marching ants) and then try some variations. When I started I didn't have all these algorithms in mind. Actually, I had exactly one algorithm that I thought of initially: the arc-based FMA. However, while implementing it I was annoyed by some properties of the solution, tried to improve them, and came up with the other algorithms gradually. Many people say that you have to understand a problem before you can solve it. I say that you have to solve a problem in several ways before you can really understand it (at least when it comes to software development).