wmlbinary2d.cpp

来自「3D Game Engine Design Source Code非常棒」· C++ 代码 · 共 985 行 · 第 1/3 页

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlBinary2D.h"
#include "WmlMath.h"
using namespace Wml;
using namespace std;

//----------------------------------------------------------------------------
Binary2D::Binary2D (int iXBound, int iYBound, Eint* atData)
    :
    ImageInt2D(iXBound,iYBound,atData)
{
}
//----------------------------------------------------------------------------
Binary2D::Binary2D (const Binary2D& rkImage)
    :
    ImageInt2D(rkImage)
{
}
//----------------------------------------------------------------------------
Binary2D::Binary2D (const char* acFilename)
    :
    ImageInt2D(acFilename)
{
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// Extraction of boundary from binary objects in image.
//
// Directions are:  W=0, NW=1, N=2, NE=3, E=4, SE=5, S=6, SW=7.  If a pixel
// was reached from the direction indicated, then its eight neighbors are
// searched in the order shown:
//
//     W      NW     N      NE     E      SE     S      SW
//     0 1 2  7 0 1  6 7 0  5 6 7  4 5 6  3 4 5  2 3 4  1 2 3
//     7 * 3  6 * 2  5 * 1  4 * 0  3 * 7  2 * 6  1 * 5  0 * 4
//     6 5 4  5 4 3  4 3 2  3 2 1  2 1 0  1 0 7  0 7 6  7 6 5
//
// The formula for the next direction is:  newdir = (index+5+olddir) MOD 8
// where index is the number of the neighbor in the search.  For example, in
// the configuration,
//
//   010
//   010
//   001
//
// suppose the center pixel was reached from the North (olddir=2).  Neighbors
// at index=0 and index=1 are zero.  The first nonzero neighbor is at index=2.
// Thus, newdir = (2+5+2) MOD 8 = 1, so the direction from which the next
// pixel is reached is NorthWest.
//
// One-pixel thick structures are treated as having more thickness in the
// sense that they are traversed twice, once per "side".
//----------------------------------------------------------------------------
int* Binary2D::GetBoundaries () const
{
    // Create a temporary copy of image to store intermediate information
    // during boundary extraction.  The original image is embedded in an
    // image with two more rows and two more columns so that the image
    // boundary pixels are properly handled.
    ImageInt2D kTemp(GetBound(0)+2,GetBound(1)+2);  // initially zero
    int iX, iY, iXP, iYP;
    for (iY = 0, iYP = 1; iY < GetBound(1); iY++, iYP++)
    {
        for (iX = 0, iXP = 1; iX < GetBound(0); iX++, iXP++)
            kTemp(iXP,iYP) = ( (*this)(iX,iY) ? 1 : 0 );
    }

    // Label interior pixels as 2.  Exterior pixels are then 0, boundary
    // pixels are then 1.
    for (iY = 1; iY+1 < kTemp.GetBound(1); iY++)
    {
        for (iX = 1; iX+1 < kTemp.GetBound(0); iX++)
        {
            if ( kTemp(iX,iY) && kTemp(iX-1,iY) && kTemp(iX+1,iY)
            &&   kTemp(iX,iY-1) && kTemp(iX,iY+1) )
            {
                kTemp(iX,iY) = 2;
            }
        }
    }

    // Search image for boundary points and extract the full boundaries.
    vector<BoundaryList*> kBoundaries;
    for (iY = 0; iY < kTemp.GetBound(1); iY++)
    {
        for (iX = 0; iX < kTemp.GetBound(0); iX++)
        {
            if ( kTemp(iX,iY) == 1 )
                kBoundaries.push_back(ExtractBoundary(iX,iY,kTemp));
        }
    }

    // Repackage lists into a single array.
    int iSize = 1;  // make room for boundary count
    int i;
    for (i = 0; i < (int)kBoundaries.size(); i++)
        iSize += (int)kBoundaries[i]->size() + 1;

    int* aiPacked = new int[iSize];
    aiPacked[0] = (int)kBoundaries.size();
    int iIndex = 1;
    for (i = 0; i < (int)kBoundaries.size(); i++)
    {
        BoundaryList* pkBoundary = kBoundaries[i];

        aiPacked[iIndex++] = (int)pkBoundary->size();
        for (int j = 0; j < (int)pkBoundary->size(); j++)
            aiPacked[iIndex++] = (*pkBoundary)[j];

        delete pkBoundary;
    }

    return aiPacked;
}
//----------------------------------------------------------------------------
Binary2D::BoundaryList* Binary2D::ExtractBoundary (int iX0, int iY0,
    ImageInt2D& rkTemp) const
{
    static const int s_aiDx[8] = { -1,  0, +1, +1, +1,  0, -1, -1 };
    static const int s_aiDy[8] = { -1, -1, -1,  0, +1, +1, +1,  0 };

    // Create new point list containing first boundary point.  Note that the
    // index for the pixel is computed for the original image, not for the
    // larger temporary image.
    BoundaryList* pkBoundary = new BoundaryList;
    pkBoundary->push_back(GetIndex(iX0-1,iY0-1));

    // Compute the direction from background (0) to boundary pixel (1).
    int iCx = iX0, iCy = iY0;
    int iNx, iNy, iDir;
    for (iDir = 0; iDir < 8; iDir++)
    {
        iNx = iCx + s_aiDx[iDir];
        iNy = iCy + s_aiDy[iDir];
        if ( rkTemp(iNx,iNy) == 0 )
        {
            iDir = (iDir+1)%8;
            break;
        }
    }

    // Traverse boundary in clockwise order.  Mark visited pixels as 3.
    rkTemp(iCx,iCy) = 3;
    while ( true )
    {
        int i, iNbr;
        for (i = 0, iNbr = iDir; i < 8; i++, iNbr = (iNbr+1)%8)
        {
            iNx = iCx + s_aiDx[iNbr];
            iNy = iCy + s_aiDy[iNbr];
            if ( rkTemp(iNx,iNy) )  // next boundary pixel found
                break;
        }

        if ( i == 8 )  // (iCx,iCy) is isolated
            break;

        if ( iNx == iX0 && iNy == iY0 )  // boundary traversal completed
            break;

        // (iNx,iNy) is next boundary point, add point to list.  Note that
        // the index for the pixel is computed for the original image, not
        // for the larger temporary image.
        pkBoundary->push_back(GetIndex(iNx-1,iNy-1));

        // mark visited pixels as 3
        rkTemp(iNx,iNy) = 3;

        // start search for next point
        iCx = iNx;
        iCy = iNy;
        iDir = (i+5+iDir)%8;
    }

    return pkBoundary;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// Connected component labeling.
//
// The 1D connected components of each row are labeled first.  The labels
// of row-adjacent components are merged by using an associative memory
// scheme.  The associative memory is stored as an array that initially
// represents the identity permutation M = {0,1,2,...}.  Each association of
// i and j is represented by applying the transposition (i,j) to the array.
// That is, M[i] and M[j] are swapped.  After all associations have been
// applied during the merge step, the array has cycles that represent the
// connected components.  A relabeling is done to give a consecutive set of
// positive component labels.
//
// For example:
//
//     Image       Rows labeled
//     00100100    00100200
//     00110100    00330400
//     00011000    00055000
//     01000100    06000700
//     01000000    08000000
//
// Initially, the associated memory is M[i] = i for 0 <= i <= 8.  Background
// label is 0 and never changes.
// 1. Pass through second row.
//    a. 3 is associated with 1, M = {0,3,2,1,4,5,6,7,8}
//    b. 4 is associated with 2, M = {0,3,4,1,2,5,6,7,8}
// 2. Pass through third row.
//    a. 5 is associated with 3, M = {0,3,4,5,2,1,6,7,8}.  Note that
//       M[5] = 5 and M[3] = 1 have been swapped, not a problem since
//       1 and 3 are already "equivalent labels".
//    b. 5 is associated with 4, M = {0,3,4,5,1,2,6,7,8}
// 3. Pass through fourth row.
//    a. 7 is associated with 5, M = {0,3,4,5,1,7,6,2,8}
// 4. Pass through fifth row.
//    a. 8 is associated with 6, M = {0,3,4,5,1,7,8,2,6}
//
// The M array has two cycles.  Cycle 1 is
//   M[1] = 3, M[3] = 5, M[5] = 7, M[7] = 2, M[2] = 4, M[4] = 1
// and cycle 2 is
//   M[6] = 8, M[8] = 6
// The image is relabeled by replacing each pixel value with the index of
// the cycle containing it.  The result for this example is
//     00100100
//     00110100
//     00011000
//     02000100
//     02000000
//----------------------------------------------------------------------------
void Binary2D::GetComponents (int& riQuantity, ImageInt2D& rkComponents) const
{
    // Create a temporary copy of image to store intermediate information
    // during component labeling.  The original image is embedded in an
    // image with two more rows and two more columns so that the image
    // boundary pixels are properly handled.
    ImageInt2D kTemp(GetBound(0)+2,GetBound(1)+2);  // initially zero
    int iX, iY, iXP, iYP;
    for (iY = 0, iYP = 1; iY < GetBound(1); iY++, iYP++)
    {
        for (iX = 0, iXP = 1; iX < GetBound(0); iX++, iXP++)
            kTemp(iXP,iYP) = ( (*this)(iX,iY) ? 1 : 0 );
    }

    // label connected components in 1D array
    int i, iComponent = 0;
    for (i = 0; i < kTemp.GetQuantity(); i++)
    {
        if ( kTemp[i] )
        {
            iComponent++;
            while ( kTemp[i] )
            {
                // loop terminates since kTemp is zero on its boundaries
                kTemp[i++] = iComponent;
            }
        }
    }

    if ( iComponent == 0 )
    {
        // input image is identically zero
        riQuantity = 0;
        rkComponents = (Eint)0;
        return;
    }

    // associative memory for merging
    int* aiAssoc = new int[iComponent+1];
    for (i = 0; i < iComponent + 1; i++)
        aiAssoc[i] = i;

    // Merge equivalent components.  Pixel (x,y) has previous neighbors
    // (x-1,y-1), (x,y-1), (x+1,y-1), and (x-1,y) [4 of 8 pixels visited
    // before (x,y) is visited, get component labels from them].
    for (iY = 1; iY < kTemp.GetBound(1)-1; iY++)
    {
        for (iX = 1; iX < kTemp.GetBound(0)-1; iX++)
        {
            int iValue = kTemp(iX,iY);
            if ( iValue > 0 )
            {
                AddToAssociative(iValue,kTemp(iX-1,iY-1),aiAssoc);
                AddToAssociative(iValue,kTemp(iX  ,iY-1),aiAssoc);
                AddToAssociative(iValue,kTemp(iX+1,iY-1),aiAssoc);
                AddToAssociative(iValue,kTemp(iX-1,iY  ),aiAssoc);
            }
        }
    }

    // replace each cycle of equivalent labels by a single label
    riQuantity = 0;
    for (i = 1; i <= iComponent; i++)
    {
        if ( i <= aiAssoc[i] )
        {
            riQuantity++;
            int iCurrent = i;
            while ( aiAssoc[iCurrent] != i )
            {
                int iNext = aiAssoc[iCurrent];
                aiAssoc[iCurrent] = riQuantity;
                iCurrent = iNext;
            }
            aiAssoc[iCurrent] = riQuantity;
        }
    }

    // pack a relabeled image in smaller size output
    for (iY = 0, iYP = 1; iY < rkComponents.GetBound(1); iY++, iYP++)
    {
        for (iX = 0, iXP = 1; iX < rkComponents.GetBound(0); iX++, iXP++)
            rkComponents(iX,iY) = aiAssoc[kTemp(iXP,iYP)];
    }

    delete[] aiAssoc;
}
//----------------------------------------------------------------------------
void Binary2D::AddToAssociative (int i0, int i1, int* aiAssoc) const
{
    // Adjacent pixels have labels i0 and i1. Associate them so that they
    // represent the same component.  [assert: i0 > 0]