[774] | 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
|
---|