00001 //---------------------------------------------------------------------------------
00002 // File Name: AABBTree.h
00003 // Description: Axis Aligned Bounding Box Tree
00004 //
00005 // Copyright (C) 2004 - 2006 True Axis Pty Ltd, Australia. 
00006 // All Rights Reserved.
00007 //
00008 // History:
00009 //      Created File.
00010 //---------------------------------------------------------------------------------
00011 
00012 #ifndef TA_AABBTREE_H
00013 #define TA_AABBTREE_H
00014 
00015 #ifndef TA_AABB_H
00016 #include "AABB.h"
00017 #endif // TA_AABB_H
00018 
00019 #ifndef TA_ARRAY_H
00020 #include "Array.h"
00021 #endif // TA_ARRAY_H
00022 
00023 namespace TA
00024 {
00025 
00026 class Serialiser;
00027 
00028 class TACOMMON_CLASS AABBTree
00029 {
00030 public: 
00031     
00032     struct TACOMMON_CLASS Item
00033     {
00034         void* GetData() { return pData; }
00035 
00036     private:
00037         friend class AABBTree;
00038         void* pData;
00039     };
00040 
00041     typedef void (TAC_CALL *ParseCallBack)(Item* pItem, void* pData);
00042 
00043     AABBTree();
00044     ~AABBTree();
00045 
00046     void Initialise(int nNumItems);
00047     void Finalise();
00048     void Serialise(Serialiser& serialiser, void* pDataStart);
00049     void Serialise1007(Serialiser& serialiser, void* pDataStart);
00050 
00051     void AddItem(void* pItemData, const AABB& aabb);
00052     void BuildTree();
00053     //void OptimiseMemoryUsage(); // reallocates memory to exactly fit our data
00054     void ParseAABBTree(const AABB& aabb, ParseCallBack pParseCallBack, void* pCallBackData) const;
00055     void ParseAABBTree(const Vec3& v3Start, const Vec3& v3Normal, float fLength, ParseCallBack pParseCallBack, void* pCallBackData) const;
00056     const AABB& GetAABB() const;
00057 
00058 private:
00059 
00060     int m_nRoot;
00061     int m_nNumItems;
00062     Array<AABB, false> m_aabbArray;
00063     Array<void*, false> m_itemDataArray;
00064 
00065     void BuildTreeRecursive(int nStart, int nEnd);
00066     void TestTree(int nStart, int nEnd, int nIndex, const AABB& parentAABB) const;
00067     void ParseAABBTreeRecursive(int nStart, int nEnd, int nIndex) const;
00068     void ParseAABBTreeRecursive(int nStart, int nEnd, int nIndex, float fStart, float fEnd) const;
00069     bool ChopLine(float& fStart, float& fEnd, const AABB& aabb) const;
00070 
00071 };
00072 
00073 }
00074 
00075 #include "AABBTree.inl"
00076 
00077 #endif // TA_AABBTREE_H