2011. május 21., szombat

BitmapToRegion (Delphi-like version - very fast)


Problem/Question/Abstract:

How to convert Windows Bitmaps to Windows Regions very fast. This is the Delphi-like replacement for the BitmapToRegion function. This version is much cleaner, smaller and educational mantaining a high performance. You will also find many interesting comments and techniques inside.

Answer:

Overview

The function BitmapToRegion creates a Windows Region (HRGN) from a Windows Bitmap (HBITMAP) which is used as a mask. You choose one color to be made "transparent", meaning that areas of the bitmap with this color will be left out of the resulting region. This region will take the shape of the "non-transparent" pixels from the original bitmap, which may or may not have a regular shape. You can later apply this region to any window (all windowed controls including the form) using the SetWindowRgn API call. Using this method you can create non-rectangular forms or controls easily. The function also accepts a color tolerance for red, green, and blue values which means that a color range could be specified rather than only one color.

How it works?

The function iterates over all the bitmap scanlines searching for contiguous non-transparent pixels on a row-by-row basis.

It keeps record of the last visible pixel position on the row and loops until a transparent pixel is found or the end of the row reached. Variable "x0" holds the last visible pixel position and "x" holds the current pixel position. If x0 = x it means that the current pixel is transparent and must be ignored, if x > x0 then we have at least one visible pixel.

We then add a rect containing the pixels (x0,y) to (x,y+1) to a windows structure RGNDATA which is passed to the function ExtCreateRegion, later used to create the desired region (the RGNDATA is explained later on this article). The variable y holds the current row being scanned. If we aren't yet at the end of the row we will make x0 = x and will restart looping until another transparent pixel is found or the end of the row reached (doing the same procedures again). If the end of the row is finally reached we will jump to the next bitmap row, starting with x0 = x = 0.

By doing this to the entire bitmap we will end up with the desired visible region.

Problems found

** Windows 98 Limitations
Using this function on Windows 98 could fail with very complex masks (bitmaps). That is due to a limitation on ExtCreateRegion under this OS: the function fails if the number of rects is too large. To workaround this, every time the number of rects reachs 2000, we call ExtCreateRegion and store it in Result (if it is the first region created) or we combine this region with the one already created.

** Accessing the RGNDATA rects by index
The region data is made up of a RGNDATAHEADER which specifies the type and size of the region plus a buffer of arbitrary size called Buffer (brilliant!). The problem is that we need to access Buffer as if it was an Array of Rects, but it is defined as:

Buffer: array[0..0] of CHAR;

This is a very commom C construct actually denoting a char pointer (char *), but Pascal is a far more strong typed language preventing us from accessing this array directly. The easiest way to access the rects on this buffer is by typecasting it to a more convenient structure like:

TRectArray = array[0..(MaxInt div SizeOf(TRect)) - 1] of TRect;

This creates the largest possible array of TRect elements. Do not attempt to create a variable of this type because you will certainly exhaust system resources. It is meant to be used for typecasting variables only (or a pointer contents: TRectArrat(MyPrt^)[x] not TRectArray(MyPtr)[x]!). If we did declare a pointer to this structure, we will be able to typecast another pointer without having to dereference it:

PRectArray = ^TRectArray;

Now the following statement is correct: PRectArray(MyPtr)[x]. We can make a variable of type PRectArray (let's say pr) point to Buffer with the simple statement: pr := @RgnData.Buffer; This technique can be used to simplify and clarify your code the same way it is used here.

** Bitmap Orientation and Scanline Access
The code:

ScanLinePtr := bmp.ScanLine[0];
ScanLineInc := Integer(bmp.ScanLine[1]) - Integer(ScanLinePtr);

is very tricky. The first line gets a pointer to the first bitmap scanline. The second line gets the (signed) distance in bytes that separates the bitmap scanlines in memory (scanlines need not to be contiguos in memory). If the bitmap is bottom-up the distance will be negative. When we make Inc(Integer(ScanLinePtr),ScanLineInc) we are already taking into account this possibility (Inc with negative values actually decrements).

The access to individual pixels are made using the techniques shown earlier on "Accessing the RGNDATA rects by index". We find the value of the xth character by typecasting ScanLinePrt to PByteArray at the index [x*SizeOf(TRGBQuad)]. TRGBQuad is an structure of red, green, blue, plus an extra byte that represents a pixel for a 32-bit RGB image. We then make b point to this element of the array. Since b is itself a PByteArray, we can access its individual bytes by index where the first (0) is red, the second is green, and the last (2) is blue (we do not use the fourth byte). The code is as follows:

b := @PByteArray(ScanLinePtr)[x * SizeOf(TRGBQuad)];
if (b[0] >= lr) and (b[0] <= hr) and
  (b[1] >= lg) and (b[1] <= hg) and
  (b[2] >= lb) and (b[2] <= hb) then
  ...

Rationales

** Use of RGNDATA and ExtCreateRegion:
Speed! Speed is one of the main concerns of this algorithm. We could have made the code much simpler if we used CreateRectRgn for every rect found and combined them one-by-one with CombineRgn instead of adding rects to a RGNDATA and later calling ExtCreateRegion to create the region at once, but ExtCreateRegion is much faster than the combined use of CreateRectRgn and ComineRgn.

** Use of AllocUnit
Performance again is the factor of choice of this added complexity. We could allocate memory as needed, one rect at a time, but it is much faster to allocate a chunk of rects (even if we ended up with unused memory) and only do memory reallocation (expansion) when we run out of space (we catch this when we test if RgnData^.rdh.nCount >= maxRects). In the end all data (even unused) is freed.

** Use of Scanline Instead of Pixels property Scanline is a hundred times faster than Pixels property for accessing the pixels of a bitmap.

** 32-bit Depth Conversion
I have chosen to convert every bitmap to pf32bit first to be able to deal uniformly with the bitmap data, no need to have a special case for every pixel format and since the algorithm is meant to be used only with RGB images (not palette indexed) it was a matter of choosing between pf24bit and pf32bit. Second because Windows being a 32-Bit environment is faster when dealing with 32-bit per pixel bitmaps.

Conclusion

This article provided a very fast Delphi friendly routine to convert bitmaps into windows regions. These regions could be used to apply astonishing effects to your forms simply by making them non-rectangular and decorated art painted over the visible areas (if you ever saw the Quintessential CD player or the new apple Quicktime interface you know what I mean).

You will also find inside a discussion on some Windows 98 limitations regarding complex region creation and the best (fastest) method to use the TBitmap Scanline property to access the pixels of an image. There's also some comments on how to access arbitrary sizeable structs often found in C/C++ code from within Delphi.

Final Comments

This function is used by a component which I wrote called TFormShapper to apply persintent non-regular shapes to forms. The component has a mask property of type TPicture that stores the picture along with the form. This picture can be any valid TGraphic descendant (including my own TPNGImage or TTGAImage implementations). All I did to use it as a bitmap was to create a temporary bitmap and draw the stored graphic over it with: tmpBMP.Canvas.Draw(0, 0, TheGraphic); then I passed this tmpBMP to the function, freeing it later to release memory and system resources. You can use this technique if you have any image that is not a TBitmap, but that could be drawn over one.

My next post will regard the techniques used to extend the graphics capabilities of Delphi, adding new image file formats and creating a new derived TGraphic class. Stay tuned.

--- CODE STARTS HERE ---

function BitmapToRegion(bmp: TBitmap; TransparentColor: TColor = clBlack;
  RedTol: Byte = 1; GreenTol: Byte = 1; BlueTol: Byte = 1): HRGN;
const
  AllocUnit = 100;
type
  PRectArray = ^TRectArray;
  TRectArray = array[0..(MaxInt div SizeOf(TRect)) - 1] of TRect;
var
  pr: PRectArray; // used to access the rects array of RgnData by index
  h: HRGN; // Handles to regions
  RgnData: PRgnData; // Pointer to structure RGNDATA used to create regions
  lr, lg, lb, hr, hg, hb: Byte; // values for lowest and hightest trans. colors
  x, y, x0: Integer; // coordinates of current rect of visible pixels
  b: PByteArray; // used to easy the task of testing the byte pixels (R,G,B)
  ScanLinePtr: Pointer; // Pointer to current ScanLine being scanned
  ScanLineInc: Integer; // Offset to next bitmap scanline (can be negative)
  maxRects: Cardinal; // Number of rects to realloc memory by chunks of AllocUnit
begin
  Result := 0;
  { Keep on hand lowest and highest values for the "transparent" pixels }
  lr := GetRValue(TransparentColor);
  lg := GetGValue(TransparentColor);
  lb := GetBValue(TransparentColor);
  hr := Min($FF, lr + RedTol);
  hg := Min($FF, lg + GreenTol);
  hb := Min($FF, lb + BlueTol);
  { ensures that the pixel format is 32-bits per pixel }
  bmp.PixelFormat := pf32bit;
  { alloc initial region data }
  maxRects := AllocUnit;
  GetMem(RgnData, SizeOf(RGNDATAHEADER) + (SizeOf(TRect) * maxRects));
  try
    with RgnData^.rdh do
    begin
      dwSize := SizeOf(RGNDATAHEADER);
      iType := RDH_RECTANGLES;
      nCount := 0;
      nRgnSize := 0;
      SetRect(rcBound, MAXLONG, MAXLONG, 0, 0);
    end;
    { scan each bitmap row - the orientation doesn't matter (Bottom-up or not) }
    ScanLinePtr := bmp.ScanLine[0];
    ScanLineInc := Integer(bmp.ScanLine[1]) - Integer(ScanLinePtr);
    for y := 0 to bmp.Height - 1 do
    begin
      x := 0;
      while x < bmp.Width do
      begin
        x0 := x;
        while x < bmp.Width do
        begin
          b := @PByteArray(ScanLinePtr)[x * SizeOf(TRGBQuad)];
          // BGR-RGB: Windows 32bpp BMPs are made of BGRa quads (not RGBa)
          if (b[2] >= lr) and (b[2] <= hr) and
            (b[1] >= lg) and (b[1] <= hg) and
            (b[0] >= lb) and (b[0] <= hb) then
            Break; // pixel is transparent
          Inc(x);
        end;
        { test to see if we have a non-transparent area in the image }
        if x > x0 then
        begin
          { increase RgnData by AllocUnit rects if we exceeds maxRects }
          if RgnData^.rdh.nCount >= maxRects then
          begin
            Inc(maxRects, AllocUnit);
            ReallocMem(RgnData, SizeOf(RGNDATAHEADER) + (SizeOf(TRect) * MaxRects));
          end;
          { Add the rect (x0, y)-(x, y+1) as a new visible area in the region }
          pr := @RgnData^.Buffer; // Buffer is an array of rects
          with RgnData^.rdh do
          begin
            SetRect(pr[nCount], x0, y, x, y + 1);
            { adjust the bound rectangle of the region if we are "out-of-bounds" }
            if x0 < rcBound.Left then
              rcBound.Left := x0;
            if y < rcBound.Top then
              rcBound.Top := y;
            if x > rcBound.Right then
              rcBound.Right := x;
            if y + 1 > rcBound.Bottom then
              rcBound.Bottom := y + 1;
            Inc(nCount);
          end;
        end; // if x > x0
        { Need to create the region by muliple calls to ExtCreateRegion, 'cause }
        { it will fail on Windows 98 if the number of rectangles is too large   }
        if RgnData^.rdh.nCount = 2000 then
        begin
          h := ExtCreateRegion(nil, SizeOf(RGNDATAHEADER) + (SizeOf(TRect) *
            maxRects), RgnData^);
          if Result > 0 then
          begin // Expand the current region
            CombineRgn(Result, Result, h, RGN_OR);
            DeleteObject(h);
          end
          else // First region, assign it to Result
            Result := h;
          RgnData^.rdh.nCount := 0;
          SetRect(RgnData^.rdh.rcBound, MAXLONG, MAXLONG, 0, 0);
        end;
        Inc(x);
      end; // scan every sample byte of the image
      Inc(Integer(ScanLinePtr), ScanLineInc);
    end;
    { need to call ExCreateRegion one more time because we could have left    }
    { a RgnData with less than 2000 rects, so it wasn't yet created/combined  }
    h := ExtCreateRegion(nil, SizeOf(RGNDATAHEADER) + (SizeOf(TRect) * MaxRects),
      RgnData^);
    if Result > 0 then
    begin
      CombineRgn(Result, Result, h, RGN_OR);
      DeleteObject(h);
    end
    else
      Result := h;
  finally
    FreeMem(RgnData, SizeOf(RGNDATAHEADER) + (SizeOf(TRect) * MaxRects));
  end;
end;

I've supplied a couple of simple examples of using this function for beginners:

{This first example sets the region of a TForm}

procedure TForm1.Button1Click(Sender: TObject);
var
  ARgn: HRGN;
  ABitmap: TBitmap;
begin
  ABitmap := TBitmap.Create;
  try
    ABitmap.LoadFromFile('C:\MyImage.bmp');
    ARgn := BitmapToRegion(ABitmap, clFuchsia);
    SetWindowRgn(Form1.Handle, ARgn, True);
  finally
    ABitmap.Free;
  end;
end;

{This second example sets the region of a TPanel}

procedure TForm1.Button1Click(Sender: TObject);
var
  ARgn: HRGN;
  ABitmap: TBitmap;
begin
  ABitmap := TBitmap.Create;
  try
    ABitmap.LoadFromFile('C:\MyImage.bmp');
    ARgn := BitmapToRegion(ABitmap, clFuchsia);
    SetWindowRgn(Panel1.Handle, ARgn, True);
  finally
    ABitmap.Free;
  end;
end;

From both examples, you can see how simple it is to simply specify the Handle of the window control that you wish to set the region of. Be it a TForm, TPanel, TMemo, etc.

Nincsenek megjegyzések:

Megjegyzés küldése