| 52 | // }; |
| 53 | template <typename _Track, typename _Adapter> |
| 54 | void Decimate(const _Track& _src, const _Adapter& _adapter, float _tolerance, |
| 55 | _Track* _dest) { |
| 56 | // Early out if not enough data. |
| 57 | if (_src.size() < 2) { |
| 58 | *_dest = _src; |
| 59 | return; |
| 60 | } |
| 61 | |
| 62 | // Stack of segments to process. |
| 63 | typedef std::pair<size_t, size_t> Segment; |
| 64 | ozz::stack<Segment> segments; |
| 65 | |
| 66 | // Bit vector of all points to included. |
| 67 | ozz::vector<bool> included(_src.size(), false); |
| 68 | |
| 69 | // Pushes segment made from first and last points. |
| 70 | segments.push(Segment(0, _src.size() - 1)); |
| 71 | included[0] = true; |
| 72 | included[_src.size() - 1] = true; |
| 73 | |
| 74 | // Empties segments stack. |
| 75 | while (!segments.empty()) { |
| 76 | // Pops next segment to process. |
| 77 | const Segment segment = segments.top(); |
| 78 | segments.pop(); |
| 79 | |
| 80 | // Looks for the furthest point from the segment. |
| 81 | float max = -1.f; |
| 82 | size_t candidate = segment.first; |
| 83 | typename _Track::const_reference left = _src[segment.first]; |
| 84 | typename _Track::const_reference right = _src[segment.second]; |
| 85 | for (size_t i = segment.first + 1; i < segment.second; ++i) { |
| 86 | SKR_ASSERT(!included[i] && "Included points should be processed once only."); |
| 87 | typename _Track::const_reference test = _src[i]; |
| 88 | if (!_adapter.Decimable(test)) { |
| 89 | candidate = i; |
| 90 | break; |
| 91 | } else { |
| 92 | const float distance = |
| 93 | _adapter.Distance(_adapter.Lerp(left, right, test), test); |
| 94 | if (distance > _tolerance && distance > max) { |
| 95 | max = distance; |
| 96 | candidate = i; |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | // If found, include the point and pushes the 2 new segments (before and |
| 102 | // after the new point). |
| 103 | if (candidate != segment.first) { |
| 104 | included[candidate] = true; |
| 105 | if (candidate - segment.first > 1) { |
| 106 | segments.push(Segment(segment.first, candidate)); |
| 107 | } |
| 108 | if (segment.second - candidate > 1) { |
| 109 | segments.push(Segment(candidate, segment.second)); |
| 110 | } |
| 111 | } |