00001 //---------------------------------------------------------------------------------
00002 // File Name: CollisionOctree.h
00003 // Description: 
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_COLLISIONOCTTREE_H
00013 #define TA_COLLISIONOCTTREE_H
00014 
00015 #ifndef TA_ARRAY_H
00016 #include "../Common/Array.h"
00017 #endif // TA_ARRAY_H
00018 
00019 #ifndef TA_AABB_H
00020 #include "../Common/AABB.h"
00021 #endif // TA_AABB_H
00022 
00023 #ifndef TA_SPACEDIVISION_H
00024 #include "SpaceDivision.h"
00025 #endif // TA_SPACEDIVISION_H
00026 
00027 namespace TA
00028 {
00029 
00030 struct AABB;
00031 
00032 class TAPHYSICS_CLASS CollisionOctree : public SpaceDivision
00033 {
00034 public:
00035     CollisionOctree();
00036     ~CollisionOctree();
00037 
00038     void Initialise(
00039         float fMinElementSize, 
00040         int nMaxMemory,
00041         const AABB& aabb);
00042     void Finalise();
00043 
00044     void Add(SpaceDivisionObject& object);
00045     void Remove(SpaceDivisionObject& object);
00046 
00047     void ForAllIntersections(
00048         const AABB& aabb,
00049         void (TAC_CALL *callBack)(SpaceDivisionObject& object, void* pData),
00050         void* pCallBackData);
00051     
00052     void ForAllIntersectionsWithLineSegment(
00053         const Vec3& v3Start,
00054         const Vec3& v3End,
00055         void (TAC_CALL *callBack)(SpaceDivisionObject& object, void* pData),
00056         void* pCallBackData);
00057     
00058 //  inline int WorldXToGridX(float fWorldX) { return FastFloatToInt((fWorldX + m_fOffsetX) * m_fScaleX); }
00059 //  inline int WorldYToGridY(float fWorldY) { return FastFloatToInt((fWorldY + m_fOffsetY) * m_fScaleY); }
00060 
00061 private:
00062     
00063     enum
00064     {
00065         NEG_X_NEG_Y_NEG_Z = 0,
00066         NEG_X_NEG_Y_POS_Z,
00067         NEG_X_POS_Y_NEG_Z,
00068         NEG_X_POS_Y_POS_Z,
00069         
00070         POS_X_NEG_Y_NEG_Z,
00071         POS_X_NEG_Y_POS_Z,
00072         POS_X_POS_Y_NEG_Z,
00073         POS_X_POS_Y_POS_Z,
00074     };
00075     enum Flags
00076     {
00077         NODE_FLAG_8_WAY = 0x1,
00078         NODE_FLAG_IN_FREE_LIST = 0x2,
00079     };
00080     struct Node
00081     {
00082         SpaceDivisionObject* pObjectList; // must be first.
00083         Node* pParent;
00084         s8 nNode;
00085         s8 nChildNode;
00086         u8 nCount;
00087         u8 nFlags;
00088         Node* pChildList[8];
00089 
00090         Node();
00091         Node*& pNext() { return (Node*&)pObjectList; }
00092         Node**& ppPrev() { return (Node**&)pParent; }
00093     };
00094     struct SmallNode
00095     {
00096         SpaceDivisionObject* pObjectList; // must be first.
00097         Node* pParent;
00098         s8 nNode;
00099         s8 nChildNode;
00100         u8 nCount;
00101         u8 nFlags;
00102         Node* pChild;
00103 
00104         SmallNode();
00105         SmallNode*& pNext() { return (SmallNode*&)pObjectList; }
00106         SmallNode**& ppPrev() { return (SmallNode**&)pParent; }
00107     };
00108     struct FindRecursiveData
00109     {
00110         AABB aabb;
00111         int nX;
00112         int nY;
00113         int nZ;
00114         int nExtentX;
00115         int nExtentY;
00116         int nExtentZ;
00117         void (TAC_CALL *callBack)(SpaceDivisionObject& object, void* pData);
00118         void* pCallBackData;
00119     };
00120     struct FindForLineRecursiveData
00121     {
00122         CollisionOctree* pThis;
00123         void (TAC_CALL *callBack)(SpaceDivisionObject& object, void* pData);
00124         void* pCallBackData;
00125         Vec3 v3Start;
00126         Vec3 v3End;
00127         float fLength;
00128         struct Axis
00129         {
00130             float fNormal;
00131             float fPosition;
00132             float fInvNormal;
00133             int nNotParallel;
00134             float fCenter;
00135             float fExtent;
00136         };
00137         Axis axis[3];
00138     };
00139     
00140     int m_nMaxNumLevels;
00141     Node* m_pFreeList;
00142     SmallNode* m_pSmallFreeList;
00143     int m_nBigListSize;
00144     int m_nSmallListSize;
00145     Array<u32, false> m_dataArray;
00146 
00147     AABB m_aabb;
00148     Node* m_pRootNode;
00149 
00150     Node* AllocNode(Node** ppUpdateIfNeeded);
00151     void FreeNode(Node* pNode);
00152     SmallNode* AllocSmallNode(Node** ppUpdateIfNeeded);
00153     void FreeSmallNode(SmallNode* pNode);
00154     void RelocateSmallItem(int nPos, Node** ppUpdateIfNeeded);
00155     void RelocateBigItem(int nPos, Node** ppUpdateIfNeeded);
00156     void CheckNodeIsValid(Node* pNode, bool bCheckMinimumCount);
00157     
00158     void ForAllIntersectionsRecursive(
00159         Node* pNode,
00160         int nLevel,
00161         int nX,
00162         int nY,
00163         int nZ,
00164         FindRecursiveData* pRecursionData);
00165 
00166     void ForAllIntersectionsWithLineRecursive(
00167         Node* pNode,
00168         float fScale,
00169         Vec3& v3Center,
00170         FindForLineRecursiveData* pRecursionData);
00171 
00172     void CheckRecursive(Node* pNode);
00173     bool CheckNodeIsInTree(Node* pNode, Node* pNodeToCheck);
00174     void CheckNodeIsInFreeList(Node* pNode, Node* pNodeToCheck);
00175 
00176 };
00177 
00178 };
00179 
00180 #endif // TA_COLLISIONOCTTREE_H