Compact Graphics Code

Two-dimensional transformations can be the key to reducing the memory cost often associated with graphical user interfaces. All you need to start is a simple set of drawing primitives.

Generating a custom GUI for an embedded system can be a tricky proposition. For one thing, a GUI demands a large portion of system resources. This article offers ideas for reducing custom graphics code memory requirements by using two-dimensional graphics transformations.

Library problems

When you launch a project that requires custom graphics, your first chore is to find a suitable graphics library. Graphics libraries are typically written in C++ and they contain many widgets from which to assemble your GUI components. While these libraries offer functionality, they consume RAM and ROM. Their use of dynamic memory allocation may also be a problem for you. Furthermore, you may discover that the graphics library does not allow you to modify the standard components.

One alternative is to find a smaller graphics library containing only basic drawing features. Not only would it take up fewer resources, but you would have complete control over the appearance of the GUI. A library of this kind allows you to draw each component from scratch.

To understand the distinction between the two approaches, consider the difference between two methods of CPU design-CISC and RISC. CPUs designed with complex instruction sets contain instructions that perform many micro code operations. On the upside, much is accomplished with a single instruction; however, each instruction executes slowly. CPUs with reduced instruction sets have much simpler instructions. RISCs execute faster but require more instructions to complete tasks. RISC computers use compilers to help manage the problem of stringing the many instructions into usable statements. If everyone had to program in assembly language, RISC would not be as popular as it is today.

Traditional GUI libraries parallel CISC machines; they accomplish much but are cumbersome and set in their ways. Small, minimum-feature graphics libraries resemble RISC machines because they are light, fast, and require more function calls to operate. We can make good use of small graphics libraries, but we must devise a better way to manage them.

Reduced complexity GUI

The solution is a reduced complexity GUI (RCGUI). How do you build one? Like a RISC CPU, an RCGUI needs additional tools and techniques to render it a usable technology.

The first tool is two-dimensional graphics transformation, which can be used to manipulate simple graphics primitives to create the complex animated objects needed for a sophisticated GUI. Graphics transformations are applied to a graphic object's coordinates to move, scale, or rotate the object. This allows you to animate the graphic in an object-independent manner. We will explore this in greater detail in the next section.

Another tool is interpolating the 2D graphics transformations. Interpolating transforms allows us to build new transforms from existing ones and to expand the range of motion of our objects. For example, let's say we have an object that has an animation that moves it from one side of the screen to the other. We have a transform that will move the object to the left side of the screen and another that will move the object to the right side of the screen. Since we want the object to move smoothly across the full range of the screen, we build a new transform for each position to which the object is to be drawn by interpolating between the two end transforms. This reduces the number of transforms that we need to provide for objects.

Another necessary tool is a graphics editor that allows graphical objects to be constructed without programming. Consider a GUI object called a “push button.” Traditional GUIs would draw this object with a function called DrawButton . Our RCGUI would draw this object with a series of DrawRectangle , DrawLine , and DrawText functions. The two approaches are compared in Listing 1.

Listing 1: Drawing buttons: traditional vs. RCGUI

// Traditional GUI library
Button = CreatePushButton(“My button”, x, y);
DrawButton(Button);

// RCGUI library
DrawFillRectangle(rectangle[m]); // button base
DrawLine(line[n]); // the shadow
DrawLine(line[o]); // the.highlight
DrawText(label[p]); // the button text

One of the best tools for obtaining the object coordinates the RCGUI draw functions will use is a graphics editor in which the GUI components are drawn on the screen, and their coordinates saved for use in the RCGUI. The features and functionality of the editor are important, but in this article we will focus on transforms and interpolation.

Transforms

Two-dimensional transformations are 3X2 matrices of floating-point numbers.

The coordinates of an object can be applied to the transform to move, scale, or rotate it. These 2D transforms are in a class of transforms called affine transforms, which preserve lines. For example, polygons and triangles will retain their shapes after transformation. Parallel lines and proportional distances are also preserved. For an excellent discussion of 2D graphics transforms, read Computer Graphics by F. S. Hill Jr. (1990).

The transforming of a coordinate pair is accomplished by means of a function transform defined as:

transform(T, x, y, xptr, yptr)
{
    *xptr = x * T->a00 + y * T->a10
        + T->a20;
    *yptr = x * T->a01 + y * T->a11
        + T->a21;
}

Figure 1: Combining text and graphics

where x is the x coordinate to be transformed and y is the y coordinate; T is the transform matrix to use; and xptr and yptr are pointers to the resulting transformed coordinates. Figure 1 shows the effect of applying this function to the coordinates of an object.The identity transform I is defined by the following matrix:

Applying the identity transform produces the same coordinates that were passed in. Multiplying transforms can be very useful. Let's say that you have an object with animation that can be shown by applying a transform T1 . If that object is part of a larger group of objects with another animation transform, such as T2 , you can multiply to get a transform that takes both transforms into account: T3 = T1 XT2 . You can take the inverse of a transform such that TXT-1 =I. Transform multiplication is not commutative, so T1 XT2 π T2 XT1 .

Logically, we should ask where we obtain the values for each transform. If an object is moved, the process may be defined as:

translate(T, x, y)
{
    T->a20 += x;
    T->a21 += y;
}

where T is the transform, and x and y are the offsets to move an object.

To scale or stretch an object requires a standard scale function called scale:

scale(T, sx, sy, cx, cy)
{
    translate(T, -cx, -cy);
    T->a00 *= sx;
    T->a01 *= sy;
    T->a10 *= sx;
    T->a11 *= sy;
    T->a20 *= sx;
    T->a21 *= sy;
    translate(T, cx, cy);
}

where sx is the scale factor in the x direction; sy is the scale factor in the y direction; cx is the x coordinate of the point to scale about; and cy is the y coordinate of that point.

Figure 1: Scaling by a factor of 2

Figure 2 shows a scale transformation on an object.Rotation requires a function defined as:

rotate(T, angle, cx, cy)
{
    translate(T, -cx, -cy);
    angle *= RADIANS_PER_DEGREE;
    cosval = cos(angle);
    sinval = sin(angle);
    m00 = T->a00 * cosval;
    m01 = T->a01 * sinval;
    m10 = T->a10 * cosval
    m11 = T->a11 * sinval;
    m20 = T->a20 * cosval;
    m21 = T->a21 * sinval;
    T->a01 = T->a00 * sinval
        + T->a01 * cosval;
    T->a11 = T->a10 * sinval
        + T->a11 * cosval;
    T->a21 = T->a20 * sinval
        + T->a21 * cosval;
    T->a00 = m00 – m01;
    T->a10 = m10 – m11;
    T->a20 = m20 – m21;
    translate(T, cx, cy);
}

where angle is the angle in degrees and cx, cy is the point about which to rotate. Figure 3 shows an object rotated by a rotation transformation.

Figure 3: Rotation by an angle of 75 degrees

The advantage of using transforms is that they allow you to treat all animations and objects equally. In keeping with the CISC/RISC analogy, transforms provide simplicity and reduce complexity. They reduce your graphics code to applying transforms to coordinate pairs, whereas a complex GUI library has to handle a plethora of special cases. The complex GUI library requires object-specific drawing code for each object, while a RCGUI needs only the application of transformations to coordinates. In fact, you don't even need to save all the objects' coordinates. If your screen contains similar objects, simply save one of the coordinates and use transforms to generate the rest of the objects. When objects differ only by their x,y position, only the a20 and a21 part of the transform needs to be stored. These may be added to the identity transform to make the complete transform.

Transform interpolation

Figure 4: One bar makes a bar graph

Transform interpolation is another useful technique for creating RCGUIs. Imagine you need to draw four different bar graphs. Each graph consists of a small rectangle that looks almost like a line at 0 value. At 100 value, it's a tall rectangle. Figure 4 shows one of the bars. Let's assume that we have a rectangle consisting of two coordinate points. Applying transform T1 with our transform function to point (X2 , Y2 ) will yield (X2 , Y2 ). Applying T2 to (X2 , Y2 ) yields (X2 , Y2 ). This is the value that the graph should have when sent a 0 value. Applying T2 to (X2 , Y2 ) yields (X2 , Y2 ), which is the upper right coordinate of the rectangle for value 100. To draw the rectangle for value 60 we need to compute T2 , which is the interpolated transform for value 60. To compute this transform the following calculations apply:

percent = (60 – 0) / (100 – 0) = 0.60

Then:

a´ ij + (bij – aij ) X percent

where aij is the transform matrix values of the transform of the rectangle with value 0 (the low value transform), and bij is the transform matrix values of the transform of the rectangle with value 100 (the high value transform). The resulting matrix values can be applied to the first rectangle's coordinates, and the bar graph will be drawn correctly for value 60. This is a transformation interpolation. A linear interpolation is done to the values of the extreme transformations to derive a new transform that can be applied to an object's coordinates to draw intermediate values.

What are the savings over just scaling the object directly? Let's assume we have four bars in a graph. The savings in raw data stored can be reduced to the following formula:

(2 * 4) + (6 * 4) + n <= 4="" *="" n="">

where n is the size in points of the object drawn. Eight transforms must be saved, but four of them need only a20 and a21 , while the other four require all six values. Interpolation only requires one saved copy of the object, while in the other case, four copies are necessary.

Solving this equation results in:

3 * n >= 32 or n >= 11

This implies that the object would have 11 coordinates (or 5.5 coordinate pairs) for the interpolation to save raw data storage space. If you have a bar graph with 100 vertical plots, that number drops to eight coordinates (or four coordinate pairs) before memory is saved. It is easy for an attractive bar graph to use more than four coordinate pairs of data.

The reduction in code size and complexity is equally important because it enables the bar graph animation to be treated in the same manner as your other animations. Your push buttons, knobs, sliders, gauges, and other components will all use the same animation code. Whereas a complex GUI library has dedicated code for each type of object, the RCGUI's objects all share the same drawing code.

Figure 5: Rotating a needle gauge

Let's examine another interpolation example: a needle gauge. In Figure 5, p0, p1, …, p9 are the ten coordinate pairs for a needle that must rotate. Applying transform Tl to these points puts the needle in the lowVal position. Applying transform Th rotates the needle to the highVal . We need to find the transform Ti such that the needle will be at the value position. If we apply our interpolation method to the rotation of a needle, we will not get the desired results. The problem is that the transforms do not have enough information to rotate the needle properly. Not only are we missing the point about which the rotation occurs, but the angle information is not usable. To perform the interpolation, we must remove the rotation component from the transform, apply the interpolation, compute the angle of interpolation, and put the new angle into the transform. The code for this is shown in Listing 2, in which lowval is the value assigned to the lower bound transform Tl , lowAngle is the corresponding angle of rotation for that transform, highval is the value assigned to the upper bound transform Th , highAngle is the corresponding angle of rotation for that transform, and rotateX and rotateY are the x and y of the point about which the rotation occurs.

Listing 2: Interpolation

percent = ( value – lowval ) / (highval – lowval);
angle = highAngle – lowAngle;

if (angle != 0)
{
    // remove the rotation difference between the transforms
    translate(Th, -rotateX, – rotateY);
    rotate(Th, -angle);
    translate(Th, rotateX, rotateY);
}

interpolate(Tl, percent, Th);

if (angle != 0)
{
    // compute the new angle
    angle *= percent;
    if (angle != 0)
    {
        //apply the new angle to our transform
        translate(Tl, -rotateX, -rotateY);
        rotate(Tl, angle);
        translate(Tl, rotateX, rotateY);
    }
}

It can be argued that this requires more code than simply taking the coordinate points that make up the needle and transforming them with a transform created by:

translate(T, -rotateX, -rotateY);
rotate(T, angle);
translate(T, rotateX, rotateY);

However, with interpolation, we must perform that same sequence twice. Once to remove the rotation component and once to put it back. The savings of interpolation occur when you have more than one needle gauge in your GUI. You only need to keep one copy of the needle gauge coordinates, regardless of how many gauges you have. The transforms are used to position those coordinates as you get values to display. Since an attractive vector graphic of a needle gauge takes many coordinate points, such savings can add up.

Interpolation trade-offs

The greatest drawback of using interpolations is that they use floating-point values. If you are running your embedded system without floating-point hardware, what kind of performance can you expect?

Several solutions can be employed for the floating-point problem. The first is to use a software floating-point emulation library. This is the easiest, but also the slowest, solution. The fastest solution is to use integer math with the transforms, but that requires more work. If you want rotations in your transforms, you must provide sine and cosine functions that work without floating point. The best way to do this is to provide tables of values for the functions, using a base multiplier. The values in the tables have already been multiplied by the multiplier, and when the calculation is complete, the value is divided by the multiplier. This same approach may be used for the values stored in the transforms and all of the graphic object's coordinates. If we choose a base multiplier of 1,024, all our values will be in 1/1,024 of a screen pixel. When the calculations are complete, we shift the resulting value right by 10 and convert it to actual pixels on the screen. The transform value 0.523 would be stored as 536. CPU's with 32-bit integers should see little or no loss of precision, given the range of values typically occuring in the transforms and screen coordinates. (For a more complete solution to this problem, check out the article “Fixed-Point Math in C” in the April 2001 issue of ESP .)

Is the RCGUI for you?

The concept of an RCGUI can be very appealing for several reasons. For one thing, a small graphics library with only lower-level drawing functions is easier to port than a large, complex GUI. The size reductions of reusing coordinate points between similar objects by using transforms saves code space, as does the ability to use the same code regardless of the animation or the type of object. Additionally, since you are building a custom GUI from primitive objects (such as lines and rectangles), you have complete control over the final appearance and behavior. This allows you to differentiate your product from the competition. Unlike desktops, embedded systems need GUIs that fit within certain constraints and display the interface in a way that is unique to the product.

Still, the RCGUI is not for everyone. If your embedded system requires a complicated user interface, a complex GUI is ideal because all the objects you need are provided. It would be much more difficult to reproduce that exact behavior from primitive objects. In systems without memory constraints or on projects where you lack the time to build a custom interface, a complex GUI may be best.

On the other hand, the RCGUI may be the faster solution if you have tools to support it. If you can draw your graphics and utilize a tool to generate the RCGUI code at a touch of a button, then RCGUI construction is undeniably faster. When code size is an issue and when you can afford to spend a little time handcrafting a custom interface, consider an RCGUI. By incorporating the use of 2D transforms and transform interpolation, significant size savings can be achieved.

Tom Batcha works for Altia, where he is the chief technical officer. He has been developing embedded software since he started working for HP 22 years ago. Tom holds an MS in computer science from Cal Poly San Luis Obispo and a BS in statistics from UC Davis. His e-mail address is .

Tom would like to thank Niall Murphy and Hannah Henry for their help with this article.

Return to December 2001 Table of Contents

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.