From 0ea5fc66924303d1bf73ba283a383e2aadee02f2 Mon Sep 17 00:00:00 2001 From: neodarz Date: Sat, 11 Aug 2018 20:21:34 +0200 Subject: Initial commit --- docs/doxygen/nel/a03273.html | 1600 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1600 insertions(+) create mode 100644 docs/doxygen/nel/a03273.html (limited to 'docs/doxygen/nel/a03273.html') diff --git a/docs/doxygen/nel/a03273.html b/docs/doxygen/nel/a03273.html new file mode 100644 index 00000000..2f04d163 --- /dev/null +++ b/docs/doxygen/nel/a03273.html @@ -0,0 +1,1600 @@ + + +NeL: TemplateNL3D::CQuadGrid< T > class Reference + + + +
+Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages | Search for 
+

NL3D::CQuadGrid< T > Class Template Reference

#include <quad_grid.h> +

+

Detailed Description

+

template<class T>
+ class NL3D::CQuadGrid< T >

+ +This container is a simple grid, used to quickly find elements. His purpose is similiar to CQuadTree, but it is a simple grid, so test are in O(1), not in O(log n). It is perfect for local lookup (like in collisions). Use it if you want to select small area, not large. Also, for best use, elements should have approximatively the same size, and this size should be little smaller than the size of a grid element...

+By default, the quad grid is aligned on XY. (unlike the quadtree!!!)

+Unlike the quadtree, the quadgrid is NOT geographicly delimited, ie, its limits "tiles"!! This is why no "center" is required. As a direct consequence, when you select something, you are REALLY not sure that what you select is not a mile away from your selection :) ....

+Also, for memory optimisation, no bbox is stored in the quadgrid. Hence no particular selection is made on the Z components...

+For maximum allocation speed Efficiency, it uses a CBlockMemory<CNode> to allocate elements at insert(). DefaultBlockSize is 16, but you can change it at construction.

+because elements may lies in multiples squares, QuadGrid use lists per square which points on elements. For faster allocation, it uses a CSTLBlockList<>. The entire quadGrid has its own CBlockMemory for the CSTLBlockLists. memoryBlockSize is the same than the blockSize for allocation of nodes.

+

Author:
Lionel Berenguier

+Nevrax France

+
Date:
2000
+ +

+ +

+Definition at line 76 of file 3d/quad_grid.h. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Public Member Functions

 CQuadGrid (uint memoryBlockSize=16)
 Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1.

 ~CQuadGrid ()
 dtor.

Selection
CIterator begin ()
void clearSelection ()
CIterator end ()
void select (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
void selectAll ()
Initialization
void changeBase (const NLMISC::CMatrix &base)
void create (uint size, float eltSize)
const NLMISC::CMatrix & getBasis () const
float getEltSize () const
uint getSize () const
Container operation
void clear ()
CIterator erase (CIterator it)
CIterator insert (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)

Private Member Functions

void addQuadNodeToSelection (CQuadNode &quad)
void addToSelection (CNode *ptr)
void linkToRoot (CBaseNode &root, CBaseNode *ptr)
void selectQuads (CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1)

Private Attributes

NLMISC::CMatrix _ChangeBasis
float _EltSize
std::vector< CQuadNode > _Grid
NLMISC::CBlockMemory< CNode > _NodeBlockMemory
NLMISC::CBlockMemory< CNode *,
+ false > 		_NodeListBlockMemory
CBaseNode _SelectedList
sint _Size
sint _SizePower
CBaseNode _UnSelectedList

Friends

class CIterator
+

Constructor & Destructor Documentation

+

+ + + + +
+ + + + + + + + + + + + + +
+template<class T>
NL3D::CQuadGrid< T >::CQuadGrid ( uint  memoryBlockSize = 16  ) 
+
+ + + + + +
+   + + +

+Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1. +

+ +

+Definition at line 412 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_ChangeBasis, NL3D::CQuadGrid< T >::_EltSize, NLMISC::CMatrix::identity(), and uint. +

+

00412                                                                     : 
+00413         _NodeBlockMemory(memoryBlockSize), _NodeListBlockMemory(memoryBlockSize)
+00414 {
+00415         _SizePower=4;
+00416         _Size=1<<_SizePower;
+00417         _EltSize=1;
+00418         _ChangeBasis.identity();
+00419 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
NL3D::CQuadGrid< T >::~CQuadGrid (   ) 
+
+ + + + + +
+   + + +

+dtor. +

+ +

+Definition at line 421 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::clear(). +

+

00422 {
+00423         clear();
+00424         // must clear the array, before _NodeListBlockMemory.purge() is called.
+00425         _Grid.clear();
+00426 }
+
+

Member Function Documentation

+

+ + + + +
+ + + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::addQuadNodeToSelection ( CQuadNode &  quad  )  [inline, private]
+
+ + + + + +
+   + + +

+ +

+Definition at line 322 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::select(). +

+

00323         {
+00324                 typename NLMISC::CSTLBlockList<CNode*>::iterator        itNode;
+00325                 for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00326                 {
+00327                         addToSelection(*itNode);
+00328                 }
+00329         }
+
+

+ + + + +
+ + + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::addToSelection ( CNode *  ptr  )  [inline, private]
+
+ + + + + +
+   + + +

+ +

+Definition at line 303 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< CWaterShape * >::addQuadNodeToSelection(). +

+

00304         {
+00305                 // if not selected
+00306                 if(!ptr->Selected)
+00307                 {
+00308                         // remove from the unselected list.
+00309                         ptr->Prev->Next= ptr->Next;
+00310                         if(ptr->Next)
+00311                                 ptr->Next->Prev= ptr->Prev;
+00312 
+00313                         // Append to front of the _Selected list.
+00314                         linkToRoot(_SelectedList, ptr);
+00315 
+00316                         // mark it
+00317                         ptr->Selected= true;
+00318                 }
+00319         }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::begin (   ) 
+
+ + + + + +
+   + + +

+Return the first iterator of the selected element list. begin and end are valid till the next insert. Speed is in O(1) +

+Definition at line 641 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::CIterator, and NL3D::CQuadGrid< T >::CBaseNode::Next. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(), NL3D::CQuadGrid< T >::clear(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CShadowPolyReceiver::getCameraCollision(), NL3D::CLightingManager::getDynamicPointLightList(), NL3D::CMiniCol::getFaces(), NL3D::CMiniCol::getGroundNormal(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CShadowPolyReceiver::render(), and NL3D::CMiniCol::snapToGround(). +

+

00642 {
+00643         return CIterator((CNode*)(_SelectedList.Next));
+00644 }
+
+

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

+Change the base matrix of the quad grid. For exemple this code init the grid tree in the plane XZ: 

 CQuadGrid                      grid;
+ 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 grid
+
+ +

+Definition at line 428 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_ChangeBasis. +

+Referenced by NL3D::CInstanceLighter::computeSunContribution(). +

+

00429 {
+00430         _ChangeBasis= base;
+00431 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::clear (   ) 
+
+ + + + + +
+   + + +

+Clear the container. Elements are deleted, but the quadgrid is not erased. Speed is in O(Nelts) +

+Definition at line 454 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::_UnSelectedList, NL3D::CQuadGrid< T >::begin(), NL3D::CQuadGrid< T >::end(), NL3D::CQuadGrid< T >::erase(), NL3D::CQuadGrid< T >::CBaseNode::Next, and NL3D::CQuadGrid< T >::selectAll(). +

+Referenced by NL3D::CQuadGrid< T >::create(), and NL3D::CQuadGrid< T >::~CQuadGrid(). +

+

00455 {
+00456         CIterator       it;
+00457         selectAll();
+00458         while( (it=begin())!=end())
+00459         {
+00460                 erase(it);
+00461         }
+00462 
+00463         // Clear the 2 selection...
+00464         _SelectedList.Next= NULL;
+00465         _UnSelectedList.Next= NULL;
+00466 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::clearSelection (   ) 
+
+ + + + + +
+   + + +

+Clear the selection list Speed is in O(Nelts) +

+Definition at line 567 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::_UnSelectedList, NL3D::CQuadGrid< T >::linkToRoot(), NL3D::CQuadGrid< T >::CBaseNode::Next, and NL3D::CQuadGrid< T >::CBaseNode::Selected. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), and NL3D::CQuadGrid< T >::select(). +

+

00568 {
+00569         CBaseNode       *ptr= _SelectedList.Next;
+00570         while(ptr)
+00571         {
+00572                 // next selected.
+00573                 CBaseNode       *nextSelected= ptr->Next;
+00574 
+00575                 // Link to _Unselected list.
+00576                 linkToRoot(_UnSelectedList, ptr);
+00577 
+00578                 // mark as not selected.
+00579                 ptr->Selected= false;
+00580 
+00581                 // next.
+00582                 ptr= nextSelected;
+00583         }
+00584 
+00585         // the selected list is now empty.
+00586         _SelectedList.Next= NULL;
+00587 }
+
+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::create ( uint  size,
float  eltSize
) 
+
+ + + + + +
+   + + +

+Init the container. container is first clear() ed.

+

Parameters:
+ + + +
size is the width and the height of the initial quad tree, in number of square. For performance view, this should be a power of 2, and <=32768. (eg: 256,512, 8, 16 ...)
eltSize is the width and height of an element. Must be >0. Notice that the quadgrid MUST be square!!
+
+ +

+Definition at line 433 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_EltSize, NL3D::CQuadGrid< T >::_NodeListBlockMemory, NL3D::CQuadGrid< T >::clear(), NLMISC::getPowerOf2(), nlassert, size, and uint. +

+Referenced by NL3D::CMiniCol::CMiniCol(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CShadowPolyReceiver::CShadowPolyReceiver(), and NL3D::CZoneLighter::makeQuadGridFromWaterShapes(). +

+

00434 {
+00435         clear();
+00436 
+00437         nlassert(NLMISC::isPowerOf2(size));
+00438         nlassert(size<=32768);
+00439         _SizePower= NLMISC::getPowerOf2(size);
+00440         _Size=1<<_SizePower;
+00441         _Grid.resize(_Size*_Size, CQuadNode(&_NodeListBlockMemory));
+00442 
+00443         nlassert(eltSize>0);
+00444         _EltSize= eltSize;
+00445 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::end (   ) 
+
+ + + + + +
+   + + +

+Return the end iterator of the selected element list. begin and end are valid till the next insert. Speed is in O(1) +

+Definition at line 646 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::CIterator. +

+Referenced by NL3D::CLightingManager::addDynamicLight(), NL3D::CStaticQuadGrid< T >::build(), NL3D::CQuadGrid< T >::clear(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CQuadGrid< T >::erase(), NL3D::CShadowPolyReceiver::getCameraCollision(), NL3D::CLightingManager::getDynamicPointLightList(), NL3D::CMiniCol::getFaces(), NL3D::CMiniCol::getGroundNormal(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CShadowPolyReceiver::removeTriangle(), NL3D::CShadowPolyReceiver::render(), and NL3D::CMiniCol::snapToGround(). +

+

00647 {
+00648         return CIterator(NULL);
+00649 }
+
+

+ + + + +
+ + + + + + + + + + + + + +
+template<class T>
CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::erase ( CIterator  it  ) 
+
+ + + + + +
+   + + +

+Erase an interator from the container Speed is in O(1 * L*H) where L*H is the number of squares surrounded by the element

+

Parameters:
+ + +
it is the iterator to erase.
+
+
Returns:
if element is currently selected, the next selected element is returned, (or end()). if the element is not selected, end() is returned.
+ +

+Definition at line 468 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_NodeBlockMemory, NL3D::CQuadGrid< T >::CIterator, NL3D::CQuadGrid< T >::end(), NLMISC::CBlockMemory< CNode >::free(), NL3D::CQuadGrid< T >::CBaseNode::Next, NL3D::CQuadGrid< T >::CQuadNode::Nodes, NL3D::CQuadGrid< T >::CBaseNode::Prev, NL3D::CQuadGrid< T >::CBaseNode::Selected, sint, x, NL3D::CQuadGrid< T >::CNode::x0, NL3D::CQuadGrid< T >::CNode::x1, y, NL3D::CQuadGrid< T >::CNode::y0, and NL3D::CQuadGrid< T >::CNode::y1. +

+Referenced by NL3D::CQuadGrid< T >::clear(), NL3D::CMiniCol::removeLandScapePart(), and NL3D::CShadowPolyReceiver::removeTriangle(). +

+

00469 {
+00470         sint    x,y;
+00471         CNode   *ptr= it._Ptr;
+00472 
+00473         if(!ptr)
+00474                 return end();
+00475 
+00476         // First erase all references to it.
+00477         //==================================
+00478         for(y= ptr->y0;y<ptr->y1;y++)
+00479         {
+00480                 sint    xe,ye;
+00481                 ye= y &(_Size-1);
+00482                 for(x= ptr->x0;x<ptr->x1;x++)
+00483                 {
+00484                         xe= x &(_Size-1);
+00485                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00486                         typename NLMISC::CSTLBlockList<CNode*>::iterator        itNode;
+00487                         for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00488                         {
+00489                                 if((*itNode)==ptr)
+00490                                 {
+00491                                         quad.Nodes.erase(itNode);
+00492                                         break;
+00493                                 }
+00494                         }
+00495                 }
+00496         }
+00497 
+00498         // Then delete it..., and update selection linked list.
+00499         //=====================================================
+00500         // remove it from _SelectedList or _UnSelectedList
+00501         CBaseNode       *next= NULL;
+00502         next= ptr->Next;
+00503         if(next)
+00504                 next->Prev=ptr->Prev;
+00505         ptr->Prev->Next= next;
+00506         // if not selected, then must return NULL
+00507         if(!ptr->Selected)
+00508                 next= NULL;
+00509         // delete the object.
+00510         _NodeBlockMemory.free(ptr);
+00511 
+00512 
+00513         return CIterator((CNode*)next);
+00514 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
const NLMISC::CMatrix& NL3D::CQuadGrid< T >::getBasis (   )  const [inline]
+
+ + + + + +
+   + + +

+Change the base matrix of the quad grid. For exemple this code init the grid tree in the plane XZ: 

 CQuadGrid                      grid;
+ 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 grid
+
+ +

+Definition at line 119 of file 3d/quad_grid.h. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(). +

+

00119 {return _ChangeBasis;}
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
float NL3D::CQuadGrid< T >::getEltSize (   )  const [inline]
+
+ + + + + +
+   + + +

+Change the base matrix of the quad grid. For exemple this code init the grid tree in the plane XZ: 

 CQuadGrid                      grid;
+ 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 grid
+
+ +

+Definition at line 121 of file 3d/quad_grid.h. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(). +

+

00121 {return _EltSize;}
+
+

+ + + + +
+ + + + + + + + + + + + + +
+template<class T>
uint NL3D::CQuadGrid< T >::getSize ( void   )  const [inline]
+
+ + + + + +
+   + + +

+Change the base matrix of the quad grid. For exemple this code init the grid tree in the plane XZ: 

 CQuadGrid                      grid;
+ 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 grid
+
+ +

+Definition at line 120 of file 3d/quad_grid.h. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(). +

+

00120 {return _Size;}
+
+

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

+Insert a new element in the container. Speed is in O(1 * L*H) where L*H is the number of squares surrounded by the element

+Warning! : bboxmin and bboxmax are multiplied by matrix setuped by changeBase. This work for any matrix with 90deg rotations (min and max are recomputed internally), but not with any rotation (43° ...) because of the nature of AABBox. To do this correclty you should compute the bbox min and max in the basis given in changeBase, and insert() with multiplying min and max with inverse of this basis. eg: CMatrix base= getSomeBase(); CMatrix invBase= base.inverted(); // create quadGrid. CQuadGrid<CTriangle> quadGrid; quadGrid.changeBase(base); quadGrid.create(...); // Insert a triangle tri correctly CAABBox bbox; bbox.setCenter(base * tri.V0); bbox.extend(base * tri.V1); bbox.extend(base * tri.V2); quadGrid.insert(invBase*bbox.getMin(), invBase*bbox.getMax(), tri);

+

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 516 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_ChangeBasis, NL3D::CQuadGrid< T >::_NodeBlockMemory, NL3D::CQuadGrid< T >::_UnSelectedList, NLMISC::CBlockMemory< CNode >::allocate(), NL3D::CQuadGrid< T >::CIterator, NL3D::CQuadGrid< T >::CNode::Elt, NL3D::CQuadGrid< T >::linkToRoot(), NL3D::CQuadGrid< T >::CQuadNode::Nodes, NL3D::CQuadGrid< T >::CBaseNode::Selected, NL3D::CQuadGrid< T >::selectQuads(), sint, x, NL3D::CQuadGrid< T >::CNode::x0, NL3D::CQuadGrid< T >::CNode::x1, y, NL3D::CQuadGrid< T >::CNode::y0, and NL3D::CQuadGrid< T >::CNode::y1. +

+Referenced by NL3D::CMiniCol::addFaces(), NL3D::CShadowPolyReceiver::addTriangle(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), and NL3D::CZoneLighter::makeQuadGridFromWaterShapes(). +

+

00517 {
+00518         CVector         bmin,bmax;
+00519         bmin= _ChangeBasis*bboxmin;
+00520         bmax= _ChangeBasis*bboxmax;
+00521 
+00522         // init the object.
+00523         CNode   *ptr= _NodeBlockMemory.allocate();
+00524         ptr->Elt= val;
+00525         // Link to _Unselected list.
+00526         linkToRoot(_UnSelectedList, ptr);
+00527         // mark as not selected.
+00528         ptr->Selected= false;
+00529 
+00530 
+00531         // Find which quad include the object.
+00532         //===================================
+00533         sint    x0,y0;
+00534         sint    x1,y1;
+00535         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00536 
+00537         ptr->x0= x0;
+00538         ptr->x1= x1;
+00539         ptr->y0= y0;
+00540         ptr->y1= y1;
+00541 
+00542         // Then for all of them, insert the node in their list.
+00543         //=====================================================
+00544         sint    x,y;
+00545         for(y= ptr->y0;y<ptr->y1;y++)
+00546         {
+00547                 sint    xe,ye;
+00548                 ye= y &(_Size-1);
+00549                 for(x= ptr->x0;x<ptr->x1;x++)
+00550                 {
+00551                         xe= x &(_Size-1);
+00552                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00553                         quad.Nodes.push_back(ptr);
+00554                 }
+00555         }
+00556 
+00557         return CIterator(ptr);
+00558 }
+
+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::linkToRoot ( CBaseNode &  root,
CBaseNode *  ptr
)  [inline, private]
+
+ + + + + +
+   + + +

+ +

+Definition at line 251 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< CWaterShape * >::addToSelection(), NL3D::CQuadGrid< T >::clearSelection(), NL3D::CQuadGrid< T >::insert(), and NL3D::CQuadGrid< T >::selectAll(). +

+

00252         {
+00253                 ptr->Prev= &root;
+00254                 ptr->Next= root.Next;
+00255                 ptr->Prev->Next= ptr;
+00256                 if(ptr->Next)
+00257                         ptr->Next->Prev= ptr;
+00258         }
+
+

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

+Select element intersecting a bounding box. Clear the selection first. Speed is in O(Nelts * L*H), where L*H is the number of squares surrounded by the selection

+

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 613 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_ChangeBasis, NL3D::CQuadGrid< T >::addQuadNodeToSelection(), NL3D::CQuadGrid< T >::clearSelection(), NL3D::CQuadGrid< T >::selectQuads(), sint, x, and y. +

+Referenced by NL3D::CStaticQuadGrid< T >::build(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CShadowPolyReceiver::getCameraCollision(), NL3D::CLightingManager::getDynamicPointLightList(), NL3D::CMiniCol::getFaces(), NL3D::CMiniCol::getGroundNormal(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CShadowPolyReceiver::render(), and NL3D::CMiniCol::snapToGround(). +

+

00614 {
+00615         CVector         bmin,bmax;
+00616         bmin= _ChangeBasis*bboxmin;
+00617         bmax= _ChangeBasis*bboxmax;
+00618 
+00619         clearSelection();
+00620 
+00621         // What are the quads to access?
+00622         sint    x0,y0;
+00623         sint    x1,y1;
+00624         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00625 
+00626         sint    x,y;
+00627         for(y= y0;y<y1;y++)
+00628         {
+00629                 sint    xe,ye;
+00630                 ye= y &(_Size-1);
+00631                 for(x= x0;x<x1;x++)
+00632                 {
+00633                         xe= x &(_Size-1);
+00634                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00635                         addQuadNodeToSelection(quad);
+00636                 }
+00637         }
+00638 
+00639 }
+
+

+ + + + +
+ + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::selectAll (   ) 
+
+ + + + + +
+   + + +

+Select all the container. Speed is in O(Nelts) +

+Definition at line 589 of file 3d/quad_grid.h. +

+References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::_UnSelectedList, NL3D::CQuadGrid< T >::linkToRoot(), NL3D::CQuadGrid< T >::CBaseNode::Next, and NL3D::CQuadGrid< T >::CBaseNode::Selected. +

+Referenced by NL3D::CQuadGrid< T >::clear(). +

+

00590 {
+00591         // This is the opposite of clearSelection(). get all that are in _UnSelectedList,
+00592         // and put them in _SelectedList
+00593         CBaseNode       *ptr= _UnSelectedList.Next;
+00594         while(ptr)
+00595         {
+00596                 // next selected.
+00597                 CBaseNode       *nextUnSelected= ptr->Next;
+00598 
+00599                 // Link to _Selected list.
+00600                 linkToRoot(_SelectedList, ptr);
+00601 
+00602                 // mark as selected.
+00603                 ptr->Selected= true;
+00604 
+00605                 // next.
+00606                 ptr= nextUnSelected;
+00607         }
+00608 
+00609         // the Unselected list is now empty.
+00610         _UnSelectedList.Next= NULL;
+00611 }
+
+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+template<class T>
void NL3D::CQuadGrid< T >::selectQuads ( CVector  bmin,
CVector  bmax,
sint &  x0,
sint &  x1,
sint &  y0,
sint &  y1
)  [inline, private]
+
+ + + + + +
+   + + +

+ +

+Definition at line 261 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::insert(), and NL3D::CQuadGrid< T >::select(). +

+

00262         {
+00263                 CVector         bminp, bmaxp;
+00264                 bminp= bmin;
+00265                 bmaxp= bmax;
+00266                 bmin.minof(bminp, bmaxp);
+00267                 bmax.maxof(bminp, bmaxp);
+00268                 bmin/= _EltSize;
+00269                 bmax/= _EltSize;
+00270                 x0= (sint)(floor(bmin.x));
+00271                 x1= (sint)(ceil(bmax.x));
+00272                 y0= (sint)(floor(bmin.y));
+00273                 y1= (sint)(ceil(bmax.y));
+00274 
+00275                 // Very special case where the bbox.size==0 AND position is JUST on an edge of a case.
+00276                 if(x0==x1)
+00277                         x1++;
+00278                 if(y0==y1)
+00279                         y1++;
+00280 
+00281                 // Manage tiling.
+00282                 if(x1-x0>=_Size)
+00283                         x0=0, x1= _Size;
+00284                 else
+00285                 {
+00286                         x0&= _Size-1;
+00287                         x1&= _Size-1;
+00288                         if(x1<=x0)
+00289                                 x1+=_Size;
+00290                 }
+00291                 if(y1-y0>=_Size)
+00292                         y0=0, y1= _Size;
+00293                 else
+00294                 {
+00295                         y0&= _Size-1;
+00296                         y1&= _Size-1;
+00297                         if(y1<=y0)
+00298                                 y1+=_Size;
+00299                 }
+00300         }
+
+

Friends And Related Function Documentation

+

+ + + + +
+ + + + + +
+template<class T>
friend class CIterator [friend] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 81 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::begin(), NL3D::CQuadGrid< T >::end(), NL3D::CQuadGrid< T >::erase(), and NL3D::CQuadGrid< T >::insert().

+

Field Documentation

+

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

+ +

+Definition at line 238 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::changeBase(), NL3D::CQuadGrid< T >::CQuadGrid(), NL3D::CQuadGrid< T >::insert(), and NL3D::CQuadGrid< T >::select().

+

+ + + + +
+ + + + + +
+template<class T>
float NL3D::CQuadGrid< T >::_EltSize [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 237 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::CQuadGrid(), and NL3D::CQuadGrid< T >::create().

+

+ + + + +
+ + + + + +
+template<class T>
std::vector<CQuadNode> NL3D::CQuadGrid< T >::_Grid [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 234 of file 3d/quad_grid.h.

+

+ + + + +
+ + + + + +
+template<class T>
NLMISC::CBlockMemory<CNode> NL3D::CQuadGrid< T >::_NodeBlockMemory [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 243 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::erase(), and NL3D::CQuadGrid< T >::insert().

+

+ + + + +
+ + + + + +
+template<class T>
NLMISC::CBlockMemory<CNode*, false> NL3D::CQuadGrid< T >::_NodeListBlockMemory [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 245 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::create().

+

+ + + + +
+ + + + + +
+template<class T>
CBaseNode NL3D::CQuadGrid< T >::_SelectedList [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 240 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::begin(), NL3D::CQuadGrid< T >::clear(), NL3D::CQuadGrid< T >::clearSelection(), and NL3D::CQuadGrid< T >::selectAll().

+

+ + + + +
+ + + + + +
+template<class T>
sint NL3D::CQuadGrid< T >::_Size [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 235 of file 3d/quad_grid.h.

+

+ + + + +
+ + + + + +
+template<class T>
sint NL3D::CQuadGrid< T >::_SizePower [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 236 of file 3d/quad_grid.h.

+

+ + + + +
+ + + + + +
+template<class T>
CBaseNode NL3D::CQuadGrid< T >::_UnSelectedList [private] +
+
+ + + + + +
+   + + +

+ +

+Definition at line 241 of file 3d/quad_grid.h. +

+Referenced by NL3D::CQuadGrid< T >::clear(), NL3D::CQuadGrid< T >::clearSelection(), NL3D::CQuadGrid< T >::insert(), and NL3D::CQuadGrid< T >::selectAll().

+

The documentation for this class was generated from the following file: +
Generated on Tue Mar 16 07:33:41 2004 for NeL by + +doxygen +1.3.6
+ + -- cgit v1.2.1