6
\$\begingroup\$

This is meant to be used (amongst other things) in a dynamic texture atlas, i.e. it's meant to be long-lived and incrementally added to over time. Think full unicode font were needed glyphs are added on a per-demand basis.

It employs the "Guillotine" approach to bin packing.

#ifndef SLT_RECT_PACK_H
#define SLT_RECT_PACK_H

#include <array>
#include <limits>
#include <vector>

namespace slt {

  // Default scorer: fits the rect as snuggly as possible in a dimension
  // Note: lower means better.
  template<typename T>
  T DefaultRectScorer(std::array<T, 2> const& src, std::array<T, 2> const& dst) {
    return std::max(dst[0] - src[0], dst[1] - src[1]);
  }

  // This is an open-ended incremental rect packer.
  //
  // For optimal results, you should sort the list of rectangles to pack
  // beforehand, but this is not a hard requirement.
  //
  // If using a custom allocator, it has to be rebindable.
  template<typename T, typename Alloc = std::allocator<char>>
  class RectPacker2D {
  public:
    using Vec = std::array<T, 2>;
    struct Result { 
      Vec pos; 
      Vec size; 
    };

    inline explicit RectPacker2D(Vec bin_size, Alloc const& alloc = Alloc());

    // Packs a rect of size `rect`.
    // On failure, the result will be {{0,0}, {0,0}}
    // The width and height may have been flipped from the source rect.
    template<typename RECT_SCORER = decltype(DefaultRectScorer<T>)>
    inline Result pack(Vec rect, RECT_SCORER = DefaultRectScorer<T>);

  private:
    static inline bool fits(Vec src, Vec dst);

    struct FreeRect {
      Vec pos;
      Vec size;
    };

    using FreeRectAllocator = typename Alloc::template rebind<FreeRect>::other;
    std::vector<FreeRect, FreeRectAllocator> free_rects_;
  };

  template<typename T, typename Alloc>
  bool RectPacker2D<T, Alloc>::fits(Vec src, Vec dst) {
    return dst[0] >= src[0] && dst[1] >= src[1];
  }

  template<typename T, typename Alloc>
  RectPacker2D<T, Alloc>::RectPacker2D(Vec bin_size, Alloc const& alloc)
    : free_rects_(alloc) {
    free_rects_.emplace_back(FreeRect{ { { T(0), T(0) } }, bin_size });
  }

  template<typename T, typename Alloc>
  template<typename RECT_SCORER>
  typename RectPacker2D<T, Alloc>::Result RectPacker2D<T, Alloc>::pack(Vec rect, RECT_SCORER scorer) {
    const T non_fit_score = std::numeric_limits<T>::max();

    Vec flipped_rect = { { rect[1], rect[0] } };

    // 1. Identify where we will store the rect.
    // Lower scores are better.
    T best_score = non_fit_score;
    auto best_rect = free_rects_.end();
    bool flip = false;

    for (auto ite = free_rects_.begin(); ite != free_rects_.end(); ++ite) {
      // Test for perfect fit
      if (rect == ite->size) {
        best_rect = ite;
        flip = false;
        break;
      }

      if (flipped_rect == ite->size) {
        best_rect = ite;
        flip = true;
        break;
      }

      T score = fits(rect, ite->size) ? scorer(rect, ite->size) : non_fit_score;
      T flipped_score = fits(flipped_rect, ite->size) ? scorer(flipped_rect, ite->size) : non_fit_score;

      if (score < best_score) {
        best_rect = ite;
        best_score = score;
        flip = false;
      }

      if (flipped_score < best_score) {
        best_rect = ite;
        best_score = score;
        flip = true;
      }
    }

    // If we failed to find a suitable rect.
    if (best_rect == free_rects_.end()) {
      return Result{
        {{ T(0), T(0) }},
        {{ T(0) ,T(0) }}
      };
    }

    if (flip) {
      std::swap(rect[0], rect[1]);
    }

    //3. remove the chosen rect
    FreeRect destination = *best_rect;

    auto last = std::prev(free_rects_.end());
    if (last != best_rect) {
      *best_rect = std::move(*last);
    }
    free_rects_.pop_back();

    // Insert the remainders
    const T rem_w = destination.size[0] - rect[0];
    const T rem_h = destination.size[1] - rect[1];
    if (rem_h == T(0)) {
      if (rem_w > (0)) {
        free_rects_.emplace_back(FreeRect{
          {{ destination.pos[0] + rect[0], destination.pos[1] }},
          {{ rem_w, rect[1] }}
        });
      }
    }
    else if (rem_w == T(0)) {
      //rem_h is implicitly > 0
      free_rects_.emplace_back(FreeRect{
        {{ destination.pos[0], destination.pos[1] + rect[1] }},
        {{ rect[0], rem_h }} 
      });
    }
    else {
      //rem_h > 0 and rem_w > 0
      bool horiz_split = rem_w < rem_h;
      if (horiz_split) {
        free_rects_.emplace_back(FreeRect{
          {{ destination.pos[0] + rect[0], destination.pos[1] }},
          {{ rem_w, rect[1] }}
        });

        free_rects_.emplace_back(FreeRect{
          {{ destination.pos[0], destination.pos[1] + rect[1] }},
          {{ destination.size[0], rem_h }}
        });
      }
      else {
        //vertical split
        free_rects_.emplace_back(FreeRect{
          {{ destination.pos[0], destination.pos[1] + rect[1] }},
          {{ rect[0], rem_h }}
        });

        free_rects_.emplace_back(FreeRect{
          {{ destination.pos[0] + rect[0], destination.pos[1] }},
          {{ rem_w, destination.size[1] }}
        });
      }
    }

    return Result{
      {{ destination.pos[0], destination.pos[1] }},
      {{ rect[0], rect[1] }}
    };
  }
}
#endif

non-trivial usage example:

#include <random>
#include <functional>
#include <iostream>
#include <algorithm>

int main() {
  using packer_t = slt::RectPacker2D<int>;
  packer_t packer( {{80, std::numeric_limits<int>::max() }});

  std::random_device r;
  std::default_random_engine e1(r());
  std::uniform_int_distribution<int> uniform_dist(1, 10);

  std::vector<std::vector<char>> result;

  std::vector<packer_t::RectSize> data;
  for (int i = 0; i < 26; ++i) {
    int w = uniform_dist(e1);
    int h = uniform_dist(e1);

    data.emplace_back(packer_t::RectSize{{ w, h}});
  }

  std::sort(data.begin(), data.end(), std::greater<packer_t::RectSize>());

  char c = 'A';
  for (auto const & d : data) {
    auto packed = packer.pack(d);

    for (int i = packed.pos[0]; i < packed.pos[0] + packed.size[0]; ++i) {
      for (int j = packed.pos[1]; j < packed.pos[1] + packed.size[1]; ++j) {
        if ((int)result.size() < j + 1) {
          result.resize(j+1, std::vector<char>(80, ' '));
        }
        result[j][i] = c;
      }
    }
    ++c;
  }

  for(auto const & l : result) {
    std::cout << '|';
    for (auto const & ch : l) {
      std::cout << ch;
    }
    std::cout << "|\n";
  }
  return 0;
}

Which produces something like:

|AAAAAAAAABBBBBBBBBBCCCCCCCCCCEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJLLLLLNNNNPPPPPPPPP  |
|AAAAAAAAABBBBBBBBBBCCCCCCCCCCEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJLLLLLNNNNPPPPPPPPP  |
|AAAAAAAAABBBBBBBBBBCCCCCCCCCCEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJLLLLLNNNNPPPPPPPPP  |
|AAAAAAAAABBBBBBBBBBCCCCCCCCCCEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJLLLLLNNNNSSSSWW     |
|AAAAAAAAABBBBBBBBBBCCCCCCCCCCEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJMMMMZOOVVSSSSWW     |
|AAAAAAAAABBBBBBBBBBFFFFFFFFFYEEEEEEEEEHHHHHHHHIIIIIIIJJJJJJJMMMMZOOVVSSSSWW     |
|AAAAAAAAABBBBBBBBBBFFFFFFFFFYGGGGGGGG HHHHHHHHIIIIIIIKKKKKKKMMMMZOOVVTTT WW     |
|AAAAAAAAADDDDDDDDDDFFFFFFFFFYGGGGGGGG QQQQQQQQRRRRR  KKKKKKKMMMMZOOVVTTT        |
|AAAAAAAAADDDDDDDDDDFFFFFFFFFY         QQQQQQQQRRRRR  KKKKKKKMMMMZ  VVTTT        |
|AAAAAAAAA          FFFFFFFFFY         QQQQQQQQRRRRR  KKKKKKK       VV           |
|UUXXXXXXXX                                                                      |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |
|UU                                                                              |

Things I am on the fence about:

  • std::array: I can easiliy move to N-dimensions in the future, but the abundance of braces is kinda nuts.
  • rebinding a char allocator felt like the right way to handle a vector of an externally inacessible type, but I am really not familiar with that scenario, so there might be a better pattern I'm overlooking.
  • The scoring function might be better as a class parameter. On one hand, it's highly unlikely that anyone would want to reuse the same packer with different heuristics, on the other hand, this class is meant to be long-lived in memory, so I'm reluctant to adding another potentially stateful member.
  • I keep going back and forth with putting a flipped bool in the result instead of the size. The only reason I'm not doing it is that size == {0,0} is my packing failure signal. maybe returning an optional<Result> might be better? Throwing an exception is out of the question as I have code paths that are written in a way to expect an eventual failure as part of the main flow (pack until full).
\$\endgroup\$
  • 1
    \$\begingroup\$ The use allocator<char> looks strange, what do you hope to archive with it? \$\endgroup\$ – Surt Nov 4 '17 at 15:20
  • \$\begingroup\$ @Surt allow users to provide custom allocators without having to expose FreeRect as a public member. allocator<char> is just a default value that gets rebound to allocator<FreeRect> \$\endgroup\$ – Frank Nov 4 '17 at 15:22
3
\$\begingroup\$

The first thing I would like to mention is that I was unable to compile given code. And compilation fails not because of some fancy problem, but because RectSize declaration or something else is clearly missing from the code.

  • Naming is rather inconsistent and not as informative as it could be. For example 3 completely different naming for template parameters at one spot. T might be ok for some container that does not care about type of items being stored, but in this case you could've used something more obvious such as Distance. ALLCAPS names should be used for macros:
template<typename T, typename Alloc>
template<typename RECT_SCORER>
  • Declaring functions inside of template class as inline and then defining them right away in the same file seems to be redundant.
  • It seems that many braces are redundant and can be safely omitted, for example:
data.emplace_back(packer_t::RectSize{{ w, h}});
// can be simplified to
data.emplace_back(packer_t::RectSize{ w, h});
// or even to
data.emplace_back(w, h);
  • RectPacker2D<T, Alloc>::pack function body is rather large, probably it could be splitted into smaller parts.
  • Repetitive parts at the end of pack function probably could be simplified to use indexing from some lookup table instead of manually copypasting emplace_back bodies with slightly different indexes:
free_rects_.emplace_back(FreeRect{
    {{ destination.pos[0] + rect[0], destination.pos[1] }},
    {{ rem_w, rect[1] }}
});
\$\endgroup\$
  • \$\begingroup\$ Oops, the example is out of sync with the library, RectSize should be Vec, obviously. Thanks for the feedback! \$\endgroup\$ – Frank Nov 4 '17 at 14:37
  • \$\begingroup\$ I disagree on two points: 1. Implementing code outside of the template makes the top of the file act as effective documentation with less clutter. It's the same as using a .inl file 2. The braces are needed according to clang (omitting them raises warnings) \$\endgroup\$ – Frank Nov 4 '17 at 14:40
  • \$\begingroup\$ @Frank, I've been suppressing the warning about braces for about a year, I believe. Nothing bad happened yet, at least not something I know of. \$\endgroup\$ – Incomputable Nov 4 '17 at 14:53
  • \$\begingroup\$ @Incomputable I can't possibly require users of the library to suppress these warnings, and I don't want to put #pragmas in there unless absolutely necessary. \$\endgroup\$ – Frank Nov 4 '17 at 14:57
  • \$\begingroup\$ @Frank, may be this is a special case, but it seems like people are already annoyed by it. Also, gcc doesn't even enable it. \$\endgroup\$ – Incomputable Nov 4 '17 at 15:00
0
\$\begingroup\$

The 2 structs

struct Result { 
  Vec pos; 
  Vec size; 
};

and

struct FreeRect {
  Vec pos;
  Vec size;
};

looks very similar so you can bleed the Result type out and use that as the default allocator type.

template<typename T, typename Alloc = std::allocator<Result>>
class RectPacker2D

Even if you have to expose Result more.

\$\endgroup\$
  • \$\begingroup\$ That's making a big assumption about the fact that the implementation won't change. In fact, I'm already experimenting with a better algorithm that's adding new members to FreeRect. If I relied on the fact these two struct stayed the same I wouldn't be able to do that without requiring agressive upstream refactoring. \$\endgroup\$ – Frank Nov 4 '17 at 15:56
  • \$\begingroup\$ A better alternative would have been to simply use std::allocator<> as the default value, but that's getting deprecated in C++17. \$\endgroup\$ – Frank Nov 4 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.