mstristrip.cpp

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

//-----------------------------------------------------------------------------
// FILE: TRISTRIP.CPP
//
// Desc: Xbox tristripper
//
// Copyright (c) 1999-2000 Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------

// identifier was truncated to '255' characters in the debug information
#pragma warning(disable: 4786)
// conversion from 'double' to 'float'
#pragma warning(disable: 4244)
#pragma warning(disable: 4530)

#include <stdio.h>
#include <stdarg.h>
#include <algorithm>
#include <list>
#include <vector>

#include <assert.h>
#ifdef _DEBUG
#include <crtdbg.h>
#endif

#include "mstristrip.h"

using namespace std;

//=========================================================================
// structs
//=========================================================================
typedef vector<WORD> STRIPVERTS;
typedef list<STRIPVERTS *> STRIPLIST;
typedef WORD (*TRIANGLELIST)[3];

struct TRIANGLEINFO
{
    int neighbortri[3];
    int neighboredge[3];
};

// return true if strip starts clockwise
inline bool FIsStripCW(const STRIPVERTS &stripvertices)
{
    // last index should have cw/ccw bool
    return !!stripvertices[stripvertices.size() - 1];
}

// return length of strip
inline int StripLen(const STRIPVERTS &stripvertices)
{
    return stripvertices.size() - 1;
}

// free all stripverts and clear the striplist
inline void FreeStripListVerts(STRIPLIST *pstriplist)
{
    STRIPLIST::iterator istriplist = pstriplist->begin();
    while(istriplist != pstriplist->end())
    {
        STRIPVERTS *pstripverts = *istriplist;
        delete pstripverts;
        pstriplist->erase(istriplist++);
    }
}

//=========================================================================
// main stripper class
//=========================================================================
class CStripper
{
public:
    // ctors/dtors
    CStripper(int numtris, TRIANGLELIST ptriangles);
    ~CStripper();

    // initialize tri info
    void InitTriangleInfo(int tri, int vert);

    // get maximum length strip from tri/vert
    int CreateStrip(int tri, int vert, int maxlen, int *pswaps,
        bool flookahead, bool fstartcw, int *pstriptris, int *pstripverts);

    // stripify entire mesh
    void BuildStrips(STRIPLIST *pstriplist, int maxlen, bool flookahead);

    // blast strip indices to ppstripindices
    int CreateManyStrips(STRIPLIST *pstriplist, WORD **ppstripindices);
    int CreateLongStrip(STRIPLIST *pstriplist, WORD **ppstripindices);

    inline int GetNeighborCount(int tri)
    {
        int count = 0;
        for(int vert = 0; vert < 3; vert++)
        {
            int neighbortri = m_ptriinfo[tri].neighbortri[vert];
            count += (neighbortri != -1) && !m_pused[neighbortri];
        }
        return count;
    }

    // from callee
    int m_numtris;              // # tris
    TRIANGLELIST m_ptriangles;  // trilist

    TRIANGLEINFO *m_ptriinfo;   // tri edge, neighbor info
    int *m_pused;               // tri used flag
};

//=========================================================================
// vertex cache class
//=========================================================================
class CVertCache
{
public:
    CVertCache()
        { Reset(); }
    ~CVertCache()
        {};

    // reset cache
    void Reset()
    {
        m_iCachePtr = 0;
        m_cachehits = 0;
        memset(m_rgCache, 0xff, sizeof(m_rgCache));
    }

    // add vertindex to cache
    bool Add(int strip, int vertindex);

    int NumCacheHits() const
        { return m_cachehits; }

//    enum { CACHE_SIZE = 10 };
    enum { CACHE_SIZE = 18 };

private:
    int m_cachehits;                // current # of cache hits
    WORD m_rgCache[CACHE_SIZE];     // vertex cache
    int m_rgCacheStrip[CACHE_SIZE]; // strip # which added vert
    int m_iCachePtr;                // fifo ptr
};

//=========================================================================
// Get maximum length of strip starting at tri/vert
//=========================================================================
int CStripper::CreateStrip(int tri, int vert, int maxlen, int *pswaps,
    bool flookahead, bool fstartcw, int *pstriptris, int *pstripverts)
{
    *pswaps = 0;

    // this guy has already been used?
    if(m_pused[tri])
        return 0;

    // mark tri as used
    m_pused[tri] = 1;

    int swaps = 0;

    // add first tri info
    pstriptris[0] = tri;
    pstriptris[1] = tri;
    pstriptris[2] = tri;

    if(fstartcw)
    {
        pstripverts[0] = (vert) % 3;
        pstripverts[1] = (vert + 1) % 3;
        pstripverts[2] = (vert + 2) % 3;
    }
    else
    {
        pstripverts[0] = (vert + 1) % 3;
        pstripverts[1] = (vert + 0) % 3;
        pstripverts[2] = (vert + 2) % 3;
    }
    fstartcw = !fstartcw;

    // get next tri information
    int edge = (fstartcw ? vert + 2 : vert + 1) % 3;
    int nexttri = m_ptriinfo[tri].neighbortri[edge];
    int nextvert = m_ptriinfo[tri].neighboredge[edge];

    // start building the strip until we run out of room or indices
	int stripcount;
    for( stripcount = 3; stripcount < maxlen; stripcount++)
    {
        // dead end?
        if(nexttri == -1 || m_pused[nexttri])
            break;

        // move to next tri
        tri = nexttri;
        vert = nextvert;

        // toggle orientation
        fstartcw = !fstartcw;

        // find the next natural edge
        int edge = (fstartcw ? vert + 2 : vert + 1) % 3;
        nexttri = m_ptriinfo[tri].neighbortri[edge];
        nextvert = m_ptriinfo[tri].neighboredge[edge];

        bool fswap = false;
        if(nexttri == -1 || m_pused[nexttri])
        {
            // if the next tri is a dead end - try swapping orientation
            fswap = true;
        }
        else if(flookahead)
        {
            // try a swap and see who our new neighbor would be
            int edgeswap = (fstartcw ? vert + 1 : vert + 2) % 3;
            int nexttriswap = m_ptriinfo[tri].neighbortri[edgeswap];
            int nextvertswap = m_ptriinfo[tri].neighboredge[edgeswap];

            if(nexttriswap != -1 && !m_pused[nexttriswap])
            {
                assert(nexttri != -1);

                // if the swap neighbor has a lower count, change directions
                if(GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri))
                {
                    fswap = true;
                }
                else if(GetNeighborCount(nexttriswap) == GetNeighborCount(nexttri))
                {
                    // if they have the same number of neighbors - check their neighbors
                    edgeswap = (fstartcw ? nextvertswap + 2 : nextvertswap + 1) % 3;
                    nexttriswap = m_ptriinfo[nexttriswap].neighbortri[edgeswap];

                    int edge1 = (fstartcw ? nextvert + 1 : nextvert + 2) % 3;
                    int nexttri1 = m_ptriinfo[nexttri].neighbortri[edge1];

                    if(nexttri1 == -1 || m_pused[nexttri1])
                    {
                        // natural winding order leads us to a dead end so turn
                        fswap = true;
                    }
                    else if(nexttriswap != -1 && !m_pused[nexttriswap])
                    {
                        // check neighbor counts on both directions and swap if it's better
                        if(GetNeighborCount(nexttriswap) < GetNeighborCount(nexttri1))
                            fswap = true;
                    }
                }
            }
        }

        if(fswap)
        {
            // we've been told to change directions so make sure we actually can
            // and then add the swap vertex
            int edgeswap = (fstartcw ? vert + 1 : vert + 2) % 3;
            nexttri = m_ptriinfo[tri].neighbortri[edgeswap];
            nextvert = m_ptriinfo[tri].neighboredge[edgeswap];

            if(nexttri != -1 && !m_pused[nexttri])
            {
                pstriptris[stripcount] = pstriptris[stripcount - 2];
                pstripverts[stripcount] = pstripverts[stripcount - 2];
                stripcount++;
                swaps++;
                fstartcw = !fstartcw;
            }
        }

        // record index information
        pstriptris[stripcount] = tri;
        pstripverts[stripcount] = (vert + 2) % 3;

        // mark triangle as used
        m_pused[tri] = 1;
    }

    // clear the used flags
    for(int j = 2; j < stripcount; j++)
        m_pused[pstriptris[j]] = 0;

    // return swap count and striplen
    *pswaps = swaps;
    return stripcount;
}

//=========================================================================
// Given a striplist and current cache state, pick the best next strip
//=========================================================================
STRIPLIST::iterator FindBestCachedStrip(STRIPLIST *pstriplist,
    const CVertCache &vertcachestate)
{
    if(pstriplist->empty())
        return NULL;

    bool fFlipStrip = false;
    int maxcachehits = -1;
    STRIPLIST::iterator istriplistbest = pstriplist->begin();

    int striplen = StripLen(**istriplistbest);
    bool fstartcw = FIsStripCW(**istriplistbest);

    // go through all the other strips looking for the best caching
    for(STRIPLIST::iterator istriplist = pstriplist->begin();
        istriplist != pstriplist->end();
        ++istriplist)
    {
        bool fFlip = false;
        const STRIPVERTS &stripverts = **istriplist;
        int striplennew = StripLen(stripverts);

        // check cache if this strip is the same type as us (ie: cw/odd)
        if((FIsStripCW(stripverts) == fstartcw) &&
            ((striplen & 0x1) == (striplennew & 0x1)))
        {
            // copy current state of cache
            CVertCache vertcachenew = vertcachestate;

            // figure out what this guy would do to our cache
            for(int ivert = 0; ivert < striplennew; ivert++)
                vertcachenew.Add(2, stripverts[ivert]);

            // even length strip - see if better cache hits reversed
            if(!(striplennew & 0x1))
            {
                CVertCache vertcacheflipped = vertcachestate;

                for(int ivert = StripLen(stripverts) - 1; ivert >= 0; ivert--)
                    vertcacheflipped.Add(2, stripverts[ivert]);

                if(vertcacheflipped.NumCacheHits() > vertcachenew.NumCacheHits())
                {
                    vertcachenew = vertcacheflipped;
                    fFlip = true;
                }
            }

            // record the best number of cache hits to date
            int numcachehits = vertcachenew.NumCacheHits() - vertcachestate.NumCacheHits();
            if(numcachehits > maxcachehits)
            {
                maxcachehits = numcachehits;
                istriplistbest = istriplist;
                fFlipStrip = fFlip;
            }
        }
    }

    if(fFlipStrip)
    {
        STRIPVERTS &stripverts = **istriplistbest;
        STRIPVERTS::iterator vend = stripverts.end();
        
        reverse(stripverts.begin(), --vend);
    }

    // make sure we keep the list in order and always pull off
    // the first dude.
    if(istriplistbest != pstriplist->begin())
        swap(*istriplistbest, *pstriplist->begin());

    return pstriplist->begin();
}


//=========================================================================
// Don't merge the strips - just blast em into the stripbuffer one by one
// (useful for debugging)
//=========================================================================
int CStripper::CreateManyStrips(STRIPLIST *pstriplist, WORD **ppstripindices)
{
    // allow room for each of the strips size plus the final 0
    int indexcount = pstriplist->size() + 1;

    // we're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
	STRIPLIST::iterator istriplist;
    for( istriplist = pstriplist->begin(); istriplist != pstriplist->end(); ++istriplist)
    {
        // add striplength plus potential degenerate to swap ccw --> cw
        indexcount += StripLen(**istriplist) + 1;
    }

    // alloc the space for all this stuff
    WORD *pstripindices = new WORD [indexcount];
    assert(pstripindices);

    CVertCache vertcache;
    int numstripindices = 0;

    for(istriplist = pstriplist->begin();
        !pstriplist->empty();
        istriplist = FindBestCachedStrip(pstriplist, vertcache))
    {
        const STRIPVERTS &stripverts = **istriplist;

        if(!FIsStripCW(stripverts))
        {
            // add an extra index if it's ccw
            pstripindices[numstripindices++] = StripLen(stripverts) + 1;
            pstripindices[numstripindices++] = stripverts[0];
        }
        else
        {
            // add the strip length
            pstripindices[numstripindices++] = StripLen(stripverts);
        }

        // add all the strip indices
        for(int i = 0; i < StripLen(stripverts); i++)
        {
            pstripindices[numstripindices++] = stripverts[i];
            vertcache.Add(1, stripverts[i]);
        }

        // free this guy and pop him off the list
        delete &stripverts;
        pstriplist->pop_front();
    }

    // add terminating zero
    pstripindices[numstripindices++] = 0;
    *ppstripindices = pstripindices;

    return numstripindices;
}

//=========================================================================
// Merge striplist into one big uberlist with (hopefully) optimal caching
//=========================================================================
int CStripper::CreateLongStrip(STRIPLIST *pstriplist, WORD **ppstripindices)
{
    // allow room for one strip length plus a possible 3 extra indices per
    // concatenated strip list plus the final 0
    int indexcount = (pstriplist->size() * 3) + 2;

    // we're storing the strips in [size1 i1 i2 i3][size2 i4 i5 i6][0] format
	STRIPLIST::iterator istriplist;
    for( istriplist = pstriplist->begin(); istriplist != pstriplist->end(); ++istriplist)
    {
        indexcount += StripLen(**istriplist);
    }

    // alloc the space for all this stuff
    WORD *pstripindices = new WORD [indexcount];
    assert(pstripindices);

    CVertCache vertcache;
    int numstripindices = 0;

    // add first strip
    istriplist = pstriplist->begin();
    const STRIPVERTS &stripverts = **istriplist;

    // first strip should be cw
    assert(FIsStripCW(stripverts));

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