00001
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include "std3d.h"
00027
00028 #include "3d/tess_face_priority_list.h"
00029 #include "nel/misc/debug.h"
00030 #include <math.h>
00031 #include "3d/tessellation.h"
00032 #include "3d/fast_floor.h"
00033
00034
00035 using namespace NLMISC;
00036 using namespace std;
00037
00038 namespace NL3D
00039 {
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 void CTessFacePListNode::linkInPList(CTessFacePListNode &root)
00050 {
00051
00052 _PrecTessFaceInPList->_NextTessFaceInPList= _NextTessFaceInPList;
00053 _NextTessFaceInPList->_PrecTessFaceInPList= _PrecTessFaceInPList;
00054
00055
00056 _PrecTessFaceInPList= &root;
00057 _NextTessFaceInPList= root._NextTessFaceInPList;
00058
00059 root._NextTessFaceInPList->_PrecTessFaceInPList= this;
00060 root._NextTessFaceInPList= this;
00061
00062
00063
00064
00065
00066
00067
00068 }
00069
00070
00071 void CTessFacePListNode::unlinkInPList()
00072 {
00073
00074
00075
00076
00077
00078 _PrecTessFaceInPList->_NextTessFaceInPList= _NextTessFaceInPList;
00079 _NextTessFaceInPList->_PrecTessFaceInPList= _PrecTessFaceInPList;
00080
00081
00082 _PrecTessFaceInPList= this;
00083 _NextTessFaceInPList= this;
00084 }
00085
00086
00087
00088 void CTessFacePListNode::appendPList(CTessFacePListNode &root)
00089 {
00090
00091 if( root._NextTessFaceInPList != &root )
00092 {
00093
00094 if( _NextTessFaceInPList==this )
00095 {
00096
00097 _PrecTessFaceInPList= root._PrecTessFaceInPList;
00098 _NextTessFaceInPList= root._NextTessFaceInPList;
00099
00100 _PrecTessFaceInPList->_NextTessFaceInPList= this;
00101 _NextTessFaceInPList->_PrecTessFaceInPList= this;
00102 }
00103
00104 else
00105 {
00106 CTessFacePListNode *first= root._NextTessFaceInPList;
00107 CTessFacePListNode *last= root._PrecTessFaceInPList;
00108 CTessFacePListNode *prec= this;
00109 CTessFacePListNode *next= _NextTessFaceInPList;
00110
00111 next->_PrecTessFaceInPList= last;
00112 prec->_NextTessFaceInPList= first;
00113
00114 last->_NextTessFaceInPList= next;
00115 first->_PrecTessFaceInPList= prec;
00116 }
00117
00118
00119 root._PrecTessFaceInPList= &root;
00120 root._NextTessFaceInPList= &root;
00121 }
00122 }
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134 CTessFacePriorityList::CTessFacePriorityList()
00135 {
00136 _OODistStep= 1;
00137 _NEntries= 0;
00138 _MaskEntries= 0;
00139 _EntryModStart= 0;
00140 _NumQuadrant= 0;
00141 }
00142
00143
00144 CTessFacePriorityList::~CTessFacePriorityList()
00145 {
00146 clear();
00147 }
00148
00149
00150 void CTessFacePriorityList::init(float distStep, uint numEntries, float distMaxMod, uint numQuadrant)
00151 {
00152 uint i;
00153 nlassert(distStep>0);
00154 nlassert(numEntries>0 && isPowerOf2(numEntries));
00155 nlassert(distMaxMod<1);
00156 nlassert(numQuadrant==0 || (numQuadrant>=4 && isPowerOf2(numQuadrant)) );
00157
00158
00159 clear();
00160
00161
00162 _OODistStep= 1.0f / distStep;
00163 _NEntries= numEntries;
00164 _MaskEntries= _NEntries-1;
00165 _EntryModStart= (uint)ceil(distMaxMod * _NEntries);
00166 NLMISC::clamp(_EntryModStart, 0U, _NEntries-1);
00167 _NumQuadrant= numQuadrant;
00168
00169
00170 _RollingTables.resize(1+_NumQuadrant);
00171 for(i=0;i<_RollingTables.size();i++)
00172 {
00173 _RollingTables[i].init(_NEntries);
00174
00175 if(i>=1)
00176 {
00177 uint idx= i-1;
00178
00179 float angle= float(2*Pi*idx)/_NumQuadrant;
00180 CMatrix mat;
00181 mat.rotateZ(angle);
00182
00183 _RollingTables[i].QuadrantDirection= mat.getJ();
00184 }
00185 }
00186
00187
00188 const uint quarterLut[4]= {1,3,2,0};
00189 _MaskQuadrant= _NumQuadrant-1;
00190 for(i=0;i<4;i++)
00191 {
00192
00193 uint idx= quarterLut[i];
00194 _QuarterQuadrantStart[idx]= i*_NumQuadrant/4;
00195 _QuarterQuadrantEnd[idx]= 1+ (i+1)*_NumQuadrant/4;
00196 }
00197
00198 }
00199
00200
00201 void CTessFacePriorityList::clear()
00202 {
00203
00204 _RollingTables.clear();
00205 }
00206
00207
00208
00209 uint CTessFacePriorityList::selectQuadrant(const CVector &direction)
00210 {
00211
00212 if(_NumQuadrant==0)
00213 return 0;
00214
00215
00216
00217 uint quarterId;
00218 #ifdef NL_OS_WINDOWS
00219 __asm
00220 {
00221 mov esi, direction
00222 mov eax, [esi]direction.y
00223 mov ebx, [esi]direction.x
00224
00225 and eax, 0x80000000
00226 and ebx, 0x80000000
00227
00228 shr eax, 30
00229 shr ebx, 31
00230
00231 or eax, ebx
00232 mov quarterId, eax
00233 }
00234 #else
00235 if(direction.y>0)
00236 {
00237 if(direction.x>0) quarterId= 0;
00238 else quarterId= 1;
00239 }
00240 else
00241 {
00242 if(direction.x>0) quarterId= 2;
00243 else quarterId= 3;
00244 }
00245 #endif
00246
00247
00248 uint quadrantStart= _QuarterQuadrantStart[quarterId];
00249 uint quadrantEnd= _QuarterQuadrantEnd[quarterId];
00250
00251
00252
00253 float bestDirPs= -FLT_MAX;
00254 uint bestQuadrant= 0;
00255 for(uint i=quadrantStart;i<quadrantEnd;i++)
00256 {
00257
00258 uint quadrantId= (i&_MaskQuadrant)+1;
00259
00260 float ps= direction*_RollingTables[i].QuadrantDirection;
00261 if(ps>bestDirPs)
00262 {
00263 bestDirPs= ps;
00264 bestQuadrant= i;
00265 }
00266 }
00267
00268 return bestQuadrant;
00269 }
00270
00271
00272
00273 void CTessFacePriorityList::insert(uint quadrantId, float distance, CTessFace *value)
00274 {
00275
00276 nlassert(_NEntries>0 && quadrantId<_RollingTables.size());
00277
00278
00279 distance*= _OODistStep;
00280
00281
00282 CRollingTable &rollTable= _RollingTables[quadrantId];
00283
00284
00285 sint idInsert;
00286 if(distance<=0)
00287 idInsert= 0;
00288 else
00289 {
00290
00291 idInsert= OptFastFloor(distance + rollTable.Remainder);
00292 }
00293 idInsert= std::max(0, idInsert);
00294
00295
00296
00297 if(idInsert>(sint)_MaskEntries)
00298 {
00299
00300 uint nMod= _NEntries - _EntryModStart;
00301
00302 idInsert= idInsert - _MaskEntries;
00303
00304 idInsert= idInsert % nMod;
00305 idInsert= _EntryModStart + idInsert;
00306 }
00307
00308
00309 rollTable.insertInRollTable(idInsert, value);
00310 }
00311
00312
00313
00314 void CTessFacePriorityList::shift(const CVector &direction, CTessFacePListNode &pulledElements)
00315 {
00316
00317 nlassert(_NEntries>0);
00318
00319 pulledElements.unlinkInPList();
00320
00321
00322 for(uint i=0;i<_RollingTables.size();i++)
00323 {
00324 CRollingTable &rollTable= _RollingTables[i];
00325 float shiftDistance;
00326
00327
00328 if(i==0)
00329 {
00330 shiftDistance= direction.norm();
00331 }
00332
00333 else
00334 {
00335 shiftDistance= direction*rollTable.QuadrantDirection;
00336
00337 shiftDistance= max(0.f, shiftDistance);
00338 }
00339
00340
00341 shiftDistance*= _OODistStep;
00342
00343
00344
00345 pulledElements.appendPList(rollTable.getRollTableEntry(0));
00346
00347
00348 rollTable.Remainder+= shiftDistance;
00349
00350 uint entryShift= (uint)floor(rollTable.Remainder);
00351 rollTable.Remainder= rollTable.Remainder - entryShift;
00352
00353
00354 if( entryShift >= _NEntries)
00355 {
00356 entryShift= _NEntries;
00357
00358 rollTable.Remainder= 0;
00359 }
00360
00361
00362 rollTable.shiftEntries(entryShift, pulledElements);
00363 }
00364 }
00365
00366
00367
00368 void CTessFacePriorityList::shiftAll(CTessFacePListNode &pulledElements)
00369 {
00370
00371 nlassert(_NEntries>0);
00372
00373 pulledElements.unlinkInPList();
00374
00375
00376 for(uint i=0;i<_RollingTables.size();i++)
00377 {
00378
00379 uint entryShift= _NEntries;
00380 _RollingTables[i].Remainder= 0;
00381
00382
00383 _RollingTables[i].shiftEntries(entryShift, pulledElements);
00384 }
00385 }
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395 CTessFacePriorityList::CRollingTable::CRollingTable()
00396 {
00397 _EntryStart= 0;
00398 _NEntries= 0;
00399 _MaskEntries= 0;
00400 Remainder= 0;
00401 }
00402
00403
00404 CTessFacePriorityList::CRollingTable::~CRollingTable()
00405 {
00406 clearRollTable();
00407 }
00408
00409
00410
00411 void CTessFacePriorityList::CRollingTable::init(uint numEntries)
00412 {
00413 _EntryStart= 0;
00414 _NEntries= numEntries;
00415 _MaskEntries= _NEntries-1;
00416 Remainder= 0;
00417 _Entries.resize(numEntries);
00418 }
00419
00420
00421
00422 void CTessFacePriorityList::CRollingTable::insertInRollTable(uint entry, CTessFace *value)
00423 {
00424 CTessFacePListNode &root= _Entries[ (entry + _EntryStart) & _MaskEntries ];
00425
00426
00427 value->linkInPList(root);
00428 }
00429
00430
00431 CTessFacePListNode &CTessFacePriorityList::CRollingTable::getRollTableEntry(uint entry)
00432 {
00433 CTessFacePListNode &root= _Entries[ (entry + _EntryStart) & _MaskEntries ];
00434 return root;
00435 }
00436
00437
00438 void CTessFacePriorityList::CRollingTable::clearRollTableEntry(uint entry)
00439 {
00440 CTessFacePListNode &root= _Entries[ (entry + _EntryStart) & _MaskEntries ];
00441
00442
00443 while( root.nextInPList() != &root )
00444 {
00445
00446 CTessFacePListNode *node= root.nextInPList();
00447 node->unlinkInPList();
00448 }
00449 }
00450
00451
00452 void CTessFacePriorityList::CRollingTable::shiftRollTable(uint shiftEntry)
00453 {
00454
00455 for(uint i=0; i<shiftEntry; i++)
00456 {
00457 clearRollTableEntry(i);
00458 }
00459
00460 _EntryStart+= shiftEntry;
00461 _EntryStart= _EntryStart & _MaskEntries;
00462 }
00463
00464
00465 void CTessFacePriorityList::CRollingTable::clearRollTable()
00466 {
00467 for(uint i=0; i<_NEntries; i++)
00468 {
00469 clearRollTableEntry(i);
00470 }
00471 _EntryStart= 0;
00472
00473 Remainder= 0;
00474 }
00475
00476
00477 void CTessFacePriorityList::CRollingTable::shiftEntries(uint entryShift, CTessFacePListNode &pulledElements)
00478 {
00479 if(entryShift>0)
00480 {
00481
00482 for(uint i=0; i<entryShift; i++)
00483 {
00484
00485 pulledElements.appendPList(getRollTableEntry(i));
00486 }
00487
00488
00489 shiftRollTable(entryShift);
00490 }
00491 }
00492
00493
00494
00495
00496 }