Advanced multi-dimensional region template class

• Download source code - 17.6 KB

Introduction

A couple of years ago, I had to write a sort of a video hook driver. And there, I needed (among other things) to handle region operations, such as finding intersections, subtracting, joining regions, and etc.

There's a support for such regions in Win32 API. Functions for manipulating regions are CreateRectRgn, CreateEllipticRgn, EqualRgn, GetRgnBox, OffsetRgn, CombineRgn, and etc. This API is pretty ugly and uncomfortable, in my opinion. Its implementation is concealed, and you have to mess with handles (HRGN) to work with it. When you need, for instance, to find an intersection of two regions, you have to create a new empty region handle, and then "fill" it with the intersection. That is:

// Find intersection of hRgn1 and hRgn2
HRGN hIntersect = CreateRectRgn(0, 0, 0, 0); // create an empty region
CombineRgn(hIntersect, hRgn1, hRgn2, RGN_AND);

Plus, if you want to iterate through the rectangles (of which the region consists), the API creates a copy of its data, whereas this is not always needed.

So, I didn't want to use it. However, I couldn't actually use it even if I wanted, because it's just not supported in the kernel mode. Hence, I decided to write my own implementation of regions.

Then, I created a pretty simple regions implementation. But recently, I had to work with regions again, and this time, I decided to make it more flexible and efficient.

Multi-dimensional template regions

Key features of this regions implementation:

1. The number of dimensions is the template parameter.
2. The coordinate type of each dimension is the template parameter as well.
3. The region is represented in terms of N-dimensional cubes.
4. In case of a 2-dimensional region with integer coordinates - it's a regular planar region, whereas the cube is identical to the RECT.
5. On every axis, the coordinates are organized in a binary search tree, so that all the operations (union, intersect, etc.) are done fast.
6. Handles well complex regions.

First, let's look at how to use the code. This is how the region class is defined:

template <typename T, class RgnInternal>
class Rgn_T;

The Rgn_T class has two template parameters: the type of the first coordinate and the base region class. This base class should be specified as follows:

• If no more dimensions - RgnNull.
• If more dimensions needed - use Rgn_T with its template parameters.

Here are some examples of the instantiation:

// One-dimensional region with 'double' coordinate
typedef Rgn_T<double, RgnNull> MyRgn;

// Two-dimensional region. 1st coordinate is 'float', second is 'int'
typedef Rgn_T<float, Rgn_T<int, RgnNull> > MyRgn;

In case all the dimensions use coordinates of the same type, there's a simplified definition:

template <typename T, int Dim>
class Rgn_Dim_T;

// 3-dimensional region, all the coordinates are 'long'
typedef Rgn_Dim_T<long, 3> MyRgn;

Those are types defined in the region class:

template <typename T, class RgnInternal>
class Rgn_T {
    // ...
public:

    // N-dimensional point
    struct Point
        :public RgnInternal::Point
    {
        T m_Value;
        // ...
    };

    // N-dimensional rectangular area.
    // Consists of two 'corner; points bounding the area.
    struct Cube {
        Point lo, hi; // low-hi
        // ...
    };

    // Class used to iterate through the region
    class Iterator
        :public Cube
        // ...
    {
    public:
        // ...
        bool Init(const Rgn_T& rgn);
        bool MoveNext();
    };
};

The key type is Point. It is, as its name suggests, a point in the N-dimensional space. The value of the specific coordinate is accessed this way:

MyRgn::Point p;
p.get_Level<0>() = 0.0f; // 1st coordinate
p.get_Level<1>() = 44; // 2nd coorinate
p.get_Level<2>() = 12.76; // 3rd coorinate

And, Cube represents an N-dimensional rectangular area. It consists of two Points describing the 'corner' points of the specified area. These are the operations supported for regions:

void Clear():
bool IsEmpty() const;
void AddCube(const Cube&);
bool GetBounds(Cube& c) const; // get the bounding box of the region
// If empty - returns false and zeroes 'c'
void Offset(const Point&); // Offset (move) the region by the given increment

bool IsEqual(const Rgn_T&) const;
void Swap(Rgn_T& rgn);

bool CubeInsidePart(const Cube& c) const; // Is a part of 'c' inside the region
bool CubeInsideFull(const Cube&c) const; // Is 'c' totally inside the region
bool PtInside(const Point&) const; // Is this point inside the region

void Subtract(const Rgn_T&);
void SubtractEx(const Rgn_T& rgn, Rgn_T& rgnIntersect);
// Same as above, the removed part
// is added to 'rgnIntersect'
void Copy(const Rgn_T&);
void Intersect(const Rgn_T&);
void Combine(const Rgn_T&);

In general, this class gives the functionality you'd expect from such a class - all kinds of 'raster' operations, iteration through Cubes, boolean tests (such as PtInside).

Note: its interface is described in terms of Point and Cube. There's no direct mention of coordinates.

For simplicity, let's look at a couple of examples:

typedef Rgn_Dim_T<int, 1> MyRgn; // 1-dimensional, integer

MyRgn rgn1, rgn2;

MyRgn::Cube c;
c.lo.get_Level<0>() = 1;
c.hi.get_Level<0>() = 100;
rgn1.AddCube(c); // [1 .. 100]

c.lo.get_Level<0>() = 32;
c.hi.get_Level<0>() = 711;
rgn2.AddCube(c); // [32 .. 711]

rgn1.Intersect(rgn2); // intersect rgn1 by rgn2.

rgn1.GetBounds(c); // get the bounding (should be [32 .. 100]

This is a bit more complex example. Here, the regions are 2-dimensional. Note: here at some point, we actually iterate through one of the regions, not just take its bounding box.

typedef Rgn_Dim_T<int, 2> MyRgn; // 2-dimensional, integer

MyRgn rgn1, rgn2;

MyRgn::Cube c;
c.lo.get_Level<0>() = 1;
c.lo.get_Level<1>() = 10;
c.hi.get_Level<0>() = 100;
c.hi.get_Level<1>() = 15;
rgn1.AddCube(c);

c.lo.get_Level<0>() = 32;
c.lo.get_Level<1>() = 12;
c.hi.get_Level<0>() = 711;
c.hi.get_Level<1>() = 300;
rgn2.AddCube(c);

rgn1.Combine(rgn2);

MyRgn::Iterator it;
for (it.Init(rgn1); it; it.MoveNext())
{
    const MyRgn::Cube& curCube = it;
    // do something...
}

Here, we should eliminate one ambiguity. There're actually several ways to divide a region into Cubes. Our region class does this division by the order of coordinates. The first coordinate is divided into segments; then, inside every segment, the second coordinate is divided into sub-segments, and so on.

For example, we provide a 2-dimensional region here. Depending on how the X,Y coordinates are interpreted, the partition will be different

Actual region	level<0>=X, level<1>=Y	level<0>=Y, level<1>=X

If such a region is used for drawing, the second option is preferred. That is, level<0> should represent the Y coordinate, and level<1> should be X. By this, we get longer horizontal lines, and this is preferable for drawing (drawing algorithms usually work for scan lines, where adjacent pixels on the line are consequent in memory).

Comparison with GDI regions

First of all, this comparison is not fair, because our regions are multi-dimensional with any coordinate type, so that their usage is far wider. However, we may instantiate a 2-dimensional region with long coordinates, which is equivalent (in some sense) to the GDI region. This is where we may compare our regions with GDI ones.

Actually, GDI regions, as discovered, are implemented in a way similar to our regions, where Y is the first coordinate and X is the second one. That is, the whole region is divided into segments of Y coordinates, and inside every such segment, there're sub-segments of X coordinates. In particular, our regions produce exactly the same partition as GDI ones (I even used this fact in the Unit Tests).

There's a big difference, however, in how ours and GDI regions are stored in memory. Our region segments are dynamically-allocated nodes stored in the binary tree structure. Whereas GDI stores its segments in arrays, and the whole GDI region data is one solid memory block of those consequent arrays. Because of this, GDI regions take significantly less memory. Plus, in my opinion, they can be constructed faster (by ExtCreateRegion), because one big allocation is faster than many small ones.

But this method has its drawbacks too. Regions stored in such a way can't be modified! That is, if you want to perform an operation on a region (for example, add a rectangle to it), you just can't do this! Instead, you can only construct a new region which will be a union of that region and the specified rectangle. This also explains (partially) why the GDI API for regions looks so awkward. In contrast, our regions offer efficient modification.

Another disadvantage of GDI regions is that their implementation is concealed. To look 'inside' the region, you have to call GetRegionData, which creates a copy of the region. Actually, I have no idea why the implementation is concealed. GDI regions are implemented in user mode!

Let's summarize:

In favor of GDI regions:

• Better memory utilization (especially for huge regions)
• Can be constructed faster
• Generic for drawing: most of the GDI drawing functions work with respect to the currently-selected region

In favor of our regions:

• Flexible: can be used for arbitrary number of dimensions and coordinate types
• Nice and friendly API (in contrast to the extremely ugly GDI API)
• Allows in-place modification of the region; as a result, adjustments of a complex region are much faster
• Explicit iteration doesn't require copying the region (which is really stupid, in my opinion)
• Can also be used for drawing, though not in a generic way (during the iteration, must call drawing functions repeatedly for each region in the partition)
• More functionality: can test if a specified rectangle is totally or partially contained in the region; GDI just has RectInRegion which is a partial variant
• Tend to be faster for small regions (less overhead); in particular, creating an empty region object is trivial

Conclusion

I hope some people will find this region class useful. Maybe for implementation of some mathematical algorithms, the N-dimensionality and the ability to work in floating-point coordinates are useful.

I use this for drawing in the kernel mode. There, the GDI API is inaccessible, but even if it was accessible, I'd prefer this implementation. Although the GDI regions do have some advantages - for my specific case, our regions are better suited.

Actually, after Ie implemented (and used for some time) those regions, and before writing this article, I took time to learn how GDI regions are implemented. And, I was really surprised by the discovery. Then, I realized why the GDI API for regions looks like it looks. It just reflects the way the regions are implemented in GDI.

Is our implementation better? Well, this depends on how the regions are intended to be used. After I realized how GDI implemented its regions, I thought about making an additional implementation for my regions too, which will be better for some specific cases.

Nevertheless, the difference in the implementation will affect the performance only for very extensive use of huge regions. And from the flexibility and usability point of view, our implementation looks very much better.

By the way, if you want to look at the code level of the regions implementation, you should read this article about container classes. Its yet another demonstration of their flexibility.

Criticism and new ideas are welcome, as usual.