mstristrip.cpp

来自「hl2 source code. Do not use it illegal.」· C++ 代码 · 共 925 行 · 第 1/2 页

    // kill first dude
    delete &stripverts;
    pstriplist->erase(istriplist);

    // add all the others
    while(pstriplist->size())
    {
        istriplist = FindBestCachedStrip(pstriplist, vertcache);
        STRIPVERTS &stripverts = **istriplist;
        short lastvert = pstripindices[numstripindices - 1];
        short firstvert = stripverts[0];

        if(firstvert != lastvert)
        {
            // add degenerate from last strip
            pstripindices[numstripindices++] = lastvert;

            // add degenerate from our strip
            pstripindices[numstripindices++] = firstvert;
        }

        // if we're not orientated correctly, we need to add a degenerate
        if(FIsStripCW(stripverts) != !(numstripindices & 0x1))
        {
            // This shouldn't happen - we're currently trying very hard
            // to keep everything oriented correctly.
            assert(false);
            pstripindices[numstripindices++] = firstvert;
        }

        // add these verts
        for(int ivert = 0; ivert < StripLen(stripverts); ivert++)
        {
            pstripindices[numstripindices++] = stripverts[ivert];
            vertcache.Add(1, stripverts[ivert]);
        }

        // free these guys
        delete &stripverts;
        pstriplist->erase(istriplist);
    }

    *ppstripindices = pstripindices;
    return numstripindices;
}

//=========================================================================
// Build a (hopefully) optimal set of strips from a trilist
//=========================================================================
void CStripper::BuildStrips(STRIPLIST *pstriplist, int maxlen, bool flookahead)
{
    // temp indices storage
    const int ctmpverts = 1024;
    int pstripverts[ctmpverts + 1];
    int pstriptris[ctmpverts + 1];

    assert(maxlen <= ctmpverts);

    // clear all the used flags for the tris
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);

    bool fstartcw = true;
    for(;;)
    {
        int besttri;
        int bestvert;
        float bestratio = 2.0f;
        int bestneighborcount = INT_MAX;

		int tri;
        for( tri = 0; tri < m_numtris; tri++)
        {
            // if used the continue
            if(m_pused[tri])
                continue;

            // get the neighbor count
            int curneightborcount = GetNeighborCount(tri);
            assert(curneightborcount >= 0 && curneightborcount <= 3);

            // push all the singletons to the very end
            if(!curneightborcount)
                curneightborcount = 4;

            // if this guy has more neighbors than the current best - bail
            if(curneightborcount > bestneighborcount)
                continue;

            // try starting the strip with each of this tris verts
            for(int vert = 0; vert < 3; vert++)
            {
                int swaps;
                int len = CreateStrip(tri, vert, maxlen, &swaps, flookahead,
                    fstartcw, pstriptris, pstripverts);
                assert(len);

                int striplen = len - swaps;
                float ratio = (len == 3) ? 1.0f : (float)swaps / len;

                // check if this ratio is better than what we've already got for
                // this neighborcount
                if((curneightborcount < bestneighborcount) ||
                    ((curneightborcount == bestneighborcount) && (ratio < bestratio)))
                {
                    bestneighborcount = curneightborcount;

                    besttri = tri;
                    bestvert = vert;
                    bestratio = ratio;
                }

            }
        }

        // no strips found?
        if(bestneighborcount == INT_MAX)
            break;

        // recreate this strip
        int swaps;
        int len = CreateStrip(besttri, bestvert, maxlen,
            &swaps, flookahead, fstartcw, pstriptris, pstripverts);
        assert(len);

        // mark the tris on the best strip as used
        for(tri = 0; tri < len; tri++)
            m_pused[pstriptris[tri]] = 1;

        // create a new STRIPVERTS and stuff in the indices
        STRIPVERTS *pstripvertices = new STRIPVERTS(len + 1);
        assert(pstripvertices);

        // store orientation in first entry
        for(tri = 0; tri < len; tri++)
            (*pstripvertices)[tri] = m_ptriangles[pstriptris[tri]][pstripverts[tri]];
        (*pstripvertices)[len] = fstartcw;

        // store the STRIPVERTS
        pstriplist->push_back(pstripvertices);

        // if strip was odd - swap orientation
        if((len & 0x1))
            fstartcw = !fstartcw;
    }

#ifdef _DEBUG
    // make sure all tris are used
    for(int t = 0; t < m_numtris; t++)
        assert(m_pused[t]);
#endif
}

//=========================================================================
// Guesstimate on the total index count for this list of strips
//=========================================================================
int EstimateStripCost(STRIPLIST *pstriplist)
{
    int count = 0;

    for(STRIPLIST::iterator istriplist = pstriplist->begin();
        istriplist != pstriplist->end();
        ++istriplist)
    {
        // add count of indices
        count += StripLen(**istriplist);
    }

    // assume 2 indices per strip to tack all these guys together
    return count + (pstriplist->size() - 1) * 2;
}

//=========================================================================
// Initialize triangle information (edges, #neighbors, etc.)
//=========================================================================
void CStripper::InitTriangleInfo(int tri, int vert)
{
    WORD *ptriverts = &m_ptriangles[tri + 1][0];
    int vert1 = m_ptriangles[tri][(vert + 1) % 3];
    int vert2 = m_ptriangles[tri][vert];

    for(int itri = tri + 1; itri < m_numtris; itri++, ptriverts += 3)
    {
        if(m_pused[itri] != 0x7)
        {
            for(int ivert = 0; ivert < 3; ivert++)
            {
                if((ptriverts[ivert] == vert1) &&
                    (ptriverts[(ivert + 1) % 3] == vert2))
                {
                    // add the triangle info
                    m_ptriinfo[tri].neighbortri[vert] = itri;
                    m_ptriinfo[tri].neighboredge[vert] = ivert;
                    m_pused[tri] |= (1 << vert);

                    m_ptriinfo[itri].neighbortri[ivert] = tri;
                    m_ptriinfo[itri].neighboredge[ivert] = vert;
                    m_pused[itri] |= (1 << ivert);
                    return;
                }
            }
        }
    }
}

//=========================================================================
// CStripper ctor
//=========================================================================
CStripper::CStripper(int numtris, TRIANGLELIST ptriangles)
{
    // store trilist info
    m_numtris = numtris;
    m_ptriangles = ptriangles;

    m_pused = new int[numtris];
    assert(m_pused);
    m_ptriinfo = new TRIANGLEINFO[numtris];
    assert(m_ptriinfo);

    // init triinfo
	int itri;
    for( itri = 0; itri < numtris; itri++)
    {
        m_ptriinfo[itri].neighbortri[0] = -1;
        m_ptriinfo[itri].neighbortri[1] = -1;
        m_ptriinfo[itri].neighbortri[2] = -1;
    }

    // clear the used flag
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);

    // go through all the triangles and find edges, neighbor counts
    for(itri = 0; itri < numtris; itri++)
    {
        for(int ivert = 0; ivert < 3; ivert++)
        {
            if(!(m_pused[itri] & (1 << ivert)))
                InitTriangleInfo(itri, ivert);
        }
    }

    // clear the used flags from InitTriangleInfo
    memset(m_pused, 0, sizeof(m_pused[0]) * m_numtris);
}

//=========================================================================
// CStripper dtor
//=========================================================================
CStripper::~CStripper()
{
    // free stuff
    delete [] m_pused;
    m_pused = NULL;

    delete [] m_ptriinfo;
    m_ptriinfo = NULL;
}

//=========================================================================
// Add an index to the cache - returns true if it was added, false otherwise
//=========================================================================
bool CVertCache::Add(int strip, int vertindex)
{
    // find index in cache
    for(int iCache = 0; iCache < CACHE_SIZE; iCache++)
    {
        if(vertindex == m_rgCache[iCache])
        {
            // if it's in the cache and it's from a different strip
            // change the strip to the new one and count the cache hit
            if(strip != m_rgCacheStrip[iCache])
            {
                m_cachehits++;
                m_rgCacheStrip[iCache] = strip;
                return true;
            }

            // we added this item to the cache earlier - carry on
            return false;
        }
    }

    // not in cache, add vert and strip
    m_rgCache[m_iCachePtr] = vertindex;
    m_rgCacheStrip[m_iCachePtr] = strip;
    m_iCachePtr = (m_iCachePtr + 1) % CACHE_SIZE;
    return true;
}

#ifdef _DEBUG
//=========================================================================
// Turn on c runtime leak checking, etc.
//=========================================================================
void EnableLeakChecking()
{
    int flCrtDbgFlags = _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG);

    flCrtDbgFlags &=
        ~(_CRTDBG_LEAK_CHECK_DF |
        _CRTDBG_CHECK_ALWAYS_DF |
        _CRTDBG_DELAY_FREE_MEM_DF);

    // always check for memory leaks
    flCrtDbgFlags |= _CRTDBG_LEAK_CHECK_DF;

    // others you may / may not want to set
    flCrtDbgFlags |= _CRTDBG_CHECK_ALWAYS_DF;
    flCrtDbgFlags |= _CRTDBG_DELAY_FREE_MEM_DF;

    _CrtSetDbgFlag(flCrtDbgFlags);

    // all types of reports go via OutputDebugString
    _CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_DEBUG);
    _CrtSetReportMode(_CRT_ERROR, _CRTDBG_MODE_DEBUG);
    _CrtSetReportMode(_CRT_ASSERT, _CRTDBG_MODE_DEBUG);

    // big errors and asserts get their own assert window
    _CrtSetReportMode(_CRT_ERROR, _CRTDBG_MODE_WNDW);
    _CrtSetReportMode(_CRT_ASSERT, _CRTDBG_MODE_WNDW);

    // _CrtSetBreakAlloc(0);
}
#endif

//=========================================================================
// Main Stripify routine
//=========================================================================
int Stripify(int numtris, WORD *ptriangles, int *pnumindices, WORD **ppstripindices)
{
    if(!numtris || !ptriangles)
        return 0;

#ifdef _DEBUG
//    EnableLeakChecking();
#endif

    CStripper stripper(numtris, (TRIANGLELIST)ptriangles);

    // map of various args to try stripifying mesh with
    struct ARGMAP
    {
        int     maxlen;         // maximum length of strips
        bool    flookahead;     // use sgi greedy lookahead (or not)
    } rgargmap[] =
    {
        { 1024,  true  },
        { 1024,  false },
    };
    static const int cargmaps = sizeof(rgargmap) / sizeof(rgargmap[0]);
    STRIPLIST   striplistbest;
    int         bestlistcost = 0;

    for(int imap = 0; imap < cargmaps; imap++)
    {
        STRIPLIST striplist;

        // build the strip with the various args
        stripper.BuildStrips(&striplist, rgargmap[imap].maxlen,
            rgargmap[imap].flookahead);

        // guesstimate the list cost and store it if it's good
        int listcost = EstimateStripCost(&striplist);
        if(!bestlistcost || (listcost < bestlistcost))
        {
            // free the old best list
            FreeStripListVerts(&striplistbest);

            // store the new best list
            striplistbest = striplist;
            bestlistcost = listcost;
            assert(bestlistcost > 0);
        }
        else
        {
            FreeStripListVerts(&striplist);
        }
    }

#ifdef NEVER
    // Return the strips in [size1 i1 i2 i3][size2 i4 i5 i6]...[0] format
    // Very useful for debugging...
    return stripper.CreateManyStrips(&striplistbest, ppstripindices);
#endif // NEVER

    // return one big long strip
    int numindices = stripper.CreateLongStrip(&striplistbest, ppstripindices);

    if(pnumindices)
        *pnumindices = numindices;
    return numindices;
}

//=========================================================================
// Class used to vertices for locality of access.
//=========================================================================
struct SortEntry
{
public:
    int iFirstUsed;
    int iOrigIndex;

    bool operator<(const SortEntry& rhs)
    {
        return iFirstUsed < rhs.iFirstUsed;
    }
};

//=========================================================================
// Reorder the vertices
//=========================================================================
void ComputeVertexPermutation(int numstripindices, WORD* pstripindices,
                              int* pnumverts, WORD** ppvertexpermutation)
{
    // Sort verts to maximize locality.
    SortEntry* pSortTable = new SortEntry[*pnumverts];

    // Fill in original index.
	int i;
    for( i = 0; i < *pnumverts; i++)
    {
        pSortTable[i].iOrigIndex = i;
        pSortTable[i].iFirstUsed = -1;
    }

    // Fill in first used flag.
    for(i = 0; i < numstripindices; i++)
    {
        int index = pstripindices[i];

        if(pSortTable[index].iFirstUsed == -1)
            pSortTable[index].iFirstUsed = i;
    }

    // Sort the table.
    sort(pSortTable, pSortTable + *pnumverts);

    // Copy re-mapped to orignal vertex permutaion into output array.
    *ppvertexpermutation = new WORD[*pnumverts];

    for(i = 0; i < *pnumverts; i++)
    {
        (*ppvertexpermutation)[i] = pSortTable[i].iOrigIndex;
    }

    // Build original to re-mapped permutation.
    WORD* pInversePermutation = new WORD[numstripindices];

    for(i = 0; i < *pnumverts; i++)
    {
        pInversePermutation[pSortTable[i].iOrigIndex] = i;
    }

    // We need to remap indices as well.
    for(i = 0; i < numstripindices; i++)
    {
        pstripindices[i] = pInversePermutation[pstripindices[i]];
    }

    delete[] pSortTable;
    delete[] pInversePermutation;
}