Home | History | Annotate | Download | only in drm_hwcomposer
      1 /*
      2  * Copyright (C) 2015 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "separate_rects.h"
     18 #include <algorithm>
     19 #include <assert.h>
     20 #include <iostream>
     21 #include <map>
     22 #include <set>
     23 #include <utility>
     24 #include <vector>
     25 
     26 namespace separate_rects {
     27 
     28 enum EventType { START, END };
     29 
     30 template <typename TId, typename TNum>
     31 struct StartedRect {
     32   IdSet<TId> id_set;
     33   TNum left, top, bottom;
     34 
     35   // Note that this->left is not part of the key. That field is only to mark the
     36   // left edge of the rectangle.
     37   bool operator<(const StartedRect<TId, TNum> &rhs) const {
     38     return (top < rhs.top || (top == rhs.top && bottom < rhs.bottom)) ||
     39            (top == rhs.top && bottom == rhs.bottom && id_set < rhs.id_set);
     40   }
     41 };
     42 
     43 template <typename TId, typename TNum>
     44 struct SweepEvent {
     45   EventType type;
     46   union {
     47     TNum x;
     48     TNum y;
     49   };
     50 
     51   TId rect_id;
     52 
     53   bool operator<(const SweepEvent<TId, TNum> &rhs) const {
     54     return (y < rhs.y || (y == rhs.y && rect_id < rhs.rect_id));
     55   }
     56 };
     57 
     58 template <typename TNum>
     59 std::ostream &operator<<(std::ostream &os, const Rect<TNum> &rect) {
     60   return os << rect.bounds[0] << ", " << rect.bounds[1] << ", "
     61             << rect.bounds[2] << ", " << rect.bounds[3];
     62 }
     63 
     64 template <typename TUInt>
     65 std::ostream &operator<<(std::ostream &os, const IdSet<TUInt> &obj) {
     66   int bits = IdSet<TUInt>::max_elements;
     67   TUInt mask = ((TUInt)0x1) << (bits - 1);
     68   for (int i = 0; i < bits; i++)
     69     os << ((obj.getBits() & (mask >> i)) ? "1" : "0");
     70   return os;
     71 }
     72 
     73 template <typename TNum, typename TId>
     74 void separate_rects(const std::vector<Rect<TNum>> &in,
     75                     std::vector<RectSet<TId, TNum>> *out) {
     76   // Overview:
     77   // This algorithm is a line sweep algorithm that travels from left to right.
     78   // The sweep stops at each vertical edge of each input rectangle in sorted
     79   // order of x-coordinate. At each stop, the sweep line is examined in order of
     80   // y-coordinate from top to bottom. Along the way, a running set of rectangle
     81   // IDs is either added to or subtracted from as the top and bottom edges are
     82   // encountered, respectively. At each change of that running set, a copy of
     83   // that set is recorded in along with the the y-coordinate it happened at in a
     84   // list. This list is then interpreted as a sort of vertical cross section of
     85   // our output set of non-overlapping rectangles. Based of the algorithm found
     86   // at: http://stackoverflow.com/a/2755498
     87 
     88   if (in.size() > IdSet<TNum>::max_elements) {
     89     return;
     90   }
     91 
     92   // Events are when the sweep line encounters the starting or ending edge of
     93   // any input rectangle.
     94   std::set<SweepEvent<TId, TNum>> sweep_h_events;  // Left or right bounds
     95   std::set<SweepEvent<TId, TNum>> sweep_v_events;  // Top or bottom bounds
     96 
     97   // A started rect is a rectangle whose left, top, bottom edge, and set of
     98   // rectangle IDs is known. The key of this map includes all that information
     99   // (except the left edge is never used to determine key equivalence or
    100   // ordering),
    101   std::map<StartedRect<TId, TNum>, bool> started_rects;
    102 
    103   // This is cleared after every event. Its declaration is here to avoid
    104   // reallocating a vector and its buffers every event.
    105   std::vector<std::pair<TNum, IdSet<TId>>> active_regions;
    106 
    107   // This pass will add rectangle start and end events to be triggered as the
    108   // algorithm sweeps from left to right.
    109   for (TId i = 0; i < in.size(); i++) {
    110     const Rect<TNum> &rect = in[i];
    111 
    112     // Filter out empty or invalid rects.
    113     if (rect.left >= rect.right || rect.top >= rect.bottom)
    114       continue;
    115 
    116     SweepEvent<TId, TNum> evt;
    117     evt.rect_id = i;
    118 
    119     evt.type = START;
    120     evt.x = rect.left;
    121     sweep_h_events.insert(evt);
    122 
    123     evt.type = END;
    124     evt.x = rect.right;
    125     sweep_h_events.insert(evt);
    126   }
    127 
    128   for (typename std::set<SweepEvent<TId, TNum>>::iterator it =
    129            sweep_h_events.begin();
    130        it != sweep_h_events.end(); ++it) {
    131     const SweepEvent<TId, TNum> &h_evt = *it;
    132     const Rect<TNum> &rect = in[h_evt.rect_id];
    133 
    134     // During this event, we have encountered a vertical starting or ending edge
    135     // of a rectangle so want to append or remove (respectively) that rectangles
    136     // top and bottom from the vertical sweep line.
    137     SweepEvent<TId, TNum> v_evt;
    138     v_evt.rect_id = h_evt.rect_id;
    139     if (h_evt.type == START) {
    140       v_evt.type = START;
    141       v_evt.y = rect.top;
    142       sweep_v_events.insert(v_evt);
    143 
    144       v_evt.type = END;
    145       v_evt.y = rect.bottom;
    146       sweep_v_events.insert(v_evt);
    147     } else {
    148       v_evt.type = START;
    149       v_evt.y = rect.top;
    150       typename std::set<SweepEvent<TId, TNum>>::iterator start_it =
    151           sweep_v_events.find(v_evt);
    152       assert(start_it != sweep_v_events.end());
    153       sweep_v_events.erase(start_it);
    154 
    155       v_evt.type = END;
    156       v_evt.y = rect.bottom;
    157       typename std::set<SweepEvent<TId, TNum>>::iterator end_it =
    158           sweep_v_events.find(v_evt);
    159       assert(end_it != sweep_v_events.end());
    160       sweep_v_events.erase(end_it);
    161     }
    162 
    163     // Peeks ahead to see if there are other rectangles sharing a vertical edge
    164     // with the current sweep line. If so, we want to continue marking up the
    165     // sweep line before actually processing the rectangles the sweep line is
    166     // intersecting.
    167     typename std::set<SweepEvent<TId, TNum>>::iterator next_it = it;
    168     ++next_it;
    169     if (next_it != sweep_h_events.end()) {
    170       if (next_it->x == h_evt.x) {
    171         continue;
    172       }
    173     }
    174 
    175 #ifdef RECTS_DEBUG
    176     std::cout << h_evt.x << std::endl;
    177 #endif
    178 
    179     // After the following for loop, active_regions will be a list of
    180     // y-coordinates paired with the set of rectangle IDs that are intersect at
    181     // that y-coordinate (and the current sweep line's x-coordinate). For
    182     // example if the current sweep line were the left edge of a scene with only
    183     // one rectangle of ID 0 and bounds (left, top, right, bottom) == (2, 3, 4,
    184     // 5), active_regions will be [({ 0 }, 3), {}, 5].
    185     active_regions.clear();
    186     IdSet<TId> active_set;
    187     for (typename std::set<SweepEvent<TId, TNum>>::iterator it =
    188              sweep_v_events.begin();
    189          it != sweep_v_events.end(); ++it) {
    190       const SweepEvent<TId, TNum> &v_evt = *it;
    191 
    192       if (v_evt.type == START) {
    193         active_set.add(v_evt.rect_id);
    194       } else {
    195         active_set.subtract(v_evt.rect_id);
    196       }
    197 
    198       if (active_regions.size() > 0 && active_regions.back().first == v_evt.y) {
    199         active_regions.back().second = active_set;
    200       } else {
    201         active_regions.push_back(std::make_pair(v_evt.y, active_set));
    202       }
    203     }
    204 
    205 #ifdef RECTS_DEBUG
    206     std::cout << "x:" << h_evt.x;
    207     for (std::vector<std::pair<TNum, IdSet>>::iterator it =
    208              active_regions.begin();
    209          it != active_regions.end(); ++it) {
    210       std::cout << " " << it->first << "(" << it->second << ")"
    211                 << ",";
    212     }
    213     std::cout << std::endl;
    214 #endif
    215 
    216     // To determine which started rectangles are ending this event, we make them
    217     // all as false, or unseen during this sweep line.
    218     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
    219              started_rects.begin();
    220          it != started_rects.end(); ++it) {
    221       it->second = false;
    222     }
    223 
    224     // This for loop will iterate all potential new rectangles and either
    225     // discover it was already started (and then mark it true), or that it is a
    226     // new rectangle and add it to the started rectangles. A started rectangle
    227     // is unique if it has a distinct top, bottom, and set of rectangle IDs.
    228     // This is tricky because a potential rectangle could be encountered here
    229     // that has a non-unique top and bottom, so it shares geometry with an
    230     // already started rectangle, but the set of rectangle IDs differs. In that
    231     // case, we have a new rectangle, and the already existing started rectangle
    232     // will not be marked as seen ("true" in the std::pair) and will get ended
    233     // by the for loop after this one. This is as intended.
    234     for (typename std::vector<std::pair<TNum, IdSet<TId>>>::iterator it =
    235              active_regions.begin();
    236          it != active_regions.end(); ++it) {
    237       IdSet<TId> region_set = it->second;
    238 
    239       if (region_set.isEmpty())
    240         continue;
    241 
    242       // An important property of active_regions is that each region where a set
    243       // of rectangles applies is bounded at the bottom by the next (in the
    244       // vector) region's starting y-coordinate.
    245       typename std::vector<std::pair<TNum, IdSet<TId>>>::iterator next_it = it;
    246       ++next_it;
    247       assert(next_it != active_regions.end());
    248 
    249       TNum region_top = it->first;
    250       TNum region_bottom = next_it->first;
    251 
    252       StartedRect<TId, TNum> rect_key;
    253       rect_key.id_set = region_set;
    254       rect_key.left = h_evt.x;
    255       rect_key.top = region_top;
    256       rect_key.bottom = region_bottom;
    257 
    258       // Remember that rect_key.left is ignored for the purposes of searching
    259       // the started rects. This follows from the fact that a previously started
    260       // rectangle would by definition have a left bound less than the current
    261       // event's x-coordinate. We are interested in continuing the started
    262       // rectangles by marking them seen (true) but we don't know, care, or wish
    263       // to change the left bound at this point. If there are no matching
    264       // rectangles for this region, start a new one and mark it as seen (true).
    265       typename std::map<StartedRect<TId, TNum>, bool>::iterator
    266           started_rect_it = started_rects.find(rect_key);
    267       if (started_rect_it == started_rects.end()) {
    268         started_rects[rect_key] = true;
    269       } else {
    270         started_rect_it->second = true;
    271       }
    272     }
    273 
    274     // This for loop ends all rectangles that were unseen during this event.
    275     // Because this is the first event where we didn't see this rectangle, it's
    276     // right edge is exactly the current event's x-coordinate. With this, we
    277     // have the final piece of information to output this rectangle's geometry
    278     // and set of input rectangle IDs. To end a started rectangle, we erase it
    279     // from the started_rects map and append the completed rectangle to the
    280     // output vector.
    281     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
    282              started_rects.begin();
    283          it != started_rects.end();
    284          /* inc in body */) {
    285       if (!it->second) {
    286         const StartedRect<TId, TNum> &proto_rect = it->first;
    287         Rect<TNum> out_rect;
    288         out_rect.left = proto_rect.left;
    289         out_rect.top = proto_rect.top;
    290         out_rect.right = h_evt.x;
    291         out_rect.bottom = proto_rect.bottom;
    292         out->push_back(RectSet<TId, TNum>(proto_rect.id_set, out_rect));
    293         started_rects.erase(it++);  // Also increments out iterator.
    294 
    295 #ifdef RECTS_DEBUG
    296         std::cout << "    <" << proto_rect.id_set << "(" << rect << ")"
    297                   << std::endl;
    298 #endif
    299       } else {
    300         // Remember this for loop has no built in increment step. We do it here.
    301         ++it;
    302       }
    303     }
    304   }
    305 }
    306 
    307 void separate_frects_64(const std::vector<Rect<float>> &in,
    308                         std::vector<RectSet<uint64_t, float>> *out) {
    309   separate_rects(in, out);
    310 }
    311 
    312 void separate_rects_64(const std::vector<Rect<int>> &in,
    313                        std::vector<RectSet<uint64_t, int>> *out) {
    314   separate_rects(in, out);
    315 }
    316 
    317 }  // namespace separate_rects
    318 
    319 #ifdef RECTS_TEST
    320 
    321 using namespace separate_rects;
    322 
    323 int main(int argc, char **argv) {
    324 #define RectSet RectSet<TId, TNum>
    325 #define Rect Rect<TNum>
    326 #define IdSet IdSet<TId>
    327   typedef uint64_t TId;
    328   typedef float TNum;
    329 
    330   std::vector<Rect> in;
    331   std::vector<RectSet> out;
    332   std::vector<RectSet> expected_out;
    333 
    334   in.push_back({0, 0, 4, 5});
    335   in.push_back({2, 0, 6, 6});
    336   in.push_back({4, 0, 8, 5});
    337   in.push_back({0, 7, 8, 9});
    338 
    339   in.push_back({10, 0, 18, 5});
    340   in.push_back({12, 0, 16, 5});
    341 
    342   in.push_back({20, 11, 24, 17});
    343   in.push_back({22, 13, 26, 21});
    344   in.push_back({32, 33, 36, 37});
    345   in.push_back({30, 31, 38, 39});
    346 
    347   in.push_back({40, 43, 48, 45});
    348   in.push_back({44, 41, 46, 47});
    349 
    350   in.push_back({50, 51, 52, 53});
    351   in.push_back({50, 51, 52, 53});
    352   in.push_back({50, 51, 52, 53});
    353 
    354   in.push_back({0, 0, 0, 10});
    355   in.push_back({0, 0, 10, 0});
    356   in.push_back({10, 0, 0, 10});
    357   in.push_back({0, 10, 10, 0});
    358 
    359   for (int i = 0; i < 100000; i++) {
    360     out.clear();
    361     separate_rects(in, &out);
    362   }
    363 
    364   for (int i = 0; i < out.size(); i++) {
    365     std::cout << out[i].id_set << "(" << out[i].rect << ")" << std::endl;
    366   }
    367 
    368   std::cout << "# of rects: " << out.size() << std::endl;
    369 
    370   expected_out.push_back(RectSet(IdSet(0), Rect(0, 0, 2, 5)));
    371   expected_out.push_back(RectSet(IdSet(1), Rect(2, 5, 6, 6)));
    372   expected_out.push_back(RectSet(IdSet(1) | 0, Rect(2, 0, 4, 5)));
    373   expected_out.push_back(RectSet(IdSet(1) | 2, Rect(4, 0, 6, 5)));
    374   expected_out.push_back(RectSet(IdSet(2), Rect(6, 0, 8, 5)));
    375   expected_out.push_back(RectSet(IdSet(3), Rect(0, 7, 8, 9)));
    376   expected_out.push_back(RectSet(IdSet(4), Rect(10, 0, 12, 5)));
    377   expected_out.push_back(RectSet(IdSet(5) | 4, Rect(12, 0, 16, 5)));
    378   expected_out.push_back(RectSet(IdSet(4), Rect(16, 0, 18, 5)));
    379   expected_out.push_back(RectSet(IdSet(6), Rect(20, 11, 22, 17)));
    380   expected_out.push_back(RectSet(IdSet(6) | 7, Rect(22, 13, 24, 17)));
    381   expected_out.push_back(RectSet(IdSet(6), Rect(22, 11, 24, 13)));
    382   expected_out.push_back(RectSet(IdSet(7), Rect(22, 17, 24, 21)));
    383   expected_out.push_back(RectSet(IdSet(7), Rect(24, 13, 26, 21)));
    384   expected_out.push_back(RectSet(IdSet(9), Rect(30, 31, 32, 39)));
    385   expected_out.push_back(RectSet(IdSet(8) | 9, Rect(32, 33, 36, 37)));
    386   expected_out.push_back(RectSet(IdSet(9), Rect(32, 37, 36, 39)));
    387   expected_out.push_back(RectSet(IdSet(9), Rect(32, 31, 36, 33)));
    388   expected_out.push_back(RectSet(IdSet(9), Rect(36, 31, 38, 39)));
    389   expected_out.push_back(RectSet(IdSet(10), Rect(40, 43, 44, 45)));
    390   expected_out.push_back(RectSet(IdSet(10) | 11, Rect(44, 43, 46, 45)));
    391   expected_out.push_back(RectSet(IdSet(11), Rect(44, 41, 46, 43)));
    392   expected_out.push_back(RectSet(IdSet(11), Rect(44, 45, 46, 47)));
    393   expected_out.push_back(RectSet(IdSet(10), Rect(46, 43, 48, 45)));
    394   expected_out.push_back(RectSet(IdSet(12) | 13 | 14, Rect(50, 51, 52, 53)));
    395 
    396   for (int i = 0; i < expected_out.size(); i++) {
    397     RectSet &ex_out = expected_out[i];
    398     if (std::find(out.begin(), out.end(), ex_out) == out.end()) {
    399       std::cout << "Missing Rect: " << ex_out.id_set << "(" << ex_out.rect
    400                 << ")" << std::endl;
    401     }
    402   }
    403 
    404   for (int i = 0; i < out.size(); i++) {
    405     RectSet &actual_out = out[i];
    406     if (std::find(expected_out.begin(), expected_out.end(), actual_out) ==
    407         expected_out.end()) {
    408       std::cout << "Extra Rect: " << actual_out.id_set << "(" << actual_out.rect
    409                 << ")" << std::endl;
    410     }
    411   }
    412 
    413   return 0;
    414 }
    415 
    416 #endif
    417