source: downloads/ogre_src_v1-9-0/OgreMain/include/OgreProgressiveMeshGenerator.h @ 156

/*
 * -----------------------------------------------------------------------------
 * This source file is part of OGRE
 * (Object-oriented Graphics Rendering Engine)
 * For the latest info, see http://www.ogre3d.org/
 *
 * Copyright (c) 2000-2013 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.
 * -----------------------------------------------------------------------------
 */

#ifndef __ProgressiveMeshGenerator_H_
#define __ProgressiveMeshGenerator_H_

#include "OgrePrerequisites.h"
#include "OgreVector3.h"
#include "OgreSmallVector.h"
#include "OgreMesh.h"
#include "OgreLodConfig.h"

namespace Ogre
{

class _OgreExport ProgressiveMeshGeneratorBase
{
public:
        /**
         * @brief Generates the LOD levels for a mesh.
         * 
         * @param lodConfig Specification of the requested LOD levels.
         */
        virtual void generateLodLevels(LodConfig& lodConfig) = 0;

        /**
         * @brief Generates the LOD levels for a mesh without configuring it.
         *
         * @param mesh Generate the LOD for this mesh.
         */
        virtual void generateAutoconfiguredLodLevels(MeshPtr& mesh);

        /**
         * @brief Fills LOD Config with a config, which works on any mesh.
         *
         * @param inMesh Optimize for this mesh.
         * @param outLodConfig LOD configuration storing the output.
         */
        virtual void getAutoconfig(MeshPtr& inMesh, LodConfig& outLodConfig);

        virtual ~ProgressiveMeshGeneratorBase() { }
};

/**
 * @brief Improved version of ProgressiveMesh.
 */
class _OgreExport ProgressiveMeshGenerator :
        public ProgressiveMeshGeneratorBase
{
public:

        ProgressiveMeshGenerator();
        virtual ~ProgressiveMeshGenerator();

        /// @copydoc ProgressiveMeshGeneratorBase::generateLodLevels
        void generateLodLevels(LodConfig& lodConfig);

protected:

        // VectorSet is basically a helper to use a vector as a small set container.
        // Also these functions keep the code clean and fast.
        // You can insert in O(1) time, if you know that it doesn't exists.
        // You can remove in O(1) time, if you know the position of the item.
        template<typename T, unsigned S>
        struct _OgrePrivate VectorSet :
                public SmallVector<T, S> {
                typedef typename SmallVector<T, S>::iterator iterator;

                void addNotExists(const T& item); // Complexity: O(1)!!
                void remove(iterator it); // Complexity: O(1)!!
                iterator add(const T& item); // Complexity: O(N)
                void removeExists(const T& item); // Complexity: O(N)
                bool remove(const T& item); // Complexity: O(N)
                void replaceExists(const T& oldItem, const T& newItem); // Complexity: O(N)
                bool has(const T& item); // Complexity: O(N)
                iterator find(const T& item); // Complexity: O(N)
                iterator findExists(const T& item); // Complexity: O(N)
        };

        struct PMEdge;
        struct PMVertex;
        struct PMTriangle;
        struct PMVertexHash;
        struct PMVertexEqual;
        struct PMCollapseCostLess;
        struct PMCollapsedEdge;
        struct PMIndexBufferInfo;

        typedef vector<PMVertex>::type VertexList;
        typedef vector<PMTriangle>::type TriangleList;
        typedef HashSet<PMVertex*, PMVertexHash, PMVertexEqual> UniqueVertexSet;
        typedef multimap<Real, PMVertex*>::type CollapseCostHeap;
        typedef vector<PMVertex*>::type VertexLookupList;

        typedef VectorSet<PMEdge, 8> VEdges;
        typedef VectorSet<PMTriangle*, 7> VTriangles;

        typedef vector<PMCollapsedEdge>::type CollapsedEdges;
        typedef vector<PMIndexBufferInfo>::type IndexBufferInfoList;

        // Hash function for UniqueVertexSet.
        struct _OgrePrivate PMVertexHash {
                ProgressiveMeshGenerator* mGen;

                PMVertexHash() { assert(0); }
                PMVertexHash(ProgressiveMeshGenerator* gen) { mGen = gen; }
                size_t operator() (const PMVertex* v) const;
        };

        // Equality function for UniqueVertexSet.
        struct _OgrePrivate PMVertexEqual {
                bool operator() (const PMVertex* lhs, const PMVertex* rhs) const;
        };

        // Directed edge
        struct _OgrePrivate PMEdge {
                PMVertex* dst;
                Real collapseCost;
                int refCount;

                explicit PMEdge(PMVertex* destination);
                bool operator== (const PMEdge& other) const;
                PMEdge& operator= (const PMEdge& b);
                PMEdge(const PMEdge& b);
                bool operator< (const PMEdge& other) const;
        };

        struct _OgrePrivate PMVertex {
                Vector3 position;
                VEdges edges;
                VTriangles triangles; /// Triangle ID set, which are using this vertex.

                PMVertex* collapseTo;
                bool seam;
                CollapseCostHeap::iterator costHeapPosition; /// Iterator pointing to the position in the mCollapseCostSet, which allows fast remove.
        };

        struct _OgrePrivate PMTriangle {
                PMVertex* vertex[3];
                Vector3 normal;
                bool isRemoved;
                unsigned short submeshID; /// ID of the submesh. Usable with mMesh.getSubMesh() function.
                unsigned int vertexID[3]; /// Vertex ID in the buffer associated with the submeshID.

                void computeNormal();
                bool hasVertex(const PMVertex* v) const;
                unsigned int getVertexID(const PMVertex* v) const;
                bool isMalformed();
        };

        struct _OgrePrivate PMIndexBufferInfo {
                size_t indexSize;
                size_t indexCount;
        };

        union _OgrePrivate IndexBufferPointer {
                unsigned short* pshort;
                unsigned int* pint;
        };

        struct _OgrePrivate PMCollapsedEdge {
                unsigned int srcID;
                unsigned int dstID;
                unsigned short submeshID;
        };

        VertexLookupList mSharedVertexLookup;
        VertexLookupList mVertexLookup;
        VertexList mVertexList;
        TriangleList mTriangleList;
        UniqueVertexSet mUniqueVertexSet;
        CollapseCostHeap mCollapseCostHeap;
        CollapsedEdges tmpCollapsedEdges; // Tmp container used in collapse().
        IndexBufferInfoList mIndexBufferInfoList;

        MeshPtr mMesh;

#ifndef NDEBUG
        /**
         * @brief The name of the mesh being processed.
         *
         * This is separate from mMesh in order to allow for access from background threads.
         */
        String mMeshName;
#endif
        Real mMeshBoundingSphereRadius;
        Real mCollapseCostLimit;

        size_t calcLodVertexCount(const LodLevel& lodConfig);
        void tuneContainerSize();
        void addVertexData(VertexData* vertexData, bool useSharedVertexLookup);
        template<typename IndexType>
        void addIndexDataImpl(IndexType* iPos, const IndexType* iEnd, VertexLookupList& lookup, unsigned short submeshID);
        void addIndexData(IndexData* indexData, bool useSharedVertexLookup, unsigned short submeshID);

        void computeCosts();
        bool isBorderVertex(const PMVertex* vertex) const;
        PMEdge* getPointer(VEdges::iterator it);
        void computeVertexCollapseCost(PMVertex* vertex);
        Real computeEdgeCollapseCost(PMVertex* src, PMEdge* dstEdge);
        virtual void bakeLods();
        void collapse(PMVertex* vertex);
        void initialize();
        void computeLods(LodConfig& lodConfigs);
        void updateVertexCollapseCost(PMVertex* src);

        bool hasSrcID(unsigned int srcID, unsigned short submeshID);
        size_t findDstID(unsigned int srcID, unsigned short submeshID);
        void replaceVertexID(PMTriangle* triangle, unsigned int oldID, unsigned int newID, PMVertex* dst);

#ifndef NDEBUG
        void assertValidVertex(PMVertex* v);
        void assertValidMesh();
        void assertOutdatedCollapseCost(PMVertex* vertex);
#endif // ifndef NDEBUG

        void addTriangleToEdges(PMTriangle* triangle);
        void removeTriangleFromEdges(PMTriangle* triangle, PMVertex* skip = NULL);
        void addEdge(PMVertex* v, const PMEdge& edge);
        void removeEdge(PMVertex* v, const PMEdge& edge);
        void printTriangle(PMTriangle* triangle, stringstream& str);
        PMTriangle* findSideTriangle(const PMVertex* v1, const PMVertex* v2);
        bool isDuplicateTriangle(PMTriangle* triangle, PMTriangle* triangle2);
        PMTriangle* isDuplicateTriangle(PMTriangle* triangle);
        int getTriangleID(PMTriangle* triangle);
        void cleanupMemory();
};

}
#endif