1 #include <mbgl/algorithm/generate_clip_ids_impl.hpp>
2 #include <mbgl/algorithm/covered_by_children.hpp>
3 
4 #include <mbgl/util/std.hpp>
5 
6 #include <list>
7 #include <vector>
8 #include <bitset>
9 #include <cassert>
10 #include <iostream>
11 #include <algorithm>
12 #include <iterator>
13 
14 namespace mbgl {
15 namespace algorithm {
16 
Leaf(ClipID & clip_)17 ClipIDGenerator::Leaf::Leaf(ClipID& clip_) : clip(clip_) {
18 }
19 
add(const CanonicalTileID & p)20 void ClipIDGenerator::Leaf::add(const CanonicalTileID& p) {
21     // Ensure that no already present child is a parent of the new p.
22     for (const auto& child : children) {
23         if (p.isChildOf(child)) {
24             return;
25         }
26     }
27     children.emplace(p);
28 }
29 
operator ==(const Leaf & other) const30 bool ClipIDGenerator::Leaf::operator==(const Leaf& other) const {
31     return children == other.children;
32 }
33 
getClipIDs() const34 std::map<UnwrappedTileID, ClipID> ClipIDGenerator::getClipIDs() const {
35     std::map<UnwrappedTileID, ClipID> clipIDs;
36 
37     // Merge everything.
38     for (auto& pair : pool) {
39         auto& id = pair.first;
40         auto& leaf = pair.second;
41         auto res = clipIDs.emplace(id, leaf.clip);
42         if (!res.second) {
43             // Merge with the existing ClipID when there was already an element with the
44             // same tile ID.
45             res.first->second |= leaf.clip;
46         }
47     }
48 
49     for (auto it = clipIDs.begin(); it != clipIDs.end(); ++it) {
50         auto& childId = it->first;
51         auto& childClip = it->second;
52 
53         // Loop through all preceding stencils, and find all parents.
54 
55         for (auto parentIt = std::reverse_iterator<decltype(it)>(it);
56              parentIt != clipIDs.rend(); ++parentIt) {
57             auto& parentId = parentIt->first;
58             if (childId.isChildOf(parentId)) {
59                 // Once we have a parent, we add the bits  that this ID hasn't set yet.
60                 const auto& parentClip = parentIt->second;
61                 const auto mask = ~(childClip.mask & parentClip.mask);
62                 childClip.reference |= mask & parentClip.reference;
63                 childClip.mask |= parentClip.mask;
64             }
65         }
66     }
67 
68     // Remove tiles that are entirely covered by children.
69     util::erase_if(clipIDs, [&](const auto& stencil) {
70         return algorithm::coveredByChildren(stencil.first, clipIDs);
71     });
72 
73     return clipIDs;
74 }
75 
76 } // namespace algorithm
77 } // namespace mbgl
78