bsp_tree.hh

Go to the documentation of this file.

#ifndef VTESTBED_GEOMETRY_BSP_TREE_HH
#define VTESTBED_GEOMETRY_BSP_TREE_HH

#include <iosfwd>
#include <iterator>
#include <memory>
#include <queue>
#include <vector>

#include <vtestbed/base/view.hh>
#include <vtestbed/geometry/plane.hh>
#include <vtestbed/geometry/polygon.hh>
#include <vtestbed/geometry/triangle.hh>

namespace vtb {

    namespace geometry {

        template <class T>
        class BSP_node_iterator {

        public:
            using value_type = T;
            using difference_type = std::ptrdiff_t;
            using size_type = std::size_t;
            using pointer = value_type*;
            using const_pointer = const value_type*;
            using reference = value_type&;
            using const_reference = const value_type&;
            using iterator_category = std::forward_iterator_tag;

        private:
            std::queue<pointer> _queue;
            pointer _ptr = nullptr;

        public:

            inline explicit
            BSP_node_iterator(value_type& tree) {
                if (!tree.empty()) { this->_queue.push(&tree); }
                this->_ptr = this->current_node();
            }

            BSP_node_iterator() = default;
            BSP_node_iterator(const BSP_node_iterator&) = default;
            BSP_node_iterator(BSP_node_iterator&&) = default;
            BSP_node_iterator& operator=(const BSP_node_iterator&) = default;
            BSP_node_iterator& operator=(BSP_node_iterator&&) = default;

            inline bool
            operator==(const BSP_node_iterator& rhs) {
                return this->_queue == rhs._queue;
            }

            inline bool
            operator!=(const BSP_node_iterator& rhs) {
                return !this->operator==(rhs);
            }

            inline pointer operator->() { return this->_ptr; }
            inline const_pointer operator->() const { return this->_ptr; }
            inline reference operator*() { return *this->_ptr; }
            inline const_reference operator*() const { return *this->_ptr; }

            inline const_reference
            operator++() {
                auto& q = this->_queue;
                auto& t = *q.front();
                if (t.front()) { q.push(t.front().get()); }
                if (t.back()) { q.push(t.back().get()); }
                q.pop();
                this->_ptr = q.empty() ? nullptr : this->current_node();
                return *this->_ptr;
            }

            inline BSP_node_iterator
            operator++(int) {
                BSP_node_iterator tmp(*this);
                this->operator++();
                return *tmp;
            }

        private:

            inline const_pointer
            current_node() const
            { return this->_queue.front(); }

            inline pointer
            current_node()
            { return this->_queue.front(); }

        };


        template <class T, int N>
        struct BSP_traits;

        template <class T>
        struct BSP_traits<T,3> {
            using value_type = Triangle<T,3>;
        };

        template <class T>
        struct BSP_traits<T,2> {
            using value_type = Line_segment<T,2>;
        };

        template <class T, int N>
        class BSP_tree {

        public:
            using scalar_type = T;
            static constexpr const int dimensions = N;
            using traits_type = BSP_traits<T,N>;
            using value_type = typename traits_type::value_type;
            using plane_type = Plane<T,N>;
            using pointer = std::unique_ptr<BSP_tree<T,N>>;
            using reference = pointer&;
            using const_reference = const pointer&;
            using polygon_array = std::vector<value_type>;
            using node_iterator = BSP_node_iterator<BSP_tree<T,N>>;
            using node_const_iterator = BSP_node_iterator<const BSP_tree<T,N>>;
            using node_view = vtb::base::view<node_iterator>;
            using node_const_view = vtb::base::view<node_const_iterator>;

        private:
            using raw_pointer = BSP_tree<T,N>*;
            using raw_const_pointer = const BSP_tree<T,N>*;
            struct Polygon_and_plane {
                plane_type plane;
                value_type polygon;
                inline
                Polygon_and_plane(const plane_type& plane, const value_type& polygon):
                plane(plane), polygon(polygon) {}
            };
            using pair_array = std::vector<Polygon_and_plane>;

        private:
            polygon_array _polygons;
            plane_type _plane;
            pointer _front;
            pointer _back;
            T _epsilon{1e-3};

        public:

            inline explicit
            BSP_tree(const plane_type& plane, T eps):
            _plane(plane), _epsilon(eps) {}

            inline explicit
            BSP_tree(const plane_type& plane, T eps, polygon_array&& polygons):
            _plane(plane), _epsilon(eps) {
                this->insert(std::forward<polygon_array>(polygons));
            }

            inline explicit
            BSP_tree(polygon_array&& polygons, T eps): _epsilon(eps) {
                this->insert(std::forward<polygon_array>(polygons));
            }

            BSP_tree() = default;
            BSP_tree(BSP_tree&&) = default;
            BSP_tree& operator=(BSP_tree&&) = default;
            inline BSP_tree(const BSP_tree& rhs) { this->deep_copy(rhs); }
            inline BSP_tree& operator=(const BSP_tree& rhs)
            { this->clear(); this->deep_copy(rhs); return *this; }
            inline ~BSP_tree() { this->clear_nodes(); }

            void insert(polygon_array&& new_polygons);
            void insert(BSP_tree&& rhs);
            void clear();
            void invert();
            size_t subtract(const BSP_tree& rhs);
            void sort();

            inline bool
            has_plane() const {
                return !all(plane().normal() == T{});
            }

            inline const plane_type plane() const { return this->_plane; }
            inline const_reference front() const { return this->_front; }
            inline const_reference back() const { return this->_back; }

            inline const polygon_array&
            polygons() const {
                return this->_polygons;
            }

            inline const value_type&
            polygon(size_t i) const {
                return this->_polygons[i];
            }

            inline node_view
            nodes() {
                return node_view{node_iterator(*this), node_iterator()};
            }

            inline node_const_view
            nodes() const {
                return node_const_view{
                    node_const_iterator(*this),
                    node_const_iterator()
                };
            }

            bool empty() const;
            inline scalar_type accuracy() const { return this->_epsilon; }
            void accuracy(scalar_type rhs);
            void dot(std::ostream& out) const;
            void simplify();

        private:

            void insert(pair_array&& pairs);

            inline void
            shallow_copy(const BSP_tree& rhs) {
                this->_polygons = rhs._polygons;
                this->_plane = rhs._plane;
            }

            void
            deep_copy(const BSP_tree& rhs);

            void
            clear_nodes();

            // remove polygons that this tree contains
            void
            clip(polygon_array& polygons, const plane_type& plane) const;

            static inline raw_pointer
            get_pointer(reference ptr) {
                if (!ptr) { ptr.reset(new BSP_tree<T,N>); } return ptr.get();
            }

            inline raw_pointer get_front()
            { return get_pointer(this->_front); }
            inline raw_pointer get_back()
            { return get_pointer(this->_back); }

            static inline void
            remove_empty(reference ptr) {
                if (ptr && ptr->empty()) { ptr.reset(); }
            }

            inline void
            update_accuracy(T eps) {
                if (eps < this->_epsilon) { this->_epsilon = eps; }
            }

        };

        template <class T, int N>
        inline BSP_tree<T,N>
        set_union(const BSP_tree<T,N>& lhs, const BSP_tree<T,N>& rhs) {
            BSP_tree<T,N> a(lhs), b(rhs);
            a.subtract(rhs);
            auto n = b.subtract(lhs);
            if (n > 0) {
                b.invert();
                b.subtract(a);
                b.invert();
                a.insert(std::move(b));
            }
            a.sort();
            return a;
        }

        template <class T, int N>
        inline BSP_tree<T,N>
        set_difference(const BSP_tree<T,N>& lhs, const BSP_tree<T,N>& rhs) {
            BSP_tree<T,N> a(lhs), b(rhs);
            a.invert();
            a.subtract(b);
            b.subtract(a);
            b.invert();
            b.subtract(a);
            b.invert();
            a.insert(std::move(b));
            a.invert();
            a.sort();
            return a;
        }

        template <class T, int N>
        inline BSP_tree<T,N>
        set_intersection(const BSP_tree<T,N>& lhs, const BSP_tree<T,N>& rhs) {
            BSP_tree<T,N> a(lhs), b(rhs);
            a.invert();
            b.subtract(a);
            b.invert();
            a.subtract(b);
            b.subtract(a);
            a.insert(std::move(b));
            a.invert();
            a.sort();
            return a;
        }

    }

}

#endif // vim:filetype=cpp