diff --git a/toonz/sources/common/tgeometry/tgeometry.cpp b/toonz/sources/common/tgeometry/tgeometry.cpp index 7b96071..bef8959 100644 --- a/toonz/sources/common/tgeometry/tgeometry.cpp +++ b/toonz/sources/common/tgeometry/tgeometry.cpp @@ -352,3 +352,181 @@ TAffine4 TAffine4::rotationZ(double angle) { r.a22 = c; return r; } + +//================================================================================================== + + +int TAngleRangeSet::find(Type a) const { + assert(!m_angles.empty()); + int i0 = 0, i1 = m_angles.size() - 1; + if (a < m_angles[0]) return i1; + if (m_angles[i1] <= a) return i1; + while(true) { + int i = (i1 + i0)/2; + if (i == i0) break; + if (m_angles[i] <= a) i0 = i; else i1 = i; + } + return i0; +} + +void TAngleRangeSet::insert(Type a) { + int i = find(a); + if (m_angles[i] == a) m_angles.erase(m_angles.begin() + i); else + if (a < m_angles[0]) m_angles.insert(m_angles.begin(), a); else + m_angles.insert(m_angles.begin()+1, a); +} + +bool TAngleRangeSet::doAdd(Type a0, Type a1) { + int i0 = find(a0); + int i1 = find(a1); + if (i0 == i1) { + bool visible = (i0%2 != 0) == m_flip; + if (m_angles[i0] != a0 && m_angles[i0] - a0 <= a1 - a0) { + if (visible) { fill(); return true; } + set(a0, a1); + } else + if (!visible) { + if (a1 < a0) m_flip = true; + insert(a0); + insert(a1); + } + return false; + } + + bool visible0 = (i0%2 != 0) == m_flip; + bool visible1 = (i1%2 != 0) == m_flip; + + // remove range (i0, i1] + i0 = (i0 + 1)%m_angles.size(); + if (i1 < i0) { + m_angles.erase(m_angles.begin() + i0, m_angles.end()); + m_angles.erase(m_angles.begin(), m_angles.begin() + i1 + 1); + } else { + m_angles.erase(m_angles.begin() + i0, m_angles.begin() + i1 + 1); + } + + // insert new angles if need + if (!visible0) insert(a0); + if (!visible1) insert(a1); + if (m_angles.empty()) { m_flip = true; return true; } + if (a1 < a0) m_flip = true; + return false; +} + +bool TAngleRangeSet::contains(Type a) const { + if (isEmpty()) return false; + if (isFull()) return true; + return (find(a)%2 != 0) == m_flip; +} + +bool TAngleRangeSet::check() const { + if (m_angles.size() % 2 != 0) + return false; + for(int i = 1; i < (int)m_angles.size(); ++i) + if (m_angles[i-1] >= m_angles[i]) + return false; + return true; +} + +void TAngleRangeSet::set(Type a0, Type a1) { + m_angles.clear(); + if (a0 < a1) { + m_flip = false; + m_angles.push_back(a0); + m_angles.push_back(a1); + } else + if (a0 > a1) { + m_flip = true; + m_angles.push_back(a1); + m_angles.push_back(a0); + } else { + m_flip = true; + } +} + +void TAngleRangeSet::set(const TAngleRangeSet &x, bool flip = false) { + if (&x == this) return; + m_flip = (x.isFlipped() != flip); + m_angles = x.angles(); +} + +void TAngleRangeSet::invert(Type a0, Type a1) { + if (a0 == a1) return; + if (isEmpty()) { set(a0, a1); return; } + if (isFull()) { set(a1, a0); return; } + if (a1 < a0) m_flip = !m_flip; + insert(a0); + insert(a1); +} + +void TAngleRangeSet::invert(const TAngleRangeSet &x) { + if (x.isEmpty()) { return; } + if (x.isFull()) { invert(); return; } + if (isEmpty()) { set(x); return; } + if (isFull()) { set(x, true); return; } + m_flip = m_flip != x.isFlipped(); + for(List::const_iterator i = x.angles().begin(); i != x.angles().end(); ++i) + insert(*i); +} + +void TAngleRangeSet::add(Type a0, Type a1) { + if (!isFull() && a0 != a1) + { if (isEmpty()) set(a0, a1); else doAdd(a0, a1); } +} + +void TAngleRangeSet::add(const TAngleRangeSet &x) { + if (&x == this || isFull() || x.isEmpty()) return; + if (isEmpty()) { set(x); return; } + if (x.isFull()) { fill(); return; } + bool f = x.isFlipped(); + Type prev = x.angles().back(); + for(List::const_iterator i = x.angles().begin(); i != x.angles().end(); ++i) + if (f && doAdd(prev, *i)) return; + else { prev = *i; f = !f; } +} + +void TAngleRangeSet::subtract(Type a0, Type a1) { + if (!isEmpty() && a0 != a1) { + if (isFull()) set(a1, a0); else + { invert(); doAdd(a0, a1); invert(); } + } +} + +void TAngleRangeSet::subtract(const TAngleRangeSet &x) { + if (isEmpty() || x.isEmpty()) return; + if (&x == this || x.isFull()) { clear(); return; } + if (isFull()) { set(x); invert(); return; } + + // a - b = !(!a + b) + invert(); + bool f = x.isFlipped(); + Type prev = x.angles().back(); + for(List::const_iterator i = x.angles().begin(); i != x.angles().end(); ++i) + if (f && doAdd(prev, *i)) return; + else { prev = *i; f = !f; } + invert(); +} + +void TAngleRangeSet::intersect(Type a0, Type a1) { + if (!isEmpty()) { + if (a0 == a1) clear(); else + if (isFull()) set(a0, a1); else + { invert(); doAdd(a1, a0); invert(); } + } +} + +void TAngleRangeSet::intersect(const TAngleRangeSet &x) { + if (&x == this || isEmpty() || x.isFull()) return; + if (x.isEmpty()) { clear(); return; } + if (isFull()) { set(x); return; } + + // a & b = !(!a + b) + invert(); + bool f = !x.isFlipped(); + Type prev = x.angles().back(); + for(List::const_iterator i = x.angles().begin(); i != x.angles().end(); ++i) + if (f && doAdd(prev, *i)) return; + else { prev = *i; f = !f; } + invert(); +} + diff --git a/toonz/sources/include/tgeometry.h b/toonz/sources/include/tgeometry.h index fb5c7a0..aab04ec 100644 --- a/toonz/sources/include/tgeometry.h +++ b/toonz/sources/include/tgeometry.h @@ -1301,4 +1301,77 @@ public: static TAffine4 perspective(double near, double far, double tangent); }; + +//============================================================================= + +//! This class performs binary manipulations with angle ranges + +class DVAPI TAngleRangeSet { +public: + typedef unsigned int Type; + typedef std::vector List; + + static const Type max = Type() - Type(1); + static const Type half = ((Type() - Type(1)) >> 1) + Type(1); + + static Type fromDouble(double a) + { return Type(round((a/M_2PI + 0.5)*max)); } + static double toDouble(Type a) + { return ((double)a/(double)max - 0.5)*M_2PI; } + + struct Range { + Type a0, a1; + Range(): a0(), a1() { } + Range(Type a0, Type a1): a0(a0), a1(a1) { } + inline bool isEmpty() const { return a0 == a1; } + inline Range flip() const { return Range(a1, a0); } + }; + +private: + bool m_flip; + List m_angles; + + int find(Type a) const; + void insert(Type a); + bool doAdd(Type a0, Type a1); + +public: + inline explicit TAngleRangeSet(bool fill = false): m_flip(fill) { } + inline TAngleRangeSet(const TAngleRangeSet &x, bool flip = false): + m_flip(x.isFlipped() != flip), m_angles(x.angles()) { } + + inline const List& angles() const { return m_angles; } + inline bool isFlipped() const { return m_flip; } + inline bool isEmpty() const { return !m_flip && m_angles.empty(); } + inline bool isFull() const { return m_flip && m_angles.empty(); } + + bool contains(Type a) const; + bool check() const; + + inline void clear() { m_flip = false; m_angles.clear(); } + inline void fill() { m_flip = true; m_angles.clear(); } + inline void invert() { m_flip = !m_flip; } + + void set(Type a0, Type a1); + void set(const TAngleRangeSet &x, bool flip = false); + + //! also known as 'xor' + void invert(Type a0, Type a1); + inline void invert(const Range &x) { invert(x.a0, x.a1); } + void invert(const TAngleRangeSet &x); + + void add(Type a0, Type a1); + inline void add(const Range &x) { add(x.a0, x.a1); } + void add(const TAngleRangeSet &x); + + void subtract(Type a0, Type a1); + inline void subtract(const Range &x) { subtract(x.a0, x.a1); } + void subtract(const TAngleRangeSet &x); + + void intersect(Type a0, Type a1); + inline void intersect(const Range &x) { intersect(x.a0, x.a1); } + void intersect(const TAngleRangeSet &x); +}; + + #endif // __T_GEOMETRY_INCLUDED__