2
// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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.
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.
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
20
#ifndef GNASH_SNAPPINGRANGE_H
21
#define GNASH_SNAPPINGRANGE_H
32
/// Snapping range class. Can hold a number of 2D ranges and combines
33
/// ranges that come very close. This class is used for multiple invalidated
34
/// bounds calculation.
36
/// Additionally to merge intersecting ranges this class also "snaps" ranges
37
/// together which "probably" would be rendered in one single step. When the
38
/// area of the potential merged range is not much greater than the sum of
39
/// two single range areas, then these two ranges are merged together to one
40
/// single range. The "snap factor" defines how much bigger the merged area
41
/// can become to be a snap candidate (it's the maximum allowed factor that
42
/// the merged area can be greater than the sum).
44
/// Optimally the factor 1.0 would be best, but multiple snapping ranges also
45
/// increase rendering preprocessing overhead and the factor tries to equalize
46
/// this. The default value is usually fine for most situations.
48
/// The factor method makes sure that very close, but also very different
49
/// shapes, don't get merged, like in the following example:
58
/// +-----------------------------------+
60
/// +-----------------------------------+
62
/// Merging these two ranges would create a much bigger range which in some
63
/// situations means that rendering is notably slower (for example, when
64
/// there is a scaled bitmap behind these shapes).
68
class SnappingRanges2d
71
typedef geometry::Range2d<T> RangeType;
72
typedef std::vector<RangeType> RangeList; // TODO: list might be more appropriate
73
typedef typename RangeList::size_type size_type;
76
friend std::ostream& operator<< (std::ostream& os, const SnappingRanges2d<U>& r);
87
/// Templated copy constructor, for casting between range types
89
SnappingRanges2d(const SnappingRanges2d<U>& from)
91
snap_factor(from.getSnapFactor()),
92
single_mode(from.getSingleMode()),
93
ranges_limit(from.getRangeCountLimit()),
96
if ( from.isWorld() ) {
98
} else if ( from.isNull() ) {
101
// TODO: can we safely assume that the 'from' parameter was
103
// from.finalize(); // can't call finalize, it's private !!
105
// TODO: use visitor pattern !
106
unsigned rcount = from.size();
107
for (unsigned int rno=0; rno<rcount; rno++)
109
Range2d<U> r = from.getRange(rno);
116
/// Sets the snapping factor (which must be > 1.0). Higher factors make
117
/// the ranges more attractive for snapping. A good value is usually 1.3.
118
void setSnapFactor(float factor) {
119
assert(factor > 1.0f);
120
snap_factor = factor;
123
float getSnapFactor() const {
127
/// if mode==true, then the snapping ranges will act like a normal Range2d
128
void setSingleMode(bool mode) {
132
bool getSingleMode() const {
136
/// Sets the maximum number of ranges allowed (to avoid lots of small
138
void setRangeCountLimit(unsigned limit) {
139
ranges_limit = limit;
142
unsigned getRangeCountLimit() const {
146
/// Copy the snapping settings from another ranges list, without
147
/// copying the ranges itself
148
void inheritConfig(const SnappingRanges2d<T>& from) {
149
snap_factor = from.snap_factor;
150
single_mode = from.single_mode;
153
/// Add a Range to the set, merging when possible and appropriate
154
void add(const RangeType& range) {
155
if (range.isWorld()) {
160
if (range.isNull()) return;
166
if (_ranges.empty()) {
168
_ranges.push_back(temp);
171
_ranges[0].expandTo(range);
177
for (unsigned int rno=0; rno<_ranges.size(); rno++) {
178
if (snaptest(_ranges[rno], range)) {
179
_ranges[rno].expandTo(range);
184
// reached this point we need a new range
185
_ranges.push_back(range);
187
combine_ranges_lazy();
192
/// combines two snapping ranges
193
void add(SnappingRanges2d<T> other_ranges) {
194
for (unsigned int rno=0; rno<other_ranges.size(); rno++)
195
add(other_ranges.getRange(rno));
198
/// Grows all ranges by the specified amount
199
void growBy(T amount) {
201
if (isWorld() || isNull())
204
unsigned rcount = _ranges.size();
206
for (unsigned int rno=0; rno<rcount; rno++)
207
_ranges[rno].growBy(amount);
209
combine_ranges_lazy();
212
/// Scale all ranges by the specified factor
213
void scale(float factor) {
215
if (isWorld() || isNull())
218
unsigned rcount = _ranges.size();
220
for (unsigned int rno=0; rno<rcount; rno++)
221
_ranges[rno].scale(factor);
223
combine_ranges_lazy();
226
/// Combines known ranges. Previously merged ranges may have come close
227
/// to other ranges. Algorithm could be optimized.
228
void combine_ranges() {
230
if (single_mode) // makes no sense in single mode
239
int rcount = _ranges.size();
243
for (int i=0; i<rcount; i++) {
245
for (int j=i+1; j<rcount; j++) {
247
if (snaptest(_ranges[i], _ranges[j])) {
249
_ranges[i].expandTo(_ranges[j]);
251
_ranges.erase(_ranges.begin() + j);
253
restart=true; // restart from beginning
268
// limit number of ranges
269
if (_ranges.size() > ranges_limit) {
271
// We found way too much ranges, so reduce to just one single range.
272
// We could also double the factor and try again, but that probably
273
// won't make much difference, so we avoid the trouble...
275
RangeType single = getFullArea();
284
/// Calls combine_ranges() once in a while, but not always. Avoids too many
285
/// combine_ranges() checks, which could slow down everything.
286
void combine_ranges_lazy() {
288
if (_combine_counter > 5)
292
/// returns true, when two ranges should be merged together
293
inline bool snaptest(const RangeType& range1, const RangeType& range2) {
295
// when they intersect anyway, they should of course be merged!
296
// TODO: not really, a "+" style ranges list might be worth to
297
// remain unmerged (but needs special handling, i.e. create three
298
// ranges out of two)...
299
if (range1.intersects(range2))
302
// simply search for the minimum x or y distances
307
T xa1 = range1.getMinX();
308
T xa2 = range2.getMinX();
309
T xb1 = range1.getMaxX();
310
T xb2 = range2.getMaxX();
311
T ya1 = range1.getMinY();
312
T ya2 = range2.getMinY();
313
T yb1 = range1.getMaxY();
314
T yb2 = range2.getMaxY();
316
xdist = absmin(xdist, xa1-xa2);
317
xdist = absmin(xdist, xa1-xb2);
318
xdist = absmin(xdist, xb1-xa2);
319
xdist = absmin(xdist, xb1-xb2);
321
ydist = absmin(ydist, ya1-ya2);
322
ydist = absmin(ydist, ya1-yb2);
323
ydist = absmin(ydist, yb1-ya2);
324
ydist = absmin(ydist, yb1-yb2);
326
return (xdist + ydist) <= snap_distance;
329
RangeType temp = range1;
330
temp.expandTo(range2);
332
return (range1.getArea() + range2.getArea()) * snap_factor > temp.getArea();
336
/// Resets to NULL range
341
/// Resets to one range with world flags
343
if (isWorld()) return;
345
_ranges[0].setWorld();
348
/// Returns true, when the ranges equal world range
349
bool isWorld() const {
350
return ( (size()==1) && (_ranges.front().isWorld()) );
353
/// Returns true, when there is no range
354
bool isNull() const {
355
return _ranges.empty();
358
/// Returns the number of ranges in the list
359
size_type size() const {
361
return _ranges.size();
364
/// Returns the range at the specified index
366
/// TODO: return by reference ?
368
RangeType getRange(unsigned int index) const {
370
assert(index<size());
372
return _ranges[index];
375
/// Return a range that surrounds *all* added ranges. This is used mainly
376
/// for compatibilty issues.
377
RangeType getFullArea() const {
382
int rcount = _ranges.size();
384
for (int rno=0; rno<rcount; rno++)
385
range.expandTo(_ranges[rno]);
391
/// Returns true if any of the ranges contains the point
392
bool contains(T x, T y) const {
396
for (unsigned rno=0, rcount=_ranges.size(); rno<rcount; rno++)
397
if (_ranges[rno].contains(x,y))
404
/// Returns true if any of the ranges contains the range
406
/// Note that a NULL range is not contained in any range and
407
/// a WORLD range is onluy contained in another WORLD range.
409
bool contains(const RangeType& r) const {
413
for (unsigned rno=0, rcount=_ranges.size(); rno<rcount; rno++)
414
if (_ranges[rno].contains(r))
421
/// Returns true if any of the ranges intersect the given range
423
/// Note that a NULL range doesn't intersect anything
424
/// and a WORLD range intersects everything except a NULL Range.
426
bool intersects(const RangeType& r) const {
430
for (unsigned rno=0, rcount=_ranges.size(); rno<rcount; rno++)
431
if (_ranges[rno].intersects(r))
439
/// Returns true if all ranges in the given SnappingRanges2d
440
/// are contained in at least one of the ranges composing this
443
/// Note that a NULL range is not contained in any range and
444
/// a WORLD range is onluy contained in another WORLD range.
446
bool contains(const SnappingRanges2d<T>& o) const
450
// o.finalize(); // should I finalize the other range too ?
452
// Null range set doesn't contain and isn't contained by anything
453
if ( isNull() ) return false;
454
if ( o.isNull() ) return false;
456
// World range contains everything (except null ranges)
457
if ( isWorld() ) return true;
459
// This snappingrange is neither NULL nor WORLD
460
// The other can still be WORLD, but in that case the
461
// first iteration would return false
463
/// TODO: use a visitor !
465
for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++)
467
RangeType r = o.getRange(rno);
479
/// Intersect this ranges list with the given ranges list,
480
/// updating the current ranges list.
481
/// Note this is currently a relatively expensive operation
482
/// for complex lists.
484
void intersect(const SnappingRanges2d<T>& o)
491
if (o.isWorld()) return;
493
// We create a new ranges set for each range in "o" and
494
// then update ourselves with the *union* of these ranges.
495
// Anybody knows a better method (in terms of efficieny) ?
497
std::vector< SnappingRanges2d<T> > list;
499
//TODO: use a visitor !
500
for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) {
502
// add a copy of ourselves to the list
503
list.push_back(*this);
505
// intersect that copy with the single range
506
list.back().intersect(o.getRange(rno));
510
// update ourselves with the union of the "list"
512
for (unsigned lno=0, lcount=list.size(); lno<lcount; lno++)
518
/// Intersects this ranges list with the given single range,
519
/// updating the current ranges list.
520
void intersect(const RangeType& r)
525
if (isWorld()) { // world intersection with X = X
531
if (isNull()) return; // NULL will always remain NULL
533
if (r.isNull()) { // X intersection with NULL = NULL
538
if (r.isWorld()) return; // X intersection with WORLD = X
541
// TODO: use a vector (remember to walk in reverse dir.)
542
for (int rno=_ranges.size()-1; rno>=0; rno--) {
544
RangeType newrange = Intersection(_ranges[rno], r);
546
if (newrange.isNull())
547
_ranges.erase(_ranges.begin() + rno);
549
_ranges[rno] = newrange;
554
/// Visit the current Ranges set
556
/// Visitor functor will be invoked
557
/// for each RangeType in the current set.
559
/// The visitor functor will
560
/// receive a RangeType reference; must return true if
561
/// it wants next item or false to exit the loop.
564
inline void visit(V& visitor) const
566
for (typename RangeList::const_iterator
567
it = _ranges.begin(), itEnd = _ranges.end();
571
if ( ! visitor(*it) )
578
/// Visit the current Ranges set
580
/// Visitor functor will be invoked inconditionally
581
/// for each RangeType in the current set.
583
/// The visitor functor will receive a RangeType reference.
586
inline void visitAll(V& visitor) const
588
for (typename RangeList::const_iterator
589
it = _ranges.begin(), itEnd = _ranges.end();
600
inline T absmin(T a, T b) {
602
return std::min<T>(a,b);
605
void finalize() const {
606
if (_combine_counter > 0) {
607
SnappingRanges2d<T>* me_nonconst = const_cast< SnappingRanges2d<T>* > (this);
608
me_nonconst->combine_ranges();
613
// The current Ranges list
616
/// snapping factor - see setSnapFactor()
619
/// if set, only a single, outer range is maintained (extended).
622
/// maximum number of ranges allowed
623
unsigned ranges_limit;
625
unsigned int _combine_counter;
627
}; //class SnappingRanges2d
630
std::ostream& operator<< (std::ostream& os, const SnappingRanges2d<T>& r)
632
if ( r.isNull() ) return os << "NULL";
633
if ( r.isWorld() ) return os << "WORLD";
635
for (typename SnappingRanges2d<T>::RangeList::const_iterator
636
it = r._ranges.begin(), itEnd = r._ranges.end();
639
if ( it != r._ranges.begin() ) os << ", ";
645
} //namespace gnash.geometry
647
/// Standard snapping 2d ranges type for invalidated bounds calculation
648
typedef geometry::SnappingRanges2d<float> InvalidatedRanges;
added
removed
libbase/snappingrange.h
