OgreProgressiveMesh.h

Go to the documentation of this file.

/*
-----------------------------------------------------------------------------
This source file is part of OGRE
    (Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2012 Torus Knot Software Ltd

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
-----------------------------------------------------------------------------
*/
// The underlying algorithms in this class are based heavily on:
/*
 *  Progressive Mesh type Polygon Reduction Algorithm
 *  by Stan Melax (c) 1998
 */

#ifndef __ProgressiveMesh_H_
#define __ProgressiveMesh_H_

#include "OgrePrerequisites.h"
#include "OgreVector3.h"
#include "OgreVector2.h"
#include "OgreHardwareVertexBuffer.h"
#include "OgreHardwareIndexBuffer.h"
#include "OgreRenderOperation.h"
#include "OgreSmallVector.h"

namespace Ogre {

    class Mesh;
    class SubMesh;
    
    class _OgreExport BitArray
    {
    public:
        BitArray()                  : bits_ptr(NULL) {}
        BitArray(int bits_count)    : bits_ptr(NULL) { resize(bits_count); }
        BitArray& operator=(const BitArray& ba) { bits = ba.bits; bits_ptr = bits.size() > 0 ? &bits.front() : NULL; return *this; }
        
        bool getBit(size_t i) const { return bits_ptr[i >> 3] & bit_mask[i & 7]; }
        void setBit(size_t i)       { bits_ptr[i >> 3] |= bit_mask[i & 7]; }
        void clearBit(size_t i)     { bits_ptr[i >> 3] &= ~bit_mask[i & 7]; }
        void clearAllBits()         { memset(bits_ptr, 0, bits.size()); }
        
        bool empty() const          { return bits.empty(); }
        void resize(size_t bits_count)
        {       
            bits.resize((bits_count + 7) / 8);
            bits_ptr = bits.size() > 0 ? &bits.front() : NULL;
            clearAllBits();
        }
        
        size_t getBitsCount() const
        {
            size_t count = 0;
            for(unsigned char *ptr = bits_ptr, *end_ptr = bits_ptr + bits.size(); ptr != end_ptr; ++ptr)
            {
                const unsigned char b = *ptr;
                count += bit_count[b & 0xF] + bit_count[b >> 4];
            }
            return count;
        }
        
    private:
        unsigned char*              bits_ptr;       // it`s so performance critical, so we place raw data pointer before all other members
        vector<unsigned char>::type bits;
        
        const static unsigned char  bit_mask[8];    // = { 1, 2, 4, 8, 16, 32, 64, 128 };
        const static unsigned char  bit_count[16];  // = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
    };
    
    class _OgreExport ProgressiveMesh : public ProgMeshAlloc
    {
    public:
        typedef vector<Real>::type LodValueList;
        
        enum VertexReductionQuota
        {
            VRQ_CONSTANT,
            VRQ_PROPORTIONAL,
            VRQ_ERROR_COST
        };

        
        static bool generateLodLevels(Mesh* pMesh, const LodValueList& lodValues,
                                      VertexReductionQuota reductionMethod, Real reductionValue);

        static MeshPtr generateSimplifiedMesh(const String& name, const String& groupName, Mesh* inMesh,
                                              bool dropOriginalGeometry, const LodValueList& lodValues,
                                              VertexReductionQuota reductionMethod, Real reductionValue,
                                              size_t* removedVertexDuplicatesCount);
    protected:
        typedef vector<ProgressiveMesh*>::type ProgressiveMeshList;

        static void initializeProgressiveMeshList(ProgressiveMeshList& pmList, Mesh* pMesh);

        static void freeProgressiveMeshList(ProgressiveMeshList* pmList);

        ProgressiveMesh(SubMesh* pSubMesh);
        virtual ~ProgressiveMesh();

        virtual void addExtraVertexPositionBuffer(const VertexData* vertexData);

        static bool build(ProgressiveMeshList& pmInList,
                          const LodStrategy *lodStrategy, const LodValueList& lodValues,
                          VertexReductionQuota quota, Real reductionValue = 0.5f);
                        
    protected:
        SubMesh* mSubMesh;
        
        VertexData *mVertexData;
        IndexData *mIndexData;

        vector<IndexData*>::type mLodFaceList;
        
        size_t mRemovedVertexDuplicatesCount;   
        size_t mCurrNumIndexes;
        float mInvSquaredBoundBoxDiagonal;
        int mVertexComponentFlags;  

        // Internal classes
        class PMTriangle;
        class PMVertex;
        struct vertexLess;

    public: // VC6 hack

        class _OgrePrivate PMFaceVertex {
        public:
            size_t realIndex;
            PMVertex* commonVertex;
        };

    protected:

        class _OgrePrivate PMTriangle {
        public:
            PMTriangle();
            void setDetails(size_t index, PMFaceVertex *v0, PMFaceVertex *v1, PMFaceVertex *v2);
            void computeNormal(void);
            void replaceVertex(PMFaceVertex *vold, PMFaceVertex *vnew);
            bool hasCommonVertex(PMVertex *v) const;
            bool hasFaceVertex(PMFaceVertex *v) const;
            PMFaceVertex* getFaceVertexFromCommon(PMVertex* commonVert);
            void notifyRemoved(void);

            PMFaceVertex*   vertex[3];  // the 3 points that make this tri
            Vector3         normal;     // unit vector orthogonal to this face
            Real            area;
            bool            removed;    // true if this tri is now removed
            size_t          index;
        };

        class _OgrePrivate PMVertex {
        public:
            enum BorderStatus { BS_UNKNOWN = 0, BS_NOT_BORDER, BS_BORDER };
            typedef SmallVector<PMVertex *, 8> NeighborList;
            typedef SmallVector<PMTriangle *, 8> FaceList;

        public:
            PMVertex() : mBorderStatus(BS_UNKNOWN), removed(false) {}

            void setDetails(size_t index, const Vector3& pos, const Vector3& normal, const Vector2& uv);
        
            bool isNearEnough(PMVertex* other) const;
            void removeIfNonNeighbor(PMVertex *n);
            void initBorderStatus(void);
            bool isManifoldEdgeWith(PMVertex* v); // is edge this->src a manifold edge?
            void notifyRemoved(void);
            void calculateNormal();
        
            Vector3 position;  // location of point in euclidean space
            Vector3 normal;
            Vector2 uv;
            
            size_t index;       // place of vertex in original list

            BorderStatus mBorderStatus;         
            bool      removed;   // true if this vert is now removed
            bool      toBeRemoved; // debug

            Real collapseCost;  // cached cost of collapsing edge
            PMVertex * collapseTo; // candidate vertex for collapse
            
            NeighborList neighbor; // adjacent vertices
            FaceList face;     // adjacent triangles
        };
        
        typedef vector<PMTriangle>::type TriangleList;
        typedef vector<PMFaceVertex>::type FaceVertexList;
        typedef vector<PMVertex>::type CommonVertexList;
        typedef std::pair<Real, unsigned int> CostIndexPair;
        typedef vector<CostIndexPair>::type WorstCostList;

        struct PMWorkingData
        {
            TriangleList mTriList; 
            FaceVertexList mFaceVertList; // The vertex details referenced by the triangles
            CommonVertexList mVertList; // The master list of common vertices
        };

        typedef vector<PMWorkingData>::type WorkingDataList;
        WorkingDataList mWorkingData;

        WorstCostList   mWorstCosts;        // sorted by cost, but some of entries are invalidated, so check invalidCostMask
        BitArray        mInvalidCostMask;   // indexed by vertex index
        size_t          mInvalidCostCount;
        size_t          mWorstCostsSize;
        size_t          mNextWorstCostHint; // getNextCollapser() uses it to reduce complexity from O(n^2) to O(n)
            
        mutable PMVertex::FaceList mEdgeAdjacentSides;

        void addWorkingData(const VertexData* vertexData, const IndexData* indexData);
        void mergeWorkingDataBorders();
        
        void initialiseEdgeCollapseCosts(void);
        Real computeEdgeCollapseCost(PMVertex *src, PMVertex *dest) const;
        bool collapseInvertsNormals(PMVertex *src, PMVertex *dest) const;
        Real computeEdgeCostAtVertexForBuffer(PMVertex* v);
        Real computeEdgeCostAtVertex(size_t vertIndex);
        void computeAllCosts(void);

        static size_t getInvalidCostCount(ProgressiveMesh::ProgressiveMeshList& pmList);
        static bool recomputeInvalidCosts(ProgressiveMeshList& pmInList);
        void recomputeInvalidCosts();
        void sortIndexesByCost();
        static int cmpByCost(const void* p1, const void* p2); // comparator for mWorstCosts sorting
        
        static void getNextCollapser(ProgressiveMeshList& pmList, ProgressiveMesh*& pm, CostIndexPair*& bestCollapser);
        CostIndexPair* getNextCollapser();
        
        void bakeNewLOD(IndexData* pData);
        static void bakeLodUsage(Mesh* pMesh, LodStrategy *lodStrategy, const LodValueList& lodValues, bool skipFirstLodLevel = false);

        void collapse(PMVertex *collapser);

        typedef std::pair<unsigned, PMVertex*> IndexVertexPair;
        static void bakeSimplifiedMesh(Mesh* destMesh, Mesh* srcMesh, ProgressiveMeshList& pmList, bool dropFirstLodLevel = false);
        static void createSimplifiedVertexData(vector<IndexVertexPair>::type& usedVertices, VertexData* inVData, VertexData*& outVData, AxisAlignedBox& aabox);
        static void createIndexMap(vector<IndexVertexPair>::type& usedVertices, unsigned allVertexCount, vector<unsigned>::type& indexMap);
        
        void dumpContents(const String& log);
    };
            
    template <typename T> struct HardwareBufferLockGuard
    {
        HardwareBufferLockGuard(const T& p, HardwareBuffer::LockOptions options)
        : pBuf(p)
        {
            pData = pBuf->lock(options);
        }
        HardwareBufferLockGuard(const T& p, size_t offset, size_t length, HardwareBuffer::LockOptions options)
        : pBuf(p)
        {
            pData = pBuf->lock(offset, length, options);
        }       
        ~HardwareBufferLockGuard()
        {
            pBuf->unlock();
        }
        const T& pBuf;
        void* pData;
    };
    
    typedef HardwareBufferLockGuard<HardwareVertexBufferSharedPtr> VertexBufferLockGuard;
    typedef HardwareBufferLockGuard<HardwareIndexBufferSharedPtr> IndexBufferLockGuard;
    
}

#endif