NL3D::CTessFacePriorityList Class Reference

#include <tess_face_priority_list.h>

---

Detailed Description

This class manage a Priority list of elements, inserted with a "distance". The priority list can be shifted, so elements with new distance <=0 are pulled from the priority list.

NB: it works quite well if you have (as example) a distStep of 1, and you shift only with value of 0.01 etc.., because it manages a "Remainder system", which do the good stuff. How does it works? in essence, it is a Rolling table, with 1+ shift back when necessary (maybe not at each shift()).

Additionally, it includes a "2D quadrant" notion. If you use this class to know when the "camera" enters a specific area, then Quadrants help you because the notion of direction is kept. Only the XY plane is used here.

Instead, if you use this class to know when the "camera" leaves a specific area, then the quadrant notion is not interesting since the camera can leave the area in any direction...

Author:

Lionel Berenguier

Nevrax France

Date:

2001

Definition at line 112 of file tess_face_priority_list.h.

Public Member Functions
void	clear ()
	CTessFacePriorityList ()
	Constructor.
const NLMISC::CVector &	getQuadrantDirection (uint quadrantId) const
void	init (float distStep, uint numEntries, float distMaxMod, uint numQuadrant)
void	insert (uint quadrantId, float distance, CTessFace *value)
uint	selectQuadrant (const NLMISC::CVector &direction)
void	shift (const NLMISC::CVector &direction, CTessFacePListNode &pulledElements)
void	shiftAll (CTessFacePListNode &pulledElements)
	~CTessFacePriorityList ()
Private Attributes
uint	_EntryModStart
uint	_MaskEntries
uint	_MaskQuadrant
uint	_NEntries
uint	_NumQuadrant
float	_OODistStep
uint	_QuarterQuadrantEnd [4]
uint	_QuarterQuadrantStart [4]
float	_Remainder
The rolling tables
std::vector< CRollingTable >	_RollingTables

---

Constructor & Destructor Documentation

NL3D::CTessFacePriorityList::CTessFacePriorityList (   )

Constructor. Definition at line 134 of file tess_face_priority_list.cpp. References _EntryModStart, _MaskEntries, _NEntries, _NumQuadrant, and _OODistStep. { _OODistStep= 1; _NEntries= 0; _MaskEntries= 0; _EntryModStart= 0; _NumQuadrant= 0; }

NL3D::CTessFacePriorityList::~CTessFacePriorityList (   )

Definition at line 144 of file tess_face_priority_list.cpp. References clear(). { clear(); }

---

Member Function Documentation

void NL3D::CTessFacePriorityList::clear (   )

Clear the priority list. All elements are removed. NB: for convenience, the remainder is reset. Definition at line 201 of file tess_face_priority_list.cpp. References _RollingTables. Referenced by init(), and ~CTessFacePriorityList(). { // just clear all the rolling tables. _RollingTables.clear(); }

const NLMISC::CVector& NL3D::CTessFacePriorityList::getQuadrantDirection (  uint  quadrantId  )  const [inline]

get the quadrant dir associated to the Id. Undefined if 0. Definition at line 145 of file tess_face_priority_list.h. References _RollingTables, and uint. Referenced by NL3D::CTessFace::updateRefineSplit(). {return _RollingTables[quadrantId].QuadrantDirection;}

void NL3D::CTessFacePriorityList::init (  float  distStep, uint  numEntries, float  distMaxMod, uint  numQuadrant )

Clear and Init the priority list. It reserve (numQuadrants+1) Rolling table of numEntries entries. Parameters: numEntries  gives the number of entries and MUST be powerOf2. distMax= numEntries*distStep distMaxMod is important for performance and MUST be < 1. eg: distMaxMod= 0.8. It is a trick to avoid the "Too Far Priority problem". Imagine you have a setup such distMax= 1000, and you insert(1100, an element). If we clamp to the max, it may be a bad thing, because ALL elements inserted after 1000 will be poped in one shift(), after 1000 shift(1) for example. To avoid this, if distMaxMod==0.8, then insert(1050) will really insert at 850, so elements will be poped not as the same time (for the extra cost of some elements get poped too early...). numQuadrant  set 0 if don't want to support quadrant notion. else set >=4 and a power of 2 (else nlassert) Definition at line 150 of file tess_face_priority_list.cpp. References _EntryModStart, _MaskEntries, _MaskQuadrant, _NEntries, _NumQuadrant, _OODistStep, _QuarterQuadrantEnd, _QuarterQuadrantStart, _RollingTables, NLMISC::clamp(), clear(), NLMISC::CMatrix::getJ(), NLMISC::isPowerOf2(), nlassert, NLMISC::Pi, NLMISC::CMatrix::rotateZ(), and uint. Referenced by NL3D::CLandscape::CLandscape(). { uint i; nlassert(distStep>0); nlassert(numEntries>0 && isPowerOf2(numEntries)); nlassert(distMaxMod<1); nlassert(numQuadrant==0 || (numQuadrant>=4 && isPowerOf2(numQuadrant)) ); // clear the prioriy list before. clear(); // setup _OODistStep= 1.0f / distStep; _NEntries= numEntries; _MaskEntries= _NEntries-1; _EntryModStart= (uint)ceil(distMaxMod * _NEntries); NLMISC::clamp(_EntryModStart, 0U, _NEntries-1); _NumQuadrant= numQuadrant; // Build the Rolling tables. _RollingTables.resize(1+_NumQuadrant); for(i=0;i<_RollingTables.size();i++) { _RollingTables[i].init(_NEntries); // setup the quadrant direction. NB: 0 not used since "Direction less rolling table" if(i>=1) { uint idx= i-1; // split evenly the plane with direction. float angle= float(2*Pi*idx)/_NumQuadrant; CMatrix mat; mat.rotateZ(angle); // setup the vector _RollingTables[i].QuadrantDirection= mat.getJ(); } } // Build Quarter Selection. In is in CCW order. Out: see selectQuadrant() const uint quarterLut[4]= {1,3,2,0}; _MaskQuadrant= _NumQuadrant-1; for(i=0;i<4;i++) { // Re-Order for faster ASM acces. see selectQuadrant() uint idx= quarterLut[i]; _QuarterQuadrantStart[idx]= i*_NumQuadrant/4; _QuarterQuadrantEnd[idx]= 1+ (i+1)*_NumQuadrant/4; } }

void NL3D::CTessFacePriorityList::insert (  uint  quadrantId, float  distance, CTessFace *  value )

Insert an element at a given distance, and in a given quadrant. Insert at the closest step. eg insert(1.2, elt) will insert elt at entry 1 (assuming distStep==1 here). Special case: if distance<=0, it is ensured that at each shift(), the element will be pulled. NB: manage correctly the entry where it is inserted, according to the Remainder system. USE OptFastFloor if distance>0 => MUST be enclosed in OptFastFloorBegin/OptFastFloorEnd() Parameters: quadrantId  set 0 if you want to insert in the "direction less" rolling table. else set the value returned by selectQuadrant() distance  if quadrantId==0, distance should be the norm()-SphereSize, else it shoudl be direction*quadrantDirection-SphereSize. Definition at line 273 of file tess_face_priority_list.cpp. References _EntryModStart, _MaskEntries, _NEntries, _OODistStep, _RollingTables, NL3D::CTessFacePriorityList::CRollingTable::insertInRollTable(), nlassert, NLMISC::OptFastFloor(), NL3D::CTessFacePriorityList::CRollingTable::Remainder, sint, uint, and value. Referenced by NL3D::CTessFace::doMerge(), NL3D::CTessFace::split(), NL3D::CTessFace::splitRectangular(), NL3D::CTessFace::updateRefineMerge(), and NL3D::CTessFace::updateRefineSplit(). { // plist must be inited. nlassert(_NEntries>0 && quadrantId<_RollingTables.size()); // First, setup in our basis. distance*= _OODistStep; // Insert int the good quadrant CRollingTable &rollTable= _RollingTables[quadrantId]; // Then, look where we must insert it. sint idInsert; if(distance<=0) idInsert= 0; else { // Must insert so we can't miss it when a shift occurs (=> floor). idInsert= NLMISC::OptFastFloor(distance + rollTable.Remainder); } idInsert= std::max(0, idInsert); // Manage Mod. // If the element to insert must be inserted at distance > distMax. if(idInsert>(sint)_MaskEntries) { // Compute number of entries to apply the mod. uint nMod= _NEntries - _EntryModStart; // Of how many entries are we too far. idInsert= idInsert - _MaskEntries; // Then loop in the interval [_EntryModStart, _NEntries[. idInsert= idInsert % nMod; idInsert= _EntryModStart + idInsert; } // insert in the Roll Table. rollTable.insertInRollTable(idInsert, value); }

uint NL3D::CTessFacePriorityList::selectQuadrant (  const NLMISC::CVector &  direction  )

prior to insert an element with a direction notion, select which quadrant according to the direction Camera -> center of interest. Returns: 0 if no quadrant available, else the quadrant id Definition at line 209 of file tess_face_priority_list.cpp. References _MaskQuadrant, _NumQuadrant, _QuarterQuadrantEnd, _QuarterQuadrantStart, _RollingTables, uint, NLMISC::CVector::x, and NLMISC::CVector::y. Referenced by NL3D::CTessFace::updateRefineSplit(). { // if numQuadrants=0, ret 0. if(_NumQuadrant==0) return 0; // select the quarter. uint quarterId; #ifdef NL_OS_WINDOWS __asm { mov esi, direction mov eax, [esi]direction.y mov ebx, [esi]direction.x // read the sign and eax, 0x80000000 and ebx, 0x80000000 // set the bit shr eax, 30 shr ebx, 31 // assemble or eax, ebx mov quarterId, eax } #else if(direction.y>0) { if(direction.x>0) quarterId= 0; else quarterId= 1; } else { if(direction.x>0) quarterId= 2; else quarterId= 3; } #endif // Run only the quadrants of the associated quarter. uint quadrantStart= _QuarterQuadrantStart[quarterId]; uint quadrantEnd= _QuarterQuadrantEnd[quarterId]; // For all quadrants of the quarter, return the best direction float bestDirPs= -FLT_MAX; uint bestQuadrant= 0; for(uint i=quadrantStart;i<quadrantEnd;i++) { // get the quadrant Id. Must mask for last (0). And Start at 1 in the _RollingTables. uint quadrantId= (i&_MaskQuadrant)+1; // Test with this quadrant float ps= direction*_RollingTables[i].QuadrantDirection; if(ps>bestDirPs) { bestDirPs= ps; bestQuadrant= i; } } return bestQuadrant; }

void NL3D::CTessFacePriorityList::shift (  const NLMISC::CVector &  direction, CTessFacePListNode &  pulledElements )

Shift the Priority list in a given direction. NB: for each rolling table, even if shiftDistance==0, all elements in the entry 0 are pulled out. pulledElements is the root of the list which will contains elements pulled from the list. Definition at line 314 of file tess_face_priority_list.cpp. References _NEntries, _OODistStep, _RollingTables, NL3D::CTessFacePListNode::appendPList(), NL3D::CTessFacePriorityList::CRollingTable::getRollTableEntry(), nlassert, NLMISC::CVector::norm(), NL3D::CTessFacePriorityList::CRollingTable::QuadrantDirection, NL3D::CTessFacePriorityList::CRollingTable::Remainder, NL3D::CTessFacePriorityList::CRollingTable::shiftEntries(), uint, and NL3D::CTessFacePListNode::unlinkInPList(). Referenced by NL3D::CLandscape::refine(). { // plist must be inited. nlassert(_NEntries>0); pulledElements.unlinkInPList(); // Shift all the rolling tables for(uint i=0;i<_RollingTables.size();i++) { CRollingTable &rollTable= _RollingTables[i]; float shiftDistance; // if quadrant 0, Direction less => get distance with Euler norm. if(i==0) { shiftDistance= direction.norm(); } // Else compute the effective distance we run to the plane. else { shiftDistance= direction*rollTable.QuadrantDirection; // For now, just clamp, but may be interesting to shift Back the rolling table !! shiftDistance= max(0.f, shiftDistance); } // First, setup in our basis. shiftDistance*= _OODistStep; // at least, fill OUT with elements of entry 0. // For all elements of the entry 0 of , pull them, and insert in result list. pulledElements.appendPList(rollTable.getRollTableEntry(0)); // shift. rollTable.Remainder+= shiftDistance; // If Remainder>=1, it means that we must shift the rolling table, and get elements deleted. uint entryShift= (uint)floor(rollTable.Remainder); rollTable.Remainder= rollTable.Remainder - entryShift; // shift full array?? if( entryShift >= _NEntries) { entryShift= _NEntries; // The entire array is pulled, _Remainder should get a good value. rollTable.Remainder= 0; } // If some real shift, do it. rollTable.shiftEntries(entryShift, pulledElements); } }

void NL3D::CTessFacePriorityList::shiftAll (  CTessFacePListNode &  pulledElements  )

Same as shift(), but shift all the array. Definition at line 368 of file tess_face_priority_list.cpp. References _NEntries, _RollingTables, nlassert, uint, and NL3D::CTessFacePListNode::unlinkInPList(). Referenced by NL3D::CLandscape::refine(). { // plist must be inited. nlassert(_NEntries>0); pulledElements.unlinkInPList(); // Do it for all rolling tables. for(uint i=0;i<_RollingTables.size();i++) { // The entire array is pulled, _Remainder should get a good value. uint entryShift= _NEntries; _RollingTables[i].Remainder= 0; // shift the entire array. _RollingTables[i].shiftEntries(entryShift, pulledElements); } }

---

Field Documentation

uint NL3D::CTessFacePriorityList::_EntryModStart [private]

Definition at line 187 of file tess_face_priority_list.h. Referenced by CTessFacePriorityList(), init(), and insert().

uint NL3D::CTessFacePriorityList::_MaskEntries [private]

Definition at line 186 of file tess_face_priority_list.h. Referenced by CTessFacePriorityList(), init(), and insert().

uint NL3D::CTessFacePriorityList::_MaskQuadrant [private]

Definition at line 190 of file tess_face_priority_list.h. Referenced by init(), and selectQuadrant().

uint NL3D::CTessFacePriorityList::_NEntries [private]

Definition at line 185 of file tess_face_priority_list.h. Referenced by CTessFacePriorityList(), init(), insert(), shift(), and shiftAll().

uint NL3D::CTessFacePriorityList::_NumQuadrant [private]

Definition at line 188 of file tess_face_priority_list.h. Referenced by CTessFacePriorityList(), init(), and selectQuadrant().

float NL3D::CTessFacePriorityList::_OODistStep [private]

Definition at line 184 of file tess_face_priority_list.h. Referenced by CTessFacePriorityList(), init(), insert(), and shift().

uint NL3D::CTessFacePriorityList::_QuarterQuadrantEnd[4] [private]

Definition at line 192 of file tess_face_priority_list.h. Referenced by init(), and selectQuadrant().

uint NL3D::CTessFacePriorityList::_QuarterQuadrantStart[4] [private]

Definition at line 191 of file tess_face_priority_list.h. Referenced by init(), and selectQuadrant().

float NL3D::CTessFacePriorityList::_Remainder [private]

Definition at line 183 of file tess_face_priority_list.h.

std::vector<CRollingTable> NL3D::CTessFacePriorityList::_RollingTables [private]

Definition at line 243 of file tess_face_priority_list.h. Referenced by clear(), getQuadrantDirection(), init(), insert(), selectQuadrant(), shift(), and shiftAll().

---

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

• tess_face_priority_list.h
• tess_face_priority_list.cpp

---