Custom light-weight regions

• Download source files - 5.35 Kb

Introduction

Have you ever worked with GDI regions? If you haven't - I'll tell you: they suck. Really!

The API is so uncomfortable that in some cases you have to write tens of lines for relatively simple things, not to speak about complicated tasks. Also, it is very easy to create 'regions leaks'. In particular, usually in order to get some region (either from the window/DC or as the result from logical operation on another regions), you create a dumb region handle, such as CreateRectRgn(0, 0, 0, 0), and only then OS can fill it with what you need.

Most of the programmers (at least those I know) even never use regions to optimize window redraws. For instance, when receiving the WM_PAINT message, you can query the area that needs updating by GetUpdateRgn() function (this must be done prior to calling BeginPaint), and then redraw only necessary parts. If you want to paint some animation in your window, you could invalidate relevant regions of your window (upon animation), and repaint exactly affected areas on WM_PAINT message.

But those techniques are pretty rarely used. When you call BeginPaint() function, you receive the bounding update rectangle in the PAINTSTRUCT, whereas it�d better be the exact region. In most of the MFC�s drawing callbacks (such as OnDraw) also, usually only bounding rectangle is provided. Even more ridiculous fact: bit block transfer functions (such as BitBlt, PatBlt, MaskBlt) ignore the clipping region selected to the DC! Regions are considered something too complex to involve.

That is barbarity! Drawing operations are far heavier than simple arithmetic operations needed for region handlings. I started using regions extensively when I had to create a game with a lot of animations (for pocket PC), and suffered from its dumb API. But later, I started another project that had to use regions very heavily where part of it had to run in the kernel mode, where standard GDI API is inaccessible (at least I don�t know how). Then I decided to write my own regions.

Custom regions implementation

When working on my implementation, I had the following criteria: each region should be represented by a C++ light-weight object. Also, regions in my case should not be too complex in general.

Hence I decided that regions should be held as a linked list of rectangles with integer coordinates. (If you need them for floating-point calculations, you can easily modify the original implementation for your needs.) The advantage of such a method is that it is scale-independent: we need the same amount of resources and CPU time to handle rectangles 10x10 and 1000x1000. However, everything has its price. This method should not be used where regions are too complicated within relatively small area. A good example of such a case can be definition of a glyph (a single font character) through region of its pixels. In this case, a monochrome DIB would be far more efficient.

All rectangles within the region must obey the following rules:

1. They must be well-ordered. Meaning that right>left and bottom>top.
2. They are bottom-right exclusive. Means that if top=10 and bottom=20, then included lines are from 10 to 19, excluding 20. Same about right threshold.
3. They must not intersect. However, they can be adjacent. For example, left=5 and right=10 in first rectangle, and left = 10 and right = 15 in second one.
4. No assumption is made about how they are sorted.

OK, a good start. Next, we have to implement logical operations for our regions, such as intersection, union and etc. First of all goes the implementation of subtraction of a rectangle from another one. The algorithm is the following:

1. If rectangles don�t intersect then we have nothing to do.
2. If those rectangles do intersect then we erase our initial rectangle (but possibly add other ones).
3. For each side of the cutter (left, top, right, and bottom), we check if it lies within our original rectangle. If it does � indeed there is a part of the original rectangle that is not obscured by the cutter. Hence we add this part.

So that in the end of this operation, we can either receive nothing (the original rectangle is totally obscured), or up to 4 rectangles (if the cutter erased the interior).

Using this operation, we can extend it to subtraction of one region from another, all we need is to perform this operation for every pair of rectangles, one from the first region, and one from the second. This is also called RGN_DIFF operation.

Union (logical OR): We can�t just append one region to another, because it would violate our rule that rectangles within a region must not intersect. We first subtract one region from another, and than append it. In such a way, we unite regions.

Intersection (logical AND): Similar to subtraction, except that the initial rectangle that we have to discard during subtraction � we�d rather truncate it (not to exceed the cutter) and collect them somewhere. In fact, they form region of the intersection.

Logical XOR operation: It can be produced as union of two subtractions of the source regions respectively.

And so on. So, as you can see, we managed to implement all logical operations within our regions via a single subtraction operation for two arbitrary rectangles. Now, about the performance: easy to see that the complexity of operations is sqr(N). Theoretically, it could be reduced to almost N if we could assume something about how our rectangles are ordered. But in my particular case, it was absolutely insignificant. Consider you have two regions, even 100 rectangles in each. Any binary operation will take up to 10000 our iterations, which are very fast and simple. Plus the memory overhead is tolerable: each region contains only a pointer to the rectangles chain (4 bytes on WIN32), and each rectangle node has a pointer to the next one, thus increasing its size by 25%.

Now, we have to solve one last problem: the most basic our operation is a subtraction. During it, large rectangles are broken into smaller ones, but it never works in another direction. Even when we unite regions (where we could expect creation of large rectangle areas) in fact everything works via subtraction. So, after a lot of logical operations, our regions degenerate into a linked list of pixels with all unpleasant consequences, which are increased memory and CPU usage. Also, at some point, we usually want to walk through the resulting list of rectangles to perform some operations (drawing, for instance). Doing so for each pixel would be awful. Plus there is an ambiguity: the same area can be represented by different rectangle pieces.

So, we have to invent one more operation for our regions: bringing them to a canonical form. Let�s define it in the following way:

1. All rectangles must be as wide as possible.
2. Rectangles should be also as tall as possible, unless it affects their width.
3. To solve the ambiguity, the rectangles should be ordered, say from top to bottom and then from left to right.

Why do I insist on the width? Because, in my case, I used regions for drawing, and most of the drawing algorithms work on scan lines, horizontally.

Well, how do we do that? The algorithm is the following:

1. We sort all rectangles by their �top� member.
2. Divide rectangles vertically until there is no overlapping on the vertical axis. This means that after we finish, there must not be a situation where either �top� or �bottom� member of one rectangle lies between �top� and �bottom� of another one. At this stage, in fact we have stripes, several rectangles with the same �top� and �bottom� members, and with different �left� and �right� of course.
3. On every such a stripe, we sort rectangles horizontally.
4. Time to unite. We walk through every stripe, and unite rectangles there if they are adjacent. After we finish, we�d still have stripes, but more solid (without unneeded fragmentations).
5. Finally, we seek and unite stripes that are adjacent vertically and equal horizontally.

That is all. Not too complex. Bringing regions to a canonical form also enables us to compare them quickly, by just comparing all rectangles in their chain.

Tips and precautions

The main precaution is about SubstractEx() function. It is described in the interface file. Improper use of this function can lead to a corrupted region. And once the region is corrupted (contains internal intersections) � its behavior is unpredictable. It can crash or hang within Optimize() function.

Consider you want to optimize your window�s redrawing. First of all, you�d want to obtain the update region. Perhaps the following code will be useful:

void GetWndUpdateRgn(HWND hWnd, CRgnLight& rgnValue)
{
    HRGN hRgn = CreateRectRgn(0, 0, 0, 0);
    if (hRgn)
    {
        switch (GetUpdateRgn(hWnd, hRgn, FALSE))
        {
            case SIMPLEREGION:
            case COMPLEXREGION:
                rgnValue.FromGdi(hRgn);
        }
        VERIFY(DeleteObject(hRgn));
    }
}

Next comes the drawing itself. Suppose you paint something, the rest must be filled with the background brush.

void MyDraw(HWND hWnd)
{
    // Get the update region. You have to do it BEFORE calling BeginPaing()

    CRgnLight rgnClip;
    GetWndUpdateRgn(hWnd, rgnClip);

    // start drawing

    CRgnLight rgnShape;
    rgnShape.AddRect(20, 20, 70, 38);
    // say that's where your shape should be placed :)


    CRgnLight rgnFinal;
    rgnClip.SubstractEx(rgnShape, rgnFinal);

    // by now the rgnFinal contains the exact part of the rgnShape1 that has

    // to be drawn, and this part is excluded from the rgnClip

    // NOTE: Don't forget to optimize regions before drawing.

    rgnFinal.Optimize();
    for (const RECT* pRect = rgnFinal.GetFirst(); 
           pRect; pRect = CRgnLight::GetNext(pRect))
    {
        // paint the rectangle piece of your shape

    }

    // draw another shape:

    rgnShape.Clear();
    rgnFinal.Clear();
    rgnShape.AddRect(90, 20, 112, 70);
    rgnClip.SubstractEx(rgnShape, rgnFinal);
    rgnFinal.Optimize();
    for (pRect = rgnFinal.GetFirst(); 
        pRect; pRect = CRgnLight::GetNext(pRect))
    {
        // paint the rectangle piece of your shape

    }

    // And so on. At the end - don't forget to paint the background.

    // It is left in the rgnClip object.

    rgnClip.Optimize();
    for (pRect = rgnClip.GetFirst(); 
            pRect; pRect = CRgnLight::GetNext(pRect))
        VERIFY(PatBlt(
                  hDC,
                  pRect->left,
                  pRect->top,
                  pRect->right - pRect->left,
                  pRect->bottom - pRect->top,
                  PATCOPY));
}

As I�ve already mentioned, GDI�s raster bit block transfer functions ignore the region selected into the DC. So, this function can be useful too:

void ClippedCopy(HDC hDst, HDC hSrc, 
    int nSrcX, int nSrcY, const CArlRgn& rgnClip)
{
    for (const RECT* pRect = rgnClip.GetFirst(); 
               pRect; pRect = rgnClip.GetNext(pRect))

        VERIFY(BitBlt(
            hDst,
            pRect->left - nSrcX,
            pRect->top - nSrcY,
            pRect->right - pRect->left,
            pRect->bottom - pRect->top,
            hSrc,
            pRect->left,
            pRect->top,
            SRCCOPY));
}

That�s all I can remember just on the fly. But there are a lot of more uses. Hope you�ll enjoy this.