git.sesse.net Git - casparcg/blob - core/producer/text/utils/texture_atlas.cpp

   1 /* ============================================================================
   2  * Freetype GL - A C OpenGL Freetype engine
   3  * Platform:    Any
   4  * WWW:         http://code.google.com/p/freetype-gl/
   5  * ----------------------------------------------------------------------------
   6  * Copyright 2011,2012 Nicolas P. Rougier. All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are met:
  10  *
  11  *  1. Redistributions of source code must retain the above copyright notice,
  12  *     this list of conditions and the following disclaimer.
  13  *
  14  *  2. Redistributions in binary form must reproduce the above copyright
  15  *     notice, this list of conditions and the following disclaimer in the
  16  *     documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY NICOLAS P. ROUGIER ''AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  20  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
  21  * EVENT SHALL NICOLAS P. ROUGIER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  22  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and documentation are
  30  * those of the authors and should not be interpreted as representing official
  31  * policies, either expressed or implied, of Nicolas P. Rougier.
  32  * ============================================================================
  33  */
  34
  35 #include <limits.h>
  36 #include <list>
  37 #include <vector>
  38 #include "texture_atlas.h"
  39
  40 namespace caspar { namespace core { namespace text {
  41
  42
  43 struct texture_atlas::impl
  44 {
  45 private:
  46         struct node
  47         {
  48                 int x;
  49                 int y;
  50                 int width;
  51         };
  52
  53         typedef std::list<node> node_list;
  54         typedef std::list<node>::iterator node_iterator;
  55
  56         node_list nodes_;
  57
  58         size_t width_;
  59         size_t height_;
  60         size_t depth_;
  61         std::vector<uint8_t> data_;
  62         size_t used_                                            = 0;
  63
  64 public:
  65         impl(const size_t width, const size_t height, const size_t depth) : width_(width), height_(height), depth_(depth), data_(width*height*depth, 0)
  66         {
  67                 // We want a one pixel border around the whole atlas to avoid any artefact when sampling texture
  68                 node n = {1, 1, static_cast<int>(width_) - 2};
  69                 nodes_.push_back(n);
  70         }
  71
  72         rect get_region(int width, int height)
  73         {
  74                 rect region = { 0, 0, static_cast<int>(width), static_cast<int>(height) };
  75
  76                 int best_height = INT_MAX;
  77                 int best_width = INT_MAX;
  78                 node_iterator best_it = nodes_.end();
  79
  80                 for(auto it = nodes_.begin(); it != nodes_.end(); ++it)
  81                 {
  82                         int y = fit(it, width, height);
  83                         if( y >= 0 )
  84                         {
  85                                 if( ( (y + height) < best_height ) ||
  86                                         ( ((y + height) == best_height) && ((*it).width < best_width)) )
  87                                 {
  88                                         best_height = y + height;
  89                                         best_it = it;
  90                                         best_width = (*it).width;
  91                                         region.x = (*it).x;
  92                                         region.y = (int)y;
  93                                 }
  94                         }
  95                 }
  96
  97                 if(best_it == nodes_.end())
  98                 {
  99                         region.x = -1;
 100                         region.y = -1;
 101                         region.width = 0;
 102                         region.height = 0;
 103                         return region;
 104                 }
 105
 106                 node new_node;
 107                 new_node.x = region.x;
 108                 new_node.y = region.y + (int)height;
 109                 new_node.width = (int)width;
 110
 111                 best_it = nodes_.insert(best_it, new_node);
 112
 113                 for(auto it = ++best_it; it != nodes_.end(); ++it)
 114                 {
 115                         auto prev = it; --prev;
 116
 117                         if ((*it).x < ((*prev).x + (*prev).width) )
 118                         {
 119                                 int shrink = (*prev).x + (*prev).width - (*it).x;
 120                                 (*it).x += shrink;
 121                                 (*it).width -= shrink;
 122                                 if ((*it).width <= 0)
 123                                 {
 124                                         nodes_.erase(it);
 125                                         it = prev;
 126                                 }
 127                                 else
 128                                         break;
 129                         }
 130                         else
 131                                 break;
 132                 }
 133
 134                 merge();
 135                 used_ += width * height;
 136                 return region;
 137         }
 138
 139         //the data parameter points to bitmap-data that is 8-bit grayscale.
 140         void set_region(const size_t x, const size_t y, const size_t width, const size_t height, const unsigned char *src, const size_t stride, const color<double>& col)
 141         {
 142                 //this assumes depth_ is set to 4
 143                 for(size_t i=0; i<height; ++i)
 144                 {
 145                         for(size_t j=0; j<width; ++j)
 146                         {
 147                                 unsigned char* pixel = &data_[((y+i)*width_ + x + j)*depth_];
 148                                 unsigned char value = src[i*stride + j];
 149                                 pixel[0] = (unsigned char)(value*col.b);
 150                                 pixel[1] = (unsigned char)(value*col.g);
 151                                 pixel[2] = (unsigned char)(value*col.r);
 152                                 pixel[3] = (unsigned char)(value*col.a);
 153                         }
 154                 }
 155         }
 156
 157         void clear()
 158         {
 159                 nodes_.clear();
 160                 used_ = 0;
 161
 162                 node n = {1,1,(int)width_-2};
 163                 nodes_.push_back(n);
 164                 data_.assign(width_*height_*depth_, 0);
 165         }
 166
 167         size_t depth() const { return depth_; }
 168         size_t width() const { return width_; }
 169         size_t height() const { return height_; }
 170         const uint8_t* data() const { return data_.data(); }
 171
 172 private:
 173         int fit(node_iterator it, const size_t width, const size_t height)
 174         {
 175                 int x = (*it).x;
 176                 int y = (*it).y;
 177                 int width_left = (int)width;
 178
 179                 if ((x + width) > (width_ - 1))
 180                         return -1;
 181
 182                 while( width_left > 0 && it != nodes_.end())
 183                 {
 184                         if((*it).y > y)
 185                                 y = (*it).y;
 186                         if((y + height) > (height_ - 1))
 187                                 return -1;
 188
 189                         width_left -= (*it).width;
 190                         ++it;
 191                 }
 192
 193                 return y;
 194         }
 195
 196         void merge()
 197         {
 198                 auto it = nodes_.begin();
 199                 while(true)
 200                 {
 201                         auto next = it; ++next;
 202                         if(next == nodes_.end())
 203                                 break;
 204
 205                         if((*it).y == (*next).y)
 206                         {
 207                                 (*it).width += (*next).width;
 208                                 nodes_.erase(next);
 209                         }
 210                         else
 211                                 ++it;
 212                 }
 213         }
 214 };
 215
 216 texture_atlas::texture_atlas(const size_t w, const size_t h, const size_t d) : impl_(new impl(w, h, d)) {}
 217 rect texture_atlas::get_region(int width, int height) const { return impl_->get_region(width, height); }
 218 void texture_atlas::set_region(const size_t x, const size_t y, const size_t width, const size_t height, const unsigned char *src, const size_t stride, const color<double>& col)
 219         { impl_->set_region(x, y, width, height, src, stride, col); }
 220
 221 void texture_atlas::clear() { impl_->clear(); }
 222
 223 size_t texture_atlas::width() const { return impl_->width(); }
 224 size_t texture_atlas::height() const { return impl_->height(); }
 225 size_t texture_atlas::depth() const { return impl_->depth(); }
 226 const uint8_t* texture_atlas::data() const { return impl_->data(); }
 227
 228 }}}