SkRTree.cpp 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178
  1. /*
  2. * Copyright 2012 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/SkRTree.h"
  8. SkRTree::SkRTree() : fCount(0) {}
  9. SkRect SkRTree::getRootBound() const {
  10. if (fCount) {
  11. return fRoot.fBounds;
  12. } else {
  13. return SkRect::MakeEmpty();
  14. }
  15. }
  16. void SkRTree::insert(const SkRect boundsArray[], int N) {
  17. SkASSERT(0 == fCount);
  18. SkTDArray<Branch> branches;
  19. branches.setReserve(N);
  20. for (int i = 0; i < N; i++) {
  21. const SkRect& bounds = boundsArray[i];
  22. if (bounds.isEmpty()) {
  23. continue;
  24. }
  25. Branch* b = branches.push();
  26. b->fBounds = bounds;
  27. b->fOpIndex = i;
  28. }
  29. fCount = branches.count();
  30. if (fCount) {
  31. if (1 == fCount) {
  32. fNodes.setReserve(1);
  33. Node* n = this->allocateNodeAtLevel(0);
  34. n->fNumChildren = 1;
  35. n->fChildren[0] = branches[0];
  36. fRoot.fSubtree = n;
  37. fRoot.fBounds = branches[0].fBounds;
  38. } else {
  39. fNodes.setReserve(CountNodes(fCount));
  40. fRoot = this->bulkLoad(&branches);
  41. }
  42. }
  43. }
  44. SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
  45. SkDEBUGCODE(Node* p = fNodes.begin());
  46. Node* out = fNodes.push();
  47. SkASSERT(fNodes.begin() == p); // If this fails, we didn't setReserve() enough.
  48. out->fNumChildren = 0;
  49. out->fLevel = level;
  50. return out;
  51. }
  52. // This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
  53. int SkRTree::CountNodes(int branches) {
  54. if (branches == 1) {
  55. return 1;
  56. }
  57. int numBranches = branches / kMaxChildren;
  58. int remainder = branches % kMaxChildren;
  59. if (remainder > 0) {
  60. numBranches++;
  61. if (remainder >= kMinChildren) {
  62. remainder = 0;
  63. } else {
  64. remainder = kMinChildren - remainder;
  65. }
  66. }
  67. int currentBranch = 0;
  68. int nodes = 0;
  69. while (currentBranch < branches) {
  70. int incrementBy = kMaxChildren;
  71. if (remainder != 0) {
  72. if (remainder <= kMaxChildren - kMinChildren) {
  73. incrementBy -= remainder;
  74. remainder = 0;
  75. } else {
  76. incrementBy = kMinChildren;
  77. remainder -= kMaxChildren - kMinChildren;
  78. }
  79. }
  80. nodes++;
  81. currentBranch++;
  82. for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
  83. currentBranch++;
  84. }
  85. }
  86. return nodes + CountNodes(nodes);
  87. }
  88. SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
  89. if (branches->count() == 1) { // Only one branch. It will be the root.
  90. return (*branches)[0];
  91. }
  92. // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
  93. // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
  94. // difference in playback speed.
  95. int numBranches = branches->count() / kMaxChildren;
  96. int remainder = branches->count() % kMaxChildren;
  97. int newBranches = 0;
  98. if (remainder > 0) {
  99. ++numBranches;
  100. // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
  101. if (remainder >= kMinChildren) {
  102. remainder = 0;
  103. } else {
  104. remainder = kMinChildren - remainder;
  105. }
  106. }
  107. int currentBranch = 0;
  108. while (currentBranch < branches->count()) {
  109. int incrementBy = kMaxChildren;
  110. if (remainder != 0) {
  111. // if need be, omit some nodes to make up for remainder
  112. if (remainder <= kMaxChildren - kMinChildren) {
  113. incrementBy -= remainder;
  114. remainder = 0;
  115. } else {
  116. incrementBy = kMinChildren;
  117. remainder -= kMaxChildren - kMinChildren;
  118. }
  119. }
  120. Node* n = allocateNodeAtLevel(level);
  121. n->fNumChildren = 1;
  122. n->fChildren[0] = (*branches)[currentBranch];
  123. Branch b;
  124. b.fBounds = (*branches)[currentBranch].fBounds;
  125. b.fSubtree = n;
  126. ++currentBranch;
  127. for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
  128. b.fBounds.join((*branches)[currentBranch].fBounds);
  129. n->fChildren[k] = (*branches)[currentBranch];
  130. ++n->fNumChildren;
  131. ++currentBranch;
  132. }
  133. (*branches)[newBranches] = b;
  134. ++newBranches;
  135. }
  136. branches->setCount(newBranches);
  137. return this->bulkLoad(branches, level + 1);
  138. }
  139. void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const {
  140. if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
  141. this->search(fRoot.fSubtree, query, results);
  142. }
  143. }
  144. void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const {
  145. for (int i = 0; i < node->fNumChildren; ++i) {
  146. if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
  147. if (0 == node->fLevel) {
  148. results->push_back(node->fChildren[i].fOpIndex);
  149. } else {
  150. this->search(node->fChildren[i].fSubtree, query, results);
  151. }
  152. }
  153. }
  154. }
  155. size_t SkRTree::bytesUsed() const {
  156. size_t byteCount = sizeof(SkRTree);
  157. byteCount += fNodes.reserved() * sizeof(Node);
  158. return byteCount;
  159. }