Line data Source code
1 : /*
2 : * SPDX-License-Identifier: GPL-3.0-only
3 : * MuseScore-Studio-CLA-applies
4 : *
5 : * MuseScore Studio
6 : * Music Composition & Notation
7 : *
8 : * Copyright (C) 2021 MuseScore Limited and others
9 : *
10 : * This program is free software: you can redistribute it and/or modify
11 : * it under the terms of the GNU General Public License version 3 as
12 : * published by the Free Software Foundation.
13 : *
14 : * This program is distributed in the hope that it will be useful,
15 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : * GNU General Public License for more details.
18 : *
19 : * You should have received a copy of the GNU General Public License
20 : * along with this program. If not, see <https://www.gnu.org/licenses/>.
21 : */
22 :
23 : #include <cmath>
24 :
25 : #include "bsp.h"
26 : #include "engravingitem.h"
27 :
28 : using namespace mu;
29 :
30 : namespace mu::engraving {
31 : //---------------------------------------------------------
32 : // InsertItemBspTreeVisitor
33 : //---------------------------------------------------------
34 :
35 : class InsertItemBspTreeVisitor : public BspTreeVisitor
36 : {
37 0 : OBJECT_ALLOCATOR(engraving, InsertItemBspTreeVisitor)
38 : public:
39 : EngravingItem* item;
40 :
41 1936 : inline void visit(std::vector<EngravingItem*>& items) override { items.push_back(item); }
42 : };
43 :
44 : //---------------------------------------------------------
45 : // RemoveItemBspTreeVisitor
46 : //---------------------------------------------------------
47 :
48 : class RemoveItemBspTreeVisitor : public BspTreeVisitor
49 : {
50 0 : OBJECT_ALLOCATOR(engraving, RemoveItemBspTreeVisitor)
51 : public:
52 : EngravingItem* item;
53 :
54 0 : inline void visit(std::vector<EngravingItem*>& items) override { muse::remove(items, item); }
55 : };
56 :
57 : //---------------------------------------------------------
58 : // FindItemBspTreeVisitor
59 : //---------------------------------------------------------
60 :
61 : class FindItemBspTreeVisitor : public BspTreeVisitor
62 : {
63 0 : OBJECT_ALLOCATOR(engraving, FindItemBspTreeVisitor)
64 : public:
65 : std::vector<EngravingItem*> foundItems;
66 :
67 576 : void visit(std::vector<EngravingItem*>& items) override
68 : {
69 2480 : for (auto item : items) {
70 1904 : if (!item->itemDiscovered) {
71 390 : item->itemDiscovered = true;
72 390 : foundItems.push_back(item);
73 : }
74 : }
75 576 : }
76 : };
77 :
78 : //---------------------------------------------------------
79 : // BspTree
80 : //---------------------------------------------------------
81 :
82 3555 : BspTree::BspTree()
83 3555 : : m_leafCnt(0)
84 : {
85 3555 : m_depth = 0;
86 3555 : }
87 :
88 : //---------------------------------------------------------
89 : // intmaxlog
90 : //---------------------------------------------------------
91 :
92 7 : static inline int intmaxlog(int n)
93 : {
94 7 : return n > 0 ? std::max(int(::ceil(::log(double(n)) / ::log(double(2)))), 5) : 0;
95 : }
96 :
97 : //---------------------------------------------------------
98 : // initialize
99 : //---------------------------------------------------------
100 :
101 7 : void BspTree::initialize(const RectF& rec, int n)
102 : {
103 7 : m_depth = intmaxlog(n);
104 7 : this->m_rect = rec;
105 7 : m_leafCnt = 0;
106 :
107 7 : m_nodes.resize((1 << (m_depth + 1)) - 1);
108 7 : m_leaves.assign(1LL << m_depth, std::vector<EngravingItem*>());
109 7 : initialize(rec, m_depth, 0);
110 7 : }
111 :
112 : //---------------------------------------------------------
113 : // clear
114 : //---------------------------------------------------------
115 :
116 1 : void BspTree::clear()
117 : {
118 1 : m_leafCnt = 0;
119 1 : m_nodes.clear();
120 1 : m_leaves.clear();
121 1 : }
122 :
123 : //---------------------------------------------------------
124 : // insert
125 : //---------------------------------------------------------
126 :
127 413 : void BspTree::insert(EngravingItem* element)
128 : {
129 413 : InsertItemBspTreeVisitor insertVisitor;
130 413 : insertVisitor.item = element;
131 413 : climbTree(&insertVisitor, element->pageBoundingRect());
132 413 : }
133 :
134 : //---------------------------------------------------------
135 : // remove
136 : //---------------------------------------------------------
137 :
138 0 : void BspTree::remove(EngravingItem* element)
139 : {
140 0 : RemoveItemBspTreeVisitor removeVisitor;
141 0 : removeVisitor.item = element;
142 0 : climbTree(&removeVisitor, element->pageBoundingRect());
143 0 : }
144 :
145 : //---------------------------------------------------------
146 : // items
147 : //---------------------------------------------------------
148 :
149 5 : std::vector<EngravingItem*> BspTree::items(const RectF& rec)
150 : {
151 5 : FindItemBspTreeVisitor findVisitor;
152 5 : climbTree(&findVisitor, rec);
153 5 : std::vector<EngravingItem*> l;
154 395 : for (EngravingItem* e : findVisitor.foundItems) {
155 390 : e->itemDiscovered = false;
156 390 : if (e->pageBoundingRect().intersects(rec)) {
157 380 : l.push_back(e);
158 : }
159 : }
160 5 : return l;
161 5 : }
162 :
163 : //---------------------------------------------------------
164 : // items
165 : //---------------------------------------------------------
166 :
167 0 : std::vector<EngravingItem*> BspTree::items(const PointF& pos)
168 : {
169 0 : FindItemBspTreeVisitor findVisitor;
170 0 : climbTree(&findVisitor, pos);
171 :
172 0 : std::vector<EngravingItem*> l;
173 0 : for (EngravingItem* e : findVisitor.foundItems) {
174 0 : e->itemDiscovered = false;
175 0 : if (e->contains(pos)) {
176 0 : l.push_back(e);
177 : }
178 : }
179 0 : return l;
180 0 : }
181 :
182 : //---------------------------------------------------------
183 : // nearestNeighbor (public)
184 : //---------------------------------------------------------
185 :
186 44 : EngravingItem* BspTree::nearestNeighbor(const PointF& pos)
187 : {
188 44 : EngravingItem* nn = nullptr;
189 44 : double bestDistance = std::numeric_limits<double>::max();
190 44 : nearestNeighbor(pos, &nn, bestDistance);
191 44 : return nn;
192 : }
193 :
194 : //---------------------------------------------------------
195 : // nearestNeighbor (private)
196 : //---------------------------------------------------------
197 :
198 4121 : void BspTree::nearestNeighbor(const PointF& pos, EngravingItem** bestItem, double& bestDistance, int nodeIndex)
199 : {
200 4121 : if (m_nodes.empty()) {
201 0 : return;
202 : }
203 :
204 4121 : Node* node = &m_nodes[nodeIndex];
205 :
206 : // Base case: go through the items in the leaf node (if any), and update bestItem/bestDistance accordingly
207 4121 : if (node->type == Node::Type::LEAF) {
208 1929 : for (auto item : m_leaves[node->leafIndex]) {
209 78 : PointF itemPos = item->pageBoundingRect().center();
210 78 : double currDistance = std::sqrt(std::pow(pos.x() - itemPos.x(), 2) + std::pow(pos.y() - itemPos.y(), 2));
211 78 : if (currDistance < bestDistance) {
212 59 : *bestItem = item;
213 59 : bestDistance = currDistance;
214 : }
215 : }
216 1851 : return;
217 : }
218 :
219 : // Find which child contains pos and which is the "sibling"
220 2270 : int containerIdx = firstChildIndex(nodeIndex);
221 2270 : int siblingIdx = containerIdx + 1;
222 2270 : if (node->type == Node::Type::VERTICAL) {
223 1438 : if (pos.x() >= node->offset) {
224 500 : ++containerIdx;
225 500 : --siblingIdx;
226 : }
227 832 : } else if (pos.y() >= node->offset) {
228 330 : ++containerIdx;
229 330 : --siblingIdx;
230 : }
231 :
232 : // Recursion on container node
233 2270 : nearestNeighbor(pos, bestItem, bestDistance, containerIdx);
234 :
235 : // If the distance to the "offset" is shorter than the best distance we've found so far, then it's possible that the nearest
236 : // neighbour is in the sibling node (so we should search there too).
237 : double distanceToOffset;
238 2270 : if (node->type == Node::Type::HORIZONTAL) {
239 832 : distanceToOffset = std::abs(pos.y() - node->offset);
240 : } else {
241 1438 : distanceToOffset = std::abs(pos.x() - node->offset);
242 : }
243 :
244 2270 : if (distanceToOffset < bestDistance) {
245 : // Recursion on sibling node
246 1807 : nearestNeighbor(pos, bestItem, bestDistance, siblingIdx);
247 : }
248 : }
249 :
250 : #ifndef NDEBUG
251 : //---------------------------------------------------------
252 : // debug
253 : //---------------------------------------------------------
254 :
255 0 : String BspTree::debug(int index) const
256 : {
257 0 : const Node* node = &m_nodes.at(index);
258 :
259 0 : String tmp;
260 0 : if (node->type == Node::Type::LEAF) {
261 0 : RectF rec = rectForIndex(index);
262 0 : if (!m_leaves[node->leafIndex].empty()) {
263 0 : tmp += String(u"[%1, %2, %3, %4] contains %5 items\n")
264 0 : .arg(rec.left()).arg(rec.top())
265 0 : .arg(rec.width()).arg(rec.height())
266 0 : .arg(m_leaves[node->leafIndex].size());
267 : }
268 : } else {
269 0 : if (node->type == Node::Type::HORIZONTAL) {
270 0 : tmp += debug(firstChildIndex(index));
271 0 : tmp += debug(firstChildIndex(index) + 1);
272 : } else {
273 0 : tmp += debug(firstChildIndex(index));
274 0 : tmp += debug(firstChildIndex(index) + 1);
275 : }
276 : }
277 0 : return tmp;
278 0 : }
279 :
280 : #endif
281 :
282 : //---------------------------------------------------------
283 : // initialize
284 : //---------------------------------------------------------
285 :
286 2169 : void BspTree::initialize(const RectF& rec, int dep, int index)
287 : {
288 2169 : Node* node = &m_nodes[index];
289 2169 : if (index == 0) {
290 7 : node->type = Node::Type::HORIZONTAL;
291 7 : node->offset = rec.center().y();
292 : }
293 :
294 2169 : if (dep) {
295 : Node::Type type;
296 1081 : RectF rect1, rect2;
297 : double offset1, offset2;
298 :
299 1081 : if (node->type == Node::Type::HORIZONTAL) {
300 531 : type = Node::Type::VERTICAL;
301 531 : rect1.setRect(rec.left(), rec.top(), rec.width(), rec.height() * .5);
302 531 : rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rec.height() - rect1.height());
303 531 : offset1 = rect1.center().x();
304 531 : offset2 = rect2.center().x();
305 : } else {
306 550 : type = Node::Type::HORIZONTAL;
307 550 : rect1.setRect(rec.left(), rec.top(), rec.width() * .5, rec.height());
308 550 : rect2.setRect(rect1.right(), rect1.top(), rec.width() - rect1.width(), rect1.height());
309 550 : offset1 = rect1.center().y();
310 550 : offset2 = rect2.center().y();
311 : }
312 :
313 1081 : int childIndex = firstChildIndex(index);
314 :
315 1081 : Node* child = &m_nodes[childIndex];
316 1081 : child->offset = offset1;
317 1081 : child->type = type;
318 :
319 1081 : child = &m_nodes[childIndex + 1];
320 1081 : child->offset = offset2;
321 1081 : child->type = type;
322 :
323 1081 : initialize(rect1, dep - 1, childIndex);
324 1081 : initialize(rect2, dep - 1, childIndex + 1);
325 : } else {
326 1088 : node->type = Node::Type::LEAF;
327 1088 : node->leafIndex = m_leafCnt++;
328 : }
329 2169 : }
330 :
331 : //---------------------------------------------------------
332 : // climbTree
333 : //---------------------------------------------------------
334 :
335 0 : void BspTree::climbTree(BspTreeVisitor* visitor, const PointF& pos, int index)
336 : {
337 0 : if (m_nodes.empty()) {
338 0 : return;
339 : }
340 :
341 0 : Node* node = &m_nodes[index];
342 0 : int childIndex = firstChildIndex(index);
343 :
344 0 : switch (node->type) {
345 0 : case Node::Type::LEAF:
346 0 : visitor->visit(m_leaves[node->leafIndex]);
347 0 : break;
348 0 : case Node::Type::VERTICAL:
349 0 : if (pos.x() < node->offset) {
350 0 : climbTree(visitor, pos, childIndex);
351 : } else {
352 0 : climbTree(visitor, pos, childIndex + 1);
353 : }
354 0 : break;
355 0 : case Node::Type::HORIZONTAL:
356 0 : if (pos.y() < node->offset) {
357 0 : climbTree(visitor, pos, childIndex);
358 : } else {
359 0 : climbTree(visitor, pos, childIndex + 1);
360 : }
361 0 : break;
362 : }
363 : }
364 :
365 : //---------------------------------------------------------
366 : // climbTree
367 : //---------------------------------------------------------
368 :
369 7853 : void BspTree::climbTree(BspTreeVisitor* visitor, const RectF& rec, int index)
370 : {
371 7853 : if (m_nodes.empty()) {
372 0 : return;
373 : }
374 :
375 7853 : Node* node = &m_nodes[index];
376 7853 : int childIndex = firstChildIndex(index);
377 :
378 7853 : switch (node->type) {
379 2512 : case Node::Type::LEAF:
380 2512 : visitor->visit(m_leaves[node->leafIndex]);
381 2512 : break;
382 2285 : case Node::Type::VERTICAL:
383 2285 : if (rec.left() < node->offset) {
384 1572 : climbTree(visitor, rec, childIndex);
385 1572 : if (rec.right() >= node->offset) {
386 681 : climbTree(visitor, rec, childIndex + 1);
387 : }
388 : } else {
389 713 : climbTree(visitor, rec, childIndex + 1);
390 : }
391 2285 : break;
392 3056 : case Node::Type::HORIZONTAL:
393 3056 : if (rec.top() < node->offset) {
394 2251 : climbTree(visitor, rec, childIndex);
395 2251 : if (rec.bottom() >= node->offset) {
396 1413 : climbTree(visitor, rec, childIndex + 1);
397 : }
398 : } else {
399 805 : climbTree(visitor, rec, childIndex + 1);
400 : }
401 : }
402 : }
403 :
404 : //---------------------------------------------------------
405 : // rectForIndex
406 : //---------------------------------------------------------
407 :
408 0 : RectF BspTree::rectForIndex(int index) const
409 : {
410 0 : if (index <= 0) {
411 0 : return m_rect;
412 : }
413 :
414 0 : int parentIdx = parentIndex(index);
415 0 : RectF rec = rectForIndex(parentIdx);
416 0 : const Node* parent = &m_nodes.at(parentIdx);
417 :
418 0 : if (parent->type == Node::Type::HORIZONTAL) {
419 0 : if (index & 1) {
420 0 : rec.setRight(parent->offset);
421 : } else {
422 0 : rec.setLeft(parent->offset);
423 : }
424 : } else {
425 0 : if (index & 1) {
426 0 : rec.setBottom(parent->offset);
427 : } else {
428 0 : rec.setTop(parent->offset);
429 : }
430 : }
431 0 : return rec;
432 : }
433 : }
|
