root/OpenSceneGraph/trunk/src/osgUtil/TriStrip_tri_stripper.cpp @ 10757

Revision 10757, 19.4 kB (checked in by robert, 5 years ago)

Removed throw.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under 
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13// tri_stripper.cpp: implementation of the Tri Stripper class.
14//
15// Copyright (C) 2002 Tanguy Fautrᅵ.
16// For conditions of distribution and use,
17// see copyright notice in tri_stripper.h
18//
19//////////////////////////////////////////////////////////////////////
20
21#include <osg/Notify>
22#include "TriStrip_tri_stripper.h"
23
24
25// namespace triangle_stripper
26namespace triangle_stripper {
27
28
29
30
31//////////////////////////////////////////////////////////////////////
32// Construction/Destruction
33//////////////////////////////////////////////////////////////////////
34
35
36
37//////////////////////////////////////////////////////////////////////
38// Members Functions
39//////////////////////////////////////////////////////////////////////
40
41bool tri_stripper::Strip(primitives_vector * out_pPrimitivesVector)
42{
43    // verify that the number of indices is correct
44    if (m_TriIndices.size() % 3 != 0)
45    {
46        osg::notify(osg::NOTICE)<<"Warning: tri_stripper::Strip(..) invalid number of triangle indices."<<std::endl;
47        return false;
48    }
49
50    // clear possible garbage
51    m_PrimitivesVector.clear();
52    out_pPrimitivesVector->clear();
53
54    // Initialize the triangle graph
55    InitTriGraph();
56
57    // Initialize the triangle priority queue
58    InitTriHeap();
59
60    // Initialize the cache simulator
61    InitCache();
62
63    // Launch the triangle strip generator
64    if (!Stripify())
65    {
66        return false;
67    }
68
69    // Add the triangles that couldn't be stripped
70    AddLeftTriangles();
71
72    // Free ressources
73    m_Triangles.clear();
74   
75    // Put the results into the user's vector
76    std::swap(m_PrimitivesVector, (* out_pPrimitivesVector));
77//    m_PrimitivesVector.swap(* out_pPrimitivesVector);
78
79    return true;
80}
81
82
83
84void tri_stripper::InitTriGraph()
85{
86    // Set up the graph size and complete the triangles data
87    // note: setsize() completely resets the graph as well as the node markers
88    m_Triangles.setsize(m_TriIndices.size() / 3);
89
90    size_t i;
91    for (i = 0; i < m_Triangles.size(); ++i)
92        m_Triangles[i] = triangle(m_TriIndices[i * 3 + 0], m_TriIndices[i * 3 + 1], m_TriIndices[i * 3 + 2]);
93
94    // Build the edges lookup table
95    triangle_edges TriInterface;
96    TriInterface.reserve(m_Triangles.size() * 3);
97
98    for (i = 0; i < m_Triangles.size(); ++i) {
99        TriInterface.push_back(triangle_edge(m_Triangles[i]->A(), m_Triangles[i]->B(), i));
100        TriInterface.push_back(triangle_edge(m_Triangles[i]->B(), m_Triangles[i]->C(), i));
101        TriInterface.push_back(triangle_edge(m_Triangles[i]->C(), m_Triangles[i]->A(), i));
102    }
103
104    // Sort the lookup table for faster searches
105    std::sort(TriInterface.begin(), TriInterface.end(), _cmp_tri_interface_lt());
106
107    // Link neighbour triangles together using the edges lookup table
108    for (i = 0; i < m_Triangles.size(); ++i) {
109
110        const triangle_edge EdgeBA(m_Triangles[i]->B(), m_Triangles[i]->A(), i);
111        const triangle_edge EdgeCB(m_Triangles[i]->C(), m_Triangles[i]->B(), i);
112        const triangle_edge EdgeAC(m_Triangles[i]->A(), m_Triangles[i]->C(), i);
113
114        LinkNeighboursTri(TriInterface, EdgeBA);
115        LinkNeighboursTri(TriInterface, EdgeCB);
116        LinkNeighboursTri(TriInterface, EdgeAC);
117    }   
118}
119
120
121
122void tri_stripper::LinkNeighboursTri(const triangle_edges & TriInterface, const triangle_edge Edge)
123{
124    typedef triangle_edges::const_iterator edge_const_it;
125
126    // Find the first edge equal to Edge
127    edge_const_it It = std::lower_bound(TriInterface.begin(), TriInterface.end(), Edge, _cmp_tri_interface_lt());
128
129    // See if there are any other edges that are equal
130    // (if so, it means that more than 2 triangles are sharing the same edge,
131    //  which is unlikely but not impossible)
132    for (; (It != TriInterface.end()) && ((It->A() == Edge.A()) && (It->B() == Edge.B())); ++It)
133        m_Triangles.insert(Edge.TriPos(), It->TriPos());
134
135    // Note: degenerated triangles will also point themselves as neighbour triangles
136}
137
138
139
140void tri_stripper::InitTriHeap()
141{
142    m_TriHeap.clear();
143    m_TriHeap.reserve(m_Triangles.size());
144
145    // Set up the triangles priority queue
146    // The lower the number of available neighbour triangles, the higher the priority.
147    for (size_t i = 0; i < m_Triangles.size(); ++i)
148        m_TriHeap.push(triangle_degree(i, m_Triangles[i].number_of_out_arcs()));
149
150    // Remove useless triangles
151    // (Note: we had to put all of them into the heap before to ensure coherency of the heap_array object)
152    while ((! m_TriHeap.empty()) && (m_TriHeap.top().Degree() == 0))
153        m_TriHeap.pop();
154}
155
156
157
158void tri_stripper::InitCache()
159{
160    m_IndicesCache.clear();
161
162    if (m_CacheSize > 0)
163        m_IndicesCache.resize(m_CacheSize, static_cast<indice>(-1));
164}
165
166
167
168bool tri_stripper::Stripify()
169{
170    // Reset the triangle strip id selector
171    m_StripID = 0;
172
173    // Reset the candidate list
174    m_NextCandidates.clear();
175
176    // Loop untill there is no available candidate triangle left
177    while (! m_TriHeap.empty()) {
178
179        // There is no triangle in the candidates list, refill it with the loneliest triangle
180        const size_t HeapTop = m_TriHeap.top().TriPos();
181        m_NextCandidates.push_back(HeapTop);
182
183        // Loop while BuildStrip can find good candidates for us
184        while (! m_NextCandidates.empty()) {
185
186            // Choose the best strip containing that triangle
187            // Note: FindBestStrip empties m_NextCandidates
188            const triangle_strip TriStrip = FindBestStrip();
189
190            // Build it if it's long enough, otherwise discard it
191            // Note: BuildStrip refills m_NextCandidates
192            if (TriStrip.Size() >= m_MinStripSize)
193            {
194                if (!BuildStrip(TriStrip)) return false;
195            }
196        }
197
198        // We must discard the triangle we inserted in the candidate list from the heap
199        // if it led to nothing. (We simply removed it if it hasn't been removed by BuildStrip() yet)
200        if (! m_TriHeap.removed(HeapTop))
201            m_TriHeap.erase(HeapTop);
202
203
204        // Eliminate all the triangles that have now become useless
205        while ((! m_TriHeap.empty()) && (m_TriHeap.top().Degree() == 0))
206            m_TriHeap.pop();
207    }
208
209    return true;
210}
211
212
213
214triangle_strip tri_stripper::FindBestStrip()
215{
216    triangle_strip BestStrip;
217    size_t BestStripDegree = 0;
218    size_t BestStripCacheHits = 0;
219
220    // Backup the cache, because it'll be erased during the simulations
221    indices_cache CacheBackup = m_IndicesCache;
222
223    while (! m_NextCandidates.empty()) {
224
225        // Discard useless triangles from the candidates list
226        if ((m_Triangles[m_NextCandidates.back()].marked()) || (m_TriHeap[m_NextCandidates.back()].Degree() == 0)) {
227            m_NextCandidates.pop_back();
228
229            // "continue" is evil! But it really makes things easier here.
230            // The useless triangle is discarded, and the "while" just rebegins again
231            continue;
232        }
233
234        // Invariant: (CandidateTri's Degree() >= 1) && (CandidateTri is not marked).
235        // So it can directly be used.
236        const size_t CandidateTri = m_NextCandidates.back();
237        m_NextCandidates.pop_back();
238
239        // Try to extend the triangle in the 3 possible directions
240        for (size_t i = 0; i < 3; ++i) {
241
242            // Reset the cache hit count
243            m_CacheHits = 0;
244
245            // Try a new strip with that triangle in a particular direction
246            const triangle_strip TempStrip = ExtendTriToStrip(CandidateTri, triangle_strip::start_order(i));
247
248            // Restore the cache (modified by ExtendTriToStrip)
249            m_IndicesCache = CacheBackup;
250
251            // We want to keep the best strip
252            // Discard strips that don't match the minimum required size
253            if (TempStrip.Size() >= m_MinStripSize) {
254
255                // Cache simulator disabled?
256                if (m_CacheSize == 0) {
257
258                    // Cache is disabled, take the longest strip
259                    if (TempStrip.Size() > BestStrip.Size())
260                        BestStrip = TempStrip;
261
262                // Cache simulator enabled
263                // Use other criteria to find the "best" strip
264                } else {
265
266                    // Priority 1: Keep the strip with the best cache hit count
267                    if (m_CacheHits > BestStripCacheHits) {
268                        BestStrip = TempStrip;
269                        BestStripDegree = m_TriHeap[TempStrip.StartTriPos()].Degree();
270                        BestStripCacheHits = m_CacheHits;
271
272                    } else if (m_CacheHits == BestStripCacheHits) {
273
274                        // Priority 2: Keep the strip with the loneliest start triangle
275                        if ((BestStrip.Size() != 0) && (m_TriHeap[TempStrip.StartTriPos()].Degree() < BestStripDegree)) {
276                            BestStrip = TempStrip;
277                            BestStripDegree = m_TriHeap[TempStrip.StartTriPos()].Degree();
278
279                        // Priority 3: Keep the longest strip
280                        } else if (TempStrip.Size() > BestStrip.Size()) {
281                            BestStrip = TempStrip;
282                            BestStripDegree = m_TriHeap[TempStrip.StartTriPos()].Degree();
283                        }
284                    }
285                }
286            }
287
288        }
289
290    }
291
292    return BestStrip;
293}
294
295
296
297triangle_strip tri_stripper::ExtendTriToStrip(const size_t StartTriPos, const triangle_strip::start_order StartOrder)
298{
299    typedef triangles_graph::const_out_arc_iterator const_tri_link_iter;
300    typedef triangles_graph::node_iterator tri_node_iter;
301
302    size_t Size = 1;
303    bool ClockWise = false;
304    triangle_strip::start_order Order = StartOrder;
305
306    // Begin a new strip
307    ++m_StripID;
308
309    // Mark the first triangle as used for this strip
310    m_Triangles[StartTriPos]->SetStripID(m_StripID);
311
312    // Update the indice cache
313    AddTriToCache((* m_Triangles[StartTriPos]), Order);
314
315
316    // Loop while we can further extend the strip
317    for (tri_node_iter TriNodeIt = (m_Triangles.begin() + StartTriPos);
318        (TriNodeIt != m_Triangles.end()) && ((m_CacheSize <= 0) || ((Size + 2) < m_CacheSize));
319        ++Size) {
320
321        // Get the triangle edge that would lead to the next triangle
322        const triangle_edge Edge = GetLatestEdge(** TriNodeIt, Order);
323
324        // Link to a neighbour triangle
325        const_tri_link_iter LinkIt;
326        for (LinkIt = TriNodeIt->out_begin(); LinkIt != TriNodeIt->out_end(); ++LinkIt) {
327
328            // Get the reference to the possible next triangle
329            const triangle & Tri = (** (LinkIt->terminal()));
330
331            // Check whether it's already been used
332            if ((Tri.StripID() != m_StripID) && (! (LinkIt->terminal()->marked()))) {
333
334                // Does the current candidate triangle match the required for the strip?
335
336                if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
337                    Order = (ClockWise) ? triangle_strip::ABC : triangle_strip::BCA;
338                    AddIndiceToCache(Tri.C(), true);
339                    break;
340                }
341
342                else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
343                    Order = (ClockWise) ? triangle_strip::BCA : triangle_strip::CAB;
344                    AddIndiceToCache(Tri.A(), true);
345                    break;
346                }
347
348                else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
349                    Order = (ClockWise) ? triangle_strip::CAB : triangle_strip::ABC;
350                    AddIndiceToCache(Tri.B(), true);
351                    break;
352                }
353            }
354        }
355
356        // Is it the end of the strip?
357        if (LinkIt == TriNodeIt->out_end()) {
358            TriNodeIt = m_Triangles.end();
359            --Size;
360        } else {
361            TriNodeIt = LinkIt->terminal();
362   
363            // Setup for the next triangle
364            (* TriNodeIt)->SetStripID(m_StripID);
365            ClockWise = ! ClockWise;
366        }
367    }
368
369
370    return triangle_strip(StartTriPos, StartOrder, Size);
371}
372
373
374
375triangle_edge tri_stripper::GetLatestEdge(const triangle & Triangle, const triangle_strip::start_order Order) const
376{
377    switch (Order) {
378    case triangle_strip::ABC:
379        return triangle_edge(Triangle.B(), Triangle.C(), 0);
380    case triangle_strip::BCA:
381        return triangle_edge(Triangle.C(), Triangle.A(), 0);
382    case triangle_strip::CAB:
383        return triangle_edge(Triangle.A(), Triangle.B(), 0);
384    default:
385        return triangle_edge(0, 0, 0);
386    }
387}
388
389
390
391bool tri_stripper::BuildStrip(const triangle_strip TriStrip)
392{
393    typedef triangles_graph::const_out_arc_iterator const_tri_link_iter;
394    typedef triangles_graph::node_iterator tri_node_iter;
395
396    const size_t StartTriPos = TriStrip.StartTriPos();
397
398    bool ClockWise = false;
399    triangle_strip::start_order Order = TriStrip.StartOrder();
400
401    // Create a new strip
402    m_PrimitivesVector.push_back(primitives());
403    m_PrimitivesVector.back().m_Type = PT_Triangle_Strip;
404
405    // Put the first triangle into the strip
406    AddTriToIndices((* m_Triangles[StartTriPos]), Order);
407
408    // Mark the first triangle as used
409    MarkTriAsTaken(StartTriPos);
410
411
412    // Loop while we can further extend the strip
413    tri_node_iter TriNodeIt = (m_Triangles.begin() + StartTriPos);
414
415    for (size_t Size = 1; Size < TriStrip.Size(); ++Size) {
416
417        // Get the triangle edge that would lead to the next triangle
418        const triangle_edge Edge = GetLatestEdge(** TriNodeIt, Order);
419
420        // Link to a neighbour triangle
421        const_tri_link_iter LinkIt;
422        for (LinkIt = TriNodeIt->out_begin(); LinkIt != TriNodeIt->out_end(); ++LinkIt) {
423
424            // Get the reference to the possible next triangle
425            const triangle & Tri = (** (LinkIt->terminal()));
426
427            // Check whether it's already been used
428            if (! (LinkIt->terminal()->marked())) {
429
430                // Does the current candidate triangle match the required for the strip?
431                // If it does, then add it to the Indices
432                if ((Edge.B() == Tri.A()) && (Edge.A() == Tri.B())) {
433                    Order = (ClockWise) ? triangle_strip::ABC : triangle_strip::BCA;
434                    AddIndice(Tri.C());
435                    break;
436                }
437
438                else if ((Edge.B() == Tri.B()) && (Edge.A() == Tri.C())) {
439                    Order = (ClockWise) ? triangle_strip::BCA : triangle_strip::CAB;
440                    AddIndice(Tri.A());
441                    break;
442                }
443
444                else if ((Edge.B() == Tri.C()) && (Edge.A() == Tri.A())) {
445                    Order = (ClockWise) ? triangle_strip::CAB : triangle_strip::ABC;
446                    AddIndice(Tri.B());
447                    break;
448                }
449            }
450        }
451
452        // Debug check: we must have found the next triangle
453        //assert(LinkIt != TriNodeIt->out_end());       
454        if (LinkIt == TriNodeIt->out_end())
455        {
456            osg::notify(osg::NOTICE)<<"Warning: tri_stripper::BuildStrip(,) error, next triangle not found."<<std::endl;
457            return false;
458        }
459
460
461        // Go to the next triangle
462        TriNodeIt = LinkIt->terminal();
463        MarkTriAsTaken(TriNodeIt - m_Triangles.begin());
464       
465        // Setup for the next triangle
466        ClockWise = ! ClockWise;
467    }
468    return true;
469}
470
471
472
473void tri_stripper::MarkTriAsTaken(const size_t i)
474{
475    typedef triangles_graph::node_iterator tri_node_iter;
476    typedef triangles_graph::out_arc_iterator tri_link_iter;
477
478    // Mark the triangle node
479    m_Triangles[i].mark();
480
481    // Remove triangle from priority queue if it isn't yet
482    if (! m_TriHeap.removed(i))
483        m_TriHeap.erase(i);
484
485    // Adjust the degree of available neighbour triangles
486    for (tri_link_iter LinkIt = m_Triangles[i].out_begin(); LinkIt != m_Triangles[i].out_end(); ++LinkIt) {
487
488        const size_t j = LinkIt->terminal() - m_Triangles.begin();
489
490        if ((! m_Triangles[j].marked()) && (! m_TriHeap.removed(j))) {
491            triangle_degree NewDegree = m_TriHeap.peek(j);
492            NewDegree.SetDegree(NewDegree.Degree() - 1);
493            m_TriHeap.update(j, NewDegree);
494
495            // Update the candidate list if cache is enabled
496            if ((m_CacheSize > 0) && (NewDegree.Degree() > 0))
497                m_NextCandidates.push_back(j);
498        }
499    }
500}
501
502
503
504void tri_stripper::AddIndiceToCache(const indice i, bool CacheHitCount)
505{
506    // Cache simulator enabled?
507    if (m_CacheSize > 0) {
508
509        // Should we simulate the cache hits and count them?
510        if (CacheHitCount) {
511            if (std::find(m_IndicesCache.begin(), m_IndicesCache.end(), i) != m_IndicesCache.end())
512                ++m_CacheHits;
513        }
514       
515        // Manage the indices cache as a FIFO structure
516        m_IndicesCache.pop_back();
517        m_IndicesCache.push_front(i);
518    }
519}
520
521
522
523void tri_stripper::AddIndice(const indice i)
524{
525    // Add the indice to the current indices array
526    m_PrimitivesVector.back().m_Indices.push_back(i);
527
528    // Run cache simulator
529    AddIndiceToCache(i);
530}
531
532
533
534void tri_stripper::AddTriToCache(const triangle & Tri, const triangle_strip::start_order Order)
535{
536    // Add Tri indices in the right order into the indices cache simulator.
537    // And enable the cache hit count
538    switch (Order) {
539    case triangle_strip::ABC:
540        AddIndiceToCache(Tri.A(), true);
541        AddIndiceToCache(Tri.B(), true);
542        AddIndiceToCache(Tri.C(), true);
543        return;
544    case triangle_strip::BCA:
545        AddIndiceToCache(Tri.B(), true);
546        AddIndiceToCache(Tri.C(), true);
547        AddIndiceToCache(Tri.A(), true);
548        return;
549    case triangle_strip::CAB:
550        AddIndiceToCache(Tri.C(), true);
551        AddIndiceToCache(Tri.A(), true);
552        AddIndiceToCache(Tri.B(), true);
553        return;
554    }
555}
556
557
558
559void tri_stripper::AddTriToIndices(const triangle & Tri, const triangle_strip::start_order Order)
560{
561    // Add Tri indices in the right order into the latest Indices vector.
562    switch (Order) {
563    case triangle_strip::ABC:
564        AddIndice(Tri.A());
565        AddIndice(Tri.B());
566        AddIndice(Tri.C());
567        return;
568    case triangle_strip::BCA:
569        AddIndice(Tri.B());
570        AddIndice(Tri.C());
571        AddIndice(Tri.A());
572        return;
573    case triangle_strip::CAB:
574        AddIndice(Tri.C());
575        AddIndice(Tri.A());
576        AddIndice(Tri.B());
577        return;
578    }
579}
580
581
582
583void tri_stripper::AddLeftTriangles()
584{
585    // Create the latest indices array
586    // and fill it with all the triangles that couldn't be stripped
587    primitives Primitives;
588    Primitives.m_Type = PT_Triangles;
589    m_PrimitivesVector.push_back(Primitives);
590    indices & Indices = m_PrimitivesVector.back().m_Indices;
591
592    for (size_t i = 0; i < m_Triangles.size(); ++i)
593        if (! m_Triangles[i].marked()) {
594            Indices.push_back(m_Triangles[i]->A());
595            Indices.push_back(m_Triangles[i]->B());
596            Indices.push_back(m_Triangles[i]->C());
597        }
598
599    // Undo if useless
600    if (Indices.size() == 0)
601        m_PrimitivesVector.pop_back();
602}
603
604
605
606
607} // namespace triangle_stripper
Note: See TracBrowser for help on using the browser.