Browse DevX
Sign up for e-mail newsletters from DevX


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

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




Building the Right Environment to Support AI, Machine Learning and Deep Learning

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" rendering ESC (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.

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.

// Setup Bitmap 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); }

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.

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); } }

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 region int r = m_kneeRadius+1; // make a little buffer for anti-aliasing float 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 matrix float 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(); }

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.

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