/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License version 2
 *   as published by the Free Software Foundation.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 *   Copyright (C) 2007  Benjamin Segovia <bsegovia@liris.cnrs.fr>
 */

#include "rt_bvh.h"
#include "bvhlib_internal.h"
#include "float.h" // FLT_MAX
#include <algorithm> // std::sort
#include <functional> // std::binary_function
#include <vector>

namespace bvhlib {
    /* Helper functor to sort centroid, just template the axis to perform the
     * three sorts
     */
    template<uint32_t axis>
    struct sorter_t : public std::binary_function<int, int, bool> {
        const std::vector<centroid_t> &centroids;
        sorter_t(const std::vector<centroid_t> &c) : centroids(c) {}
        FINLINE int operator() (const uint32_t a, const uint32_t b) const  {
            return centroids[a][axis] <  centroids[b][axis];
        }
    };

    /* This is the initialization of bvhlib::compiler_t. It computes the
     * centroids of triangles and sort the triangles according to the centroids
     * for each axis.
     */
    int compiler_t::injection(
        const triangle_t * const __restrict soup,
        const uint32_t tri_n, bvh::descriptor_t &fat) {
        std::vector<centroid_t> centroids;

        /* Allocate nodes and leaves for the BVH */
        root = (bvh::node_t *) new bvh::node_t [2 * tri_n + 1];
        if (root == 0) {
            return -1;
        }

        /* Allocate the data for the compiler. As it is simpler than kd-tree
         * construction, there is only one allocation
         */
        for(int i = 0; i < 3; ++i) {
            ids[i].resize(tri_n);
            if(ids[i].size() < tri_n)
                return -1;
        }
        pos.resize(tri_n);
        tmp_ids.resize(tri_n);
        centroids.resize(tri_n);
        aabbs.resize(tri_n);
        rl_aabbs.resize(tri_n);
        if(centroids.size() < tri_n || aabbs.size() < tri_n
        || rl_aabbs.size() < tri_n  || pos.size() < tri_n
        || tmp_ids.size() < tri_n)
            return -1;
        n = tri_n;

        /* We compute the centroids and the bounding boxen */
        scene_aabb = aabb_t(FLT_MAX, -FLT_MAX);
        for(int j = 0; j < n; ++j) {
            centroids[j] = centroid_t(soup[j]);
            aabbs[j] = soup[j].get_aabb();
            scene_aabb.compose(aabbs[j]);
        }

        /* We sort the centroid in order to have a total (and arbitrary)
         * order on the triangles
         */
        for(int i = 0; i < 3; ++i)
            for(int j = 0; j < n; ++j)
                ids[i][j] = j;
        std::sort(ids[0].begin(), ids[0].end(), sorter_t<0>(centroids));
        std::sort(ids[1].begin(), ids[1].end(), sorter_t<1>(centroids));
        std::sort(ids[2].begin(), ids[2].end(), sorter_t<2>(centroids));

        return n;
    }
}

