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

Revision 774, 13.6 KB checked in by gumbau, 19 years ago (diff)

GTGeometry and GeoTool? initial imports

Line 
1//
2// Copyright (C) 2004 Tanguy Fautré.
3// For conditions of distribution and use,
4// see copyright notice in tri_stripper.h
5//
6//////////////////////////////////////////////////////////////////////
7// SVN: $Id: tri_stripper.cpp 86 2005-06-08 17:47:27Z gpsnoopy $
8//////////////////////////////////////////////////////////////////////
9
10#include "tri_stripper.h"
11
12#include "detail/connectivity_graph.h"
13#include "detail/policy.h"
14
15#include <cassert>
16
17
18
19
20namespace triangle_stripper {
21
22        using namespace detail;
23
24
25
26
27tri_stripper::tri_stripper(const indices & TriIndices)
28        : m_Triangles(TriIndices.size() / 3), // Silently ignore extra indices if (Indices.size() % 3 != 0)
29          m_StripID(0),
30          m_FirstRun(true)
31{
32        SetCacheSize();
33        SetMinStripSize();
34        SetBackwardSearch();
35        SetPushCacheHits();
36
37        make_connectivity_graph(m_Triangles, TriIndices);
38
39        //      Initialize      Progress bar function.
40        mUPB    =       NULL;
41}
42
43
44
45void tri_stripper::Strip(primitive_vector * out_pPrimitivesVector)
46{
47        assert(out_pPrimitivesVector);
48
49        if (! m_FirstRun) {
50                unmark_nodes(m_Triangles);
51                ResetStripIDs();
52                m_Cache.reset();
53                m_TriHeap.clear();
54                m_Candidates.clear();
55                m_StripID = 0;
56
57                m_FirstRun = false;
58        }
59
60        out_pPrimitivesVector->clear();
61
62        InitTriHeap();
63
64        Stripify();
65        AddLeftTriangles();
66       
67        std::swap(m_PrimitivesVector, (* out_pPrimitivesVector));
68}
69
70
71
72void tri_stripper::InitTriHeap()
73{
74        m_TriHeap.reserve(m_Triangles.size());
75
76        // Set up the triangles priority queue
77        // The lower the number of available neighbour triangles, the higher the priority.
78        for (size_t i = 0; i < m_Triangles.size(); ++i)
79                m_TriHeap.push(m_Triangles[i].out_size());
80
81        // We're not going to add new elements anymore
82        m_TriHeap.lock();
83
84        // Remove useless triangles
85        // Note: we had to put all of them into the heap before to ensure coherency of the heap_array object
86        while ((! m_TriHeap.empty()) && (m_TriHeap.top() == 0))
87                m_TriHeap.pop();
88}
89
90
91
92void tri_stripper::ResetStripIDs()
93{
94        for (triangle_graph::node_iterator it = m_Triangles.begin(); it != m_Triangles.end(); ++it)
95                (**it).ResetStripID();
96}
97
98
99void tri_stripper::Stripify()
100{
101        float           percent;
102        size_t  triangle_count;
103        size_t  current_triangles;
104       
105        //      Gets the triangle count.
106        triangle_count  =       m_TriHeap.size();
107       
108        while (! m_TriHeap.empty())
109        {
110                //      If progres bar is activated.
111                if (mUPB)
112                {
113                        current_triangles       =       m_TriHeap.size();
114               
115                        percent =       (mUPBInc        *       (triangle_count - current_triangles)) / triangle_count;
116
117                        triangle_count  =       current_triangles;
118
119                        //      Update progress bar.
120                        mUPB(percent);
121                }
122               
123                // There is no triangle in the candidates list,
124                // refill it with the loneliest triangle
125                const size_t HeapTop = m_TriHeap.position(0);
126                m_Candidates.push_back(HeapTop);
127
128                while (! m_Candidates.empty())
129                {
130                        // Note: FindBestStrip empties the candidate list,
131                        // while BuildStrip refills it
132                        const strip TriStrip = FindBestStrip();
133
134                        if (TriStrip.Size() >= m_MinStripSize)
135                        {
136                                BuildStrip(TriStrip);
137                        }
138                }
139
140                if (! m_TriHeap.removed(HeapTop))
141                {
142                        m_TriHeap.erase(HeapTop);
143                }
144
145                // Eliminate all the triangles that have now become useless
146                while ((! m_TriHeap.empty()) && (m_TriHeap.top() == 0))
147                {
148                        m_TriHeap.pop();
149                }
150        }
151}
152
153//      Sets the progress bar function and the increment to update.
154void    tri_stripper::SetProgressFunc(Geometry::TIPOFUNC upb,float      increment)
155{
156        mUPB            =       upb;
157        mUPBInc =       increment;
158}
159
160inline strip tri_stripper::FindBestStrip()
161{
162        // Allow to restore the cache (modified by ExtendTriToStrip) and implicitly reset the cache hit count
163        const cache_simulator CacheBackup = m_Cache;
164
165        policy Policy(m_MinStripSize, Cache());
166
167        while (! m_Candidates.empty()) {
168
169                const size_t Candidate = m_Candidates.back();
170                m_Candidates.pop_back();
171
172                // Discard useless triangles from the candidate list
173                if ((m_Triangles[Candidate].marked()) || (m_TriHeap[Candidate] == 0))
174                        continue;               
175
176                // Try to extend the triangle in the 3 possible forward directions
177                for (size_t i = 0; i < 3; ++i) {
178
179                        const strip Strip = ExtendToStrip(Candidate, triangle_order(i));
180                        Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
181                       
182                        m_Cache = CacheBackup;
183                }
184
185                // Try to extend the triangle in the 6 possible backward directions
186                if (m_BackwardSearch) {
187
188                        for (size_t i = 0; i < 3; ++i) {
189
190                                const strip Strip = BackExtendToStrip(Candidate, triangle_order(i), false);
191                                Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
192                       
193                                m_Cache = CacheBackup;
194                        }
195
196                        for (size_t i = 0; i < 3; ++i) {
197
198                                const strip Strip = BackExtendToStrip(Candidate, triangle_order(i), true);
199                                Policy.Challenge(Strip, m_TriHeap[Strip.Start()], m_Cache.hitcount());
200                       
201                                m_Cache = CacheBackup;
202                        }
203                }
204
205        }
206
207        return Policy.BestStrip();
208}
209
210
211
212strip tri_stripper::ExtendToStrip(const size_t Start, triangle_order Order)
213{
214        const triangle_order StartOrder = Order;
215       
216        // Begin a new strip
217        m_Triangles[Start]->SetStripID(++m_StripID);
218        AddTriangle(* m_Triangles[Start], Order, false);
219
220        size_t Size = 1;
221        bool ClockWise = false;
222
223        // Loop while we can further extend the strip
224        for (tri_iterator Node = (m_Triangles.begin() + Start);
225                (Node != m_Triangles.end()) && (!Cache() || ((Size + 2) < CacheSize()));
226                ++Size) {
227
228                const const_link_iterator Link = LinkToNeighbour(Node, ClockWise, Order, false);
229
230                // Is it the end of the strip?
231                if (Link == Node->out_end()) {
232
233                        Node = m_Triangles.end();
234                        --Size;
235
236                } else {
237
238                        Node = Link->terminal();
239                        (* Node)->SetStripID(m_StripID);
240                        ClockWise = ! ClockWise;
241
242                }
243        }
244
245        return strip(Start, StartOrder, Size);
246}
247
248
249
250strip tri_stripper::BackExtendToStrip(size_t Start, triangle_order Order, bool ClockWise)
251{
252        // Begin a new strip
253        m_Triangles[Start]->SetStripID(++m_StripID);
254        BackAddIndex(LastEdge(* m_Triangles[Start], Order).B());
255        size_t Size = 1;
256
257        tri_iterator Node;
258
259        // Loop while we can further extend the strip
260        for (Node = (m_Triangles.begin() + Start);
261                !Cache() || ((Size + 2) < CacheSize());
262                ++Size) {
263
264                const const_link_iterator Link = BackLinkToNeighbour(Node, ClockWise, Order);
265
266                // Is it the end of the strip?
267                if (Link == Node->out_end())
268                        break;
269
270                else {
271                        Node = Link->terminal();
272                        (* Node)->SetStripID(m_StripID);
273                        ClockWise = ! ClockWise;
274                }
275        }
276
277        // We have to start from a counterclockwise triangle.
278        // Simply return an empty strip in the case where the first triangle is clockwise.
279        // Even though we could discard the first triangle and start from the next counterclockwise triangle,
280        // this often leads to more lonely triangles afterward.
281        if (ClockWise)
282                return strip();
283
284        if (Cache()) {
285                m_Cache.merge(m_BackCache, Size);
286                m_BackCache.reset();
287        }
288
289        return strip(Node - m_Triangles.begin(), Order, Size);
290}
291
292
293
294void tri_stripper::BuildStrip(const strip Strip)
295{
296        const size_t Start = Strip.Start();
297
298        bool ClockWise = false;
299        triangle_order Order = Strip.Order();
300
301        // Create a new strip
302        m_PrimitivesVector.push_back(primitive_group());
303        m_PrimitivesVector.back().Type = TRIANGLE_STRIP;
304        AddTriangle(* m_Triangles[Start], Order, true);
305        MarkTriAsTaken(Start);
306
307        // Loop while we can further extend the strip
308        tri_iterator Node = (m_Triangles.begin() + Start);
309
310        for (size_t Size = 1; Size < Strip.Size(); ++Size) {
311
312                const const_link_iterator Link = LinkToNeighbour(Node, ClockWise, Order, true);
313
314                assert(Link != Node->out_end());
315
316                // Go to the next triangle
317                Node = Link->terminal();
318                MarkTriAsTaken(Node - m_Triangles.begin());
319                ClockWise = ! ClockWise;
320        }
321}
322
323
324
325inline tri_stripper::const_link_iterator tri_stripper::LinkToNeighbour(const const_tri_iterator Node, const bool ClockWise, triangle_order & Order, const bool NotSimulation)
326{
327        const triangle_edge Edge = LastEdge(** Node, Order);
328
329        for (const_link_iterator Link = Node->out_begin(); Link != Node->out_end(); ++Link) {
330
331                // Get the reference to the possible next triangle
332                const triangle & Tri = ** Link->terminal();
333
334                // Check whether it's already been used
335                if (NotSimulation || (Tri.StripID() != m_StripID)) {
336
337                        if (! Link->terminal()->marked()) {
338
339                                // Does the current candidate triangle match the required position for the strip?
340
341                                if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
342                                        Order = (ClockWise) ? ABC : BCA;
343                                        AddIndex(Tri.C(), NotSimulation);
344                                        return Link;
345                                }
346
347                                else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
348                                        Order = (ClockWise) ? BCA : CAB;
349                                        AddIndex(Tri.A(), NotSimulation);
350                                        return Link;
351                                }
352
353                                else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
354                                        Order = (ClockWise) ? CAB : ABC;
355                                        AddIndex(Tri.B(), NotSimulation);
356                                        return Link;
357                                }
358                        }
359                }
360
361        }
362
363        return Node->out_end();
364}
365
366
367
368inline tri_stripper::const_link_iterator tri_stripper::BackLinkToNeighbour(const_tri_iterator Node, bool ClockWise, triangle_order & Order)
369{
370        const triangle_edge Edge = FirstEdge(** Node, Order);
371
372        for (const_link_iterator Link = Node->out_begin(); Link != Node->out_end(); ++Link) {
373
374                // Get the reference to the possible previous triangle
375                const triangle & Tri = ** Link->terminal();
376
377                // Check whether it's already been used
378                if ((Tri.StripID() != m_StripID) && ! Link->terminal()->marked()) {
379
380                        // Does the current candidate triangle match the required position for the strip?
381
382                        if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
383                                Order = (ClockWise) ? CAB : BCA;
384                                BackAddIndex(Tri.C());
385                                return Link;
386                        }
387
388                        else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
389                                Order = (ClockWise) ? ABC : CAB;
390                                BackAddIndex(Tri.A());
391                                return Link;
392                        }
393
394                        else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
395                                Order = (ClockWise) ? BCA : ABC;
396                                BackAddIndex(Tri.B());
397                                return Link;
398                        }
399                }
400
401        }
402
403        return Node->out_end();
404}
405
406
407
408void tri_stripper::MarkTriAsTaken(const size_t i)
409{
410        typedef triangle_graph::node_iterator tri_node_iter;
411        typedef triangle_graph::out_arc_iterator tri_link_iter;
412
413        // Mark the triangle node
414        m_Triangles[i].mark();
415
416        // Remove triangle from priority queue if it isn't yet
417        if (! m_TriHeap.removed(i))
418                m_TriHeap.erase(i);
419
420        // Adjust the degree of available neighbour triangles
421        for (tri_link_iter Link = m_Triangles[i].out_begin(); Link != m_Triangles[i].out_end(); ++Link) {
422
423                const size_t j = Link->terminal() - m_Triangles.begin();
424
425                if ((! m_Triangles[j].marked()) && (! m_TriHeap.removed(j))) {
426                        size_t NewDegree = m_TriHeap.peek(j);
427                        NewDegree = NewDegree - 1;
428                        m_TriHeap.update(j, NewDegree);
429
430                        // Update the candidate list if cache is enabled
431                        if (Cache() && (NewDegree > 0))
432                                m_Candidates.push_back(j);
433                }
434        }
435}
436
437
438
439inline triangle_edge tri_stripper::FirstEdge(const triangle & Triangle, const triangle_order Order)
440{
441        switch (Order)
442        {
443        case ABC:
444                return triangle_edge(Triangle.A(), Triangle.B());
445
446        case BCA:
447                return triangle_edge(Triangle.B(), Triangle.C());
448
449        case CAB:
450                return triangle_edge(Triangle.C(), Triangle.A());
451
452        default:
453                assert(false);
454                return triangle_edge(0, 0);
455        }
456}
457
458
459
460inline triangle_edge tri_stripper::LastEdge(const triangle & Triangle, const triangle_order Order)
461{
462        switch (Order)
463        {
464        case ABC:
465                return triangle_edge(Triangle.B(), Triangle.C());
466
467        case BCA:
468                return triangle_edge(Triangle.C(), Triangle.A());
469
470        case CAB:
471                return triangle_edge(Triangle.A(), Triangle.B());
472
473        default:
474                assert(false);
475                return triangle_edge(0, 0);
476        }
477}
478
479
480
481inline void tri_stripper::AddIndex(const index i, const bool NotSimulation)
482{
483        if (Cache())
484                m_Cache.push(i, ! NotSimulation);
485
486        if (NotSimulation)
487                m_PrimitivesVector.back().Indices.push_back(i);
488}
489
490
491
492inline void tri_stripper::BackAddIndex(const index i)
493{
494        if (Cache())
495                m_BackCache.push(i, true);
496}
497
498
499
500inline void tri_stripper::AddTriangle(const triangle & Tri, const triangle_order Order, const bool NotSimulation)
501{
502        switch (Order)
503        {
504        case ABC:
505                AddIndex(Tri.A(), NotSimulation);
506                AddIndex(Tri.B(), NotSimulation);
507                AddIndex(Tri.C(), NotSimulation);
508                break;
509
510        case BCA:
511                AddIndex(Tri.B(), NotSimulation);
512                AddIndex(Tri.C(), NotSimulation);
513                AddIndex(Tri.A(), NotSimulation);
514                break;
515
516        case CAB:
517                AddIndex(Tri.C(), NotSimulation);
518                AddIndex(Tri.A(), NotSimulation);
519                AddIndex(Tri.B(), NotSimulation);
520                break;
521        }
522}
523
524
525
526inline void tri_stripper::BackAddTriangle(const triangle & Tri, const triangle_order Order)
527{
528        switch (Order)
529        {
530        case ABC:
531                BackAddIndex(Tri.C());
532                BackAddIndex(Tri.B());
533                BackAddIndex(Tri.A());
534                break;
535
536        case BCA:
537                BackAddIndex(Tri.A());
538                BackAddIndex(Tri.C());
539                BackAddIndex(Tri.B());
540                break;
541
542        case CAB:
543                BackAddIndex(Tri.B());
544                BackAddIndex(Tri.A());
545                BackAddIndex(Tri.C());
546                break;
547        }
548}
549
550
551
552void tri_stripper::AddLeftTriangles()
553{
554        // Create the last indices array and fill it with all the triangles that couldn't be stripped
555        primitive_group Primitives;
556        Primitives.Type = TRIANGLES;
557        m_PrimitivesVector.push_back(Primitives);
558        indices & Indices = m_PrimitivesVector.back().Indices;
559
560        for (size_t i = 0; i < m_Triangles.size(); ++i)
561                if (! m_Triangles[i].marked()) {
562                        Indices.push_back(m_Triangles[i]->A());
563                        Indices.push_back(m_Triangles[i]->B());
564                        Indices.push_back(m_Triangles[i]->C());
565                }
566
567        // Undo if useless
568        if (Indices.size() == 0)
569                m_PrimitivesVector.pop_back();
570}
571
572
573
574inline bool tri_stripper::Cache() const
575{
576        return (m_Cache.size() != 0);
577}
578
579
580
581inline size_t tri_stripper::CacheSize() const
582{
583        return m_Cache.size();
584}
585
586
587
588
589} // namespace triangle_stripper
Note: See TracBrowser for help on using the repository browser.