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