NL3D::CQuadTree< T > Class Template Reference

#include <quad_tree.h>

---

Detailed Description

template<class T>
class NL3D::CQuadTree< T >

class: CQuadTree.

A template CQuadTree.

This first implementation support real-time quad node split, but never merge the quad node. The possibility to merge (delete) empty quads, when an element erase occurs, will be added later.

The quadtree is geometrically delimited. By default, his size is 1*1, centered on (0,0,0). If an element which is out this zone is inserted, then it will ALWAYS be considered selected in select*() methods. By default, the quad tree is aligned on XZ.

Sample code using CQuadTree:

 // My quad tree
 CQuadTree<myType> quadTree;

 // My min and max BoundingBox corner of each element
 CVector minPoint[elementCount]=...;
 CVector maxPoint[elementCount]=...;
 
 // My values
 myType value[elementCount]=...;
 
 // Init the quadTree with recursions depth = 6 (so max 64*64 cells)
 // centered in (0,0,0) with a max size of 10 in the plane XZ
 quadTree.create (6, CVector (0.f, 0.f, 0.f), 10.f);

 // Insert element in the quadTree
 for (int i=0; i<elementCount; i++)
                quadTree.insert (minPoint[i], maxPoint[i], value[i]);

 // [...]
 
 // Clear the selection
 quadTree.clearSelection ();
 
 // Select an element with the X axis as a 3d ray
 quadTree.selectRay (CVector (0,0,0), CVector (1,0,0));
 
        // Get first selected nodes..
 CQuadTree<myType>::CIterator it=quadTree.begin();
 while (it!=quadTree.end())
 {
        // Check what you want...
                
                // Next selected element
        it++;
 }

Definition at line 96 of file quad_tree.h.

Public Member Functions
	CQuadTree ()
	Default constructor, use axes XZ.
	~CQuadTree ()
	dtor.
Selection
CIterator	begin ()
void	clearSelection ()
CIterator	end ()
void	select (const std::vector< NLMISC::CPlane > &BVolume)
void	select (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
void	selectAll ()
void	selectRay (const NLMISC::CVector &source, const NLMISC::CVector &dir)
void	selectSegment (const NLMISC::CVector &source, const NLMISC::CVector &dest)
Initialization
void	changeBase (const NLMISC::CMatrix &base)
void	create (uint DepthMax, const NLMISC::CVector &center, float size)
Container operation
void	clear ()
	Clear the container. Elements are deleted, and the quadtree too (create() is undone).
void	erase (CIterator it)
void	eraseAll ()
CIterator	insert (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)
Private Attributes
NLMISC::CMatrix	_ChangeBasis
uint	_DepthMax
CQuadNode	_QuadRoot
CBaseNode	_Selection
float	_Size
Friends
class	CConstIterator
class	CIterator

---

Constructor & Destructor Documentation

template<class T> NL3D::CQuadTree< T >::CQuadTree (   )

Default constructor, use axes XZ. Definition at line 658 of file quad_tree.h. References NL3D::CQuadTree< T >::_DepthMax, NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NLMISC::CMatrix::identity(), NL3D::CQuadTree< T >::CBaseNode::Next, and NLMISC::CVector::set(). { _Selection.Next= NULL; _DepthMax= 0; _QuadRoot.BBoxMin.set(-0.5, 0, -0.5); _QuadRoot.BBoxMax.set( 0.5, 0, 0.5); _Size=1; _ChangeBasis.identity(); }

template<class T> NL3D::CQuadTree< T >::~CQuadTree< T > (   )

dtor.

---

Member Function Documentation

template<class T> CQuadTree< T >::CIterator NL3D::CQuadTree< T >::begin (   )

Return the first iterator of the selected element list. begin and end are valid till the next insert. Definition at line 884 of file quad_tree.h. References NL3D::CQuadTree< T >::CBaseNode::Next. Referenced by NL3D::CQuadTree< T >::eraseAll(). { return (CNode*)(_Selection.Next); }

template<class T> void NL3D::CQuadTree< T >::changeBase (  const NLMISC::CMatrix &  base  )

Change the base matrix of the quad tree. For exemple this code init the quad tree in the plane XY: CQuadTree quadTree; NLMISC::CMatrix tmp; NLMISC::CVector I(1,0,0); NLMISC::CVector J(0,0,-1); NLMISC::CVector K(0,1,0); tmp.identity(); tmp.setRot(I,J,K, true); quadTree.changeBase (tmp); Parameters: base  Base of the quad tree Definition at line 669 of file quad_tree.h. { _ChangeBasis=base; }

template<class T> void NL3D::CQuadTree< T >::clear (   )

Clear the container. Elements are deleted, and the quadtree too (create() is undone). Definition at line 679 of file quad_tree.h. References NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::CQuadNode::clear(), and NL3D::CQuadTree< T >::CBaseNode::Next. Referenced by NL3D::CQuadTree< T >::create(). { _QuadRoot.clear(); _Selection.Next= NULL; }

template<class T> void NL3D::CQuadTree< T >::clearSelection (   )

Clear the selection list Definition at line 775 of file quad_tree.h. References NL3D::CQuadTree< T >::CBaseNode::Next, and NL3D::CQuadTree< T >::CBaseNode::Prev. Referenced by NL3D::CQuadTree< T >::select(), and NL3D::CQuadTree< T >::selectAll(). { CBaseNode *p; while(p=_Selection.Next) { // On retire ce noeud de la selection. Ce qui va modifier implicitement _Selection.Next. if(p->Prev) p->Prev->Next= p->Next; if(p->Next) p->Next->Prev= p->Prev; p->Prev=p->Next=NULL; } }

template<class T> void NL3D::CQuadTree< T >::create (  uint  DepthMax, const NLMISC::CVector &  center, float  size )

Init the container Parameters: DepthMax  is the max depth in the tree. The max cell count is (1<<DepthMax)^2 center  is the center of the quad tree size  is the width and the height of the initial quad tree. Definition at line 685 of file quad_tree.h. References NL3D::CQuadTree< T >::_DepthMax, NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NL3D::CQuadTree< T >::clear(), size, and uint. { NLMISC::CVector mycenter=_ChangeBasis*center; clear(); _DepthMax= DepthMax; _Size= size; _QuadRoot.BBoxMin= mycenter-NLMISC::CVector(size/2, 0 , size/2); _QuadRoot.BBoxMax= mycenter+NLMISC::CVector(size/2, 0 , size/2); }

template<class T> CQuadTree< T >::CIterator NL3D::CQuadTree< T >::end (   )

Return the end iterator of the selected element list. begin and end are valid till the next insert. Definition at line 889 of file quad_tree.h. References NL3D::CQuadTree< T >::CIterator. Referenced by NL3D::CQuadTree< T >::eraseAll(). { return CIterator(NULL); }

template<class T> void NL3D::CQuadTree< T >::erase (  CIterator  it  )

Erase an interator from the container Parameters: it  is the iterator to erase. Definition at line 723 of file quad_tree.h. References NL3D::CQuadTree< T >::const_iterator::_Ptr, and NL3D::CQuadTree< T >::CBaseNode::clear(). Referenced by NL3D::CQuadTree< T >::eraseAll(). { CNode *p=it._Ptr; if(p) { // Clear links. p->clear(); // delete it!! delete p; } }

template<class T> void NL3D::CQuadTree< T >::eraseAll (   )

Erase all elements from the container Definition at line 704 of file quad_tree.h. References NL3D::CQuadTree< T >::begin(), NL3D::CQuadTree< T >::end(), NL3D::CQuadTree< T >::erase(), NL3D::CQuadTree< T >::selectAll(), and sint. { CIterator it; std::vector<CIterator> its; // First, make a copy of all elements. selectAll(); for(it= begin();it!=end();it++) { its.push_back(it); } // Then erase them. Must do it OUTSIDE the select loop. for(sint i=0;i<(sint)its.size();i++) { erase(its[i]); } }

template<class T> CQuadTree< T >::CIterator NL3D::CQuadTree< T >::insert (  const NLMISC::CVector &  bboxmin, const NLMISC::CVector &  bboxmax, const T &  val )

Insert a new element in the container. The bounding box of the element MUST be included in the bounding box of the quadtree. Parameters: bboxmin  is the corner of the bounding box of the element to insert with minimal coordinates. bboxmax  is the corner of the bounding box of the element to insert with maximal coordinates. val  is a reference on the value to insert Definition at line 736 of file quad_tree.h. References NL3D::CQuadTree< T >::_DepthMax, NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::CIterator, NL3D::CQuadTree< T >::CQuadNode::insert(), nlassert, uint, NLMISC::CVector::x, NLMISC::CVector::y, and NLMISC::CVector::z. { NLMISC::CVector myboxmin2=_ChangeBasis*bboxmin; NLMISC::CVector myboxmax2=_ChangeBasis*bboxmax; NLMISC::CVector myboxmin (std::min (myboxmin2.x, myboxmax2.x), std::min (myboxmin2.y, myboxmax2.y), std::min (myboxmin2.z, myboxmax2.z)); NLMISC::CVector myboxmax (std::max (myboxmin2.x, myboxmax2.x), std::max (myboxmin2.y, myboxmax2.y), std::max (myboxmin2.z, myboxmax2.z)); CNode *newNode=new CNode(val); nlassert(myboxmax.x>=myboxmin.x); nlassert(myboxmax.y>=myboxmin.y); nlassert(myboxmax.z>=myboxmin.z); float boxsize= std::max(myboxmax.x-myboxmin.x, myboxmax.z-myboxmin.z ); // Prevent float precision problems. Increase bbox size a little. boxsize*=1.01f; // We must find the level quad which is just bigger. float wantsize=_Size; uint wantdepth=0; while(boxsize<wantsize/2 && wantdepth<_DepthMax) { wantsize/=2; wantdepth++; } _QuadRoot.insert(myboxmin, myboxmax, wantdepth, newNode); return CIterator(newNode); }

template<class T> void NL3D::CQuadTree< T >::select (  const std::vector< NLMISC::CPlane > &  BVolume  )

Select element with multiple planes. Intersect with a polytope convex made of planes. The normals of planes must be directed outwards the polytope. Parameters: BVolume  is a plane vector Definition at line 804 of file quad_tree.h. References NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::clearSelection(), and NL3D::CQuadTree< T >::CQuadNode::select(). { std::vector<NLMISC::CPlane> BVolumeCopy; BVolumeCopy.resize (BVolume.size()); for (int i=0; i<(int)BVolumeCopy.size(); i++) { BVolumeCopy[i]=BVolume[i]*((_ChangeBasis).inverted()); } clearSelection(); _QuadRoot.select(_Selection, BVolumeCopy); }

template<class T> void NL3D::CQuadTree< T >::select (  const NLMISC::CVector &  bboxmin, const NLMISC::CVector &  bboxmax )

Select element intersecting a bounding box Parameters: bboxmin  is the corner of the bounding box used to select bboxmax  is the corner of the bounding box used to select Definition at line 793 of file quad_tree.h. References NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::clearSelection(), NL3D::CQuadTree< T >::CQuadNode::select(), NLMISC::CVector::x, NLMISC::CVector::y, and NLMISC::CVector::z. Referenced by NL3D::CQuadTree< T >::selectRay(), and NL3D::CQuadTree< T >::selectSegment(). { NLMISC::CVector myboxmin2=_ChangeBasis*bboxmin; NLMISC::CVector myboxmax2=_ChangeBasis*bboxmax; NLMISC::CVector bboxminCopy (std::min (myboxmin2.x, myboxmax2.x), std::min (myboxmin2.y, myboxmax2.y), std::min (myboxmin2.z, myboxmax2.z)); NLMISC::CVector bboxmaxCopy (std::max (myboxmin2.x, myboxmax2.x), std::max (myboxmin2.y, myboxmax2.y), std::max (myboxmin2.z, myboxmax2.z)); clearSelection(); _QuadRoot.select(_Selection, bboxminCopy, bboxmaxCopy); }

template<class T> void NL3D::CQuadTree< T >::selectAll (   )

Select all the container Definition at line 787 of file quad_tree.h. References NL3D::CQuadTree< T >::_QuadRoot, NL3D::CQuadTree< T >::clearSelection(), and NL3D::CQuadTree< T >::CQuadNode::selectAll(). Referenced by NL3D::CQuadTree< T >::eraseAll(). { clearSelection(); _QuadRoot.selectAll(_Selection); }

template<class T> void NL3D::CQuadTree< T >::selectRay (  const NLMISC::CVector &  source, const NLMISC::CVector &  dir )

Select element with a ray Parameters: source  is a point in the ray dir  is the direction off the ray Definition at line 817 of file quad_tree.h. References NLMISC::CMatrix::getJ(), NLMISC::CMatrix::getK(), NLMISC::CMatrix::identity(), NLMISC::CPlane::make(), NLMISC::CMatrix::normalize(), NL3D::CQuadTree< T >::select(), and NLMISC::CMatrix::setRot(). { NLMISC::CMatrix mat; mat.identity (); // Set a wrong matrix NLMISC::CVector vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0)); mat.setRot (dir, vTmp, dir^vTmp); // Normalize it Yoyo! mat.normalize (NLMISC::CMatrix::XYZ); // Get the planes.. std::vector<NLMISC::CPlane> BVolume; BVolume.reserve (4); // Setup the planes NLMISC::CPlane plane; plane.make (mat.getJ(), source); BVolume.push_back (plane); plane.make (mat.getK(), source); BVolume.push_back (plane); plane.make (-mat.getJ(), source); BVolume.push_back (plane); plane.make (-mat.getK(), source); BVolume.push_back (plane); // Select the nodes select (BVolume); }

template<class T> void NL3D::CQuadTree< T >::selectSegment (  const NLMISC::CVector &  source, const NLMISC::CVector &  dest )

Select element with a segment Parameters: source  is the source of the segment dest  is the destination of the segment Definition at line 848 of file quad_tree.h. References NLMISC::CMatrix::getI(), NLMISC::CMatrix::getJ(), NLMISC::CMatrix::getK(), NLMISC::CMatrix::identity(), NLMISC::CPlane::make(), NLMISC::CMatrix::normalize(), NL3D::CQuadTree< T >::select(), and NLMISC::CMatrix::setRot(). { NLMISC::CMatrix mat; mat.identity (); // Set a wrong matrix CVector dir=dest-source; NLMISC::CVector vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0)); mat.setRot (dir, vTmp, dir^vTmp); // Normalize it Yoyo! mat.normalize (NLMISC::CMatrix::XYZ); // Get the planes.. std::vector<NLMISC::CPlane> BVolume; BVolume.reserve (4); // Setup the planes NLMISC::CPlane plane; plane.make (mat.getJ(), source); BVolume.push_back (plane); plane.make (mat.getK(), source); BVolume.push_back (plane); plane.make (-mat.getJ(), source); BVolume.push_back (plane); plane.make (-mat.getK(), source); BVolume.push_back (plane); plane.make (mat.getI(), dest); BVolume.push_back (plane); plane.make (-mat.getI(), source); BVolume.push_back (plane); // Select the nodes select (BVolume); }

---

Friends And Related Function Documentation

template<class T> friend class CConstIterator [friend]

Definition at line 105 of file quad_tree.h.

template<class T> friend class CIterator [friend]

Definition at line 102 of file quad_tree.h. Referenced by NL3D::CQuadTree< T >::end(), and NL3D::CQuadTree< T >::insert().

---

Field Documentation

template<class T> NLMISC::CMatrix NL3D::CQuadTree< T >::_ChangeBasis [private]

Definition at line 581 of file quad_tree.h.

template<class T> uint NL3D::CQuadTree< T >::_DepthMax [private]

Definition at line 579 of file quad_tree.h. Referenced by NL3D::CQuadTree< T >::CQuadTree(), NL3D::CQuadTree< T >::create(), and NL3D::CQuadTree< T >::insert().

template<class T> CQuadNode NL3D::CQuadTree< T >::_QuadRoot [private]

Definition at line 577 of file quad_tree.h. Referenced by NL3D::CQuadTree< T >::clear(), NL3D::CQuadTree< T >::CQuadTree(), NL3D::CQuadTree< T >::create(), NL3D::CQuadTree< T >::insert(), NL3D::CQuadTree< T >::select(), and NL3D::CQuadTree< T >::selectAll().

template<class T> CBaseNode NL3D::CQuadTree< T >::_Selection [private]

Definition at line 578 of file quad_tree.h.

template<class T> float NL3D::CQuadTree< T >::_Size [private]

Definition at line 580 of file quad_tree.h.

---

The documentation for this class was generated from the following file:

• quad_tree.h

---