GrRectanizer_skyline.cpp 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
  1. /*
  2. * Copyright 2013 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/core/SkIPoint16.h"
  8. #include "src/gpu/GrRectanizer_skyline.h"
  9. bool GrRectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) {
  10. if ((unsigned)width > (unsigned)this->width() ||
  11. (unsigned)height > (unsigned)this->height()) {
  12. return false;
  13. }
  14. // find position for new rectangle
  15. int bestWidth = this->width() + 1;
  16. int bestX = 0;
  17. int bestY = this->height() + 1;
  18. int bestIndex = -1;
  19. for (int i = 0; i < fSkyline.count(); ++i) {
  20. int y;
  21. if (this->rectangleFits(i, width, height, &y)) {
  22. // minimize y position first, then width of skyline
  23. if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
  24. bestIndex = i;
  25. bestWidth = fSkyline[i].fWidth;
  26. bestX = fSkyline[i].fX;
  27. bestY = y;
  28. }
  29. }
  30. }
  31. // add rectangle to skyline
  32. if (-1 != bestIndex) {
  33. this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
  34. loc->fX = bestX;
  35. loc->fY = bestY;
  36. fAreaSoFar += width*height;
  37. return true;
  38. }
  39. loc->fX = 0;
  40. loc->fY = 0;
  41. return false;
  42. }
  43. bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
  44. int x = fSkyline[skylineIndex].fX;
  45. if (x + width > this->width()) {
  46. return false;
  47. }
  48. int widthLeft = width;
  49. int i = skylineIndex;
  50. int y = fSkyline[skylineIndex].fY;
  51. while (widthLeft > 0) {
  52. y = SkMax32(y, fSkyline[i].fY);
  53. if (y + height > this->height()) {
  54. return false;
  55. }
  56. widthLeft -= fSkyline[i].fWidth;
  57. ++i;
  58. SkASSERT(i < fSkyline.count() || widthLeft <= 0);
  59. }
  60. *ypos = y;
  61. return true;
  62. }
  63. void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
  64. SkylineSegment newSegment;
  65. newSegment.fX = x;
  66. newSegment.fY = y + height;
  67. newSegment.fWidth = width;
  68. fSkyline.insert(skylineIndex, 1, &newSegment);
  69. SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
  70. SkASSERT(newSegment.fY <= this->height());
  71. // delete width of the new skyline segment from following ones
  72. for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
  73. // The new segment subsumes all or part of fSkyline[i]
  74. SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
  75. if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
  76. int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
  77. fSkyline[i].fX += shrink;
  78. fSkyline[i].fWidth -= shrink;
  79. if (fSkyline[i].fWidth <= 0) {
  80. // fully consumed
  81. fSkyline.remove(i);
  82. --i;
  83. } else {
  84. // only partially consumed
  85. break;
  86. }
  87. } else {
  88. break;
  89. }
  90. }
  91. // merge fSkylines
  92. for (int i = 0; i < fSkyline.count()-1; ++i) {
  93. if (fSkyline[i].fY == fSkyline[i+1].fY) {
  94. fSkyline[i].fWidth += fSkyline[i+1].fWidth;
  95. fSkyline.remove(i+1);
  96. --i;
  97. }
  98. }
  99. }
  100. ///////////////////////////////////////////////////////////////////////////////
  101. GrRectanizer* GrRectanizer::Factory(int width, int height) {
  102. return new GrRectanizerSkyline(width, height);
  103. }