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

Revision 10764, 10.2 kB (checked in by robert, 5 years ago)

<iterator>, <stdlib.h> and <ctype.h> includes required for QNX compiler

  • 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>
[10764]70#include <stdlib.h>
[1474]71
72// namespace triangle_stripper
73namespace triangle_stripper {
74
75
76
77#include "TriStrip_graph_array.h"
78#include "TriStrip_heap_array.h"
79
[1562]80typedef unsigned int indice;
[1474]81
[1562]82class triangle
83{
84public:
85    triangle();
[9637]86   
87    triangle(const triangle& tri):
88        m_A(tri.m_A),
89        m_B(tri.m_B),
90        m_C(tri.m_C),
91        m_StripID(tri.m_StripID)
92    {
93    }
94   
[1562]95    triangle(const indice A, const indice B, const indice C);
[9637]96   
97    triangle& operator = (const triangle& tri)
98    {
99        if (&tri==this) return *this;
100       
101        m_A = tri.m_A;
102        m_B = tri.m_B;
103        m_C = tri.m_C;
104        m_StripID = tri.m_StripID;
105       
106        return *this;
107    }
[1474]108
[1562]109    void SetStripID(const size_t StripID);
110
111    indice A() const;
112    indice B() const;
113    indice C() const;
114    size_t StripID() const;
115
116private:
117    indice m_A;
118    indice m_B;
119    indice m_C;
120    size_t m_StripID;
121};
122
123
124class triangle_edge
125{
126public:
127    triangle_edge(const indice A, const indice B, const size_t TriPos);
128
129    indice A() const;
130    indice B() const;
131    size_t TriPos() const;
132
133private:
134    indice m_A;
135    indice m_B;
136    size_t m_TriPos;
137};
138
139
140class triangle_degree
141{
142public:
143    triangle_degree();
144    triangle_degree(const size_t TriPos, const size_t Degree);
145
146    size_t Degree() const;
147    size_t TriPos() const;
148
149    void SetDegree(const size_t Degree);
150
151private:
152    size_t m_TriPos;
153    size_t m_Degree;
154};
155
156
157class triangle_strip
158{
159public:
160    enum start_order { ABC = 0, BCA = 1, CAB = 2 };
161
162    triangle_strip();
163    triangle_strip(size_t StartTriPos, start_order StartOrder, size_t Size);
164
165    size_t StartTriPos() const;
166    start_order StartOrder() const;
167    size_t Size() const;
168
169private:
170    size_t        m_StartTriPos;
171    start_order    m_StartOrder;
172    size_t        m_Size;
173};
174
175
176struct _cmp_tri_interface_lt
177{
178    bool operator() (const triangle_edge & a, const triangle_edge & b) const;
179};
180
181
182struct _cmp_tri_degree_gt
183{
184    bool operator () (const triangle_degree & a, const triangle_degree & b) const;
185};
186
[1474]187class tri_stripper
188{
189public:
190
191    // New Public types
192    typedef std::vector<indice> indices;
193
194    enum primitive_type {
195        PT_Triangles        = 0x0004,    // = GL_TRIANGLES
196        PT_Triangle_Strip    = 0x0005    // = GL_TRIANGLE_STRIP
197    };
198
199    struct primitives
200    {
201        indices            m_Indices;
202        primitive_type    m_Type;
203    };
204
205    typedef std::vector<primitives> primitives_vector;
206
207    // constructor/initializer
[1670]208    inline tri_stripper(const indices & TriIndices);
[1474]209   
210    // Settings functions
[1670]211    inline void SetCacheSize(const size_t CacheSize = 16);            // = 0 will disable the cache optimizer
212    inline void SetMinStripSize(const size_t MinStripSize = 2);
[1474]213
214    // Stripper
[10755]215    bool Strip(primitives_vector * out_pPrimitivesVector);
[1474]216
217private:
218
219    friend struct _cmp_tri_interface_lt;
220
[9459]221    tri_stripper& operator = (const tri_stripper&) { return *this; }
[1474]222
223    typedef common_structures::graph_array<triangle, char> triangles_graph;
224    typedef common_structures::heap_array<triangle_degree, _cmp_tri_degree_gt> triangles_heap;
225    typedef std::vector<triangle_edge> triangle_edges;
226    typedef std::vector<size_t> triangle_indices;
227    typedef std::deque<indice> indices_cache;
228
229
230    void InitCache();
231    void InitTriGraph();
232    void InitTriHeap();
[10755]233    bool Stripify();
[1474]234    void AddLeftTriangles();
235
236    void LinkNeighboursTri(const triangle_edges & TriInterface, const triangle_edge Edge);
237    void MarkTriAsTaken(const size_t i);
238
239    triangle_edge GetLatestEdge(const triangle & Triangle, const triangle_strip::start_order Order) const;
240
241    triangle_strip FindBestStrip();
242    triangle_strip ExtendTriToStrip(const size_t StartTriPos, const triangle_strip::start_order StartOrder);
[10755]243    bool BuildStrip(const triangle_strip TriStrip);
[1474]244    void AddIndice(const indice i);
245    void AddIndiceToCache(const indice i, bool CacheHitCount = false);
246    void AddTriToCache(const triangle & Tri, const triangle_strip::start_order Order);
247    void AddTriToIndices(const triangle & Tri, const triangle_strip::start_order Order);
248
249    const indices &        m_TriIndices;
250
251    size_t                m_MinStripSize;
252    size_t                m_CacheSize;
253
254    primitives_vector    m_PrimitivesVector;
255    triangles_graph        m_Triangles;
256    triangles_heap        m_TriHeap;
257    triangle_indices    m_NextCandidates;
258    indices_cache        m_IndicesCache;
259    size_t                m_StripID;
260    size_t                m_CacheHits;
261};
262
263
264
265
266//////////////////////////////////////////////////////////////////////////
267// tri_stripper Inline functions
268//////////////////////////////////////////////////////////////////////////
269
270inline tri_stripper::tri_stripper(const indices & TriIndices) : m_TriIndices(TriIndices) {
271    SetCacheSize();
272    SetMinStripSize();
273}
274
275
276inline void tri_stripper::SetCacheSize(const size_t CacheSize) {
277    m_CacheSize = CacheSize;
278}
279
280
281inline void tri_stripper::SetMinStripSize(const size_t MinStripSize) {
282    m_MinStripSize = MinStripSize;
283}
284
285
[1562]286inline triangle::triangle() { }
[1474]287
288
[1562]289inline triangle::triangle(const indice A, const indice B, const indice C) : m_A(A), m_B(B), m_C(C), m_StripID(0) { }
[1474]290
291
[1562]292inline void triangle::SetStripID(const size_t StripID) {
[1474]293    m_StripID = StripID;
294}
295
296
[1562]297inline indice triangle::A() const {
[1474]298    return m_A;
299}
300
301
[1562]302inline indice triangle::B() const {
[1474]303    return m_B;
304}
305
306
[1562]307inline indice triangle::C() const {
[1474]308    return m_C;
309}
310
311
[1562]312inline size_t triangle::StripID() const {
[1474]313    return m_StripID;
314}
315
316
[1562]317inline triangle_edge::triangle_edge(const indice A, const indice B, const size_t TriPos) : m_A(A), m_B(B), m_TriPos(TriPos) { }
[1474]318
319
[1562]320inline indice triangle_edge::A() const {
[1474]321    return m_A;
322}
323
324
[1562]325inline indice triangle_edge::B() const {
[1474]326    return m_B;
327}
328
329
[1562]330inline size_t triangle_edge::TriPos() const {
[1474]331    return m_TriPos;
332}
333
334
[1562]335inline triangle_degree::triangle_degree() { }
[1474]336
337
[1562]338inline triangle_degree::triangle_degree(const size_t TriPos, const size_t Degree) : m_TriPos(TriPos), m_Degree(Degree) { }
[1474]339
340
[1562]341inline size_t triangle_degree::Degree() const {
[1474]342    return m_Degree;
343}
344
345
[1562]346inline size_t triangle_degree::TriPos() const {
[1474]347    return m_TriPos;
348}
349
350
[1562]351inline void triangle_degree::SetDegree(const size_t Degree) {
[1474]352    m_Degree = Degree;
353}
354
355
[1562]356inline triangle_strip::triangle_strip() : m_StartTriPos(0), m_StartOrder(ABC), m_Size(0) { }
[1474]357
358
[1562]359inline triangle_strip::triangle_strip(const size_t StartTriPos, const start_order StartOrder, const size_t Size)
[1474]360    : m_StartTriPos(StartTriPos), m_StartOrder(StartOrder), m_Size(Size) { }
361
362
[1562]363inline size_t triangle_strip::StartTriPos() const {
[1474]364    return m_StartTriPos;
365}
366
367
[1562]368inline triangle_strip::start_order triangle_strip::StartOrder() const {
[1474]369    return m_StartOrder;
370}
371
372
[1562]373inline size_t triangle_strip::Size() const {
[1474]374    return m_Size;
375}
376
377
[1562]378inline bool _cmp_tri_interface_lt::operator() (const triangle_edge & a, const triangle_edge & b) const {
379    const indice A1 = a.A();
380    const indice B1 = a.B();
381    const indice A2 = b.A();
382    const indice B2 = b.B();
[1474]383
384    if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
385        return true;
386    else
387        return false;
388}
389
390
[1562]391inline bool _cmp_tri_degree_gt::operator () (const triangle_degree & a, const triangle_degree & b) const {
[1474]392    // the triangle with a smaller degree has more priority
393    return a.Degree() > b.Degree();
394}
395
396
397
398
[6461]399} // namespace triangle_stripper
[1474]400
401#endif
Note: See TracBrowser for help on using the browser.