mgcboundingvolumetree.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 "MgcBoundingVolumeTree.h"
#include "MgcRTLib.h"

//----------------------------------------------------------------------------
MgcBoundingVolumeTree::MgcBoundingVolumeTree (unsigned short usVertexCount,
    const MgcVector3* akVertex, unsigned short usTriangleCount,
    const unsigned short* ausConnect, unsigned short usMaxTrisPerLeaf,
    CreateBound oCreateBound)
{
    // Centroids of triangles are used for splitting a mesh.  The centroids
    // are projected onto a splitting axis and sorted.  The split is based
    // on the median of the projections.
    MgcVector3* akCentroid = new MgcVector3[usTriangleCount];
    const MgcReal fOneThird = 1.0/3.0;
    unsigned int uiIndex = 0;
    unsigned short usT;
    for (usT = 0; usT < usTriangleCount; usT++)
    {
        unsigned short usI0 = ausConnect[uiIndex++];
        unsigned short usI1 = ausConnect[uiIndex++];
        unsigned short usI2 = ausConnect[uiIndex++];
        akCentroid[usT] =
            fOneThird*(akVertex[usI0]+akVertex[usI1]+akVertex[usI2]);
    }

    // Initialize binary-tree arrays for storing triangle indices.  These
    // are used to store the indices when the mesh is split.
    unsigned short* ausISplit = new unsigned short[usTriangleCount];
    unsigned short* ausOSplit = new unsigned short[usTriangleCount];
    for (usT = 0; usT < usTriangleCount; usT++)
        ausISplit[usT] = usT;

    CreateTree(usVertexCount,akVertex,usTriangleCount,ausConnect,
        usMaxTrisPerLeaf,oCreateBound,akCentroid,0,usTriangleCount-1,
        ausISplit,ausOSplit);

    delete[] akCentroid;
    delete[] ausISplit;
    delete[] ausOSplit;
}
//----------------------------------------------------------------------------
MgcBoundingVolumeTree::MgcBoundingVolumeTree ()
{
    m_usTriangleCount = 0;
    m_ausTriangle = 0;
    m_pkBound = 0;
    m_pkLChild = 0;
    m_pkRChild = 0;
}
//----------------------------------------------------------------------------
MgcBoundingVolumeTree::~MgcBoundingVolumeTree ()
{
    delete m_pkBound;
    delete[] m_ausTriangle;
    delete m_pkLChild;
    delete m_pkRChild;
}
//----------------------------------------------------------------------------
void MgcBoundingVolumeTree::CreateTree (unsigned short usVertexCount,
    const MgcVector3* akVertex, unsigned short usTriangleCount,
    const unsigned short* ausConnect, unsigned short usMaxTrisPerLeaf,
    CreateBound oCreateBound, const MgcVector3* akCentroid,
    unsigned short usI0, unsigned short usI1, unsigned short* ausISplit,
    unsigned short* ausOSplit)
{
    assert( usI0 <= usI1 );

    MgcVector3 kOrigin, kDirection;
    oCreateBound(usVertexCount,akVertex,ausConnect,usI0,usI1,ausISplit,
        m_pkBound,kOrigin,kDirection);

    if ( usI1 - usI0 < usMaxTrisPerLeaf )
    {
        // leaf node
        m_usTriangleCount = usI1 - usI0 + 1;
        m_ausTriangle = new unsigned short[m_usTriangleCount];
        memcpy(m_ausTriangle,&ausISplit[usI0],
            m_usTriangleCount*sizeof(unsigned short));

        m_pkLChild = 0;
        m_pkRChild = 0;
    }
    else
    {
        // interior node
        m_usTriangleCount = 0;
        m_ausTriangle = 0;

        unsigned short usJ0, usJ1;
        SplitTriangles(akCentroid,usI0,usI1,ausISplit,usJ0,usJ1,ausOSplit,
            kOrigin,kDirection);

        m_pkLChild = new MgcBoundingVolumeTree;
        m_pkLChild->CreateTree(usVertexCount,akVertex,usTriangleCount,
            ausConnect,usMaxTrisPerLeaf,oCreateBound,akCentroid,usI0,usJ0,
            ausOSplit,ausISplit);

        m_pkRChild = new MgcBoundingVolumeTree;
        m_pkRChild->CreateTree(usVertexCount,akVertex,usTriangleCount,
            ausConnect,usMaxTrisPerLeaf,oCreateBound,akCentroid,usJ1,usI1,
            ausOSplit,ausISplit);
    }
}
//----------------------------------------------------------------------------
int MgcBoundingVolumeTree::Compare (const void* pvElement0,
    const void* pvElement1)
{
    const ProjectionInfo* pInfo0 = (const ProjectionInfo*) pvElement0;
    const ProjectionInfo* pInfo1 = (const ProjectionInfo*) pvElement1;

    if ( pInfo0->m_fProjection < pInfo1->m_fProjection )
        return -1;

    if ( pInfo0->m_fProjection > pInfo1->m_fProjection )
        return +1;

    return 0;
}
//----------------------------------------------------------------------------
void MgcBoundingVolumeTree::SplitTriangles (const MgcVector3* akCentroid,
    unsigned short usI0, unsigned short usI1, unsigned short* ausISplit,
    unsigned short& usJ0,unsigned short& usJ1, unsigned short* ausOSplit,
    const MgcVector3& rkOrigin, const MgcVector3& rkDirection)
{
    // project onto specified line
    unsigned short usQuantity = usI1 - usI0 + 1;
    ProjectionInfo* akInfo = new ProjectionInfo[usQuantity];
    unsigned short usI, usJ;
    for (usI = usI0, usJ = 0; usI <= usI1; usI++, usJ++)
    {
        unsigned short usTriangle = ausISplit[usI];
        MgcVector3 kDiff = akCentroid[usTriangle] - rkOrigin;
        akInfo[usJ].m_usTriangle = usTriangle;
        akInfo[usJ].m_fProjection = rkDirection.Dot(kDiff);
    }

    // find median of projections by sorting
    qsort(akInfo,usQuantity,sizeof(ProjectionInfo),Compare);
    int iMedian = (usQuantity-1)/2;

    // partition the triangles by the median
    for (usJ = 0, usJ0 = usI0-1; usJ <= iMedian; usJ++)
        ausOSplit[++usJ0] = akInfo[usJ].m_usTriangle;
    for (usJ1 = usI1+1; usJ < usQuantity; usJ++)
        ausOSplit[--usJ1] = akInfo[usJ].m_usTriangle;

    delete[] akInfo;
}
//----------------------------------------------------------------------------