Okular

tilesmanager.cpp
1 /*
2  SPDX-FileCopyrightText: 2012 Mailson Menezes <[email protected]>
3  SPDX-License-Identifier: GPL-2.0-or-later
4 */
5 
6 #include "tilesmanager_p.h"
7 
8 #include <QList>
9 #include <QPainter>
10 #include <QPixmap>
11 #include <qmath.h>
12 
13 #include "tile.h"
14 
15 #define TILES_MAXSIZE 2000000
16 
17 using namespace Okular;
18 
19 static bool rankedTilesLessThan(TileNode *t1, TileNode *t2)
20 {
21  // Order tiles by its dirty state and then by distance from the viewport.
22  if (t1->dirty == t2->dirty)
23  return t1->distance < t2->distance;
24 
25  return !t1->dirty;
26 }
27 
28 class TilesManager::Private
29 {
30 public:
31  Private();
32 
33  bool hasPixmap(const NormalizedRect &rect, const TileNode &tile) const;
34  void tilesAt(const NormalizedRect &rect, TileNode &tile, QList<Tile> &result, TileLeaf tileLeaf);
35  void setPixmap(const QPixmap *pixmap, const NormalizedRect &rect, TileNode &tile, bool isPartialPixmap);
36 
37  /**
38  * Mark @p tile and all its children as dirty
39  */
40  static void markDirty(TileNode &tile);
41 
42  /**
43  * Deletes all tiles, recursively
44  */
45  void deleteTiles(const TileNode &tile);
46 
47  void markParentDirty(const TileNode &tile);
48  void rankTiles(TileNode &tile, QList<TileNode *> &rankedTiles, const NormalizedRect &visibleRect, int visiblePageNumber);
49  /**
50  * Since the tile can be large enough to occupy a significant amount of
51  * space, they may be split in more tiles. This operation is performed
52  * when the tiles of a certain region is requested and they are bigger
53  * than an arbitrary value. Only tiles intersecting the desired region
54  * are split. There's no need to do this for the entire page.
55  */
56  void split(TileNode &tile, const NormalizedRect &rect);
57 
58  /**
59  * Checks whether the tile's size is bigger than an arbitrary value and
60  * performs the split operation returning true.
61  * Otherwise it just returns false, without performing any operation.
62  */
63  bool splitBigTiles(TileNode &tile, const NormalizedRect &rect);
64 
65  // The page is split in a 4x4 grid of tiles
66  TileNode tiles[16];
67  int width;
68  int height;
69  int pageNumber;
70  qulonglong totalPixels;
71  Rotation rotation;
72  NormalizedRect visibleRect;
73  NormalizedRect requestRect;
74  int requestWidth;
75  int requestHeight;
76 };
77 
78 TilesManager::Private::Private()
79  : width(0)
80  , height(0)
81  , pageNumber(0)
82  , totalPixels(0)
83  , rotation(Rotation0)
84  , requestRect(NormalizedRect())
85  , requestWidth(0)
86  , requestHeight(0)
87 {
88 }
89 
90 TilesManager::TilesManager(int pageNumber, int width, int height, Rotation rotation)
91  : d(new Private)
92 {
93  d->pageNumber = pageNumber;
94  d->width = width;
95  d->height = height;
96  d->rotation = rotation;
97 
98  // The page is split in a 4x4 grid of tiles
99  const double dim = 0.25;
100  for (int i = 0; i < 16; ++i) {
101  int x = i % 4;
102  int y = i / 4;
103  d->tiles[i].rect = NormalizedRect(x * dim, y * dim, x * dim + dim, y * dim + dim);
104  }
105 }
106 
107 TilesManager::~TilesManager()
108 {
109  for (const TileNode &tile : d->tiles)
110  d->deleteTiles(tile);
111 
112  delete d;
113 }
114 
115 void TilesManager::Private::deleteTiles(const TileNode &tile)
116 {
117  if (tile.pixmap) {
118  totalPixels -= tile.pixmap->width() * tile.pixmap->height();
119  delete tile.pixmap;
120  }
121 
122  if (tile.nTiles > 0) {
123  for (int i = 0; i < tile.nTiles; ++i)
124  deleteTiles(tile.tiles[i]);
125 
126  delete[] tile.tiles;
127  }
128 }
129 
130 void TilesManager::setSize(int width, int height)
131 {
132  if (width == d->width && height == d->height)
133  return;
134 
135  d->width = width;
136  d->height = height;
137 
138  markDirty();
139 }
140 
141 int TilesManager::width() const
142 {
143  return d->width;
144 }
145 
146 int TilesManager::height() const
147 {
148  return d->height;
149 }
150 
151 void TilesManager::setRotation(Rotation rotation)
152 {
153  if (rotation == d->rotation)
154  return;
155 
156  d->rotation = rotation;
157 }
158 
159 Rotation TilesManager::rotation() const
160 {
161  return d->rotation;
162 }
163 
164 void TilesManager::markDirty()
165 {
166  for (TileNode &tile : d->tiles) {
167  TilesManager::Private::markDirty(tile);
168  }
169 }
170 
171 void TilesManager::Private::markDirty(TileNode &tile)
172 {
173  tile.dirty = true;
174 
175  for (int i = 0; i < tile.nTiles; ++i) {
176  markDirty(tile.tiles[i]);
177  }
178 }
179 
180 void TilesManager::setPixmap(const QPixmap *pixmap, const NormalizedRect &rect, bool isPartialPixmap)
181 {
182  const NormalizedRect rotatedRect = TilesManager::fromRotatedRect(rect, d->rotation);
183  if (!d->requestRect.isNull()) {
184  if (!(d->requestRect == rect))
185  return;
186 
187  if (pixmap) {
188  // Check whether the pixmap has the same absolute size of the expected
189  // request.
190  // If the document is rotated, rotate requestRect back to the original
191  // rotation before comparing to pixmap's size. This is to avoid
192  // conversion issues. The pixmap request was made using an unrotated
193  // rect.
194  QSize pixmapSize = pixmap->size();
195  int w = width();
196  int h = height();
197  if (d->rotation % 2) {
198  qSwap(w, h);
199  pixmapSize.transpose();
200  }
201 
202  if (rotatedRect.geometry(w, h).size() != pixmapSize)
203  return;
204  }
205 
206  d->requestRect = NormalizedRect();
207  }
208 
209  for (TileNode &tile : d->tiles) {
210  d->setPixmap(pixmap, rotatedRect, tile, isPartialPixmap);
211  }
212 }
213 
214 void TilesManager::Private::setPixmap(const QPixmap *pixmap, const NormalizedRect &rect, TileNode &tile, bool isPartialPixmap)
215 {
216  QRect pixmapRect = TilesManager::toRotatedRect(rect, rotation).geometry(width, height);
217 
218  // Exclude tiles outside the viewport
219  if (!tile.rect.intersects(rect))
220  return;
221 
222  // if the tile is not entirely within the viewport (the tile intersects an
223  // edged of the viewport), attempt to set the pixmap in the children tiles
224  if (!((tile.rect & rect) == tile.rect)) {
225  // paint children tiles
226  if (tile.nTiles > 0) {
227  for (int i = 0; i < tile.nTiles; ++i)
228  setPixmap(pixmap, rect, tile.tiles[i], isPartialPixmap);
229 
230  delete tile.pixmap;
231  tile.pixmap = nullptr;
232  }
233 
234  return;
235  }
236 
237  // the tile lies entirely within the viewport
238  if (tile.nTiles == 0) {
239  tile.dirty = isPartialPixmap;
240 
241  // check whether the tile size is big and split it if necessary
242  if (!splitBigTiles(tile, rect)) {
243  if (tile.pixmap) {
244  totalPixels -= tile.pixmap->width() * tile.pixmap->height();
245  delete tile.pixmap;
246  }
247  tile.rotation = rotation;
248  if (pixmap) {
249  const NormalizedRect rotatedRect = TilesManager::toRotatedRect(tile.rect, rotation);
250  tile.pixmap = new QPixmap(pixmap->copy(rotatedRect.geometry(width, height).translated(-pixmapRect.topLeft())));
251  totalPixels += tile.pixmap->width() * tile.pixmap->height();
252  } else {
253  tile.pixmap = nullptr;
254  }
255  } else {
256  if (tile.pixmap) {
257  totalPixels -= tile.pixmap->width() * tile.pixmap->height();
258  delete tile.pixmap;
259  tile.pixmap = nullptr;
260  }
261 
262  for (int i = 0; i < tile.nTiles; ++i)
263  setPixmap(pixmap, rect, tile.tiles[i], isPartialPixmap);
264  }
265  } else {
266  QRect tileRect = tile.rect.geometry(width, height);
267  // sets the pixmap of the children tiles. if the tile's size is too
268  // small, discards the children tiles and use the current one
269  if (tileRect.width() * tileRect.height() >= TILES_MAXSIZE) {
270  tile.dirty = isPartialPixmap;
271  if (tile.pixmap) {
272  totalPixels -= tile.pixmap->width() * tile.pixmap->height();
273  delete tile.pixmap;
274  tile.pixmap = nullptr;
275  }
276 
277  for (int i = 0; i < tile.nTiles; ++i)
278  setPixmap(pixmap, rect, tile.tiles[i], isPartialPixmap);
279  } else {
280  // remove children tiles
281  for (int i = 0; i < tile.nTiles; ++i) {
282  deleteTiles(tile.tiles[i]);
283  tile.tiles[i].pixmap = nullptr;
284  }
285 
286  delete[] tile.tiles;
287  tile.tiles = nullptr;
288  tile.nTiles = 0;
289 
290  // paint tile
291  if (tile.pixmap) {
292  totalPixels -= tile.pixmap->width() * tile.pixmap->height();
293  delete tile.pixmap;
294  }
295  tile.rotation = rotation;
296  if (pixmap) {
297  const NormalizedRect rotatedRect = TilesManager::toRotatedRect(tile.rect, rotation);
298  tile.pixmap = new QPixmap(pixmap->copy(rotatedRect.geometry(width, height).translated(-pixmapRect.topLeft())));
299  totalPixels += tile.pixmap->width() * tile.pixmap->height();
300  } else {
301  tile.pixmap = nullptr;
302  }
303  tile.dirty = isPartialPixmap;
304  }
305  }
306 }
307 
308 bool TilesManager::hasPixmap(const NormalizedRect &rect)
309 {
310  NormalizedRect rotatedRect = fromRotatedRect(rect, d->rotation);
311  for (const TileNode &tile : qAsConst(d->tiles)) {
312  if (!d->hasPixmap(rotatedRect, tile))
313  return false;
314  }
315 
316  return true;
317 }
318 
319 bool TilesManager::Private::hasPixmap(const NormalizedRect &rect, const TileNode &tile) const
320 {
321  const NormalizedRect rectIntersection = tile.rect & rect;
322  if (rectIntersection.width() <= 0 || rectIntersection.height() <= 0)
323  return true;
324 
325  if (tile.nTiles == 0)
326  return tile.isValid();
327 
328  // all children tiles are clean. doesn't need to go deeper
329  if (!tile.dirty)
330  return true;
331 
332  for (int i = 0; i < tile.nTiles; ++i) {
333  if (!hasPixmap(rect, tile.tiles[i]))
334  return false;
335  }
336 
337  return true;
338 }
339 
340 QList<Tile> TilesManager::tilesAt(const NormalizedRect &rect, TileLeaf tileLeaf)
341 {
342  QList<Tile> result;
343 
344  NormalizedRect rotatedRect = fromRotatedRect(rect, d->rotation);
345  for (TileNode &tile : d->tiles) {
346  d->tilesAt(rotatedRect, tile, result, tileLeaf);
347  }
348 
349  return result;
350 }
351 
352 void TilesManager::Private::tilesAt(const NormalizedRect &rect, TileNode &tile, QList<Tile> &result, TileLeaf tileLeaf)
353 {
354  if (!tile.rect.intersects(rect))
355  return;
356 
357  // split big tiles before the requests are made, otherwise we would end up
358  // requesting huge areas unnecessarily
359  splitBigTiles(tile, rect);
360 
361  if ((tileLeaf == TerminalTile && tile.nTiles == 0) || (tileLeaf == PixmapTile && tile.pixmap)) {
362  NormalizedRect rotatedRect;
363  if (rotation != Rotation0)
364  rotatedRect = TilesManager::toRotatedRect(tile.rect, rotation);
365  else
366  rotatedRect = tile.rect;
367 
368  if (tile.pixmap && tileLeaf == PixmapTile && tile.rotation != rotation) {
369  // Lazy tiles rotation
370  int angleToRotate = (rotation - tile.rotation) * 90;
371  int xOffset = 0, yOffset = 0;
372  int w = 0, h = 0;
373  switch (angleToRotate) {
374  case 0:
375  xOffset = 0;
376  yOffset = 0;
377  w = tile.pixmap->width();
378  h = tile.pixmap->height();
379  break;
380  case 90:
381  case -270:
382  xOffset = 0;
383  yOffset = -tile.pixmap->height();
384  w = tile.pixmap->height();
385  h = tile.pixmap->width();
386  break;
387  case 180:
388  case -180:
389  xOffset = -tile.pixmap->width();
390  yOffset = -tile.pixmap->height();
391  w = tile.pixmap->width();
392  h = tile.pixmap->height();
393  break;
394  case 270:
395  case -90:
396  xOffset = -tile.pixmap->width();
397  yOffset = 0;
398  w = tile.pixmap->height();
399  h = tile.pixmap->width();
400  break;
401  }
402  QPixmap *rotatedPixmap = new QPixmap(w, h);
403  QPainter p(rotatedPixmap);
404  p.rotate(angleToRotate);
405  p.translate(xOffset, yOffset);
406  p.drawPixmap(0, 0, *tile.pixmap);
407  p.end();
408 
409  delete tile.pixmap;
410  tile.pixmap = rotatedPixmap;
411  tile.rotation = rotation;
412  }
413  result.append(Tile(rotatedRect, tile.pixmap, tile.isValid()));
414  } else {
415  for (int i = 0; i < tile.nTiles; ++i)
416  tilesAt(rect, tile.tiles[i], result, tileLeaf);
417  }
418 }
419 
420 qulonglong TilesManager::totalMemory() const
421 {
422  return 4 * d->totalPixels;
423 }
424 
425 void TilesManager::cleanupPixmapMemory(qulonglong numberOfBytes, const NormalizedRect &visibleRect, int visiblePageNumber)
426 {
427  QList<TileNode *> rankedTiles;
428  for (TileNode &tile : d->tiles) {
429  d->rankTiles(tile, rankedTiles, visibleRect, visiblePageNumber);
430  }
431  std::sort(rankedTiles.begin(), rankedTiles.end(), rankedTilesLessThan);
432 
433  while (numberOfBytes > 0 && !rankedTiles.isEmpty()) {
434  TileNode *tile = rankedTiles.takeLast();
435  if (!tile->pixmap)
436  continue;
437 
438  // do not evict visible pixmaps
439  if (tile->rect.intersects(visibleRect))
440  continue;
441 
442  qulonglong pixels = tile->pixmap->width() * tile->pixmap->height();
443  d->totalPixels -= pixels;
444  if (numberOfBytes < 4 * pixels)
445  numberOfBytes = 0;
446  else
447  numberOfBytes -= 4 * pixels;
448 
449  delete tile->pixmap;
450  tile->pixmap = nullptr;
451 
452  d->markParentDirty(*tile);
453  }
454 }
455 
456 void TilesManager::Private::markParentDirty(const TileNode &tile)
457 {
458  if (!tile.parent)
459  return;
460 
461  if (!tile.parent->dirty) {
462  tile.parent->dirty = true;
463  markParentDirty(*tile.parent);
464  }
465 }
466 
467 void TilesManager::Private::rankTiles(TileNode &tile, QList<TileNode *> &rankedTiles, const NormalizedRect &visibleRect, int visiblePageNumber)
468 {
469  // If the page is visible, visibleRect is not null.
470  // Otherwise we use the number of one of the visible pages to calculate the
471  // distance.
472  // Note that the current page may be visible and yet its pageNumber is
473  // different from visiblePageNumber. Since we only use this value on hidden
474  // pages, any visible page number will fit.
475  if (visibleRect.isNull() && visiblePageNumber < 0)
476  return;
477 
478  if (tile.pixmap) {
479  // Update distance
480  if (!visibleRect.isNull()) {
481  NormalizedPoint viewportCenter = visibleRect.center();
482  NormalizedPoint tileCenter = tile.rect.center();
483  // Manhattan distance. It's a good and fast approximation.
484  tile.distance = qAbs(viewportCenter.x - tileCenter.x) + qAbs(viewportCenter.y - tileCenter.y);
485  } else {
486  // For non visible pages only the vertical distance is used
487  if (pageNumber < visiblePageNumber)
488  tile.distance = 1 - tile.rect.bottom;
489  else
490  tile.distance = tile.rect.top;
491  }
492  rankedTiles.append(&tile);
493  } else {
494  for (int i = 0; i < tile.nTiles; ++i) {
495  rankTiles(tile.tiles[i], rankedTiles, visibleRect, visiblePageNumber);
496  }
497  }
498 }
499 
500 bool TilesManager::isRequesting(const NormalizedRect &rect, int pageWidth, int pageHeight) const
501 {
502  return rect == d->requestRect && pageWidth == d->requestWidth && pageHeight == d->requestHeight;
503 }
504 
505 void TilesManager::setRequest(const NormalizedRect &rect, int pageWidth, int pageHeight)
506 {
507  d->requestRect = rect;
508  d->requestWidth = pageWidth;
509  d->requestHeight = pageHeight;
510 }
511 
512 bool TilesManager::Private::splitBigTiles(TileNode &tile, const NormalizedRect &rect)
513 {
514  QRect tileRect = tile.rect.geometry(width, height);
515  if (tileRect.width() * tileRect.height() < TILES_MAXSIZE)
516  return false;
517 
518  split(tile, rect);
519  return true;
520 }
521 
522 void TilesManager::Private::split(TileNode &tile, const NormalizedRect &rect)
523 {
524  if (tile.nTiles != 0)
525  return;
526 
527  if (rect.isNull() || !tile.rect.intersects(rect))
528  return;
529 
530  tile.nTiles = 4;
531  tile.tiles = new TileNode[4];
532  double hCenter = (tile.rect.left + tile.rect.right) / 2;
533  double vCenter = (tile.rect.top + tile.rect.bottom) / 2;
534 
535  tile.tiles[0].rect = NormalizedRect(tile.rect.left, tile.rect.top, hCenter, vCenter);
536  tile.tiles[1].rect = NormalizedRect(hCenter, tile.rect.top, tile.rect.right, vCenter);
537  tile.tiles[2].rect = NormalizedRect(tile.rect.left, vCenter, hCenter, tile.rect.bottom);
538  tile.tiles[3].rect = NormalizedRect(hCenter, vCenter, tile.rect.right, tile.rect.bottom);
539 
540  for (int i = 0; i < tile.nTiles; ++i) {
541  tile.tiles[i].parent = &tile;
542  splitBigTiles(tile.tiles[i], rect);
543  }
544 }
545 
546 NormalizedRect TilesManager::fromRotatedRect(const NormalizedRect &rect, Rotation rotation)
547 {
548  if (rotation == Rotation0)
549  return rect;
550 
551  NormalizedRect newRect;
552  switch (rotation) {
553  case Rotation90:
554  newRect = NormalizedRect(rect.top, 1 - rect.right, rect.bottom, 1 - rect.left);
555  break;
556  case Rotation180:
557  newRect = NormalizedRect(1 - rect.right, 1 - rect.bottom, 1 - rect.left, 1 - rect.top);
558  break;
559  case Rotation270:
560  newRect = NormalizedRect(1 - rect.bottom, rect.left, 1 - rect.top, rect.right);
561  break;
562  default:
563  newRect = rect;
564  break;
565  }
566 
567  return newRect;
568 }
569 
570 NormalizedRect TilesManager::toRotatedRect(const NormalizedRect &rect, Rotation rotation)
571 {
572  if (rotation == Rotation0)
573  return rect;
574 
575  NormalizedRect newRect;
576  switch (rotation) {
577  case Rotation90:
578  newRect = NormalizedRect(1 - rect.bottom, rect.left, 1 - rect.top, rect.right);
579  break;
580  case Rotation180:
581  newRect = NormalizedRect(1 - rect.right, 1 - rect.bottom, 1 - rect.left, 1 - rect.top);
582  break;
583  case Rotation270:
584  newRect = NormalizedRect(rect.top, 1 - rect.right, rect.bottom, 1 - rect.left);
585  break;
586  default:
587  newRect = rect;
588  break;
589  }
590 
591  return newRect;
592 }
593 
594 TileNode::TileNode()
595  : pixmap(nullptr)
596  , rotation(Rotation0)
597  , dirty(true)
598  , distance(-1)
599  , tiles(nullptr)
600  , nTiles(0)
601  , parent(nullptr)
602 {
603 }
604 
605 bool TileNode::isValid() const
606 {
607  return pixmap && !dirty;
608 }
609 
610 class Tile::Private
611 {
612 public:
613  Private();
614 
616  QPixmap *pixmap;
617  bool isValid;
618 };
619 
620 Tile::Private::Private()
621  : pixmap(nullptr)
622  , isValid(false)
623 {
624 }
625 
626 Tile::Tile(const NormalizedRect &rect, QPixmap *pixmap, bool isValid)
627  : d(new Tile::Private)
628 {
629  d->rect = rect;
630  d->pixmap = pixmap;
631  d->isValid = isValid;
632 }
633 
634 Tile::Tile(const Tile &t)
635  : d(new Tile::Private)
636 {
637  d->rect = t.d->rect;
638  d->pixmap = t.d->pixmap;
639  d->isValid = t.d->isValid;
640 }
641 
642 Tile &Tile::operator=(const Tile &other)
643 {
644  if (this == &other)
645  return *this;
646 
647  d->rect = other.d->rect;
648  d->pixmap = other.d->pixmap;
649  d->isValid = other.d->isValid;
650 
651  return *this;
652 }
653 
654 Tile::~Tile()
655 {
656  delete d;
657 }
658 
660 {
661  return d->rect;
662 }
663 
665 {
666  return d->pixmap;
667 }
668 
669 bool Tile::isValid() const
670 {
671  return d->isValid;
672 }
NormalizedPoint is a helper class which stores the coordinates of a normalized point.
Definition: area.h:116
QSize size() const const
Rotation
A rotation.
Definition: global.h:45
QSize size() const const
int width() const const
QPixmap copy(int x, int y, int width, int height) const const
NormalizedPoint center() const
Returns the center of the rectangle.
Definition: area.cpp:222
double left
The normalized left coordinate.
Definition: area.h:415
bool isValid() const
True if the pixmap is available and updated.
A NormalizedRect is a rectangle which can be defined by two NormalizedPoints.
Definition: area.h:189
int height() const const
void transpose()
double y
The normalized y coordinate.
Definition: area.h:172
Rotated 180 degrees clockwise.
Definition: global.h:48
double width() const
Definition: area.h:401
global.h
Definition: action.h:16
Not rotated.
Definition: global.h:46
This class represents a rectangular portion of a page.
Definition: tile.h:22
double right
The normalized right coordinate.
Definition: area.h:425
void append(const T &value)
double height() const
Definition: area.h:407
bool isEmpty() const const
QRect translated(int dx, int dy) const const
Rotated 2700 degrees clockwise.
Definition: global.h:49
int distance(const GeoCoordinates &coord1, const GeoCoordinates &coord2)
QRect geometry(int xScale, int yScale) const
Returns the rectangle mapped to a reference area of xScale x yScale.
Definition: area.cpp:234
QList::iterator end()
double top
The normalized top coordinate.
Definition: area.h:420
QPixmap * pixmap() const
Pixmap (may also be NULL)
Rotated 90 degrees clockwise.
Definition: global.h:47
T takeLast()
double x
The normalized x coordinate.
Definition: area.h:167
int width() const const
NormalizedRect rect() const
Location of the tile.
bool isNull() const
Returns whether this normalized rectangle is a null normalized rect.
Definition: area.cpp:156
QPoint topLeft() const const
double bottom
The normalized bottom coordinate.
Definition: area.h:430
QList::iterator begin()
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Mon Dec 6 2021 22:32:18 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.