mgcbisect3.cpp

3D Game Engine Design Source Code非常棒

    ZeroTest(m_fX1,m_fYm,m_fZm,m_fF1mm,m_fG1mm,m_fH1mm,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 110,100,101,111
    ZeroTest(m_fXm,m_fY1,m_fZm,m_fFm1m,m_fGm1m,m_fHm1m,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 010,110,111,011
    ZeroTest(m_fXm,m_fYm,m_fZ1,m_fFmm1,m_fGmm1,m_fHmm1,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 001,101,111,011
    ZeroTest(m_fX0,m_fYm,m_fZm,m_fF0mm,m_fG0mm,m_fH0mm,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 000,010,011,001
    ZeroTest(m_fXm,m_fY0,m_fZm,m_fFm0m,m_fGm0m,m_fHm0m,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 000,100,001,101
    ZeroTest(m_fXm,m_fYm,m_fZ0,m_fFmm0,m_fGmm0,m_fHmm0,
        m_fXRoot,m_fYRoot,m_fZRoot);  // face 000,100,110,010

    ZeroTest(m_fXm,m_fYm,m_fZm,m_fFmmm,m_fGmmm,m_fHmmm,
        m_fXRoot,m_fYRoot,m_fZRoot);  // center

    // edge 011,111
    AddNode(m_fXm,m_fY1,m_fZ1,m_fFm11,m_fGm11,m_fHm11);
    m_pkTemp->m_pkXNext = pkN111;
    m_pkTemp->m_pkYNext = 0;
    m_pkTemp->m_pkZNext = 0;
    pkN011->m_pkXNext = m_pkTemp;

    // edge 101,111
    AddNode(m_fX1,m_fYm,m_fZ1,m_fF1m1,m_fG1m1,m_fH1m1);
    m_pkTemp->m_pkXNext = 0;
    m_pkTemp->m_pkYNext = pkN111;
    m_pkTemp->m_pkZNext = 0;
    pkN101->m_pkYNext = m_pkTemp;

    // edge 110,111
    AddNode(m_fX1,m_fY1,m_fZm,m_fF11m,m_fG11m,m_fH11m);
    m_pkTemp->m_pkXNext = 0;
    m_pkTemp->m_pkYNext = 0;
    m_pkTemp->m_pkZNext = pkN111;
    pkN110->m_pkZNext = m_pkTemp;

    // edge 010,110
    AddNode(m_fXm,m_fY1,m_fZ0,m_fFm10,m_fGm10,m_fHm10);
    m_pkTemp->m_pkXNext = pkN110;
    m_pkTemp->m_pkYNext = 0;
    pkN010->m_pkXNext = m_pkTemp;

    // edge 100,110
    AddNode(m_fX1,m_fYm,m_fZ1,m_fF1m0,m_fG1m0,m_fH1m0);
    m_pkTemp->m_pkXNext = 0;
    m_pkTemp->m_pkYNext = pkN110;
    pkN100->m_pkYNext = m_pkTemp;

    // edge 100,101
    AddNode(m_fX1,m_fY0,m_fZm,m_fF10m,m_fG10m,m_fH10m);
    m_pkTemp->m_pkXNext = 0;
    m_pkTemp->m_pkZNext = pkN101;
    pkN100->m_pkZNext = m_pkTemp;

    // edge 001,101
    AddNode(m_fXm,m_fY0,m_fZ1,m_fFm01,m_fGm01,m_fHm01);
    m_pkTemp->m_pkXNext = pkN101;
    m_pkTemp->m_pkZNext = 0;
    pkN001->m_pkXNext = m_pkTemp;

    // edge 001,011
    AddNode(m_fX0,m_fYm,m_fZ1,m_fF0m1,m_fG0m1,m_fH0m1);
    m_pkTemp->m_pkYNext = pkN011;
    m_pkTemp->m_pkZNext = 0;
    pkN001->m_pkYNext = m_pkTemp;

    // edge 010,011
    AddNode(m_fX0,m_fY1,m_fZm,m_fF01m,m_fG01m,m_fH01m);
    m_pkTemp->m_pkYNext = 0;
    m_pkTemp->m_pkZNext = pkN011;
    pkN010->m_pkZNext = m_pkTemp;

    // edge 000,100
    AddNode(m_fXm,m_fY0,m_fZ0,m_fFm00,m_fGm00,m_fHm00);
    m_pkTemp->m_pkXNext = pkN100;
    pkN000->m_pkXNext = m_pkTemp;

    // edge 000,010
    AddNode(m_fX0,m_fYm,m_fZ0,m_fF0m0,m_fG0m0,m_fH0m0);
    m_pkTemp->m_pkYNext = pkN010;
    pkN000->m_pkYNext = m_pkTemp;

    // edge 000,001
    AddNode(m_fX0,m_fY0,m_fZm,m_fF00m,m_fG00m,m_fH00m);
    m_pkTemp->m_pkZNext = pkN001;
    pkN000->m_pkZNext = m_pkTemp;

    // face 110,100,101,111
    AddNode(m_fX1,m_fYm,m_fZm,m_fF11m,m_fG11m,m_fH11m);
    m_pkTemp->m_pkXNext = 0;
    m_pkTemp->m_pkYNext = pkN110->m_pkZNext;
    m_pkTemp->m_pkZNext = pkN101->m_pkYNext;
    pkN100->m_pkYNext->m_pkZNext = m_pkTemp;
    pkN100->m_pkZNext->m_pkYNext = m_pkTemp;

    // face 010,110,111,011
    AddNode(m_fXm,m_fY1,m_fZm,m_fFm1m,m_fGm1m,m_fHm1m);
    m_pkTemp->m_pkXNext = pkN110->m_pkZNext;
    m_pkTemp->m_pkYNext = 0;
    m_pkTemp->m_pkZNext = pkN011->m_pkXNext;
    pkN010->m_pkXNext->m_pkZNext = m_pkTemp;
    pkN010->m_pkZNext->m_pkXNext = m_pkTemp;

    // face 001,101,111,011
    AddNode(m_fXm,m_fYm,m_fZ1,m_fFmm1,m_fGmm1,m_fHmm1);
    m_pkTemp->m_pkXNext = pkN101->m_pkYNext;
    m_pkTemp->m_pkYNext = pkN011->m_pkXNext;
    m_pkTemp->m_pkZNext = 0;
    pkN001->m_pkXNext->m_pkYNext = m_pkTemp;
    pkN001->m_pkYNext->m_pkXNext = m_pkTemp;

    // face 000,010,011,001
    AddNode(m_fX0,m_fYm,m_fZm,m_fF0mm,m_fG0mm,m_fH0mm);
    m_pkTemp->m_pkYNext = pkN010->m_pkZNext;
    m_pkTemp->m_pkZNext = pkN001->m_pkYNext;
    pkN000->m_pkYNext->m_pkZNext = m_pkTemp;
    pkN000->m_pkZNext->m_pkYNext = m_pkTemp;

    // face 000,100,001,101
    AddNode(m_fXm,m_fY0,m_fZm,m_fFm0m,m_fGm0m,m_fHm0m);
    m_pkTemp->m_pkXNext = pkN100->m_pkZNext;
    m_pkTemp->m_pkZNext = pkN001->m_pkXNext;
    pkN000->m_pkXNext->m_pkZNext = m_pkTemp;
    pkN000->m_pkZNext->m_pkXNext = m_pkTemp;

    // face 000,100,110,010
    AddNode(m_fXm,m_fYm,m_fZ0,m_fFmm0,m_fGmm0,m_fHmm0);
    m_pkTemp->m_pkXNext = pkN100->m_pkYNext;
    m_pkTemp->m_pkYNext = pkN010->m_pkXNext;
    pkN000->m_pkXNext->m_pkYNext = m_pkTemp;
    pkN000->m_pkYNext->m_pkXNext = m_pkTemp;

    // center
    AddNode(m_fXm,m_fYm,m_fZm,m_fFmmm,m_fGmmm,m_fHmmm);
    m_pkTemp->m_pkXNext = pkN100->m_pkYNext->m_pkZNext;
    m_pkTemp->m_pkYNext = pkN010->m_pkXNext->m_pkZNext;
    m_pkTemp->m_pkZNext = pkN001->m_pkXNext->m_pkYNext;
    pkN000->m_pkXNext->m_pkYNext->m_pkZNext = m_pkTemp;
    pkN000->m_pkXNext->m_pkZNext->m_pkYNext = m_pkTemp;
    pkN000->m_pkYNext->m_pkZNext->m_pkXNext = m_pkTemp;

    // Search the subocts for roots
    bool bResult =
        BisectRecurse(pkN000) ||
        BisectRecurse(pkN000->m_pkXNext) ||
        BisectRecurse(pkN000->m_pkYNext) ||
        BisectRecurse(pkN000->m_pkXNext->m_pkYNext) ||
        BisectRecurse(pkN000->m_pkZNext) ||
        BisectRecurse(pkN000->m_pkZNext->m_pkXNext) ||
        BisectRecurse(pkN000->m_pkZNext->m_pkYNext) ||
        BisectRecurse(pkN000->m_pkZNext->m_pkXNext->m_pkYNext);

    // entire suboct check failed, remove the nodes that were added

    // center
    delete pkN000->m_pkXNext->m_pkYNext->m_pkZNext;

    // faces
    delete pkN000->m_pkXNext->m_pkYNext;
    delete pkN000->m_pkYNext->m_pkZNext;
    delete pkN000->m_pkXNext->m_pkZNext;
    delete pkN001->m_pkXNext->m_pkYNext;
    delete pkN010->m_pkXNext->m_pkZNext;
    delete pkN100->m_pkYNext->m_pkZNext;

    // edges
    delete pkN000->m_pkXNext;  pkN000->m_pkXNext = pkN100;
    delete pkN000->m_pkYNext;  pkN000->m_pkYNext = pkN010;
    delete pkN000->m_pkZNext;  pkN000->m_pkZNext = pkN001;
    delete pkN001->m_pkYNext;  pkN001->m_pkYNext = pkN011;
    delete pkN001->m_pkXNext;  pkN001->m_pkXNext = pkN101;
    delete pkN010->m_pkZNext;  pkN010->m_pkZNext = pkN011;
    delete pkN100->m_pkZNext;  pkN100->m_pkZNext = pkN101;
    delete pkN010->m_pkXNext;  pkN010->m_pkXNext = pkN110;
    delete pkN100->m_pkYNext;  pkN100->m_pkYNext = pkN110;
    delete pkN011->m_pkXNext;  pkN011->m_pkXNext = pkN111;
    delete pkN101->m_pkYNext;  pkN101->m_pkYNext = pkN111;
    delete pkN110->m_pkZNext;  pkN110->m_pkZNext = pkN111;

    m_iLevel--;
    return bResult;
}
//---------------------------------------------------------------------------

#ifdef BISECT3_TEST

#include "MgcRTLib.h"

// Bisection should produce a root at (r2,r3,r5).
// Output:
// root (+0.707031,+0.577393,+0.447266)
// func (-0.000076,+0.000042,+0.000052)

static const MgcReal gs_fRootHalf = MgcMath::Sqrt(0.5);
static const MgcReal gs_fRootThird = MgcMath::Sqrt(1.0/3.0);
static const MgcReal gs_fRootFifth = MgcMath::Sqrt(1.0/5.0);

MgcReal F (MgcReal fX, MgcReal fY, MgcReal fZ) { return fX - gs_fRootHalf; }
MgcReal G (MgcReal fX, MgcReal fY, MgcReal fZ) { return fY - gs_fRootThird; }
MgcReal H (MgcReal fX, MgcReal fY, MgcReal fZ) { return fZ - gs_fRootFifth; }

int main ()
{
    MgcBisect3 kBisector(F,G,H,16,1e-04);
    MgcReal fXRoot, fYRoot, fZRoot;
    if ( kBisector.Bisect(0.0,0.0,0.0,1.0,1.0,1.0,fXRoot,fYRoot,fZRoot) )
    {
        cout << "root at x = " << fXRoot << endl;
        cout << "root at y = " << fYRoot << endl;
        cout << "root at z = " << fZRoot << endl;
        cout << "function F(x,y,z) = " << F(fXRoot,fYRoot,fZRoot) << endl;
        cout << "function G(x,y,z) = " << G(fXRoot,fYRoot,fZRoot) << endl;
        cout << "function H(x,y,z) = " << H(fXRoot,fYRoot,fZRoot) << endl;
    }
    else
    {
        cout << "root not found" << endl;
    }

    return 0;
}

#endif