root/OpenSceneGraph/trunk/src/osgUtil/TriStrip_tri_stripper.h @ 10755

Revision 10755, 10.1 kB (checked in by robert, 5 years ago)

Removed usaged of throw and catch to enable better compatibility with embedded systems that don't support C++ exceptions efficiently.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
RevLine 
[1474]1// tri_stripper.h: interface for the tri_stripper class.
2//
3//////////////////////////////////////////////////////////////////////
4//
[10755]5//  Copyright (C) 2002 Tanguy Fautrï¿œ.
[1474]6//
7//  This software is provided 'as-is', without any express or implied
8//  warranty.  In no event will the authors be held liable for any damages
9//  arising from the use of this software.
10//
11//  Permission is granted to anyone to use this software for any purpose,
12//  including commercial applications, and to alter it and redistribute it
13//  freely, subject to the following restrictions:
14//
15//  1. The origin of this software must not be misrepresented; you must not
16//     claim that you wrote the original software. If you use this software
17//     in a product, an acknowledgment in the product documentation would be
18//     appreciated but is not required.eap_array.h TriStrip_tri_stripper.cpp  TriStrip_tri_stripper.h
19
20//  2. Altered source versions must be plainly marked as such, and must not be
21//     misrepresented as being the original software.
22//  3. This notice may not be removed or altered from any source distribution.
23//
[10755]24//  Tanguy Fautrï¿œ
[1474]25//  softdev@pandora.be
26//
27//////////////////////////////////////////////////////////////////////
28//
29//                            Tri Stripper
30//                            ************
31//
32// Current version: 1.00 BETA 5 (10/12/2002)
33//
34// Comment: Triangle stripper in O(n.log(n)).
35//         
36//          Currently there are no protection against crazy values
37//          given via SetMinStripSize() and SetCacheSize().
38//          So be careful. (Min. strip size should be equal or greater
39//          than 2, cache size should be about 10 for GeForce 256/2
40//          and about 16-18 for GeForce 3/4.)
41//         
42// History: - 1.00 BETA 5 (10/12/2002) - Fixed a bug in Stripify() that could sometimes
43//                                       cause it to go into an infinite loop.
44//                                       (thanks to Remy for the bug report)
45//          - 1.00 BETA 4 (18/11/2002) - Removed the dependency on OpenGL:
46//                                       modified gl_primitives to primitives,
47//                                       and gl_primitives_vector to primitives_vector;
48//                                       and added primitive_type.
49//                                       (thanks to Patrik for noticing this useless dependency)
50//          - 1.00 BETA 3 (18/11/2002) - Fixed a bug in LinkNeightboursTri() that could cause a crash
51//                                       (thanks to Nicolas for finding it)
52//          - 1.00 BETA 2 (16/11/2002) - Improved portability
53//          - 1.00 BETA 1 (27/10/2002) - First public release
54//
55//////////////////////////////////////////////////////////////////////
56
57#ifndef TRISTRIP_TRI_STRIPPER_H
58#define TRISTRIP_TRI_STRIPPER_H
59
[1488]60// include this to supress daft VisualStudio warnings.
61#include <osg/Export>
62
[1474]63#include <algorithm>
64#include <deque>
65#include <list>
66#include <map>
[1475]67#include <string>
[1474]68
69#include <vector>
70
71// namespace triangle_stripper
72namespace triangle_stripper {
73
74
75
76#include "TriStrip_graph_array.h"
77#include "TriStrip_heap_array.h"
78
[1562]79typedef unsigned int indice;
[1474]80
[1562]81class triangle
82{
83public:
84    triangle();
[9637]85   
86    triangle(const triangle& tri):
87        m_A(tri.m_A),
88        m_B(tri.m_B),
89        m_C(tri.m_C),
90        m_StripID(tri.m_StripID)
91    {
92    }
93   
[1562]94    triangle(const indice A, const indice B, const indice C);
[9637]95   
96    triangle& operator = (const triangle& tri)
97    {
98        if (&tri==this) return *this;
99       
100        m_A = tri.m_A;
101        m_B = tri.m_B;
102        m_C = tri.m_C;
103        m_StripID = tri.m_StripID;
104       
105        return *this;
106    }
[1474]107
[1562]108    void SetStripID(const size_t StripID);
109
110    indice A() const;
111    indice B() const;
112    indice C() const;
113    size_t StripID() const;
114
115private:
116    indice m_A;
117    indice m_B;
118    indice m_C;
119    size_t m_StripID;
120};
121
122
123class triangle_edge
124{
125public:
126    triangle_edge(const indice A, const indice B, const size_t TriPos);
127
128    indice A() const;
129    indice B() const;
130    size_t TriPos() const;
131
132private:
133    indice m_A;
134    indice m_B;
135    size_t m_TriPos;
136};
137
138
139class triangle_degree
140{
141public:
142    triangle_degree();
143    triangle_degree(const size_t TriPos, const size_t Degree);
144
145    size_t Degree() const;
146    size_t TriPos() const;
147
148    void SetDegree(const size_t Degree);
149
150private:
151    size_t m_TriPos;
152    size_t m_Degree;
153};
154
155
156class triangle_strip
157{
158public:
159    enum start_order { ABC = 0, BCA = 1, CAB = 2 };
160
161    triangle_strip();
162    triangle_strip(size_t StartTriPos, start_order StartOrder, size_t Size);
163
164    size_t StartTriPos() const;
165    start_order StartOrder() const;
166    size_t Size() const;
167
168private:
169    size_t        m_StartTriPos;
170    start_order    m_StartOrder;
171    size_t        m_Size;
172};
173
174
175struct _cmp_tri_interface_lt
176{
177    bool operator() (const triangle_edge & a, const triangle_edge & b) const;
178};
179
180
181struct _cmp_tri_degree_gt
182{
183    bool operator () (const triangle_degree & a, const triangle_degree & b) const;
184};
185
[1474]186class tri_stripper
187{
188public:
189
190    // New Public types
191    typedef std::vector<indice> indices;
192
193    enum primitive_type {
194        PT_Triangles        = 0x0004,    // = GL_TRIANGLES
195        PT_Triangle_Strip    = 0x0005    // = GL_TRIANGLE_STRIP
196    };
197
198    struct primitives
199    {
200        indices            m_Indices;
201        primitive_type    m_Type;
202    };
203
204    typedef std::vector<primitives> primitives_vector;
205
206    // constructor/initializer
[1670]207    inline tri_stripper(const indices & TriIndices);
[1474]208   
209    // Settings functions
[1670]210    inline void SetCacheSize(const size_t CacheSize = 16);            // = 0 will disable the cache optimizer
211    inline void SetMinStripSize(const size_t MinStripSize = 2);
[1474]212
213    // Stripper
[10755]214    bool Strip(primitives_vector * out_pPrimitivesVector);
[1474]215
216private:
217
218    friend struct _cmp_tri_interface_lt;
219
[9459]220    tri_stripper& operator = (const tri_stripper&) { return *this; }
[1474]221
222    typedef common_structures::graph_array<triangle, char> triangles_graph;
223    typedef common_structures::heap_array<triangle_degree, _cmp_tri_degree_gt> triangles_heap;
224    typedef std::vector<triangle_edge> triangle_edges;
225    typedef std::vector<size_t> triangle_indices;
226    typedef std::deque<indice> indices_cache;
227
228
229    void InitCache();
230    void InitTriGraph();
231    void InitTriHeap();
[10755]232    bool Stripify();
[1474]233    void AddLeftTriangles();
234
235    void LinkNeighboursTri(const triangle_edges & TriInterface, const triangle_edge Edge);
236    void MarkTriAsTaken(const size_t i);
237
238    triangle_edge GetLatestEdge(const triangle & Triangle, const triangle_strip::start_order Order) const;
239
240    triangle_strip FindBestStrip();
241    triangle_strip ExtendTriToStrip(const size_t StartTriPos, const triangle_strip::start_order StartOrder);
[10755]242    bool BuildStrip(const triangle_strip TriStrip);
[1474]243    void AddIndice(const indice i);
244    void AddIndiceToCache(const indice i, bool CacheHitCount = false);
245    void AddTriToCache(const triangle & Tri, const triangle_strip::start_order Order);
246    void AddTriToIndices(const triangle & Tri, const triangle_strip::start_order Order);
247
248    const indices &        m_TriIndices;
249
250    size_t                m_MinStripSize;
251    size_t                m_CacheSize;
252
253    primitives_vector    m_PrimitivesVector;
254    triangles_graph        m_Triangles;
255    triangles_heap        m_TriHeap;
256    triangle_indices    m_NextCandidates;
257    indices_cache        m_IndicesCache;
258    size_t                m_StripID;
259    size_t                m_CacheHits;
260};
261
262
263
264
265//////////////////////////////////////////////////////////////////////////
266// tri_stripper Inline functions
267//////////////////////////////////////////////////////////////////////////
268
269inline tri_stripper::tri_stripper(const indices & TriIndices) : m_TriIndices(TriIndices) {
270    SetCacheSize();
271    SetMinStripSize();
272}
273
274
275inline void tri_stripper::SetCacheSize(const size_t CacheSize) {
276    m_CacheSize = CacheSize;
277}
278
279
280inline void tri_stripper::SetMinStripSize(const size_t MinStripSize) {
281    m_MinStripSize = MinStripSize;
282}
283
284
[1562]285inline triangle::triangle() { }
[1474]286
287
[1562]288inline triangle::triangle(const indice A, const indice B, const indice C) : m_A(A), m_B(B), m_C(C), m_StripID(0) { }
[1474]289
290
[1562]291inline void triangle::SetStripID(const size_t StripID) {
[1474]292    m_StripID = StripID;
293}
294
295
[1562]296inline indice triangle::A() const {
[1474]297    return m_A;
298}
299
300
[1562]301inline indice triangle::B() const {
[1474]302    return m_B;
303}
304
305
[1562]306inline indice triangle::C() const {
[1474]307    return m_C;
308}
309
310
[1562]311inline size_t triangle::StripID() const {
[1474]312    return m_StripID;
313}
314
315
[1562]316inline triangle_edge::triangle_edge(const indice A, const indice B, const size_t TriPos) : m_A(A), m_B(B), m_TriPos(TriPos) { }
[1474]317
318
[1562]319inline indice triangle_edge::A() const {
[1474]320    return m_A;
321}
322
323
[1562]324inline indice triangle_edge::B() const {
[1474]325    return m_B;
326}
327
328
[1562]329inline size_t triangle_edge::TriPos() const {
[1474]330    return m_TriPos;
331}
332
333
[1562]334inline triangle_degree::triangle_degree() { }
[1474]335
336
[1562]337inline triangle_degree::triangle_degree(const size_t TriPos, const size_t Degree) : m_TriPos(TriPos), m_Degree(Degree) { }
[1474]338
339
[1562]340inline size_t triangle_degree::Degree() const {
[1474]341    return m_Degree;
342}
343
344
[1562]345inline size_t triangle_degree::TriPos() const {
[1474]346    return m_TriPos;
347}
348
349
[1562]350inline void triangle_degree::SetDegree(const size_t Degree) {
[1474]351    m_Degree = Degree;
352}
353
354
[1562]355inline triangle_strip::triangle_strip() : m_StartTriPos(0), m_StartOrder(ABC), m_Size(0) { }
[1474]356
357
[1562]358inline triangle_strip::triangle_strip(const size_t StartTriPos, const start_order StartOrder, const size_t Size)
[1474]359    : m_StartTriPos(StartTriPos), m_StartOrder(StartOrder), m_Size(Size) { }
360
361
[1562]362inline size_t triangle_strip::StartTriPos() const {
[1474]363    return m_StartTriPos;
364}
365
366
[1562]367inline triangle_strip::start_order triangle_strip::StartOrder() const {
[1474]368    return m_StartOrder;
369}
370
371
[1562]372inline size_t triangle_strip::Size() const {
[1474]373    return m_Size;
374}
375
376
[1562]377inline bool _cmp_tri_interface_lt::operator() (const triangle_edge & a, const triangle_edge & b) const {
378    const indice A1 = a.A();
379    const indice B1 = a.B();
380    const indice A2 = b.A();
381    const indice B2 = b.B();
[1474]382
383    if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
384        return true;
385    else
386        return false;
387}
388
389
[1562]390inline bool _cmp_tri_degree_gt::operator () (const triangle_degree & a, const triangle_degree & b) const {
[1474]391    // the triangle with a smaller degree has more priority
392    return a.Degree() > b.Degree();
393}
394
395
396
397
[6461]398} // namespace triangle_stripper
[1474]399
400#endif
Note: See TracBrowser for help on using the browser.