/************************************************************************************/ /**
// Copyright (c) 2006-2024 Advanced Micro Devices, Inc. All rights reserved.
/// \author AMD Developer Tools Team
/// \file
****************************************************************************************/
#ifndef _JRT_HEURISTIC_KD_TREE_BUILDER_H_
#define _JRT_HEURISTIC_KD_TREE_BUILDER_H_

#include "jrtkdtreebuilder.h"
#include "jrtboundingbox.h"
#include "jrtcoreutils.h"

/// \brief A smart KD tree builder which uses the surface area heuristic
/// Most of the inspiration for this code comes from Havran's PhD thesis
class JRTHeuristicKDTreeBuilder : public JRTKDTreeBuilder
{
public:
    struct TriangleBB
    {
        const JRTTriangle* pTri;
        UINT               nIndex;
        JRTBoundingBox     box;

        // state flag used to classify this BB with respect to current partitioning plane
        mutable TriPlaneState planeState;
    };

    struct Split
    {
        float    value;
        unsigned bMaxSplit : 1;
        unsigned nTriBB : 31;

        //bool bMaxSplit; /// Is this a max split (end of BB) or a min split (beginning of BB)
        //const TriangleBB* pTriBB;
    };

    typedef std::vector<Split*> SplitVec;

protected:
    virtual void BuildTreeImpl(const JRTBoundingBox&                  rBounds,
                               const std::vector<const JRTTriangle*>& rTris,
                               std::vector<JRTKDNode>&                rNodesOut,
                               std::vector<UINT>&                     rTriIndicesOut);

private:
    /* void BuildTreeRecursive( UINT nDepth,
                              const JRTBoundingBox& rNodeBounds,
                              const std::vector<TriangleBB*> rBBs[3],
                              JRTKDNode* pNode,
                              std::vector<JRTKDNode>& rNodesOut,
                              std::vector<UINT>& rTriIndicesOut );*/

    void ExtractSplits(UINT eAxis, const std::vector<TriangleBB>& rBBs, std::vector<Split>& rSplits, const JRTBoundingBox& rSceneBounds);

    void ClassifyBBs(SplitVec& rSplits, std::vector<TriangleBB>& rBBs, UINT eAxis, float fValue);

    void LocateBestSplit(float                 fNodeBBInvArea,
                         const JRTBoundingBox& rNodeBounds,
                         const SplitVec        splits[3],
                         UINT                  eAxis,
                         UINT                  nTriCount,
                         float&                fBestCost,
                         bool&                 bSplit,
                         UINT&                 eSplitAxis,
                         float&                fSplitValue);

    void BuildTreeRecursive(UINT                      nDepth,
                            const JRTBoundingBox&     rNodeBounds,
                            SplitVec                  splits[3],
                            std::vector<TriangleBB*>& rBBsThisNode,
                            JRTKDNode*                pNode,
                            std::vector<JRTKDNode>&   rNodesOut,
                            std::vector<UINT>&        rTriIndicesOut);

    JRTBoundingBox m_scene_bounds;

    std::vector<TriangleBB> m_bbs;
};

#endif