Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deOctree.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deOctree.hpp
    00003 ///
    00004 /// @brief octree for use in scenegraph, not for use outside scenegraph library
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// </hr>
    00021 ///
    00022 /// @date Jun 2002
    00023 /// @author Assassin
    00024 /// @remarks Initial Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DEOCTREE_HPP
    00029 #define DEOCTREE_HPP
    00030
    00031 #include "deGlobalTypes.hpp"
    00032 #include "deScene.hpp"
    00033 #include "deList.hpp" // for collide info
    00034
    00035 #if defined(DESCENE_DLL_EXPORTS) || defined(DESTINY3D_EXPORT_ALL)
    00036 #   define DEOCTREE_API DEDLL_EXPORT
    00037 #elif defined(DESTINY3D_STATIC_LINK)
    00038 #   define DEOCTREE_API
    00039 #else
    00040 #   define DEOCTREE_API DEDLL_IMPORT
    00041 #endif
    00042
    00043 class IdeVertexBuffer;
    00044
    00045 class deSceneOctree
    00046 {
    00047 protected:
    00048     virtual ~deSceneOctree();
    00049
    00050 public:
    00051     deSceneOctree();
    00052     int Release();
    00053
    00054     void TEST();
    00055
    00056     void SetMinOctSize(deDouble MinSize);
    00057     deDouble GetMinOctSize();
    00058     void SetMaxNodeNum(int MaxNum);
    00059     int GetMaxNodeNum();
    00060
    00061     IdeVertexBuffer * GetVB(int MaxPoints);
    00062
    00063     deBoolean WipeTree();
    00064
    00065     deBoolean AddNode(IdeSceneRoom * Node);
    00066     deBoolean RemoveNode(IdeSceneRoom * Node);
    00067
    00068     IdeSceneRoom * FindContainerNode(const deVec3d &Position);
    00069     IdeSceneRoom * FindClosestNode(const deVec3d &Position);
    00070     deBoolean FindIntersectingNodes(deTList <IdeSceneRoom*> &List, const deVec3d * Mins, const deVec3d * Maxs);
    00071
    00072     deBoolean TraceRayCollision(const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);
    00073
    00074     void CleanUp();
    00075
    00076 private:
    00077     enum Neighbor_t
    00078     {
    00079         n_None = -1,
    00080         n_Left = 0,
    00081         n_Right,
    00082         n_Bottom,
    00083         n_Top,
    00084         n_Front,
    00085         n_Back,
    00086     };
    00087     struct Octant
    00088     {
    00089         Octant* Parent;
    00090         int ParentIndex;
    00091         int NeighborRefs;
    00092         Octant* Child[8];
    00093         Octant* Neighbor[6];
    00094         deTList <IdeSceneRoom*> FixedNodes;
    00095         deTList <IdeSceneRoom*> AddedNodes;
    00096         deVec3d Min, Max, Center;
    00097         deBoolean CanBeRemoved;
    00098         int TestNumber;
    00099     };
    00100     // root for the octant tree
    00101     Octant * m_Root;
    00102     // minimum dimension for an octant
    00103     deDouble m_MinSize;
    00104     // maximum number of objects to have in an octant. MinSize overrides this
    00105     int m_MaxNodes;
    00106
    00107     int m_TestNumber;
    00108
    00109     IdeVertexBuffer * m_LineListVB;
    00110
    00111     deBoolean FillOctantLinePoints(Octant * oct, deVertex * Buffer, int & LastPoint, int MaxPoints);
    00112
    00113     void CleanUp(Octant * oct);
    00114     deBoolean SubdivideOctant(Octant * oct);
    00115     deBoolean Optimize(Octant * oct);
    00116     deBoolean InsertNode(IdeSceneRoom * Node);
    00117
    00118     deBoolean CalcNeighbors(Octant * oct);
    00119     Octant* TraceNeighbor(Octant * Start, Octant * Current, Neighbor_t N, int Depth);
    00120
    00121     deBoolean RayTestFromOctant(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);
    00122     deBoolean RayTestNodes(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo * Collision);
    00123     deBoolean RayTestParents(Octant * oct, const deVec3d & Start, const deVec3d & Dir, IdeCollision::deCollideInfo * Collision);
    00124     Neighbor_t RayToNeighbor(Octant * oct, const deVec3d & RayStart, const deVec3d & RayDir, deVec3d & ExitPoint);
    00125     int DecideChildOctant(Octant * Parent, const deVec3d & Position);
    00126     int DecideParentOctant(Octant * Child, const deVec3d & Position);
    00127
    00128     deBoolean InitializeRoot();
    00129     Octant * MakeOctant(const deVec3d &Min, const deVec3d &Max, Octant * ParentChild, int ParentID);
    00130     Octant * MakeSubOctant(Octant * ParentChild, int ParentID);
    00131
    00132     deBoolean RemoveOctant(Octant * oct, deTList <IdeSceneRoom*> * DumpList, deBoolean RemoveChildren, deBoolean IgnoreNeighbors = deFALSE);
    00133
    00134     Octant * FindOctant(const deVec3d &Position);
    00135     Octant * FindSubOctant(Octant * oct, const deVec3d &Position);
    00136     Octant * FindOctant(const deVec3d &Min, const deVec3d &Max);
    00137     Octant * FindSubOctant(Octant * oct, const deVec3d &Min, const deVec3d &Max);
    00138
    00139     deBoolean TestOctantPoint(Octant * oct, const deVec3d &Position);
    00140     deBoolean TestOctantBBox(Octant * oct, const deVec3d &Min, const deVec3d &Max);
    00141 };
    00142
    00143 #endif