libbase/snappingrange.h

   1 //
   2 //   Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   3 //
   4 // This program is free software; you can redistribute it and/or modify
   5 // it under the terms of the GNU General Public License as published by
   6 // the Free Software Foundation; either version 3 of the License, or
   7 // (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.    See the
  12 // GNU General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU General Public License
  15 // along with this program; if not, write to the Free Software
  16 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17 //
  18
  19 #ifndef GNASH_SNAPPINGRANGE_H
  20 #define GNASH_SNAPPINGRANGE_H
  21
  22 #include "Range2d.h"
  23
  24 #include <vector>
  25 #include <iterator>
  26 #include <algorithm>
  27 #include <ostream>
  28 #include <boost/cstdint.hpp>
  29
  30 namespace gnash {
  31
  32 namespace geometry {
  33
  34 /// \brief
  35 /// Snapping range class. Can hold a number of 2D ranges and combines
  36 /// ranges that come very close. This class is used for multiple invalidated
  37 /// bounds calculation.
  38 //
  39 /// Additionally to merge intersecting ranges this class also "snaps" ranges
  40 /// together which "probably" would be rendered in one single step. When the
  41 /// area of the potential merged range is not much greater than the sum of
  42 /// two single range areas, then these two ranges are merged together to one
  43 /// single range. The "snap factor" defines how much bigger the merged area
  44 /// can become to be a snap candidate (it's the maximum allowed factor that
  45 /// the merged area can be greater than the sum).
  46 ///
  47 /// Optimally the factor 1.0 would be best, but multiple snapping ranges also
  48 /// increase rendering preprocessing overhead and the factor tries to equalize
  49 /// this. The default value is usually fine for most situations.
  50 ///
  51 /// The factor method makes sure that very close, but also very different
  52 /// shapes, don't get merged, like in the following example:
  53 ///
  54 ///                    +---+
  55 ///                    |   |
  56 ///                    |   |
  57 ///                    |   |
  58 ///                    |   |
  59 ///                    |   |
  60 ///                    +---+
  61 ///     +-----------------------------------+
  62 ///     |                                   |
  63 ///     +-----------------------------------+
  64 ///
  65 /// Merging these two ranges would create a much bigger range which in some
  66 /// situations means that rendering is notably slower (for example, when
  67 /// there is a scaled bitmap behind these shapes).
  68
  69 // Forward declarations.
  70 namespace {
  71
  72     /// returns true when two ranges should be merged together
  73     template<typename T> inline bool snaptest(
  74             const geometry::Range2d<T>& range1,
  75             const geometry::Range2d<T>& range2, const float snapFactor);
  76 }
  77
  78 template <typename T>
  79 class SnappingRanges2d
  80 {
  81 public:
  82     typedef geometry::Range2d<T> RangeType;
  83     typedef std::vector<RangeType> RangeList;
  84     typedef typename RangeList::size_type size_type;
  85
  86     template<typename U> friend std::ostream& operator<<(std::ostream& os,
  87                     const SnappingRanges2d<U>& r);
  88
  89     SnappingRanges2d()
  90         :
  91         _snapFactor(1.3f),
  92         _singleMode(false),
  93         _rangesLimit(50),
  94         _combineCounter(0)
  95     {
  96     }
  97
  98     /// Templated copy constructor, for casting between range types
  99     template <typename U>
 100     SnappingRanges2d(const SnappingRanges2d<U>& from)
 101         :
 102         _snapFactor(from.getSnapFactor()),
 103         _singleMode(from.getSingleMode()),
 104         _rangesLimit(from.getRangeCountLimit()),
 105         _combineCounter(0)
 106     {
 107         if (from.isWorld()) setWorld();
 108         else if (from.isNull()) setNull();
 109         else {
 110             // TODO: can we safely assume that the 'from' parameter was
 111             //             finalized ?
 112
 113             // TODO: use visitor pattern !
 114             for (size_type i = 0, e = from.size(); i != e; ++i) {
 115                 const Range2d<U>& r = from.getRange(i);
 116                 RangeType rc(r);
 117                 add(rc);
 118             }
 119         }
 120     }
 121
 122     /// Sets the snapping factor (which must be > 1.0). Higher factors make
 123     /// the ranges more attractive for snapping. A good value is usually 1.3.
 124     void setSnapFactor(const float factor) {
 125         assert(factor > 1.0f);
 126         _snapFactor = factor;
 127     }
 128
 129     float getSnapFactor() const {
 130         return _snapFactor;
 131     }
 132
 133     /// if mode==true, then the snapping ranges will act like a normal Range2d
 134     void setSingleMode(const bool mode) {
 135         _singleMode = mode;
 136     }
 137
 138     bool getSingleMode() const {
 139         return _singleMode;
 140     }
 141
 142     /// Sets the maximum number of ranges allowed (to avoid lots of small
 143     /// ranges)
 144     void setRangeCountLimit(const size_type limit) {
 145         _rangesLimit = limit;
 146     }
 147
 148     size_type getRangeCountLimit() const {
 149         return _rangesLimit;
 150     }
 151
 152     /// Copy the snapping settings from another ranges list, without
 153     /// copying the ranges itself
 154     void inheritConfig(const SnappingRanges2d<T>& from) {
 155         _snapFactor = from._snapFactor;
 156         _singleMode = from._singleMode;
 157     }
 158
 159     /// Merge two ranges based on snaptest.
 160     struct ExpandToIfSnap
 161     {
 162     public:
 163         ExpandToIfSnap(const RangeType& rt, const float snapFactor)
 164             :
 165             _rt(rt),
 166             _snapFactor(snapFactor)
 167         {}
 168
 169         bool operator()(RangeType& r) {
 170             if (snaptest(r, _rt, _snapFactor)) {
 171                 r.expandTo(_rt);
 172                 return false;
 173             }
 174             return true;
 175         }
 176     private:
 177         const RangeType& _rt;
 178         const float _snapFactor;
 179     };
 180
 181     class Scale
 182     {
 183     public:
 184         Scale(const float scale) : _scale(scale) {}
 185         void operator()(RangeType& r) {
 186             r.scale(_scale);
 187         }
 188     private:
 189         const float _scale;
 190     };
 191
 192     class GrowBy
 193     {
 194     public:
 195         GrowBy(const float factor) : _factor(factor) {}
 196         void operator()(RangeType& r) {
 197             r.growBy(_factor);
 198         }
 199     private:
 200         const float _factor;
 201     };
 202
 203     class AddTo
 204     {
 205     public:
 206         AddTo(SnappingRanges2d<T>& us) : _this(us) {}
 207         void operator()(const RangeType& r) {
 208             _this.add(r);
 209         }
 210     private:
 211         SnappingRanges2d<T>& _this;
 212     };
 213
 214     class IntersectsRange
 215     {
 216     public:
 217         IntersectsRange(const RangeType& range) : _range(range) {}
 218         bool operator()(const RangeType& us) {
 219             return us.intersects(_range);
 220         }
 221     private:
 222         const RangeType& _range;
 223     };
 224
 225     class ContainsPoint
 226     {
 227     public:
 228         ContainsPoint(const T x, const T y) : _x(x), _y(y) {}
 229         bool operator()(const RangeType& us) {
 230             return us.contains(_x, _y);
 231         }
 232     private:
 233         const T _x, _y;
 234     };
 235
 236     class ContainsRange
 237     {
 238     public:
 239         ContainsRange(const RangeType& range) : _range(range) {}
 240         bool operator()(const RangeType& us) {
 241             return us.contains(_range);
 242         }
 243     private:
 244         const RangeType& _range;
 245     };
 246
 247
 248     /// Add a Range to the set, merging when possible and appropriate
 249     void add(const RangeType& range) {
 250         if (range.isWorld()) {
 251             setWorld();
 252             return;
 253         }
 254
 255         if (range.isNull()) return;
 256
 257         if (_singleMode) {
 258             if (_ranges.empty()) _ranges.resize(1);
 259             _ranges[0].expandTo(range);
 260             return;
 261         }
 262
 263         ExpandToIfSnap exp(range, _snapFactor);
 264         if (visit(exp)) return;
 265
 266         // reached this point we need a new range
 267         _ranges.push_back(range);
 268
 269         combineRangesLazy();
 270     }
 271
 272     /// combines two snapping ranges
 273     void add(const SnappingRanges2d<T>& other) {
 274         const RangeList& rl = other._ranges;
 275         std::for_each(rl.begin(), rl.end(), AddTo(*this));
 276     }
 277
 278     /// Grows all ranges by the specified amount
 279     void growBy(const T amount) {
 280
 281         if (isWorld() || isNull()) return;
 282
 283         std::for_each(_ranges.begin(), _ranges.end(), GrowBy(amount));
 284         combineRangesLazy();
 285     }
 286
 287     /// Scale all ranges by the specified factor
 288     void scale(const float factor) {
 289
 290         if (isWorld() || isNull()) return;
 291
 292         std::for_each(_ranges.begin(), _ranges.end(), Scale(factor));
 293         combineRangesLazy();
 294     }
 295
 296     /// Resets to NULL range
 297     void setNull() {
 298         _ranges.clear();
 299     }
 300
 301     /// Resets to one range with world flags
 302     void setWorld() {
 303         if (isWorld()) return;
 304         _ranges.resize(1);
 305         _ranges[0].setWorld();
 306     }
 307
 308     /// Returns true, when the ranges equal world range
 309     bool isWorld() const {
 310         return ((size()==1) && (_ranges.front().isWorld()));
 311     }
 312
 313     /// Returns true, when there is no range
 314     bool isNull() const {
 315         return _ranges.empty();
 316     }
 317
 318     /// Returns the number of ranges in the list
 319     size_type size() const {
 320         finalize();
 321         return _ranges.size();
 322     }
 323
 324     /// Returns the range at the specified index
 325     const RangeType& getRange(size_type index) const {
 326         finalize();
 327         assert(index<size());
 328         return _ranges[index];
 329     }
 330
 331     /// Return a range that surrounds *all* added ranges. This is used mainly
 332     /// for compatibilty issues.
 333     RangeType getFullArea() const {
 334         RangeType range;
 335
 336         range.setNull();
 337
 338         int rcount = _ranges.size();
 339
 340         for (int rno=0; rno<rcount; rno++)
 341             range.expandTo(_ranges[rno]);
 342
 343         return range;
 344     }
 345
 346
 347     /// Returns true if any of the ranges intersect the given range
 348     //
 349     /// Note that a NULL range doesn't intersect anything
 350     /// and a WORLD range intersects everything except a NULL Range.
 351     ///
 352     bool intersects(const RangeType& r) const {
 353
 354         finalize();
 355         return std::find_if(_ranges.begin(), _ranges.end(), IntersectsRange(r))
 356             != _ranges.end();
 357     }
 358
 359     /// Returns true if any of the ranges contains the point
 360     bool contains(T x, T y) const {
 361
 362         finalize();
 363         return std::find_if(_ranges.begin(), _ranges.end(), ContainsPoint(x, y))
 364             != _ranges.end();
 365     }
 366
 367     /// Returns true if any of the ranges contains the range
 368     //
 369     /// Note that a NULL range is not contained in any range and
 370     /// a WORLD range is onluy contained in another WORLD range.
 371     ///
 372     bool contains(const RangeType& r) const {
 373
 374         finalize();
 375         return std::find_if(_ranges.begin(), _ranges.end(), ContainsRange(r))
 376             != _ranges.end();
 377     }
 378
 379     /// \brief
 380     /// Returns true if all ranges in the given SnappingRanges2d
 381     /// are contained in at least one of the ranges composing this
 382     /// one.
 383     ///
 384     /// Note that a NULL range is not contained in any range and
 385     /// a WORLD range is onluy contained in another WORLD range.
 386     ///
 387     bool contains(const SnappingRanges2d<T>& o) const
 388     {
 389
 390         finalize();
 391         // o.finalize(); // should I finalize the other range too ?
 392
 393         // Null range set doesn't contain and isn't contained by anything
 394         if ( isNull() ) return false;
 395         if ( o.isNull() ) return false;
 396
 397         // World range contains everything (except null ranges)
 398         if ( isWorld() ) return true;
 399
 400         // This snappingrange is neither NULL nor WORLD
 401         // The other can still be WORLD, but in that case the
 402         // first iteration would return false
 403         //
 404         /// TODO: use a visitor !
 405         for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++)
 406         {
 407             RangeType r = o.getRange(rno);
 408             if ( ! contains(r) )
 409             {
 410                 return false;
 411             }
 412         }
 413
 414         return true;
 415
 416     }
 417
 418
 419     /// Intersect this ranges list with the given ranges list,
 420     /// updating the current ranges list.
 421     /// Note this is currently a relatively expensive operation
 422     /// for complex lists.
 423     ///
 424     void intersect(const SnappingRanges2d<T>& o)
 425     {
 426         if (o.isNull()) {
 427             setNull();
 428             return;
 429         }
 430
 431         if (o.isWorld()) return;
 432
 433         // We create a new ranges set for each range in "o" and
 434         // then update ourselves with the *union* of these ranges.
 435         // Anybody knows a better method (in terms of efficieny) ?
 436
 437         std::vector<SnappingRanges2d<T> > list;
 438         list.reserve(o.size());
 439
 440         //TODO: use a visitor !
 441         for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) {
 442
 443             // add a copy of ourselves to the list
 444             list.push_back(*this);
 445
 446             // intersect that copy with the single range
 447             list.back().intersect(o.getRange(rno));
 448
 449         }
 450
 451         // update ourselves with the union of the "list"
 452         setNull();
 453         for (size_type lno=0, lcount=list.size(); lno<lcount; lno++) {
 454             add(list[lno]);
 455         }
 456
 457     }
 458
 459
 460     /// Intersects this ranges list with the given single range,
 461     /// updating the current ranges list.
 462     void intersect(const RangeType& r)
 463     {
 464
 465         finalize();
 466
 467         if (isWorld()) {            // world intersection with X = X
 468             setNull();
 469             add(r);
 470             return;
 471         }
 472
 473         if (isNull()) return; // NULL will always remain NULL
 474
 475         if (r.isNull()) {         // X intersection with NULL = NULL
 476             setNull();
 477             return;
 478         }
 479
 480         if (r.isWorld()) return;    // X intersection with WORLD = X
 481
 482         // TODO: use a vector (remember to walk in reverse dir.)
 483         for (int rno=_ranges.size()-1; rno>=0; rno--) {
 484
 485             RangeType newrange = Intersection(_ranges[rno], r);
 486
 487             if (newrange.isNull())
 488                 _ranges.erase(_ranges.begin() + rno);
 489             else
 490                 _ranges[rno] = newrange;
 491         }
 492     }
 493
 494     /// Combines known ranges. Previously merged ranges may have come close
 495     /// to other ranges. Algorithm could be optimized.
 496     void combineRanges() const {
 497
 498         // makes no sense in single mode
 499         if (_singleMode) return;
 500
 501         bool restart = true;
 502
 503         _combineCounter = 0;
 504
 505         while (restart) {
 506
 507             int rcount = _ranges.size();
 508
 509             restart=false;
 510
 511             for (int i=0; i<rcount; i++) {
 512
 513                 for (int j=i+1; j<rcount; j++) {
 514
 515                     if (snaptest(_ranges[i], _ranges[j], _snapFactor)) {
 516                         // merge i + j
 517                         _ranges[i].expandTo(_ranges[j]);
 518
 519                         _ranges.erase(_ranges.begin() + j);
 520
 521                         restart=true; // restart from beginning
 522                         break;
 523
 524                     }
 525                 }
 526
 527                 if (restart) break;
 528             }
 529         }
 530
 531         // limit number of ranges
 532         if (_ranges.size() > _rangesLimit) {
 533
 534             // We found way too much ranges, so reduce to just one single range.
 535             // We could also double the factor and try again, but that probably
 536             // won't make much difference, so we avoid the trouble...
 537
 538             RangeType single = getFullArea();
 539             _ranges.resize(1);
 540             _ranges[0] = single;
 541
 542         }
 543
 544     }
 545
 546     /// Visit the current Ranges set
 547     //
 548     /// Visitor functor will be invoked
 549     /// for each RangeType in the current set.
 550     ///
 551     /// The visitor functor will
 552     /// receive a RangeType reference; must return true if
 553     /// it wants next item or true to exit the loop.
 554     ///
 555     /// @return false if the visitor reached the end.
 556     template<class V> inline bool visit(V& visitor) const
 557     {
 558         typename RangeList::iterator it, e;
 559         for (it = _ranges.begin(), e = _ranges.end(); it != e; ++it) {
 560             if (!visitor(*it)) break;
 561         }
 562         return it != _ranges.end();
 563     }
 564
 565     /// Visit the current Ranges set
 566     //
 567     /// Visitor functor will be invoked inconditionally
 568     /// for each RangeType in the current set.
 569     ///
 570     /// The visitor functor will receive a RangeType reference.
 571     ///
 572     template<class V> inline void visitAll(V& visitor) const
 573     {
 574         for_each(_ranges.begin(), _ranges.end(), visitor);
 575     }
 576
 577 private:
 578
 579
 580     /// Calls combineRanges() once in a while, but not always. Avoids too many
 581     /// combineRanges() checks, which could slow down everything.
 582     void combineRangesLazy() {
 583         const size_type max = 5;
 584         ++_combineCounter;
 585         if (_combineCounter > max) combineRanges();
 586     }
 587
 588     void finalize() const {
 589         if (_combineCounter > 0) combineRanges();
 590     }
 591
 592     /// The current Ranges list.
 593     //
 594     /// Mutable due to lazy finalization. This isn't very nice, but better than
 595     /// const_cast.
 596     mutable RangeList _ranges;
 597
 598     /// snapping factor - see setSnapFactor()
 599     float _snapFactor;
 600
 601     /// if set, only a single, outer range is maintained (extended).
 602     bool _singleMode;
 603
 604     /// maximum number of ranges allowed
 605     size_type _rangesLimit;
 606
 607     /// Counter used in finalizing ranges.
 608     mutable size_type _combineCounter;
 609
 610 };
 611
 612 template <class T>
 613 std::ostream&
 614 operator<< (std::ostream& os, const SnappingRanges2d<T>& r)
 615 {
 616     if ( r.isNull() ) return os << "NULL";
 617     if ( r.isWorld() ) return os << "WORLD";
 618
 619     typedef typename SnappingRanges2d<T>::RangeList R;
 620
 621     const R& ranges = r._ranges;
 622
 623     std::copy(ranges.begin(), ranges.end(),
 624             std::ostream_iterator<typename R::value_type>(os, ","));
 625
 626     return os;
 627 }
 628
 629 namespace {
 630
 631 template<typename T>
 632 inline bool snaptest(const geometry::Range2d<T>& range1,
 633         const geometry::Range2d<T>& range2, const float snapFactor)
 634 {
 635
 636     // when they intersect anyway, they should of course be merged!
 637     // TODO: not really, a "+" style ranges list might be worth to
 638     // remain unmerged (but needs special handling, i.e. create three
 639     // ranges out of two)...
 640     if (range1.intersects(range2)) return true;
 641
 642     geometry::Range2d<T> temp = range1;
 643     temp.expandTo(range2);
 644
 645     return (range1.getArea() + range2.getArea()) * snapFactor >
 646         temp.getArea();
 647
 648 }
 649
 650 } // anonymous namespace
 651 } // namespace geometry
 652
 653 /// Standard snapping 2d ranges type for invalidated bounds calculation
 654 typedef geometry::SnappingRanges2d<boost::int32_t> InvalidatedRanges;
 655
 656 } //namespace gnash
 657
 658 #endif