mgcterrainpage.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
//
// RESTRICTED USE SOURCE CODE
// http://www.magic-software.com/License/restricted.pdf

#include "MgcRenderer.h"
#include "MgcTerrainBlock.h"
#include "MgcTerrainPage.h"
#include "MgcTerrainVertex.h"

MgcImplementRTTI(MgcTerrainPage,MgcTriMesh);
MgcImplementStream(MgcTerrainPage);

//----------------------------------------------------------------------------
MgcTerrainPage::MgcTerrainPage (unsigned short usSize,
    unsigned short* ausHeight, const MgcVector2& rkOrigin,
    MgcReal fMinElevation, MgcReal fMaxElevation, MgcReal fSpacing)
    :
    MgcTriMesh(
        usSize*usSize,  // vertex quantity
        new MgcVector3[usSize*usSize],  // vertices,
        0,  // no normals
        0,  // no colors
        new MgcVector2[usSize*usSize],  // always use textures
        2*(usSize-1)*(usSize-1),  // triangle quantity
        new unsigned int[6*(usSize-1)*(usSize-1)])  // connectivity
{
    // usSize = 2^p + 1, p <= 7
    assert( usSize ==  3 || usSize ==  5 || usSize ==   9 || usSize == 17
        ||  usSize == 33 || usSize == 65 || usSize == 129 );

    //*** native data ***
    m_usSize = usSize;
    m_ausHeight = ausHeight;
    m_kOrigin = rkOrigin;
    m_fMinElevation = fMinElevation;
    m_fMaxElevation = fMaxElevation;
    m_fSpacing = fSpacing;

    //*** derived data ***
    m_usSizeM1 = usSize - 1;
    m_fPixelTolerance = 1.0;
    m_fWorldTolerance = -1.0;
    m_fInvSpacing = 1.0/m_fSpacing;
    m_fTextureSpacing = 1.0/MgcReal(m_usSizeM1);
    m_fMultiplier = (m_fMaxElevation - m_fMinElevation)/65535.0;
    m_bNeedsTessellation = true;

    // for tessellation (mapping of connectivity indices)
    m_ausLookup = new unsigned short[m_uiVertexQuantity];
    m_uiConnectLength = 0;

    // initialize vertex information array
    m_akTVertex = new MgcTerrainVertex[m_uiVertexQuantity];
    memset(m_akTVertex,0,m_uiVertexQuantity*sizeof(MgcTerrainVertex));

    // allocate quadtree
    m_usBlockQuantity = m_usSize*(m_usSize-2)/3;
    m_akBlock = new MgcTerrainBlock[m_usBlockQuantity];

    // initialize quadtree
    unsigned short usStride = (m_usSize-1)/2;
    m_akBlock[0].Initialize(this,m_akBlock,0,0,0,usStride,true);
    m_akBlock[0].UpdateBoundingBox(this,m_akBlock,0,usStride);

    // model bounding sphere contains the top level block's bounding box
    MgcVector3 kCenter = 0.5*(m_akBlock[0].GetMax() + m_akBlock[0].GetMin());
    MgcVector3 kDiag = 0.5*(m_akBlock[0].GetMax() - m_akBlock[0].GetMin());
    m_kBound.Center() = kCenter;
    m_kBound.Radius() = kDiag.Length();

    // allocate queue
    m_usQueueQuantity = m_usBlockQuantity - m_usBlockQuantity/4;
    m_ausQueue = new unsigned short[m_usQueueQuantity];

    // root of quadtree is initially active
    m_ausQueue[0] = 0;
    m_usFront = 0;
    m_usRear = 1;
    m_usItemsInQueue = 1;
}
//----------------------------------------------------------------------------
MgcTerrainPage::MgcTerrainPage ()
{
}
//----------------------------------------------------------------------------
MgcTerrainPage::~MgcTerrainPage ()
{
    delete[] m_ausHeight;
    delete[] m_akTVertex;
    delete[] m_akBlock;
    delete[] m_ausQueue;
    delete[] m_ausLookup;
}
//----------------------------------------------------------------------------
void MgcTerrainPage::SetPixelTolerance (MgcRenderer* pkRenderer,
    MgcReal fTolerance)
{
    MgcReal fWidth = MgcReal(pkRenderer->GetWidth());
    MgcCameraPtr spCamera = pkRenderer->GetCamera();
    MgcReal fRight = spCamera->GetFrustumRight();
    MgcReal fNear = spCamera->GetFrustumNear();

    m_fPixelTolerance = fTolerance;
    m_fWorldTolerance = 2.0*fRight*m_fPixelTolerance/(fNear*fWidth);
    m_fWorldTolerance *= m_fWorldTolerance;
}
//---------------------------------------------------------------------------
MgcReal MgcTerrainPage::GetHeight (const MgcVector2& rkLocation) const
{
    MgcReal fXGrid = (rkLocation.x - m_kOrigin.x)*m_fInvSpacing;
    if ( fXGrid < 0.0 || fXGrid >= MgcReal(m_usSizeM1) )
    {
        // location not in page
        return MgcMath::INFINITY;
    }

    MgcReal fYGrid = (rkLocation.y - m_kOrigin.y)*m_fInvSpacing;
    if ( fYGrid < 0.0 || fYGrid >= MgcReal(m_usSizeM1) )
    {
        // location not in page
        return MgcMath::INFINITY;
    }

    MgcReal fCol = MgcMath::Floor(fXGrid);
    unsigned short usCol = (unsigned short) fCol;
    MgcReal fRow = MgcMath::Floor(fYGrid);
    unsigned short usRow = (unsigned short) fRow;

    unsigned short usIndex = usCol + m_usSize*usRow;
    MgcReal fDx = fXGrid - fCol;
    MgcReal fDy = fYGrid - fRow;
    MgcReal fH00, fH10, fH01, fH11, fHeight;

    if ( (usCol & 1) == (usRow & 1) )
    {
        MgcReal fDiff = fDx - fDy;
        fH00 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex];
        fH11 = m_fMinElevation + m_fMultiplier *
            m_ausHeight[usIndex+1+m_usSize];
        if ( fDiff > 0.0 )
        {
            fH10 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+1];
            fHeight = (1.0-fDiff-fDy)*fH00+fDiff*fH10+fDy*fH11;
        }
        else
        {
            fH01 = m_fMinElevation + m_fMultiplier *
                m_ausHeight[usIndex+m_usSize];
            fHeight = (1.0+fDiff-fDx)*fH00-fDiff*fH01+fDx*fH11;
        }
    }
    else
    {
        MgcReal fSum = fDx + fDy;
        fH10 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+1];
        fH01 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex+m_usSize];
        if ( fSum <= 1.0 )
        {
            fH00 = m_fMinElevation + m_fMultiplier*m_ausHeight[usIndex];
            fHeight = (1.0-fSum)*fH00+fDx*fH10+fDy*fH01;
        }
        else
        {
            fH11 = m_fMinElevation + m_fMultiplier *
                m_ausHeight[usIndex+1+m_usSize];
            fHeight = (fSum-1.0)*fH11+(1.0-fDy)*fH10+(1.0-fDx)*fH01;
        }
    }

    return fHeight;
}
//---------------------------------------------------------------------------
bool MgcTerrainPage::IntersectFrustum (const MgcCamera* pkCamera)
{
    // check if terrain page itself is inside frustum
    m_akBlock[0].TestIntersectFrustum(this,pkCamera);
    bool bIntersect = m_akBlock[0].GetVisible();
    m_akBlock[0].ClearBits();
    return bIntersect;
}
//---------------------------------------------------------------------------
void MgcTerrainPage::AddToQueue (unsigned short usBlock)
{
    m_ausQueue[m_usRear] = usBlock;
    if ( ++m_usRear == m_usQueueQuantity )
        m_usRear = 0;
    m_usItemsInQueue++;
}
//---------------------------------------------------------------------------
unsigned short MgcTerrainPage::RemoveFromQueue ()
{
    unsigned short usBlock = m_ausQueue[m_usFront];
    if ( ++m_usFront == m_usQueueQuantity )
        m_usFront = 0;
    m_usItemsInQueue--;
    return usBlock;
}
//---------------------------------------------------------------------------
unsigned short MgcTerrainPage::ReadFromQueue (unsigned short usIndex)
{
    usIndex += m_usFront;
    if ( usIndex < m_usQueueQuantity )
        return m_ausQueue[usIndex];
    else
        return m_ausQueue[usIndex - m_usQueueQuantity];
}
//---------------------------------------------------------------------------
void MgcTerrainPage::ResetBlocks ()
{
    unsigned short usQueue, usBlock;
    if ( m_usFront < m_usRear )
    {
        m_usNumUnprocessed = m_usRear - m_usFront;
        for (usQueue = m_usFront; usQueue < m_usRear; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
    }
    else
    {
        m_usNumUnprocessed = m_usQueueQuantity - m_usFront + m_usRear;
        for (usQueue = m_usFront; usQueue < m_usQueueQuantity; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
        for (usQueue = 0; usQueue < m_usRear; usQueue++)
        {
            usBlock = m_ausQueue[usQueue];
            if ( m_akBlock[usBlock].BitsSet() )
            {
                m_akBlock[usBlock].Disable(this);
                m_akBlock[usBlock].ClearBits();
            }
        }
    }
}
//---------------------------------------------------------------------------
void MgcTerrainPage::SimplifyBlocks (const MgcCamera* pkCamera,
    const MgcVector3& rkModelEye, const MgcVector3& rkModelDir,
    bool bCloseAssumption)
{
    while ( m_usNumUnprocessed > 0 )
    {
        // process the block in the front of queue
        unsigned short usBlock = RemoveFromQueue();
        MgcTerrainBlock* pkBlock = &m_akBlock[usBlock];

        if ( !pkBlock->GetProcessed() )
        {
            m_usNumUnprocessed--;

            unsigned short usChild;
            MgcTerrainBlock* pkChild;
            MgcVector2 kCLoc;
            int i;

            if ( pkBlock->IsFirstChild(usBlock) )
            {
                // first child has responsibility for replacing by parent
                if ( pkBlock->IsSibling(usBlock,ReadFromQueue(2)) )
                {
                    pkChild = pkBlock;
                    if ( bCloseAssumption )
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            kCLoc.x = pkChild->GetX()*m_fSpacing+m_kOrigin.x;
                            kCLoc.y = pkChild->GetY()*m_fSpacing+m_kOrigin.y;
                            pkChild->ComputeInterval(rkModelEye,rkModelDir,
                                m_fWorldTolerance,kCLoc,m_fSpacing);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }
                    else // distant assumption
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            pkChild->ComputeInterval(rkModelEye,
                                m_fWorldTolerance);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())
                                break;
                        }
                    }

                    if ( i == 4 )
                    {
                        // remove child blocks (first child already removed)
                        for (i = 0; i < 3; i++)
                        {
                            usChild = RemoveFromQueue();
                            if ( !m_akBlock[usChild].GetProcessed() )
                                m_usNumUnprocessed--;
                            m_akBlock[usChild].ClearBits();
                        }

                        // add parent block
                        unsigned short usParent =
                            pkBlock->GetParentIndex(usBlock);
                        AddToQueue(usParent);
                        assert( !m_akBlock[usParent].GetProcessed() );
                        m_usNumUnprocessed++;
                        continue;
                    }
                }
            }

            if ( !pkBlock->GetVisibilityTested() )
                pkBlock->TestIntersectFrustum(this,pkCamera);

            if ( pkBlock->GetStride() > 1 )
            {
                // subdivide only if bounding box of block intersects frustum
                if ( pkBlock->GetVisible() )
                {
                    usChild = pkBlock->GetChildIndex(usBlock,1);
                    pkChild = &m_akBlock[usChild];
                    if ( bCloseAssumption ) 
                    {
                        for (i = 0; i < 4; i++, pkChild++)
                        {
                            kCLoc.x = pkChild->GetX()*m_fSpacing+m_kOrigin.x;
                            kCLoc.y = pkChild->GetY()*m_fSpacing+m_kOrigin.y;
                            pkChild->ComputeInterval(rkModelEye,rkModelDir,
                                m_fWorldTolerance,kCLoc,m_fSpacing);
                            if (pkChild->GetDeltaMax() > pkChild->GetDeltaL())