nevrax.org : docs

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+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 //      CTessFacePListNode
+00044 // ***************************************************************************
+00045 // ***************************************************************************
+00046 
+00047 
+00048 // ***************************************************************************
+00049 void            CTessFacePListNode::linkInPList(CTessFacePListNode      &root)
+00050 {
+00051         // unlink old list from me.
+00052         _PrecTessFaceInPList->_NextTessFaceInPList= _NextTessFaceInPList;
+00053         _NextTessFaceInPList->_PrecTessFaceInPList= _PrecTessFaceInPList;
+00054 
+00055         // link me to the list.
+00056         _PrecTessFaceInPList= &root;
+00057         _NextTessFaceInPList= root._NextTessFaceInPList;
+00058         // link the list to me.
+00059         root._NextTessFaceInPList->_PrecTessFaceInPList= this;
+00060         root._NextTessFaceInPList= this;
+00061         /*
+00062                 NB if list was empty (this, this), then
+00063                         _PrecTessFaceInPList= &root
+00064                         _NextTessFaceInPList= root._NextTessFaceInPList= &root !
+00065                         root._NextTessFaceInPList->_PrecTessFaceInPList= this;  => root._PrecTessFaceInPList= this
+00066                         root._NextTessFaceInPList= this
+00067         */
+00068 }
+00069 
+00070 // ***************************************************************************
+00071 void            CTessFacePListNode::unlinkInPList()
+00072 {
+00073         /*
+00074                 NB: if this node was empty (this, this), this is a No-Op.
+00075                 If this node was the last of a list, then the root correctly get (&root, &root) after this.
+00076         */
+00077         // unlink old list from me.
+00078         _PrecTessFaceInPList->_NextTessFaceInPList= _NextTessFaceInPList;
+00079         _NextTessFaceInPList->_PrecTessFaceInPList= _PrecTessFaceInPList;
+00080 
+00081         // reset to empty node.
+00082         _PrecTessFaceInPList= this;
+00083         _NextTessFaceInPList= this;
+00084 }
+00085 
+00086 
+00087 // ***************************************************************************
+00088 void            CTessFacePListNode::appendPList(CTessFacePListNode      &root)
+00089 {
+00090         // If list to append is not empty.
+00091         if( root._NextTessFaceInPList != &root )
+00092         {
+00093                 // If we are empty.
+00094                 if( _NextTessFaceInPList==this )
+00095                 {
+00096                         // link the appendList to the root.
+00097                         _PrecTessFaceInPList= root._PrecTessFaceInPList;
+00098                         _NextTessFaceInPList= root._NextTessFaceInPList;
+00099                         // link the root to the appendList.
+00100                         _PrecTessFaceInPList->_NextTessFaceInPList= this;
+00101                         _NextTessFaceInPList->_PrecTessFaceInPList= this;
+00102                 }
+00103                 // else bind first-last in the interval prec-next.
+00104                 else
+00105                 {
+00106                         CTessFacePListNode              *first= root._NextTessFaceInPList;
+00107                         CTessFacePListNode              *last= root._PrecTessFaceInPList;
+00108                         CTessFacePListNode              *prec= this;
+00109                         CTessFacePListNode              *next= _NextTessFaceInPList;
+00110                         // insert the appendList in our list.
+00111                         next->_PrecTessFaceInPList= last;
+00112                         prec->_NextTessFaceInPList= first;
+00113                         // insert our list in the appendList.
+00114                         last->_NextTessFaceInPList= next;
+00115                         first->_PrecTessFaceInPList= prec;
+00116                 }
+00117 
+00118                 // clear input list.
+00119                 root._PrecTessFaceInPList= &root;
+00120                 root._NextTessFaceInPList= &root;
+00121         }
+00122 }
+00123 
+00124 
+00125 
+00126 // ***************************************************************************
+00127 // ***************************************************************************
+00128 //      CTessFacePriorityList
+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         // clear the prioriy list before.
+00159         clear();
+00160 
+00161         // setup
+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         // Build the Rolling tables.
+00170         _RollingTables.resize(1+_NumQuadrant);
+00171         for(i=0;i<_RollingTables.size();i++)
+00172         {
+00173                 _RollingTables[i].init(_NEntries);
+00174                 // setup the quadrant direction. NB: 0 not used since "Direction less rolling table"
+00175                 if(i>=1)
+00176                 {
+00177                         uint    idx= i-1;
+00178                         // split evenly the plane with direction.
+00179                         float   angle= float(2*Pi*idx)/_NumQuadrant;
+00180                         CMatrix mat;
+00181                         mat.rotateZ(angle);
+00182                         // setup the vector
+00183                         _RollingTables[i].QuadrantDirection= mat.getJ();
+00184                 }
+00185         }
+00186 
+00187         // Build Quarter Selection. In is in CCW order. Out: see selectQuadrant()
+00188         const   uint    quarterLut[4]= {1,3,2,0};
+00189         _MaskQuadrant= _NumQuadrant-1;
+00190         for(i=0;i<4;i++)
+00191         {
+00192                 // Re-Order for faster ASM acces. see selectQuadrant()
+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         // just clear all the rolling tables.
+00204         _RollingTables.clear();
+00205 }
+00206 
+00207 
+00208 // ***************************************************************************
+00209 uint            CTessFacePriorityList::selectQuadrant(const CVector &direction)
+00210 {
+00211         // if numQuadrants=0, ret 0.
+00212         if(_NumQuadrant==0)
+00213                 return 0;
+00214 
+00215 
+00216         // select the quarter.
+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                 // read the sign
+00225                 and             eax, 0x80000000
+00226                 and             ebx, 0x80000000
+00227                 // set the bit
+00228                 shr             eax, 30
+00229                 shr             ebx, 31
+00230                 // assemble
+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         // Run only the quadrants of the associated quarter.
+00248         uint    quadrantStart= _QuarterQuadrantStart[quarterId];
+00249         uint    quadrantEnd= _QuarterQuadrantEnd[quarterId];
+00250 
+00251 
+00252         // For all quadrants of the quarter, return the best direction
+00253         float   bestDirPs= -FLT_MAX;
+00254         uint    bestQuadrant= 0;
+00255         for(uint i=quadrantStart;i<quadrantEnd;i++)
+00256         {
+00257                 // get the quadrant Id. Must mask for last (0). And Start at 1 in the _RollingTables.
+00258                 uint    quadrantId= (i&_MaskQuadrant)+1;
+00259                 // Test with this quadrant
+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         // plist must be inited.
+00276         nlassert(_NEntries>0 && quadrantId<_RollingTables.size());
+00277 
+00278         // First, setup in our basis.
+00279         distance*= _OODistStep;
+00280 
+00281         // Insert int the good quadrant
+00282         CRollingTable   &rollTable= _RollingTables[quadrantId];
+00283 
+00284         // Then, look where we must insert it.
+00285         sint    idInsert;
+00286         if(distance<=0)
+00287                 idInsert= 0;
+00288         else
+00289         {
+00290                 // Must insert so we can't miss it when a shift occurs (=> floor).
+00291                 idInsert= OptFastFloor(distance + rollTable.Remainder);
+00292         }
+00293         idInsert= std::max(0, idInsert);
+00294 
+00295         // Manage Mod.
+00296         // If the element to insert must be inserted at  distance > distMax.
+00297         if(idInsert>(sint)_MaskEntries)
+00298         {
+00299                 // Compute number of entries to apply the mod.
+00300                 uint    nMod= _NEntries - _EntryModStart;
+00301                 // Of how many entries are we too far.
+00302                 idInsert= idInsert - _MaskEntries;
+00303                 // Then loop in the interval [_EntryModStart, _NEntries[.
+00304                 idInsert= idInsert % nMod;
+00305                 idInsert= _EntryModStart + idInsert;
+00306         }
+00307 
+00308         // insert in the Roll Table.
+00309         rollTable.insertInRollTable(idInsert, value);
+00310 }
+00311 
+00312 
+00313 // ***************************************************************************
+00314 void            CTessFacePriorityList::shift(const CVector &direction, CTessFacePListNode       &pulledElements)
+00315 {
+00316         // plist must be inited.
+00317         nlassert(_NEntries>0);
+00318 
+00319         pulledElements.unlinkInPList();
+00320 
+00321         // Shift all the rolling tables
+00322         for(uint i=0;i<_RollingTables.size();i++)
+00323         {
+00324                 CRollingTable   &rollTable= _RollingTables[i];
+00325                 float   shiftDistance;
+00326 
+00327                 // if quadrant 0, Direction less => get distance with Euler norm.
+00328                 if(i==0)
+00329                 {
+00330                         shiftDistance= direction.norm();
+00331                 }
+00332                 // Else compute the effective distance we run to the plane.
+00333                 else
+00334                 {
+00335                         shiftDistance= direction*rollTable.QuadrantDirection;
+00336                         // For now, just clamp, but may be interesting to shift Back the rolling table !!
+00337                         shiftDistance= max(0.f, shiftDistance);
+00338                 }
+00339 
+00340                 // First, setup in our basis.
+00341                 shiftDistance*= _OODistStep;
+00342 
+00343                 // at least, fill OUT with elements of entry 0.
+00344                 // For all elements of the entry 0 of , pull them, and insert in result list.
+00345                 pulledElements.appendPList(rollTable.getRollTableEntry(0));
+00346 
+00347                 // shift.
+00348                 rollTable.Remainder+= shiftDistance;
+00349                 // If Remainder>=1, it means that we must shift the rolling table, and get elements deleted.
+00350                 uint    entryShift= (uint)floor(rollTable.Remainder);
+00351                 rollTable.Remainder= rollTable.Remainder - entryShift;
+00352 
+00353                 // shift full array??
+00354                 if( entryShift >= _NEntries)
+00355                 {
+00356                         entryShift= _NEntries;
+00357                         // The entire array is pulled, _Remainder should get a good value.
+00358                         rollTable.Remainder= 0;
+00359                 }
+00360 
+00361                 // If some real shift, do it.
+00362                 rollTable.shiftEntries(entryShift, pulledElements);
+00363         }
+00364 }
+00365 
+00366 
+00367 // ***************************************************************************
+00368 void            CTessFacePriorityList::shiftAll(CTessFacePListNode      &pulledElements)
+00369 {
+00370         // plist must be inited.
+00371         nlassert(_NEntries>0);
+00372 
+00373         pulledElements.unlinkInPList();
+00374 
+00375         // Do it for all rolling tables.
+00376         for(uint i=0;i<_RollingTables.size();i++)
+00377         {
+00378                 // The entire array is pulled, _Remainder should get a good value.
+00379                 uint entryShift= _NEntries;
+00380                 _RollingTables[i].Remainder= 0;
+00381 
+00382                 // shift the entire array.
+00383                 _RollingTables[i].shiftEntries(entryShift, pulledElements);
+00384         }
+00385 }
+00386 
+00387 
+00388 // ***************************************************************************
+00389 // ***************************************************************************
+00390 // Rolling table.
+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         // Insert into list.
+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         // clear all the list.
+00443         while( root.nextInPList() != &root )
+00444         {
+00445                 // unlink from list
+00446                 CTessFacePListNode      *node= root.nextInPList();
+00447                 node->unlinkInPList();
+00448         }
+00449 }
+00450 
+00451 // ***************************************************************************
+00452 void            CTessFacePriorityList::CRollingTable::shiftRollTable(uint shiftEntry)
+00453 {
+00454         // delete all elements shifted.
+00455         for(uint i=0; i<shiftEntry; i++)
+00456         {
+00457                 clearRollTableEntry(i);
+00458         }
+00459         // shift to right the ptr of entries.
+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         // For convenience only (not really usefull).
+00473         Remainder= 0;
+00474 }
+00475 
+00476 // ***************************************************************************
+00477 void            CTessFacePriorityList::CRollingTable::shiftEntries(uint entryShift, CTessFacePListNode  &pulledElements)
+00478 {
+00479         if(entryShift>0)
+00480         {
+00481                 // before shifting the roll Table, fill pulledElements.
+00482                 for(uint i=0; i<entryShift; i++)
+00483                 {
+00484                         // For all elements of the ith entry, pull them and isnert in result list.
+00485                         pulledElements.appendPList(getRollTableEntry(i));
+00486                 }
+00487 
+00488                 // shift the roll Table. lists are already empty.
+00489                 shiftRollTable(entryShift);
+00490         }
+00491 }
+00492 
+00493 
+00494 
+00495 
+00496 } // NL3D
+
tess_face_priority_list.cpp
