source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/libs/tri_stripper.h @ 774

//////////////////////////////////////////////////////////////////////
//
//  Copyright (C) 2004 Tanguy Fautré.
//
//  This software is provided 'as-is', without any express or implied
//  warranty.  In no event will the authors be held liable for any damages
//  arising from the use of this software.
//
//  Permission is granted to anyone to use this software for any purpose,
//  including commercial applications, and to alter it and redistribute it
//  freely, subject to the following restrictions:
//
//  1. The origin of this software must not be misrepresented; you must not
//     claim that you wrote the original software. If you use this software
//     in a product, an acknowledgment in the product documentation would be
//     appreciated but is not required.
//  2. Altered source versions must be plainly marked as such, and must not be
//     misrepresented as being the original software.
//  3. This notice may not be removed or altered from any source distribution.
//
//  Tanguy Fautré
//  softdev@telenet.be
//
//////////////////////////////////////////////////////////////////////
//
//                                                      Tri Stripper
//                                                      ************
//
// Post TnL cache aware triangle stripifier in O(n.log(n)).
//          
// History: see ChangeLog
//
//////////////////////////////////////////////////////////////////////
// SVN: $Id: tri_stripper.h 86 2005-06-08 17:47:27Z gpsnoopy $
//////////////////////////////////////////////////////////////////////

// Protection against old C habits
#if defined(max)
#error "'max' macro defined! It's against the C++ standard. Please use 'std::max' instead (undefine 'max' macro if it was defined in another library)."
#endif

// Protection against old C habits
#if defined(min)
#error "'min' macro defined! It's against the C++ standard. Please use 'std::min' instead (undefine 'min' macro if it was defined in another library)."
#endif



#ifndef TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H
#define TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H

#include <public_types.h>

#include        <detail/cache_simulator.h>
#include        <detail/graph_array.h>
#include        <detail/heap_array.h>
#include        <detail/types.h>

#include        <iostream>
#include        <GeoMesh.h>


namespace triangle_stripper {




class tri_stripper
{
public:

        tri_stripper(const indices & TriIndices);

        void Strip(primitive_vector * out_pPrimitivesVector);

        /* Stripifier Algorithm Settings */
        
        // Set the post-T&L cache size (0 disables the cache optimizer).
        void SetCacheSize(size_t CacheSize = 10);

        // Set the minimum size of a triangle strip (should be at least 2 triangles).
        // The stripifier discard any candidate strips that does not satisfy the minimum size condition.
        void SetMinStripSize(size_t MinStripSize = 2);

        // Set the backward search mode in addition to the forward search mode.
        // In forward mode, the candidate strips are build with the current candidate triangle being the first
        // triangle of the strip. When the backward mode is enabled, the stripifier also tests candidate strips
        // where the current candidate triangle is the last triangle of the strip.
        // Enable this if you want better results at the expense of being slightly slower.
        // Note: Do *NOT* use this when the cache optimizer is enabled; it only gives worse results.
        void SetBackwardSearch(bool Enabled = false);
        
        // Set the cache simulator FIFO behavior (does nothing if the cache optimizer is disabled).
        // When enabled, the cache is simulated as a simple FIFO structure. However, when
        // disabled, indices that trigger cache hits are not pushed into the FIFO structure.
        // This allows simulating some GPUs that do not duplicate cache entries (e.g. NV25 or greater).
        void SetPushCacheHits(bool Enabled = true);

        //      Sets the progress bar function and the increment to update.
        void    SetProgressFunc(Geometry::TIPOFUNC upb,float    increment);

        /* End Settings */

private:

        typedef detail::graph_array<detail::triangle> triangle_graph;
        typedef detail::heap_array<size_t, std::greater<size_t> > triangle_heap;
        typedef std::vector<size_t> candidates;
        typedef triangle_graph::node_iterator tri_iterator;
        typedef triangle_graph::const_node_iterator const_tri_iterator;
        typedef triangle_graph::out_arc_iterator link_iterator;
        typedef triangle_graph::const_out_arc_iterator const_link_iterator;

        void InitTriHeap();
        void Stripify();
        void AddLeftTriangles();
        void ResetStripIDs();

        detail::strip FindBestStrip();
        detail::strip ExtendToStrip(size_t Start, detail::triangle_order Order);
        detail::strip BackExtendToStrip(size_t Start, detail::triangle_order Order, bool ClockWise);
        const_link_iterator LinkToNeighbour(const_tri_iterator Node, bool ClockWise, detail::triangle_order & Order, bool NotSimulation);
        const_link_iterator BackLinkToNeighbour(const_tri_iterator Node, bool ClockWise, detail::triangle_order & Order);
        void BuildStrip(const detail::strip Strip);
        void MarkTriAsTaken(size_t i);
        void AddIndex(index i, bool NotSimulation);
        void BackAddIndex(index i);
        void AddTriangle(const detail::triangle & Tri, detail::triangle_order Order, bool NotSimulation);
        void BackAddTriangle(const detail::triangle & Tri, detail::triangle_order Order);

        bool Cache() const;
        size_t CacheSize() const;

        static detail::triangle_edge FirstEdge(const detail::triangle & Triangle, detail::triangle_order Order);
        static detail::triangle_edge LastEdge(const detail::triangle & Triangle, detail::triangle_order Order);

        primitive_vector                        m_PrimitivesVector;
        triangle_graph                          m_Triangles;
        triangle_heap                           m_TriHeap;
        candidates                                      m_Candidates;
        detail::cache_simulator         m_Cache;
        detail::cache_simulator         m_BackCache;
        size_t                                          m_StripID;
        size_t                                          m_MinStripSize;
        bool                                            m_BackwardSearch;
        bool                                            m_FirstRun;

        //      Progress bar function.
        Geometry::TIPOFUNC      mUPB;
        float                                                           mUPBInc;

};





//////////////////////////////////////////////////////////////////////////
// tri_stripper inline functions
//////////////////////////////////////////////////////////////////////////

inline void tri_stripper::SetCacheSize(const size_t CacheSize)
{
        m_Cache.resize(CacheSize);
        m_BackCache.resize(CacheSize);
}


inline void tri_stripper::SetMinStripSize(const size_t MinStripSize)
{
        if (MinStripSize < 2)
                m_MinStripSize = 2;
        else
                m_MinStripSize = MinStripSize;
}


inline void tri_stripper::SetBackwardSearch(const bool Enabled)
{
        m_BackwardSearch = Enabled;
}



inline void tri_stripper::SetPushCacheHits(bool Enabled)
{
        m_Cache.push_cache_hits(Enabled);
}




} // namespace triangle_stripper




#endif // TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H