Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# tri_stripper.h

Go to the documentation of this file.

    00001 // tri_stripper.h: interface for the tri_stripper class.
    00002 //
    00003 //////////////////////////////////////////////////////////////////////
    00004 //
    00005 //  Copyright (C) 2002 Tanguy Fautré.
    00006 //
    00007 //  This software is provided 'as-is', without any express or implied
    00008 //  warranty.  In no event will the authors be held liable for any damages
    00009 //  arising from the use of this software.
    00010 //
    00011 //  Permission is granted to anyone to use this software for any purpose,
    00012 //  including commercial applications, and to alter it and redistribute it
    00013 //  freely, subject to the following restrictions:
    00014 //
    00015 //  1. The origin of this software must not be misrepresented; you must not
    00016 //     claim that you wrote the original software. If you use this software
    00017 //     in a product, an acknowledgment in the product documentation would be
    00018 //     appreciated but is not required.
    00019 //  2. Altered source versions must be plainly marked as such, and must not be
    00020 //     misrepresented as being the original software.
    00021 //  3. This notice may not be removed or altered from any source distribution.
    00022 //
    00023 //  Tanguy Fautré
    00024 //  softdev@pandora.be
    00025 //
    00026 //////////////////////////////////////////////////////////////////////
    00027 //
    00028 //                          Tri Stripper
    00029 //                          ************
    00030 //
    00031 // Current version: 1.00 BETA 5 (10/12/2002)
    00032 //
    00033 // Comment: Triangle stripper in O(n.log(n)).
    00034 //
    00035 //          Currently there are no protection against crazy values
    00036 //          given via SetMinStripSize() and SetCacheSize().
    00037 //          So be careful. (Min. strip size should be equal or greater
    00038 //          than 2, cache size should be about 10 for GeForce 256/2
    00039 //          and about 16-18 for GeForce 3/4.)
    00040 //
    00041 // History: - 1.00 BETA 5 (10/12/2002) - Fixed a bug in Stripify() that could sometimes
    00042 //                                       cause it to go into an infinite loop.
    00043 //                                       (thanks to Remy for the bug report)
    00044 //          - 1.00 BETA 4 (18/11/2002) - Removed the dependency on OpenGL:
    00045 //                                       modified gl_primitives to primitives,
    00046 //                                       and gl_primitives_vector to primitives_vector;
    00047 //                                       and added primitive_type.
    00048 //                                       (thanks to Patrik for noticing this useless dependency)
    00049 //          - 1.00 BETA 3 (18/11/2002) - Fixed a bug in LinkNeightboursTri() that could cause a crash
    00050 //                                       (thanks to Nicolas for finding it)
    00051 //          - 1.00 BETA 2 (16/11/2002) - Improved portability
    00052 //          - 1.00 BETA 1 (27/10/2002) - First public release
    00053 //
    00054 //////////////////////////////////////////////////////////////////////
    00055
    00056 #ifndef TRI_STRIPPER_H
    00057 #define TRI_STRIPPER_H
    00058
    00059 #include <vector>
    00060
    00061 #include "graph_array.h"
    00062 #include "heap_array.h"
    00063
    00064
    00065 // namespace triangle_stripper
    00066 namespace triangle_stripper {
    00067
    00068
    00069 class tri_stripper
    00070 {
    00071 public:
    00072
    00073     // New Public types
    00074     typedef unsigned short indice;
    00075     typedef std::vector<indice> indices;
    00076
    00077     enum primitive_type {
    00078         PT_Triangles        = 0x0004,   // = GL_TRIANGLES
    00079         PT_Triangle_Strip   = 0x0005    // = GL_TRIANGLE_STRIP
    00080     };
    00081
    00082     struct primitives
    00083     {
    00084         indices         m_Indices;
    00085         primitive_type  m_Type;
    00086     };
    00087
    00088     typedef std::vector<primitives> primitives_vector;
    00089
    00090     struct triangles_indices_error { };
    00091
    00092
    00093     // constructor/initializer
    00094     tri_stripper(const indices & TriIndices);
    00095
    00096     // Settings functions
    00097     void SetCacheSize(const size_t CacheSize = 16);         // = 0 will disable the cache optimizer
    00098     void SetMinStripSize(const size_t MinStripSize = 2);
    00099
    00100     // Stripper
    00101     void Strip(primitives_vector * out_pPrimitivesVector);  // throw triangles_indices_error();
    00102
    00103 private:
    00104
    00105     friend struct _cmp_tri_interface_lt;
    00106
    00107
    00108     class triangle
    00109     {
    00110     public:
    00111         triangle();
    00112         triangle(const indice A, const indice B, const indice C);
    00113
    00114         void SetStripID(const size_t StripID);
    00115
    00116         indice A() const;
    00117         indice B() const;
    00118         indice C() const;
    00119         size_t StripID() const;
    00120
    00121     private:
    00122         indice m_A;
    00123         indice m_B;
    00124         indice m_C;
    00125         size_t m_StripID;
    00126     };
    00127
    00128
    00129     class triangle_edge
    00130     {
    00131     public:
    00132         triangle_edge(const indice A, const indice B, const size_t TriPos);
    00133
    00134         indice A() const;
    00135         indice B() const;
    00136         size_t TriPos() const;
    00137
    00138     private:
    00139         indice m_A;
    00140         indice m_B;
    00141         size_t m_TriPos;
    00142     };
    00143
    00144
    00145     class triangle_degree
    00146     {
    00147     public:
    00148         triangle_degree();
    00149         triangle_degree(const size_t TriPos, const size_t Degree);
    00150
    00151         size_t Degree() const;
    00152         size_t TriPos() const;
    00153
    00154         void SetDegree(const size_t Degree);
    00155
    00156     private:
    00157         size_t m_TriPos;
    00158         size_t m_Degree;
    00159     };
    00160
    00161
    00162     class triangle_strip
    00163     {
    00164     public:
    00165         enum start_order { ABC = 0, BCA = 1, CAB = 2 };
    00166
    00167         triangle_strip();
    00168         triangle_strip(size_t StartTriPos, start_order StartOrder, size_t Size);
    00169
    00170         size_t StartTriPos() const;
    00171         start_order StartOrder() const;
    00172         size_t Size() const;
    00173
    00174     private:
    00175         size_t      m_StartTriPos;
    00176         start_order m_StartOrder;
    00177         size_t      m_Size;
    00178     };
    00179
    00180
    00181     struct _cmp_tri_interface_lt
    00182     {
    00183         bool operator() (const triangle_edge & a, const triangle_edge & b) const;
    00184     };
    00185
    00186
    00187     struct _cmp_tri_degree_gt
    00188     {
    00189         bool operator () (const triangle_degree & a, const triangle_degree & b) const;
    00190     };
    00191
    00192
    00193     typedef common_structures::graph_array<triangle, char> triangles_graph;
    00194     typedef common_structures::heap_array<triangle_degree, _cmp_tri_degree_gt> triangles_heap;
    00195     typedef std::vector<triangle_edge> triangle_edges;
    00196     typedef std::vector<size_t> triangle_indices;
    00197     typedef std::deque<indice> indices_cache;
    00198
    00199
    00200     void InitCache();
    00201     void InitTriGraph();
    00202     void InitTriHeap();
    00203     void Stripify();
    00204     void AddLeftTriangles();
    00205
    00206     void LinkNeighboursTri(const triangle_edges & TriInterface, const triangle_edge Edge);
    00207     void MarkTriAsTaken(const size_t i);
    00208
    00209     triangle_edge GetLatestEdge(const triangle & Triangle, const triangle_strip::start_order Order) const;
    00210
    00211     triangle_strip FindBestStrip();
    00212     triangle_strip ExtendTriToStrip(const size_t StartTriPos, const triangle_strip::start_order StartOrder);
    00213     void BuildStrip(const triangle_strip TriStrip);
    00214     void AddIndice(const indice i);
    00215     void AddIndiceToCache(const indice i, bool CacheHitCount = false);
    00216     void AddTriToCache(const triangle & Tri, const triangle_strip::start_order Order);
    00217     void AddTriToIndices(const triangle & Tri, const triangle_strip::start_order Order);
    00218
    00219     const indices &     m_TriIndices;
    00220
    00221     size_t              m_MinStripSize;
    00222     size_t              m_CacheSize;
    00223
    00224     primitives_vector   m_PrimitivesVector;
    00225     triangles_graph     m_Triangles;
    00226     triangles_heap      m_TriHeap;
    00227     triangle_indices    m_NextCandidates;
    00228     indices_cache       m_IndicesCache;
    00229     size_t              m_StripID;
    00230     size_t              m_CacheHits;
    00231 };
    00232
    00233
    00234
    00235
    00236 //////////////////////////////////////////////////////////////////////////
    00237 // tri_stripper Inline functions
    00238 //////////////////////////////////////////////////////////////////////////
    00239
    00240 inline tri_stripper::tri_stripper(const indices & TriIndices) : m_TriIndices(TriIndices) {
    00241     SetCacheSize();
    00242     SetMinStripSize();
    00243 }
    00244
    00245
    00246 inline void tri_stripper::SetCacheSize(const size_t CacheSize) {
    00247     m_CacheSize = CacheSize;
    00248 }
    00249
    00250
    00251 inline void tri_stripper::SetMinStripSize(const size_t MinStripSize) {
    00252     m_MinStripSize = MinStripSize;
    00253 }
    00254
    00255
    00256 inline tri_stripper::triangle::triangle() { }
    00257
    00258
    00259 inline tri_stripper::triangle::triangle(const indice A, const indice B, const indice C) : m_A(A), m_B(B), m_C(C), m_StripID(0) { }
    00260
    00261
    00262 inline void tri_stripper::triangle::SetStripID(const size_t StripID) {
    00263     m_StripID = StripID;
    00264 }
    00265
    00266
    00267 inline tri_stripper::indice tri_stripper::triangle::A() const {
    00268     return m_A;
    00269 }
    00270
    00271
    00272 inline tri_stripper::indice tri_stripper::triangle::B() const {
    00273     return m_B;
    00274 }
    00275
    00276
    00277 inline tri_stripper::indice tri_stripper::triangle::C() const {
    00278     return m_C;
    00279 }
    00280
    00281
    00282 inline size_t tri_stripper::triangle::StripID() const {
    00283     return m_StripID;
    00284 }
    00285
    00286
    00287 inline tri_stripper::triangle_edge::triangle_edge(const indice A, const indice B, const size_t TriPos) : m_A(A), m_B(B), m_TriPos(TriPos) { }
    00288
    00289
    00290 inline tri_stripper::indice tri_stripper::triangle_edge::A() const {
    00291     return m_A;
    00292 }
    00293
    00294
    00295 inline tri_stripper::indice tri_stripper::triangle_edge::B() const {
    00296     return m_B;
    00297 }
    00298
    00299
    00300 inline size_t tri_stripper::triangle_edge::TriPos() const {
    00301     return m_TriPos;
    00302 }
    00303
    00304
    00305 inline tri_stripper::triangle_degree::triangle_degree() { }
    00306
    00307
    00308 inline tri_stripper::triangle_degree::triangle_degree(const size_t TriPos, const size_t Degree) : m_TriPos(TriPos), m_Degree(Degree) { }
    00309
    00310
    00311 inline size_t tri_stripper::triangle_degree::Degree() const {
    00312     return m_Degree;
    00313 }
    00314
    00315
    00316 inline size_t tri_stripper::triangle_degree::TriPos() const {
    00317     return m_TriPos;
    00318 }
    00319
    00320
    00321 inline void tri_stripper::triangle_degree::SetDegree(const size_t Degree) {
    00322     m_Degree = Degree;
    00323 }
    00324
    00325
    00326 inline tri_stripper::triangle_strip::triangle_strip() : m_StartTriPos(0), m_StartOrder(ABC), m_Size(0) { }
    00327
    00328
    00329 inline tri_stripper::triangle_strip::triangle_strip(const size_t StartTriPos, const start_order StartOrder, const size_t Size)
    00330     : m_StartTriPos(StartTriPos), m_StartOrder(StartOrder), m_Size(Size) { }
    00331
    00332
    00333 inline size_t tri_stripper::triangle_strip::StartTriPos() const {
    00334     return m_StartTriPos;
    00335 }
    00336
    00337
    00338 inline tri_stripper::triangle_strip::start_order tri_stripper::triangle_strip::StartOrder() const {
    00339     return m_StartOrder;
    00340 }
    00341
    00342
    00343 inline size_t tri_stripper::triangle_strip::Size() const {
    00344     return m_Size;
    00345 }
    00346
    00347
    00348 inline bool tri_stripper::_cmp_tri_interface_lt::operator() (const triangle_edge & a, const triangle_edge & b) const {
    00349     const tri_stripper::indice A1 = a.A();
    00350     const tri_stripper::indice B1 = a.B();
    00351     const tri_stripper::indice A2 = b.A();
    00352     const tri_stripper::indice B2 = b.B();
    00353
    00354     if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
    00355         return true;
    00356     else
    00357         return false;
    00358 }
    00359
    00360
    00361 inline bool tri_stripper::_cmp_tri_degree_gt::operator () (const triangle_degree & a, const triangle_degree & b) const {
    00362     // the triangle with a smaller degree has more priority
    00363     return a.Degree() > b.Degree();
    00364 }
    00365
    00366
    00367
    00368
    00369 }; // namespace triangle_stripper
    00370
    00371 #endif