1 |
|
---|
2 | //////////////////////////////////////////////////////////////////////
|
---|
3 | //
|
---|
4 | // Copyright (C) 2004 Tanguy Fautré.
|
---|
5 | //
|
---|
6 | // This software is provided 'as-is', without any express or implied
|
---|
7 | // warranty. In no event will the authors be held liable for any damages
|
---|
8 | // arising from the use of this software.
|
---|
9 | //
|
---|
10 | // Permission is granted to anyone to use this software for any purpose,
|
---|
11 | // including commercial applications, and to alter it and redistribute it
|
---|
12 | // freely, subject to the following restrictions:
|
---|
13 | //
|
---|
14 | // 1. The origin of this software must not be misrepresented; you must not
|
---|
15 | // claim that you wrote the original software. If you use this software
|
---|
16 | // in a product, an acknowledgment in the product documentation would be
|
---|
17 | // appreciated but is not required.
|
---|
18 | // 2. Altered source versions must be plainly marked as such, and must not be
|
---|
19 | // misrepresented as being the original software.
|
---|
20 | // 3. This notice may not be removed or altered from any source distribution.
|
---|
21 | //
|
---|
22 | // Tanguy Fautré
|
---|
23 | // softdev@telenet.be
|
---|
24 | //
|
---|
25 | //////////////////////////////////////////////////////////////////////
|
---|
26 | //
|
---|
27 | // Tri Stripper
|
---|
28 | // ************
|
---|
29 | //
|
---|
30 | // Post TnL cache aware triangle stripifier in O(n.log(n)).
|
---|
31 | //
|
---|
32 | // History: see ChangeLog
|
---|
33 | //
|
---|
34 | //////////////////////////////////////////////////////////////////////
|
---|
35 | // SVN: $Id: tri_stripper.h 86 2005-06-08 17:47:27Z gpsnoopy $
|
---|
36 | //////////////////////////////////////////////////////////////////////
|
---|
37 |
|
---|
38 | // Protection against old C habits
|
---|
39 | #if defined(max)
|
---|
40 | #error "'max' macro defined! It's against the C++ standard. Please use 'std::max' instead (undefine 'max' macro if it was defined in another library)."
|
---|
41 | #endif
|
---|
42 |
|
---|
43 | // Protection against old C habits
|
---|
44 | #if defined(min)
|
---|
45 | #error "'min' macro defined! It's against the C++ standard. Please use 'std::min' instead (undefine 'min' macro if it was defined in another library)."
|
---|
46 | #endif
|
---|
47 |
|
---|
48 |
|
---|
49 |
|
---|
50 | #ifndef TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H
|
---|
51 | #define TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H
|
---|
52 |
|
---|
53 | #include <public_types.h>
|
---|
54 |
|
---|
55 | #include <detail/cache_simulator.h>
|
---|
56 | #include <detail/graph_array.h>
|
---|
57 | #include <detail/heap_array.h>
|
---|
58 | #include <detail/types.h>
|
---|
59 |
|
---|
60 | #include <iostream>
|
---|
61 | #include <GeoMesh.h>
|
---|
62 |
|
---|
63 |
|
---|
64 | namespace triangle_stripper {
|
---|
65 |
|
---|
66 |
|
---|
67 |
|
---|
68 |
|
---|
69 | class tri_stripper
|
---|
70 | {
|
---|
71 | public:
|
---|
72 |
|
---|
73 | tri_stripper(const indices & TriIndices);
|
---|
74 |
|
---|
75 | void Strip(primitive_vector * out_pPrimitivesVector);
|
---|
76 |
|
---|
77 | /* Stripifier Algorithm Settings */
|
---|
78 |
|
---|
79 | // Set the post-T&L cache size (0 disables the cache optimizer).
|
---|
80 | void SetCacheSize(size_t CacheSize = 10);
|
---|
81 |
|
---|
82 | // Set the minimum size of a triangle strip (should be at least 2 triangles).
|
---|
83 | // The stripifier discard any candidate strips that does not satisfy the minimum size condition.
|
---|
84 | void SetMinStripSize(size_t MinStripSize = 2);
|
---|
85 |
|
---|
86 | // Set the backward search mode in addition to the forward search mode.
|
---|
87 | // In forward mode, the candidate strips are build with the current candidate triangle being the first
|
---|
88 | // triangle of the strip. When the backward mode is enabled, the stripifier also tests candidate strips
|
---|
89 | // where the current candidate triangle is the last triangle of the strip.
|
---|
90 | // Enable this if you want better results at the expense of being slightly slower.
|
---|
91 | // Note: Do *NOT* use this when the cache optimizer is enabled; it only gives worse results.
|
---|
92 | void SetBackwardSearch(bool Enabled = false);
|
---|
93 |
|
---|
94 | // Set the cache simulator FIFO behavior (does nothing if the cache optimizer is disabled).
|
---|
95 | // When enabled, the cache is simulated as a simple FIFO structure. However, when
|
---|
96 | // disabled, indices that trigger cache hits are not pushed into the FIFO structure.
|
---|
97 | // This allows simulating some GPUs that do not duplicate cache entries (e.g. NV25 or greater).
|
---|
98 | void SetPushCacheHits(bool Enabled = true);
|
---|
99 |
|
---|
100 | // Sets the progress bar function and the increment to update.
|
---|
101 | void SetProgressFunc(Geometry::TIPOFUNC upb,float increment);
|
---|
102 |
|
---|
103 | /* End Settings */
|
---|
104 |
|
---|
105 | private:
|
---|
106 |
|
---|
107 | typedef detail::graph_array<detail::triangle> triangle_graph;
|
---|
108 | typedef detail::heap_array<size_t, std::greater<size_t> > triangle_heap;
|
---|
109 | typedef std::vector<size_t> candidates;
|
---|
110 | typedef triangle_graph::node_iterator tri_iterator;
|
---|
111 | typedef triangle_graph::const_node_iterator const_tri_iterator;
|
---|
112 | typedef triangle_graph::out_arc_iterator link_iterator;
|
---|
113 | typedef triangle_graph::const_out_arc_iterator const_link_iterator;
|
---|
114 |
|
---|
115 | void InitTriHeap();
|
---|
116 | void Stripify();
|
---|
117 | void AddLeftTriangles();
|
---|
118 | void ResetStripIDs();
|
---|
119 |
|
---|
120 | detail::strip FindBestStrip();
|
---|
121 | detail::strip ExtendToStrip(size_t Start, detail::triangle_order Order);
|
---|
122 | detail::strip BackExtendToStrip(size_t Start, detail::triangle_order Order, bool ClockWise);
|
---|
123 | const_link_iterator LinkToNeighbour(const_tri_iterator Node, bool ClockWise, detail::triangle_order & Order, bool NotSimulation);
|
---|
124 | const_link_iterator BackLinkToNeighbour(const_tri_iterator Node, bool ClockWise, detail::triangle_order & Order);
|
---|
125 | void BuildStrip(const detail::strip Strip);
|
---|
126 | void MarkTriAsTaken(size_t i);
|
---|
127 | void AddIndex(index i, bool NotSimulation);
|
---|
128 | void BackAddIndex(index i);
|
---|
129 | void AddTriangle(const detail::triangle & Tri, detail::triangle_order Order, bool NotSimulation);
|
---|
130 | void BackAddTriangle(const detail::triangle & Tri, detail::triangle_order Order);
|
---|
131 |
|
---|
132 | bool Cache() const;
|
---|
133 | size_t CacheSize() const;
|
---|
134 |
|
---|
135 | static detail::triangle_edge FirstEdge(const detail::triangle & Triangle, detail::triangle_order Order);
|
---|
136 | static detail::triangle_edge LastEdge(const detail::triangle & Triangle, detail::triangle_order Order);
|
---|
137 |
|
---|
138 | primitive_vector m_PrimitivesVector;
|
---|
139 | triangle_graph m_Triangles;
|
---|
140 | triangle_heap m_TriHeap;
|
---|
141 | candidates m_Candidates;
|
---|
142 | detail::cache_simulator m_Cache;
|
---|
143 | detail::cache_simulator m_BackCache;
|
---|
144 | size_t m_StripID;
|
---|
145 | size_t m_MinStripSize;
|
---|
146 | bool m_BackwardSearch;
|
---|
147 | bool m_FirstRun;
|
---|
148 |
|
---|
149 | // Progress bar function.
|
---|
150 | Geometry::TIPOFUNC mUPB;
|
---|
151 | float mUPBInc;
|
---|
152 |
|
---|
153 | };
|
---|
154 |
|
---|
155 |
|
---|
156 |
|
---|
157 |
|
---|
158 |
|
---|
159 | //////////////////////////////////////////////////////////////////////////
|
---|
160 | // tri_stripper inline functions
|
---|
161 | //////////////////////////////////////////////////////////////////////////
|
---|
162 |
|
---|
163 | inline void tri_stripper::SetCacheSize(const size_t CacheSize)
|
---|
164 | {
|
---|
165 | m_Cache.resize(CacheSize);
|
---|
166 | m_BackCache.resize(CacheSize);
|
---|
167 | }
|
---|
168 |
|
---|
169 |
|
---|
170 | inline void tri_stripper::SetMinStripSize(const size_t MinStripSize)
|
---|
171 | {
|
---|
172 | if (MinStripSize < 2)
|
---|
173 | m_MinStripSize = 2;
|
---|
174 | else
|
---|
175 | m_MinStripSize = MinStripSize;
|
---|
176 | }
|
---|
177 |
|
---|
178 |
|
---|
179 | inline void tri_stripper::SetBackwardSearch(const bool Enabled)
|
---|
180 | {
|
---|
181 | m_BackwardSearch = Enabled;
|
---|
182 | }
|
---|
183 |
|
---|
184 |
|
---|
185 |
|
---|
186 | inline void tri_stripper::SetPushCacheHits(bool Enabled)
|
---|
187 | {
|
---|
188 | m_Cache.push_cache_hits(Enabled);
|
---|
189 | }
|
---|
190 |
|
---|
191 |
|
---|
192 |
|
---|
193 |
|
---|
194 | } // namespace triangle_stripper
|
---|
195 |
|
---|
196 |
|
---|
197 |
|
---|
198 |
|
---|
199 | #endif // TRI_STRIPPER_HEADER_GUARD_TRI_STRIPPER_H
|
---|