bvh/v2/stack.h

0001 #ifndef BVH_V2_STACK_H
0002 #define BVH_V2_STACK_H
0003
0004 #include <vector>
0005 #include <cassert>
0006
0007 namespace bvh::v2 {
0008
0009 /// Fixed-size stack that can be used for a BVH traversal.
0010 template <typename T, unsigned Capacity>
0011 struct SmallStack {
0012     static constexpr unsigned capacity = Capacity;
0013
0014     T elems[capacity];
0015     unsigned size = 0;
0016
0017     bool is_empty() const { return size == 0; }
0018     bool is_full() const { return size >= capacity; }
0019
0020     void push(const T& t) {
0021         assert(!is_full());
0022         elems[size++] = t;
0023     }
0024
0025     T pop() {
0026         assert(!is_empty());
0027         return elems[--size];
0028     }
0029 };
0030
0031 /// Growing stack that can be used for BVH traversal. Its performance may be lower than a small,
0032 /// fixed-size stack, depending on the architecture.
0033 template <typename T>
0034 struct GrowingStack {
0035     std::vector<T> elems;
0036
0037     bool is_empty() const { return elems.empty(); }
0038     void push(const T& t) { elems.push_back(t); }
0039
0040     T pop() {
0041         assert(!is_empty());
0042         auto top = std::move(elems.back());
0043         elems.pop_back();
0044         return top;
0045     }
0046
0047     void clear() {
0048       elems.clear();
0049     }
0050 };
0051
0052 } // namespace bvh::v2
0053
0054 #endif