mgcminbox2.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#include "MgcMatrix2.h"
#include "MgcMinBox2.h"
#include "MgcMinimize1D.h"

class PointArray
{
public:
    PointArray (int iQuantity, const MgcVector2* akPoint)
        :
        m_akPoint(akPoint)
    {
        m_iQuantity = iQuantity;
    }

    int m_iQuantity;
    const MgcVector2* m_akPoint;
};

//----------------------------------------------------------------------------
static MgcReal Area (MgcReal fAngle, void* pvUserData)
{
    int iQuantity = ((PointArray*)pvUserData)->m_iQuantity;
    const MgcVector2* akPoint = ((PointArray*)pvUserData)->m_akPoint;

    MgcMatrix2 kRot;
    kRot.FromAngle(fAngle);

    MgcVector2 kMin = akPoint[0]*kRot, kMax = kMin;
    for (int i = 1; i < iQuantity; i++)
    {
        MgcVector2 kTest = akPoint[i]*kRot;

        if ( kTest.x < kMin.x )
            kMin.x = kTest.x;
        else if ( kTest.x > kMax.x )
            kMax.x = kTest.x;

        if ( kTest.y < kMin.y )
            kMin.y = kTest.y;
        else if ( kTest.y > kMax.y )
            kMax.y = kTest.y;
    }

    MgcReal fArea = (kMax.x-kMin.x)*(kMax.y-kMin.y);
    return fArea;
}
//----------------------------------------------------------------------------
static void MinimalBoxForAngle (int iQuantity, const MgcVector2* akPoint,
    MgcReal fAngle, MgcBox2& rkBox)
{
    MgcMatrix2 kRot;
    kRot.FromAngle(fAngle);

    MgcVector2 kMin = akPoint[0]*kRot, kMax = kMin;
    for (int i = 1; i < iQuantity; i++)
    {
        MgcVector2 kTest = akPoint[i]*kRot;

        if ( kTest.x < kMin.x )
            kMin.x = kTest.x;
        else if ( kTest.x > kMax.x )
            kMax.x = kTest.x;

        if ( kTest.y < kMin.y )
            kMin.y = kTest.y;
        else if ( kTest.y > kMax.y )
            kMax.y = kTest.y;
    }

    MgcVector2 kMid = 0.5*(kMax + kMin);
    MgcVector2 kRng = 0.5*(kMax- kMin);
    rkBox.Center() = kRot*kMid;
    rkBox.Axis(0) = kRot.GetColumn(0);
    rkBox.Axis(1) = kRot.GetColumn(1);
    rkBox.Extent(0) = kRng.x;
    rkBox.Extent(1) = kRng.y;
}
//----------------------------------------------------------------------------
MgcBox2 MgcMinBox (int iQuantity, const MgcVector2* akPoint)
{
    unsigned int uiMaxLevel = 8;
    unsigned int uiMaxBracket = 8;
    PointArray kPA(iQuantity,akPoint);
    MgcMinimize1D kMinimizer(Area,uiMaxLevel,uiMaxBracket,&kPA);

    MgcReal fA1 = 0.25*MgcMath::PI;
    MgcReal fA0 = -fA1;

    // compute some samples to narrow down the search region
    MgcReal fMinArea = MgcMath::INFINITY;
    MgcReal fAngle, fAInitial;
    const int iMax = 3;
    for (int i = 0; i <= iMax; i++)
    {
        fAngle = fA0 + i*(fA1 - fA0)/iMax;
        MgcReal fArea = Area(fAngle,&kPA);
        if ( fArea < fMinArea )
        {
            fMinArea = fArea;
            fAInitial = fAngle;
        }
    }


    MgcReal fAMin, fVMin;
    kMinimizer.GetMinimum(fA0,fA1,fAInitial,fAMin,fVMin);

    MgcBox2 box;
    MinimalBoxForAngle(iQuantity,akPoint,fAMin,box);
    return box;
}
//----------------------------------------------------------------------------