separate_rects.h

   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 #ifndef DRM_HWCOMPOSER_SEPARATE_RECTS_H_
  18 #define DRM_HWCOMPOSER_SEPARATE_RECTS_H_
  19
  20 #include <stdint.h>
  21
  22 #include <sstream>
  23 #include <vector>
  24
  25 namespace separate_rects {
  26
  27 template <typename TFloat>
  28 struct Rect {
  29   union {
  30     struct {
  31       TFloat left, top, right, bottom;
  32     };
  33     struct {
  34       TFloat x1, y1, x2, y2;
  35     };
  36     TFloat bounds[4];
  37   };
  38
  39   typedef TFloat TNum;
  40
  41   Rect() {
  42   }
  43
  44   Rect(TFloat xx1, TFloat yy1, TFloat xx2, TFloat yy2)
  45       : x1(xx1), y1(yy1), x2(xx2), y2(yy2) {
  46   }
  47
  48   template <typename T>
  49   Rect(const Rect<T> &rhs) {
  50     for (int i = 0; i < 4; i++)
  51       bounds[i] = rhs.bounds[i];
  52   }
  53
  54   template <typename T>
  55   Rect<TFloat> &operator=(const Rect<T> &rhs) {
  56     for (int i = 0; i < 4; i++)
  57       bounds[i] = rhs.bounds[i];
  58     return *this;
  59   }
  60
  61   bool operator==(const Rect &rhs) const {
  62     for (int i = 0; i < 4; i++) {
  63       if (bounds[i] != rhs.bounds[i])
  64         return false;
  65     }
  66
  67     return true;
  68   }
  69
  70   TFloat width() const {
  71     return bounds[2] - bounds[0];
  72   }
  73
  74   TFloat height() const {
  75     return bounds[3] - bounds[1];
  76   }
  77
  78   TFloat area() const {
  79     return width() * height();
  80   }
  81
  82   void Dump(std::ostringstream *out) const {
  83     *out << "[x/y/w/h]=" << left << "/" << top << "/" << width() << "/"
  84          << height();
  85   }
  86 };
  87
  88 template <typename TUInt>
  89 struct IdSet {
  90  public:
  91   typedef TUInt TId;
  92
  93   IdSet() : bitset(0) {
  94   }
  95
  96   IdSet(TId id) : bitset(0) {
  97     add(id);
  98   }
  99
 100   void add(TId id) {
 101     bitset |= ((TUInt)1) << id;
 102   }
 103
 104   void subtract(TId id) {
 105     bitset &= ~(((TUInt)1) << id);
 106   }
 107
 108   bool isEmpty() const {
 109     return bitset == 0;
 110   }
 111
 112   TUInt getBits() const {
 113     return bitset;
 114   }
 115
 116   bool operator==(const IdSet<TId> &rhs) const {
 117     return bitset == rhs.bitset;
 118   }
 119
 120   bool operator<(const IdSet<TId> &rhs) const {
 121     return bitset < rhs.bitset;
 122   }
 123
 124   IdSet<TId> operator|(const IdSet<TId> &rhs) const {
 125     IdSet ret;
 126     ret.bitset = bitset | rhs.bitset;
 127     return ret;
 128   }
 129
 130   IdSet<TId> operator|(TId id) const {
 131     IdSet<TId> ret;
 132     ret.bitset = bitset;
 133     ret.add(id);
 134     return ret;
 135   }
 136
 137   static const int max_elements = sizeof(TId) * 8;
 138
 139  private:
 140   TUInt bitset;
 141 };
 142
 143 template <typename TId, typename TNum>
 144 struct RectSet {
 145   IdSet<TId> id_set;
 146   Rect<TNum> rect;
 147
 148   RectSet(const IdSet<TId> &i, const Rect<TNum> &r) : id_set(i), rect(r) {
 149   }
 150
 151   bool operator==(const RectSet<TId, TNum> &rhs) const {
 152     return id_set == rhs.id_set && rect == rhs.rect;
 153   }
 154 };
 155
 156 // Separates up to a maximum of 64 input rectangles into mutually non-
 157 // overlapping rectangles that cover the exact same area and outputs those non-
 158 // overlapping rectangles. Each output rectangle also includes the set of input
 159 // rectangle indices that overlap the output rectangle encoded in a bitset. For
 160 // example, an output rectangle that overlaps input rectangles in[0], in[1], and
 161 // in[4], the bitset would be (ommitting leading zeroes) 10011.
 162 void separate_frects_64(const std::vector<Rect<float>> &in,
 163                         std::vector<RectSet<uint64_t, float>> *out);
 164 void separate_rects_64(const std::vector<Rect<int>> &in,
 165                        std::vector<RectSet<uint64_t, int>> *out);
 166
 167 }  // namespace separate_rects
 168
 169 #endif