mgcminbox3.cpp

《3D游戏引擎设计》的源码

// 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 "MgcMatrix3.h"
#include "MgcMinBox3.h"
#include "MgcMinimizeND.h"

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

    int m_iQuantity;
    const MgcVector3* m_akPoint;
};

//----------------------------------------------------------------------------
static MgcReal Volume (const MgcReal* afAngle, void* pvUserData)
{
    int iQuantity = ((PointArray*)pvUserData)->m_iQuantity;
    const MgcVector3* akPoint = ((PointArray*)pvUserData)->m_akPoint;

    MgcReal fCos0 = MgcMath::Cos(afAngle[0]);
    MgcReal fSin0 = MgcMath::Sin(afAngle[0]);
    MgcReal fCos1 = MgcMath::Cos(afAngle[1]);
    MgcReal fSin1 = MgcMath::Sin(afAngle[1]);
    MgcVector3 kAxis(fCos0*fSin1,fSin0*fSin1,fCos1);
    MgcMatrix3 kRot;
    kRot.FromAxisAngle(kAxis,afAngle[2]);

    MgcVector3 kMin = akPoint[0]*kRot, kMax = kMin;
    for (int i = 1; i < iQuantity; i++)
    {
        MgcVector3 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;

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

    MgcReal fVolume = (kMax.x-kMin.x)*(kMax.y-kMin.y)*(kMax.z-kMin.z);
    return fVolume;
}
//----------------------------------------------------------------------------
static void MinimalBoxForAngles (int iQuantity, const MgcVector3* akPoint,
    MgcReal afAngle[3], MgcBox3& rkBox)
{
    MgcReal fCos0 = MgcMath::Cos(afAngle[0]);
    MgcReal fSin0 = MgcMath::Sin(afAngle[0]);
    MgcReal fCos1 = MgcMath::Cos(afAngle[1]);
    MgcReal fSin1 = MgcMath::Sin(afAngle[1]);
    MgcVector3 kAxis(fCos0*fSin1,fSin0*fSin1,fCos1);
    MgcMatrix3 kRot;
    kRot.FromAxisAngle(kAxis,afAngle[2]);

    MgcVector3 kMin = akPoint[0]*kRot, kMax = kMin;
    for (int i = 1; i < iQuantity; i++)
    {
        MgcVector3 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;

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

    MgcVector3 kMid = 0.5*(kMax + kMin);
    MgcVector3 kRng = 0.5*(kMax - kMin);

    rkBox.Center() = kRot*kMid;
    rkBox.Axis(0) = kRot.GetColumn(0);
    rkBox.Axis(1) = kRot.GetColumn(1);
    rkBox.Axis(2) = kRot.GetColumn(2);
    rkBox.Extent(0) = kRng.x;
    rkBox.Extent(1) = kRng.y;
    rkBox.Extent(2) = kRng.z;
}
//----------------------------------------------------------------------------
MgcBox3 MgcMinBox (int iQuantity, const MgcVector3* akPoint)
{
    unsigned int uiMaxLevel = 8;
    unsigned int uiMaxBracket = 8;
    unsigned int uiMaxIterations = 32;
    PointArray kPA(iQuantity,akPoint);
    MgcMinimizeND kMinimizer(3,Volume,uiMaxLevel,uiMaxBracket,
        uiMaxIterations,&kPA);

    MgcReal afA0[3] =
    {
        0.0,
        0.0,
        0.0
    };

    MgcReal afA1[3] =
    {
        MgcMath::PI,
        MgcMath::HALF_PI,
        MgcMath::PI
    };

    // compute some samples to narrow down the search region
    MgcReal fMinVolume = MgcMath::INFINITY;
    MgcReal afAngle[3], afAInitial[3];
    const int iMax = 3;
    for (int i0 = 0; i0 <= iMax; i0++)
    {
        afAngle[0] = afA0[0] + i0*(afA1[0] - afA0[0])/iMax;
        for (int i1 = 0; i1 <= iMax; i1++)
        {
            afAngle[1] = afA0[1] + i1*(afA1[1] - afA0[1])/iMax;
            for (int i2 = 0; i2 <= iMax; i2++)
            {
                afAngle[2] = afA0[2] + i2*(afA1[2] - afA0[2])/iMax;
                MgcReal fVolume = Volume(afAngle,&kPA);
                if ( fVolume < fMinVolume )
                {
                    fMinVolume = fVolume;
                    afAInitial[0] = afAngle[0];
                    afAInitial[1] = afAngle[1];
                    afAInitial[2] = afAngle[2];
                }
            }
        }
    }

    MgcReal afAMin[3], fVMin;
    kMinimizer.GetMinimum(afA0,afA1,afAInitial,afAMin,fVMin);

    MgcBox3 box;
    MinimalBoxForAngles(iQuantity,akPoint,afAMin,box);
    return box;
}
//----------------------------------------------------------------------------