#ifndef _KdTree_H__ #define _KdTree_H__ #include using namespace std; #include "Containers.h" #include "AxisAlignedBox3.h" #include "Ray.h" #include "Pvs.h" #include "Viewcell.h" #include "VssRay.h" #include "IntersectableWrapper.h" namespace GtpVisibilityPreprocessor { class KdNode; class KdLeaf; class KdInterior; class Intersectable; class Beam; class KdTree; // KdTree *SceneKdTree; // -------------------------------------------------------------- // Static statistics for kd-tree search // -------------------------------------------------------------- class KdTreeStatistics { public: // total number of nodes int nodes; // number of splits along each of the axes int splits[7]; // totals number of rays int rays; // total number of query domains int queryDomains; // total number of ray references int rayRefs; // refs in non empty leafs int rayRefsNonZeroQuery; // total number of query references int objectRefs; // nodes with zero queries int zeroQueryNodes; // max depth nodes int maxDepthNodes; // max depth nodes int minCostNodes; // max number of rays per node int maxObjectRefs; // number of dynamically added ray refs int addedRayRefs; // number of dynamically removed ray refs int removedRayRefs; // Constructor KdTreeStatistics() { Reset(); } int Nodes() const {return nodes;} int Interior() const { return nodes / 2; } int Leaves() const { return (nodes / 2) + 1; } void Reset() { nodes = 0; for (int i=0; i<7; i++) splits[i] = 0; rays = queryDomains = 0; rayRefs = rayRefsNonZeroQuery = objectRefs = 0; zeroQueryNodes = 0; maxDepthNodes = 0; minCostNodes = 0; maxObjectRefs = 0; addedRayRefs = removedRayRefs = 0; } void Print(ostream &app) const; friend ostream &operator<<(ostream &s, const KdTreeStatistics &stat) { stat.Print(s); return s; } }; class KdInterior; /** Abstract class for kd-tree node */ class KdNode { public: static int sMailId; static int sReservedMailboxes; int mMailbox; KdIntersectable *mIntersectable; void Mail() { mMailbox = sMailId; } //static void NewMail() { sMailId ++; } bool Mailed() const { return mMailbox == sMailId; } static void NewMail(const int reserve = 1) { sMailId += sReservedMailboxes; sReservedMailboxes = reserve; } void Mail(const int mailbox) { mMailbox = sMailId + mailbox; } bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; } virtual ~KdNode(){}; KdNode(KdInterior *parent); /** Determines whether this node is a leaf or interior node @return true if leaf */ virtual bool IsLeaf() const = 0; /** Determines whether this node is the root of the tree @return true if root */ virtual bool IsRoot() const { return mParent == NULL; } /** Parent of the node - the parent is a little overhead for maintanance of the tree, but allows various optimizations of tree traversal algorithms */ KdInterior *mParent; short mDepth; short mPvsTermination; }; /** Implementation of the kd-tree interior node */ class KdInterior : public KdNode { public: KdInterior(KdInterior *parent):KdNode(parent), mBack(NULL), mFront(NULL) {} ~KdInterior(); /** \sa KdNode::IsLeaf() */ virtual bool IsLeaf() const { return false; } /** splitting axis */ int mAxis; /** splitting position, absolute position within the bounding box of this node */ float mPosition; /** bounding box of interior node */ AxisAlignedBox3 mBox; /** back node */ KdNode *mBack; /** front node */ KdNode *mFront; void SetupChildLinks(KdNode *b, KdNode *f) { mBack = b; mFront = f; b->mParent = f->mParent = this; } void ReplaceChildLink(KdNode *oldChild, KdNode *newChild) { if (mBack == oldChild) mBack = newChild; else mFront = newChild; } }; class SubdivisionCandidate; /** Implementation of the kd-tree leaf node */ class KdLeaf : public KdNode { public: KdLeaf(KdInterior *parent, const int objects): KdNode(parent), mViewCell(NULL) { mObjects.reserve(objects); } void AddPassingRay(const Ray &ray, const int contributions) { mPassingRays.AddRay(ray, contributions); // Debug << "adding passing ray" << endl; } ~KdLeaf(); void AddPassingRay2(const Ray &ray, const int objects, const int viewcells ) { mPassingRays.AddRay2(ray, objects, viewcells); // Debug << "adding passing ray" << endl; } /** \sa KdNode::IsLeaf() */ virtual bool IsLeaf() const { return true; } /** pointers to occluders contained in this node */ ObjectContainer mObjects; /** Ray set description of the rays passing through this node */ PassingRaySet mPassingRays; /** PVS consisting of visible KdTree nodes */ KdPvs mKdPvs; /// pvs of view cells seeing this node. SubdivisionCandidate *mSubdivisionCandidate; /// pointer to view cell. KdViewCell *mViewCell; VssRayContainer mVssRays; /// Objects that are referenced in more than one leaf. ObjectContainer mMultipleObjects; /// universal counter int mCounter; }; /** KdTree for indexing scene entities - occluders/occludees/viewcells */ class KdTree { protected: struct TraversalData { KdNode *mNode; AxisAlignedBox3 mBox; int mDepth; float mPriority; TraversalData() {} TraversalData(KdNode *n, const float p): mNode(n), mPriority(p) {} TraversalData(KdNode *n, const AxisAlignedBox3 &b, const int d): mNode(n), mBox(b), mDepth(d) {} bool operator<( const TraversalData &b) const { KdLeaf *leafa = (KdLeaf *) mNode; KdLeaf *leafb = (KdLeaf *) b.mNode; return leafa->mObjects.size()*mBox.SurfaceArea() < leafb->mObjects.size()*b.mBox.SurfaceArea(); } // comparator for the struct less_priority : public binary_function { bool operator()(const TraversalData a, const TraversalData b) { return a.mPriority < b.mPriority; } }; }; public: enum {SPLIT_OBJECT_MEDIAN, SPLIT_SPATIAL_MEDIAN, SPLIT_SAH}; KdTree(); ~KdTree(); /** Insert view cell into the tree */ virtual void InsertViewCell(ViewCell *viewCell) { // mRoot->mViewcells.push_back(viewCell); } virtual bool Construct(); /** Check whether subdivision criteria are met for the given subtree. If not subdivide the leafs of the subtree. The criteria are specified in the environment as well as the subdivision method. By default surface area heuristics is used. @param subtree root of the subtree @return true if subdivision was performed, false if subdivision criteria were already met */ virtual KdNode *Subdivide(const TraversalData &tdata); /** Get the root of the tree */ KdNode *GetRoot() const { return mRoot; } AxisAlignedBox3 GetBox() const { return mBox; } int CastRay( Ray &ray ); int CastBeam( Beam &beam ); /** Casts line segment into tree. @returns intersected view cells. */ int CastLineSegment(const Vector3 &origin, const Vector3 &termination, vector &viewcells); const KdTreeStatistics &GetStatistics() const { return mStat; } /** Returns or creates a new intersectable for use in a kd based pvs. The OspTree is responsible for destruction of the intersectable. */ KdIntersectable *GetOrCreateKdIntersectable(KdNode *node); void SetPvsTerminationNodes( const float maxArea); KdNode * GetPvsNode(const Vector3 &point) const; void CollectKdObjects(const AxisAlignedBox3 &box, ObjectContainer &objects ); void CollectObjects(KdNode *n, ObjectContainer &objects); void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects); void CollectLeaves(vector &leaves); /** If the kd tree is used as view cell container, this methods creates the view cells. @returns the newly created view cells in a view cell container */ void CreateAndCollectViewCells(ViewCellContainer &viewCells) const; AxisAlignedBox3 GetBox(const KdNode *node) const { KdInterior *parent = node->mParent; if (parent == NULL) return mBox; if (!node->IsLeaf()) return ((KdInterior *)node)->mBox; AxisAlignedBox3 box(parent->mBox); if (parent->mFront == node) box.SetMin(parent->mAxis, parent->mPosition); else box.SetMax(parent->mAxis, parent->mPosition); return box; } float GetSurfaceArea(const KdNode *node) const { return GetBox(node).SurfaceArea(); } KdNode * FindRandomNeighbor(KdNode *n, bool onlyUnmailed ); KdNode * KdTree::GetRandomLeaf(const Plane3 &halfspace); KdNode * GetRandomLeaf(const bool onlyUnmailed = false); KdNode * GetNode(const Vector3 &point, const float maxArea) const; void GetBoxIntersections(const AxisAlignedBox3 &box, vector &leaves); int FindNeighbors(KdNode *n, vector &neighbors, bool onlyUnmailed ); int CollectLeafPvs(); bool ExportBinTree(const string &filename); bool LoadBinTree(const string &filename, ObjectContainer &object); protected: struct RayData { // pointer to the actual ray Ray *ray; // endpoints - do we need them? #if USE_FIXEDPOINT_T short tmin, tmax; #else float tmin, tmax; #endif RayData():ray(NULL) {} RayData(Ray *r):ray(r), tmin(0), #if USE_FIXEDPOINT_T #define FIXEDPOINT_ONE 0x7FFE // tmax(0xFFFF) tmax(FIXEDPOINT_ONE) #else tmax(1.0f) #endif {} RayData(Ray *r, const float _min, const float _max ):ray(r) { SetTMin(_min); SetTMax(_max); } RayData(Ray *r, const short _min, const float _max ):ray(r), tmin(_min) { SetTMax(_max); } RayData(Ray *r, const float _min, const short _max ):ray(r), tmax(_max) { SetTMin(_min); } friend bool operator<(const RayData &a, const RayData &b) { return a.ray < b.ray; } float ExtrapOrigin(const int axis) const { return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis); } float ExtrapTermination(const int axis) const { return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis); } #if USE_FIXEDPOINT_T float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); } float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); } void SetTMin (const float t) { tmin = (short) (t*(float)(FIXEDPOINT_ONE)); } void SetTMax (const float t) { tmax = (short) (t*(float)(FIXEDPOINT_ONE)); tmax++; // if (tmax!=0xFFFF) // tmax++; } #else float GetTMin () const { return tmin; } float GetTMax () const { return tmax; } void SetTMin (const float t) { tmin = t; } void SetTMax (const float t) { tmax = t; } #endif }; struct RayTraversalData { KdNode *mNode; Vector3 mExitPoint; float mMaxT; RayTraversalData() {} RayTraversalData(KdNode *n, const Vector3 &p, const float maxt): mNode(n), mExitPoint(p), mMaxT(maxt) {} }; // -------------------------------------------------------------- // For sorting objects // -------------------------------------------------------------- struct SortableEntry { enum { BOX_MIN, BOX_MAX }; int type; float value; Intersectable *intersectable; SortableEntry() {} SortableEntry(const int t, const float v, Intersectable *i):type(t), value(v), intersectable(i) {} bool operator<(const SortableEntry &b) const { return value < b.value; } }; inline static bool iltS(SortableEntry *a, SortableEntry *b) { return a->value < b->value; } // reusable array of split candidates vector *splitCandidates; float BestCostRatio( KdLeaf *node, const AxisAlignedBox3 &box, const int axis, float &position, int &objectsBack, int &objectsFront ); void SortSubdivisionCandidates( KdLeaf *node, const int axis ); void EvaluateLeafStats(const TraversalData &data); KdNode * SubdivideNode( KdLeaf *leaf, const AxisAlignedBox3 &box, AxisAlignedBox3 &backBBox, AxisAlignedBox3 &frontBBox ); bool TerminationCriteriaMet(const KdLeaf *leaf); int SelectPlane(KdLeaf *leaf, const AxisAlignedBox3 &box, float &position ); /** does some post processing on the objects in the new child leaves. */ void ProcessMultipleRefs(KdLeaf *leaf) const; void ExportBinLeaf(OUT_STREAM &stream, KdLeaf *leaf); void ExportBinInterior(OUT_STREAM &stream, KdInterior *interior); KdLeaf *ImportBinLeaf(IN_STREAM &stream, KdInterior *parent, const ObjectContainer &objects); KdInterior *ImportBinInterior(IN_STREAM &stream, KdInterior *parent); KdNode *LoadNextNode(IN_STREAM &stream, KdInterior *parent, const ObjectContainer &objects); /** Adds this objects to the kd leaf objects. @warning: Can corrupt the tree */ void InsertObjects(KdNode *node, const ObjectContainer &objects); int mTermMaxNodes; float mSplitBorder; int mTermMaxDepth; int mTermMinCost; float mMaxCostRatio; float mCt_div_ci; int mSplitMethod; bool mSahUseFaces; /// root of the tree KdNode *mRoot; /// bounding box of the tree root AxisAlignedBox3 mBox; KdTreeStatistics mStat; public: /// stores the kd node intersectables used for pvs vector mKdIntersectables; }; } #endif