Contents User Forum Source Index APIs by Task APIs by Level Data G3D::AABSPTree< T > Class Template Reference A set that supports spatial queries using an axis-aligned BSP tree for speed. More... #include <AABSPTree.h> List of all members. Public Member Functions   AABSPTree (const AABSPTree &src)   AABSPTree () void  balance (int valuesPerNode=5, int numMeanSplits=3) Iterator  begin () const BoxIntersectionIterator  beginBoxIntersection (const AABox &box) const void  clear () bool  contains (const T &value) void  deserializeStructure (BinaryInput &bi) Iterator  end () const BoxIntersectionIterator  endBoxIntersection () const void  getIntersectingMembers (const Sphere &sphere, Array< T > &members) const void  getIntersectingMembers (const AABox &box, Array< T > &members) const void  getIntersectingMembers (const GCamera::Frustum &frustum, Array< T > &members) const void  getIntersectingMembers (const Array< Plane > &plane, Array< T > &members) const void  getMembers (Array< T > &members) const void  insert (const Array< T > &valueArray) void  insert (const T &value) template<typename RayCallback> void  intersectRay (const Ray &ray, RayCallback &intersectCallback, float &distance, bool intersectCallbackIsFast=false) const AABSPTree &  operator= (const AABSPTree &src) void  remove (const T &value) void  serializeStructure (BinaryOutput &bo) const int  size () const void  update (const T &value)   ~AABSPTree () Protected Types typedef _internal::Indirector< Handle >  Member typedef Table< Member, Node * >  MemberTable Protected Member Functions Node *  cloneTree (Node *src) Node *  makeNode (Array< Handle * > &source, int valuesPerNode, int numMeanSplits, Array< Handle * > &temp) Static Protected Member Functions static AABox  computeBounds (const Array< Handle * > &point, int beginIndex, int endIndex) static void  getIntersectingMembers (const Array< Plane > &plane, Array< T > &members, Node *node, uint32 parentMask) Protected Attributes MemberTable  memberTable Node *  root Classes class   BoundsComparator   Compares bounds for strict >, <, or overlap. More... class   BoxIntersectionIterator   C++ STL style iterator variable. More... class   CenterComparator   Compares centers. More... class   Comparator   Compares bounds to the sort location. More... class   Handle   Wrapper for a value that includes a cache of its bounds. More... class   Iterator   C++ STL style iterator variable. More... class   Node Detailed Description template<class T> class G3D::AABSPTree< T > A set that supports spatial queries using an axis-aligned BSP tree for speed. AABSPTree allows you to quickly find objects in 3D that lie within a box or along a ray. For large sets of objects it is much faster than testing each object for a collision. AABSPTree is as powerful as but more general than a Quad Tree, Oct Tree, or KD Tree, but less general than an unconstrained BSP tree (which is much slower to create). Internally, objects are arranged into an axis-aligned BSP-tree according to their axis-aligned bounds. This increases the cost of insertion to O(log n) but allows fast overlap queries. Template Parameters The template parameter T must be one for which the following functions are all overloaded: void getBounds(const T&, G3D::AABox&); bool operator==(const T&, const T&); unsigned int hashCode(const T&); T::T(); (public constructor of no arguments) G3D provides these for common classes like G3D::Vector3 and G3D::Sphere. If you use a custom class, or a pointer to a custom class, you will need to define those functions. Moving Set Members It is important that objects do not move without updating the AABSPTree. If the axis-aligned bounds of an object are about to change, AABSPTree::remove it before they change and AABSPTree::insert it again afterward. For objects where the hashCode and == operator are invariant with respect to the 3D position, you can use the AABSPTree::update method as a shortcut to insert/remove an object in one step after it has moved. Note: Do not mutate any value once it has been inserted into AABSPTree. Values are copied interally. All AABSPTree iterators convert to pointers to constant values to reinforce this. If you want to mutate the objects you intend to store in a AABSPTree simply insert pointers to your objects instead of the objects themselves, and ensure that the above operations are defined. (And actually, because values are copied, if your values are large you may want to insert pointers anyway, to save space and make the balance operation faster.) Dimensions Although designed as a 3D-data structure, you can use the AABSPTree for data distributed along 2 or 1 axes by simply returning bounds that are always zero along one or more dimensions. Member Typedef Documentation template<class T> typedef _internal::Indirector<Handle> G3D::AABSPTree< T >::Member [protected] Wrapper for a Handle; used to create a memberTable that acts like Table<Handle, Node*> but stores only Handle* internally to avoid memory copies. template<class T> typedef Table<Member, Node*> G3D::AABSPTree< T >::MemberTable [protected] Constructor & Destructor Documentation template<class T> G3D::AABSPTree< T >::AABSPTree (  )  [inline] To construct a balanced tree, insert the elements and then call AABSPTree::balance(). template<class T> G3D::AABSPTree< T >::AABSPTree ( const AABSPTree< T > &  src  )  [inline] template<class T> G3D::AABSPTree< T >::~AABSPTree (  )  [inline] Member Function Documentation template<class T> void G3D::AABSPTree< T >::balance ( int  valuesPerNode = 5, int  numMeanSplits = 3   ) [inline] Rebalances the tree (slow). Call when objects have moved substantially from their original positions (which unbalances the tree and causes the spatial queries to be slow). Parameters: valuesPerNode  Maximum number of elements to put at a node. numMeanSplits  numMeanSplits = 0 gives a fully axis aligned BSP-tree, where the balance operation attempts to balance the tree so that every splitting plane has an equal number of left and right children (i.e. it is a median split along that axis). This tends to maximize average performance. You can override this behavior by setting a number of mean (average) splits. numMeanSplits = MAX_INT creates a full oct-tree, which tends to optimize peak performance at the expense of average performance. It tends to have better clustering behavior when members are not uniformly distributed. template<class T> Iterator G3D::AABSPTree< T >::begin (  )  const [inline] C++ STL style iterator method. Returns the first member. Use preincrement (++entry) to get to the next element (iteration order is arbitrary). Do not modify the set while iterating. template<class T> BoxIntersectionIterator G3D::AABSPTree< T >::beginBoxIntersection ( const AABox &  box  )  const [inline] Iterates through the members that intersect the box. template<class T> void G3D::AABSPTree< T >::clear (  )  [inline] Throws out all elements of the set. template<class T> Node* G3D::AABSPTree< T >::cloneTree ( Node *  src  )  [inline, protected] Recursively clone the passed in node tree, setting pointers for members in the memberTable as appropriate. called by the assignment operator. template<class T> static AABox G3D::AABSPTree< T >::computeBounds ( const Array< Handle * > &  point, int  beginIndex, int  endIndex   ) [inline, static, protected] Returns the bounds of the sub array. Used by makeNode. template<class T> bool G3D::AABSPTree< T >::contains ( const T &  value  )  [inline] Returns true if this object is in the set, otherwise returns false. O(1) time. template<class T> void G3D::AABSPTree< T >::deserializeStructure ( BinaryInput &  bi  )  [inline] Clears the member table. template<class T> Iterator G3D::AABSPTree< T >::end (  )  const [inline] C++ STL style iterator method. Returns one after the last iterator element. template<class T> BoxIntersectionIterator G3D::AABSPTree< T >::endBoxIntersection (  )  const [inline] template<class T> void G3D::AABSPTree< T >::getIntersectingMembers ( const Sphere &  sphere, Array< T > &  members   ) const [inline] Parameters: members  The results are appended to this array. template<class T> void G3D::AABSPTree< T >::getIntersectingMembers ( const AABox &  box, Array< T > &  members   ) const [inline] Appends all members whose bounds intersect the box. See also AABSPTree::beginBoxIntersection. template<class T> void G3D::AABSPTree< T >::getIntersectingMembers ( const GCamera::Frustum &  frustum, Array< T > &  members   ) const [inline] Typically used to find all visible objects inside the view frustum (see also GCamera::getClipPlanes). .. i.e. all objects not culled by frustum. Example: Array<Object*> visible; tree.getIntersectingMembers(camera.frustum(), visible); ... Draw all objects in the visible array. Parameters: members  The results are appended to this array. template<class T> void G3D::AABSPTree< T >::getIntersectingMembers ( const Array< Plane > &  plane, Array< T > &  members   ) const [inline] Returns all members inside the set of planes. Parameters: members  The results are appended to this array. template<class T> static void G3D::AABSPTree< T >::getIntersectingMembers ( const Array< Plane > &  plane, Array< T > &  members, Node *  node, uint32  parentMask   ) [inline, static, protected] Parameters: parentMask  The mask that this node returned from culledBy. template<class T> void G3D::AABSPTree< T >::getMembers ( Array< T > &  members  )  const [inline] Returns an array of all members of the set. See also AABSPTree::begin. template<class T> void G3D::AABSPTree< T >::insert ( const Array< T > &  valueArray  )  [inline] Inserts each elements in the array in turn. If the tree begins empty (no structure and no elements), this is faster than inserting each element in turn. You still need to balance the tree at the end. template<class T> void G3D::AABSPTree< T >::insert ( const T &  value  )  [inline] Inserts an object into the set if it is not already present. O(log n) time. Does not cause the tree to be balanced. template<class T> template<typename RayCallback> void G3D::AABSPTree< T >::intersectRay ( const Ray &  ray, RayCallback &  intersectCallback, float &  distance, bool  intersectCallbackIsFast = false   ) const [inline] Invoke a callback for every member along a ray until the closest intersection is found. Parameters: callback  either a function or an instance of a class with an overloaded operator() of the form: void callback(const Ray& ray, const T& object, float& distance). If the ray hits the object before travelling distance distance, updates distance with the new distance to the intersection, otherwise leaves it unmodified. A common example is: class Entity { public: void intersect(const Ray& ray, float& maxDist, Vector3& outLocation, Vector3& outNormal) { float d = maxDist; ... search for intersection distance d if ((d > 0) && (d < maxDist)) { Intersection occured maxDist = d; outLocation = ...; outNormal = ...; } } }; Finds the surface normal and location of the first intersection with the scene class Intersection { public: Entity* closestEntity; Vector3 hitLocation; Vector3 hitNormal; void operator()(const Ray& ray, const Entity* entity, float& distance) { entity->intersect(ray, distance, hitLocation, hitNormal); } }; AABSPTree<Entity*> scene; Intersection intersection; float distance = inf(); scene.intersectRay(camera.worldRay(x, y), intersection, distance); Parameters: distance  When the method is invoked, this is the maximum distance that the tree should search for an intersection. On return, this is set to the distance to the first intersection encountered. intersectCallbackIsFast  If false, each object's bounds are tested before the intersectCallback is invoked. If the intersect callback runs at the same speed or faster than AABox-ray intersection, set this to true. template<class T> Node* G3D::AABSPTree< T >::makeNode ( Array< Handle * > &  source, int  valuesPerNode, int  numMeanSplits, Array< Handle * > &  temp   ) [inline, protected] Recursively subdivides the subarray. Clears the source array as soon as it is no longer needed. Call assignSplitBounds() on the root node after making a tree. template<class T> AABSPTree& G3D::AABSPTree< T >::operator= ( const AABSPTree< T > &  src  )  [inline] template<class T> void G3D::AABSPTree< T >::remove ( const T &  value  )  [inline] Removes an object from the set in O(1) time. It is an error to remove members that are not already present. May unbalance the tree. Removing an element never causes a node (split plane) to be removed... nodes are only changed when the tree is rebalanced. This behavior is desirable because it allows the split planes to be serialized, and then deserialized into an empty tree which can be repopulated. template<class T> void G3D::AABSPTree< T >::serializeStructure ( BinaryOutput &  bo  )  const [inline] Stores the locations of the splitting planes (the structure but not the content) so that the tree can be quickly rebuilt from a previous configuration without calling balance. template<class T> int G3D::AABSPTree< T >::size (  )  const [inline] template<class T> void G3D::AABSPTree< T >::update ( const T &  value  )  [inline] If the element is in the set, it is removed. The element is then inserted. This is useful when the == and hashCode methods on T are independent of the bounds. In that case, you may call update(v) to insert an element for the first time and call update(v) again every time it moves to keep the tree up to date. Member Data Documentation template<class T> MemberTable G3D::AABSPTree< T >::memberTable [protected] Maps members to the node containing them. template<class T> Node* G3D::AABSPTree< T >::root [protected] The documentation for this class was generated from the following file: AABSPTree.h Hosted by