1 /** @file rowatlasallocator.cpp Row-based atlas allocator.
2 *
3 * The row allocator works according to the following principles:
4 *
5 * - In the beginning, there is a single row that spans the height of the entire atlas.
6 * The row contains a single empty segment.
7 * - If a row is completely empty, the empty space below will be split into a new empty
8 * row when the first allocation is made on the line. The first allocation also
9 * determines the initial height of the row.
10 * - The height of a row may expand if there is empty space below.
11 * - All the empty spaces are kept ordered from narrow to wide, so that when a new
12 * allocation is needed, the smallest suitable space can be picked.
13 * - Each row is a doubly-linked list containing the used and free regions.
14 * - If there are two adjacent free regions on a row, they will be merged into a larger
15 * empty space. Similarly empty rows are merged together.
16 *
17 * @authors Copyright (c) 2013-2017 Jaakko Keränen <jaakko.keranen@iki.fi>
18 *
19 * @par License
20 * LGPL: http://www.gnu.org/licenses/lgpl.html
21 *
22 * <small>This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU Lesser General Public License as published by
24 * the Free Software Foundation; either version 3 of the License, or (at your
25 * option) any later version. This program is distributed in the hope that it
26 * will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
27 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
28 * General Public License for more details. You should have received a copy of
29 * the GNU Lesser General Public License along with this program; if not, see:
30 * http://www.gnu.org/licenses</small>
31 */
32
33 #include "de/RowAtlasAllocator"
34
35 #include <QList>
36 #include <set>
37
38 namespace de {
39
40 template <typename Type>
linkAfter(Type * where,Type * object)41 void linkAfter(Type *where, Type *object)
42 {
43 object->next = where->next;
44 object->prev = where;
45
46 if (where->next) where->next->prev = object;
47 where->next = object;
48 }
49
50 template <typename Type>
unlink(Type * object)51 void unlink(Type *object)
52 {
53 if (object->prev) object->prev->next = object->next;
54 if (object->next) object->next->prev = object->prev;
55 object->next = object->prev = nullptr;
56 }
57
58 /// The allocations are only optimized if less than 70% of the area is being utilized.
59 static float const OPTIMIZATION_USAGE_THRESHOLD = .7f;
60
DENG2_PIMPL(RowAtlasAllocator)61 DENG2_PIMPL(RowAtlasAllocator)
62 {
63 struct Rows
64 {
65 struct Row;
66
67 /**
68 * Each row is composed of one or more used or empty slots.
69 */
70 struct Slot
71 {
72 Slot *next = nullptr;
73 Slot *prev = nullptr;
74 Row * row;
75
76 Id id{Id::None}; ///< Id of allocation here, or Id::None if free.
77 int x = 0; ///< Left edge of the slot.
78 duint width = 0; ///< Width of the slot.
79 dsize usedArea = 0;
80
81 Slot(Row *owner) : row(owner) {}
82
83 bool isEmpty() const
84 {
85 return id.isNone();
86 }
87
88 /**
89 * Take an empty slot into use. The remaining empty space is split off
90 * into a new slot.
91 *
92 * @param allocId Allocation identifier.
93 * @param widthWithMargin Needed width.
94 *
95 * @return If an empty slot was created, it is returned. Otherwise @c nullptr.
96 */
97 Slot *allocateAndSplit(Id const &allocId, duint widthWithMargin)
98 {
99 DENG2_ASSERT(isEmpty());
100 DENG2_ASSERT(width >= widthWithMargin);
101
102 int const remainder = width - widthWithMargin;
103
104 id = allocId;
105 width = widthWithMargin;
106
107 if (remainder > 0)
108 {
109 Slot *split = new Slot(row);
110 linkAfter(this, split);
111 split->x = x + width;
112 split->width = remainder;
113 return split;
114 }
115 return nullptr;
116 }
117
118 Slot *mergeWithNext()
119 {
120 DENG2_ASSERT(isEmpty());
121 if (!next || !next->isEmpty()) return nullptr;
122
123 Slot *merged = next;
124 unlink(merged);
125 width += merged->width;
126 return merged; // Caller gets ownership.
127 }
128
129 Slot *mergeWithPrevious()
130 {
131 DENG2_ASSERT(isEmpty());
132 if (!prev || !prev->isEmpty()) return nullptr;
133
134 Slot *merged = prev;
135 unlink(merged);
136 if (row->first == merged)
137 {
138 row->first = this;
139 }
140
141 x -= merged->width;
142 width += merged->width;
143 return merged; // Caller gets ownership.
144 }
145
146 struct SortByWidth {
147 bool operator () (Slot const *a, Slot const *b) const {
148 if (a->width == b->width) return a < b;
149 return a->width > b->width;
150 }
151 };
152 };
153
154 struct Row
155 {
156 Row *next = nullptr;
157 Row *prev = nullptr;
158
159 int y = 0; ///< Top edge of the row.
160 duint height = 0;
161 Slot *first; ///< There's always at least one empty slot.
162
163 Row() : first(new Slot(this)) {}
164
165 ~Row()
166 {
167 // Delete all the slots.
168 Slot *next;
169 for (Slot *s = first; s; s = next)
170 {
171 next = s->next;
172 delete s;
173 }
174 }
175
176 bool isEmpty() const
177 {
178 return first->isEmpty() && !first->next;
179 }
180
181 bool isTallEnough(duint heightWithMargin) const
182 {
183 if (height >= heightWithMargin) return true;
184 // The row might be able to expand.
185 if (next && next->isEmpty())
186 {
187 return (height + next->height) >= heightWithMargin;
188 }
189 return false;
190 }
191
192 Row *split(duint newHeight)
193 {
194 DENG2_ASSERT(isEmpty());
195 DENG2_ASSERT(newHeight <= height);
196
197 duint const remainder = height - newHeight;
198 height = newHeight;
199 if (remainder > 0)
200 {
201 Row *below = new Row;
202 linkAfter(this, below);
203 below->y = y + height;
204 below->height = remainder;
205 return below;
206 }
207 return nullptr;
208 }
209
210 void grow(duint newHeight)
211 {
212 DENG2_ASSERT(newHeight > height);
213 DENG2_ASSERT(next);
214 DENG2_ASSERT(next->isEmpty());
215
216 duint delta = newHeight - height;
217 height += delta;
218 next->y += delta;
219 next->height -= delta;
220 }
221 };
222
223 Row *top; ///< Always at least one row exists.
224 std::set<Slot *, Slot::SortByWidth> vacant; // not owned
225 QHash<Id, Slot *> slotsById; // not owned
226
227 dsize usedArea = 0; ///< Total allocated pixels.
228 Impl *d;
229
230 Rows(Impl *inst) : d(inst)
231 {
232 top = new Row;
233
234 /*
235 * Set up one big row, excluding the margins. This is all the space that
236 * we will be using; it will be chopped up and merged back together, but
237 * space will not be added or removed. Margin is reserved on the top/left
238 * edge; individual slots reserve it on the right, rows reserve it in the
239 * bottom.
240 */
241 top->y = d->margin;
242 top->height = d->size.y - d->margin;
243 top->first->x = d->margin;
244 top->first->width = d->size.x - d->margin;
245
246 addVacant(top->first);
247 }
248
249 ~Rows()
250 {
251 Row *next;
252 for (Row *r = top; r; r = next)
253 {
254 next = r->next;
255 delete r;
256 }
257 }
258
259 void addVacant(Slot *slot)
260 {
261 DENG2_ASSERT(slot->isEmpty());
262 vacant.insert(slot);
263 DENG2_ASSERT(*vacant.find(slot) == slot);
264 }
265
266 void removeVacant(Slot *slot)
267 {
268 DENG2_ASSERT(vacant.find(slot) != vacant.end());
269 vacant.erase(slot);
270 DENG2_ASSERT(vacant.find(slot) == vacant.end());
271 }
272
273 Slot *findBestVacancy(Atlas::Size const &size) const
274 {
275 Slot *best = nullptr;
276
277 // Look through the vacancies starting with the widest one. Statistically
278 // there are more narrow empty slots than wide ones.
279 for (Slot *s : vacant)
280 {
281 if (s->width >= size.x + d->margin)
282 {
283 if (s->row->isTallEnough(size.y + d->margin))
284 {
285 best = s;
286 }
287 }
288 else
289 {
290 // Too narrow, the rest is also too narrow.
291 break;
292 }
293 }
294
295 return best;
296 }
297
298 /**
299 * Allocate a slot for the specified size. The area used by the slot may be
300 * larger than the requested size.
301 *
302 * @param size Dimensions of area to allocate.
303 * @param rect Allocated rectangle is returned here.
304 * @param id Id for the new slot.
305 *
306 * @return Allocated slot, or @c nullptr.
307 */
308 Slot *alloc(Atlas::Size const &size, Rectanglei &rect, Id::Type id = Id::None)
309 {
310 Slot *slot = findBestVacancy(size);
311 if (!slot) return nullptr;
312
313 DENG2_ASSERT(slot->isEmpty());
314
315 // This slot will be taken into use.
316 removeVacant(slot);
317
318 Atlas::Size const needed = size + Atlas::Size(d->margin, d->margin);
319
320 // The first allocation determines the initial row height. The remainder
321 // is split into a new empty row (if something remains).
322 if (slot->row->isEmpty())
323 {
324 if (Row *addedRow = slot->row->split(needed.y))
325 {
326 // Give this new row the correct width.
327 addedRow->first->x = d->margin;
328 addedRow->first->width = d->size.x - d->margin;
329
330 addVacant(addedRow->first);
331 }
332 }
333
334 // The row may expand if needed.
335 if (slot->row->height < needed.y)
336 {
337 slot->row->grow(needed.y);
338 }
339
340 // Got a place, mark it down.
341 if (Slot *addedSlot = slot->allocateAndSplit(id? Id(id) : Id(), needed.x))
342 {
343 addVacant(addedSlot);
344 }
345 slotsById.insert(slot->id, slot);
346 rect = Rectanglei::fromSize(Vector2i(slot->x, slot->row->y), size);
347 slot->usedArea = size.x * size.y;
348 usedArea += slot->usedArea;
349
350 DENG2_ASSERT(usedArea <= d->size.x * d->size.y);
351 DENG2_ASSERT(vacant.find(slot) == vacant.end());
352 DENG2_ASSERT(!slot->isEmpty());
353
354 return slot;
355 }
356
357 void mergeLeft(Slot *slot)
358 {
359 if (Slot *removed = slot->mergeWithPrevious())
360 {
361 removeVacant(removed);
362 delete removed;
363 }
364 }
365
366 void mergeRight(Slot *slot)
367 {
368 if (Slot *removed = slot->mergeWithNext())
369 {
370 removeVacant(removed);
371 delete removed;
372 }
373 }
374
375 void mergeAbove(Row *row)
376 {
377 DENG2_ASSERT(row->isEmpty());
378 if (row->prev && row->prev->isEmpty())
379 {
380 Row *merged = row->prev;
381 unlink(merged);
382 if (top == merged)
383 {
384 top = row;
385 }
386 row->y -= merged->height;
387 row->height += merged->height;
388
389 removeVacant(merged->first);
390 delete merged;
391 }
392 }
393
394 void mergeBelow(Row *row)
395 {
396 DENG2_ASSERT(row->isEmpty());
397 if (row->next && row->next->isEmpty())
398 {
399 Row *merged = row->next;
400 unlink(merged);
401 row->height += merged->height;
402
403 removeVacant(merged->first);
404 delete merged;
405 }
406 }
407
408 void release(Id const &id)
409 {
410 DENG2_ASSERT(slotsById.contains(id));
411
412 // Make the slot vacant again.
413 Slot *slot = slotsById.take(id);
414 slot->id = Id::None;
415
416 DENG2_ASSERT(slot->usedArea > 0);
417 DENG2_ASSERT(usedArea >= slot->usedArea);
418
419 usedArea -= slot->usedArea;
420
421 mergeLeft(slot);
422 mergeRight(slot);
423
424 addVacant(slot);
425
426 // Empty rows will merge together.
427 if (slot->row->isEmpty())
428 {
429 mergeAbove(slot->row);
430 mergeBelow(slot->row);
431 }
432 }
433 };
434
435 Atlas::Size size;
436 int margin { 0 };
437 Allocations allocs;
438 std::unique_ptr<Rows> rows;
439
440 Impl(Public *i)
441 : Base(i)
442 , rows(new Rows(this))
443 {}
444
445 struct ContentSize {
446 Id::Type id;
447 Atlas::Size size;
448
449 ContentSize(Id const &allocId, Vector2ui const &sz) : id(allocId), size(sz) {}
450 bool operator < (ContentSize const &other) const {
451 if (size.y == other.size.y) {
452 // Secondary sorting by descending width.
453 return size.x > other.size.x;
454 }
455 return size.y > other.size.y;
456 }
457 };
458
459 bool optimize()
460 {
461 // Set up a LUT based on descending allocation width.
462 QList<ContentSize> descending;
463 DENG2_FOR_EACH(Allocations, i, allocs)
464 {
465 descending.append(ContentSize(i.key(), i.value().size()));
466 }
467 qSort(descending);
468
469 Allocations optimal;
470 std::unique_ptr<Rows> revised(new Rows(this));
471
472 for (auto const &ct : descending)
473 {
474 Rectanglei optRect;
475 if (!revised->alloc(ct.size, optRect, ct.id))
476 {
477 return false; // Ugh, can't actually fit these.
478 }
479 optimal[ct.id] = optRect;
480 }
481
482 allocs = optimal;
483 rows.reset(revised.release());
484 return true;
485 }
486
487 float usage() const
488 {
489 return float(rows->usedArea) / float(size.x * size.y);
490 }
491 };
492
RowAtlasAllocator()493 RowAtlasAllocator::RowAtlasAllocator() : d(new Impl(this))
494 {}
495
setMetrics(Atlas::Size const & totalSize,int margin)496 void RowAtlasAllocator::setMetrics(Atlas::Size const &totalSize, int margin)
497 {
498 d->size = totalSize;
499 d->margin = margin;
500
501 DENG2_ASSERT(d->allocs.isEmpty());
502 d->rows.reset(new Impl::Rows(d));
503 }
504
clear()505 void RowAtlasAllocator::clear()
506 {
507 d->rows.reset(new Impl::Rows(d));
508 d->allocs.clear();
509 }
510
allocate(Atlas::Size const & size,Rectanglei & rect,Id const & knownId)511 Id RowAtlasAllocator::allocate(Atlas::Size const &size, Rectanglei &rect,
512 Id const &knownId)
513 {
514 if (auto *slot = d->rows->alloc(size, rect, knownId))
515 {
516 d->allocs[slot->id] = rect;
517 return slot->id;
518 }
519
520 // Couldn't find a suitable place.
521 return 0;
522 }
523
release(Id const & id)524 void RowAtlasAllocator::release(Id const &id)
525 {
526 DENG2_ASSERT(d->allocs.contains(id));
527
528 d->rows->release(id);
529 d->allocs.remove(id);
530 }
531
count() const532 int RowAtlasAllocator::count() const
533 {
534 return d->allocs.size();
535 }
536
ids() const537 Atlas::Ids RowAtlasAllocator::ids() const
538 {
539 Atlas::Ids ids;
540 foreach (Id const &id, d->allocs.keys())
541 {
542 ids.insert(id);
543 }
544 return ids;
545 }
546
rect(Id const & id,Rectanglei & rect) const547 void RowAtlasAllocator::rect(Id const &id, Rectanglei &rect) const
548 {
549 DENG2_ASSERT(d->allocs.contains(id));
550 rect = d->allocs[id];
551 }
552
allocs() const553 RowAtlasAllocator::Allocations RowAtlasAllocator::allocs() const
554 {
555 return d->allocs;
556 }
557
optimize()558 bool RowAtlasAllocator::optimize()
559 {
560 // Optimization is not attempted unless there is a significant portion of
561 // unused space.
562 if (d->usage() >= OPTIMIZATION_USAGE_THRESHOLD) return false;
563
564 return d->optimize();
565 }
566
567 } // namespace de
568