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

# deObjectTree.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deObjectTree.hpp
    00003 ///
    00004 /// @brief [Adaptive] Binary Tree for objects
    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 Mar 2004
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DE_OBJECTTREE_HPP
    00029 #define DE_OBJECTTREE_HPP
    00030
    00031 #include "deGlobalTypes.hpp"
    00032 #include "deHash.hpp"
    00033 #include "deList.hpp"
    00034
    00035 class IdeSceneObject;
    00036 class IdeBoundingVolume;
    00037
    00038 class deObjectTree
    00039 {
    00040 public:
    00041     deObjectTree();
    00042     ~deObjectTree();
    00043
    00044     deBoolean AddObject(IdeSceneObject* object);
    00045     void RemoveObject(IdeSceneObject* object);
    00046     deBoolean RepositionObject(IdeSceneObject* object);
    00047
    00048     void IntersectionTest(IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);
    00049
    00050
    00051 private:
    00052     /// a split in an ABT node, along an axis (0,1,2)=(x,y,z) at a certain percentage
    00053     struct ABTSplit
    00054     {
    00055         long        Axis;
    00056         deDouble    Percent;
    00057     };
    00058     /// a partition within the ABT.
    00059     /// can have both child partitions and objects stored inside.
    00060     /// non-leaf nodes can have faces if in limbo while compiling.
    00061     struct ABTPartition
    00062     {
    00063         deAABB BBox;
    00064         ABTSplit Split;
    00065         ABTPartition* Parent;
    00066         ABTPartition* Children[2]; // 0 = minside, 1 = maxside
    00067         deTList<IdeSceneObject*> Objects;
    00068     };
    00069     /// information about a split - most important being the score.
    00070     /// used only while partitioning a box, to score the various sampled splits
    00071     struct ABTSplitStat
    00072     {
    00073         ABTSplit Split;
    00074         dePlane Plane;
    00075         long FrontBackDiff;
    00076         long NumOn;
    00077         deFloat Score;
    00078     };
    00079
    00080     typedef deTHashInt<ABTPartition*> ObjectHash_t;
    00081     ABTPartition* m_Root;
    00082     ObjectHash_t m_ObjectHash;
    00083     int mObjectThreshold;
    00084     int mDepthMax;
    00085
    00086     ABTPartition* CreatePartition(ABTPartition* parent, int ChildNum, int AxisNum);
    00087     deBoolean SplitPartition(ABTPartition* part, int Depth);
    00088     void DestroyPartition(ABTPartition* part);
    00089     void PrunePartition(ABTPartition* part, long Depth);
    00090     deBoolean InsertObject(ABTPartition* part, IdeSceneObject* object, int Depth);
    00091     deBoolean ExpandRoot(IdeSceneObject* outlier);
    00092     void IntersectionHelper(ABTPartition* part, IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);
    00093 };
    00094
    00095 #endif