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/vegetable_sort_block.h"
+00029 #include "3d/radix_sort.h"
+00030 #include "3d/fast_floor.h"
+00031 
+00032 
+00033 using namespace std;
+00034 using namespace NLMISC;
+00035 
+00036 namespace NL3D 
+00037 {
+00038 
+00039 
+00040 // sort triangles with 2 mm of precision. It leaves 64 m with an uint16, which is really sufficient :)
+00041 #define NL3D_VEGETABLE_TRI_RADIX_KEY_PRECISION  512
+00042 
+00043 
+00044 // ***************************************************************************
+00045 CVegetableSortBlock::CVegetableSortBlock()
+00046 {
+00047         ZSortHardMode= true;
+00048         _NTriangles= 0;
+00049         _NIndices= 0;
+00050         _Dirty= false;
+00051         _UnderWater= false;
+00052 }
+00053 
+00054 
+00055 // ***************************************************************************
+00056 // the struct to sort a triangle.
+00057 struct  CSortTri
+00058 {
+00059         // index of the triangle.
+00060         uint16  TriIndex;
+00061 
+00062         // QSort only.
+00063         // distance.
+00064         float   Dist;
+00065         bool    operator<(const CSortTri &o) const
+00066         {
+00067                 return Dist>o.Dist;
+00068         }
+00069 };
+00070 
+00071 
+00072 // ***************************************************************************
+00073 void                    CVegetableSortBlock::updateSortBlock(CVegetableManager &vegetManager)
+00074 {
+00075         // if nothing to update (ie instance added/deleted do not impact me).
+00076         if(!_Dirty)
+00077         {
+00078                 // nothing to do.
+00079                 return;
+00080         }
+00081         else
+00082         {
+00083                 // Ok clean me now.
+00084                 _Dirty= false;
+00085         }
+00086 
+00087 
+00088         // compute number of triangles.
+00089         _NTriangles= 0;
+00090         CVegetableInstanceGroup         *ptrIg= _InstanceGroupList.begin();
+00091         while(ptrIg)
+00092         {
+00093                 // add only zsort rdrPass triangles.
+00094                 _NTriangles+= ptrIg->_RdrPass[NL3D_VEGETABLE_RDRPASS_UNLIT_2SIDED_ZSORT].NTriangles;
+00095 
+00096                 // next Ig in the SortBlock
+00097                 ptrIg= (CVegetableInstanceGroup*)(ptrIg->Next);
+00098         }
+00099         // compute number of indices
+00100         _NIndices= _NTriangles*3;
+00101 
+00102 
+00103         // if no triangles, clear and go
+00104         if(_NTriangles == 0)
+00105         {
+00106                 // reset the array of indices.
+00107                 _SortedTriangleArray.clear();
+00108                 // bye
+00109                 return;
+00110         }
+00111         else
+00112         {
+00113                 // else, re-allocate the array
+00114                 _SortedTriangleArray.resize(_NIndices * NL3D_VEGETABLE_NUM_QUADRANT);
+00115         }
+00116 
+00117 
+00118         // resize an array for sorting.
+00119         nlassert(_NTriangles < 65536);
+00120         static  std::vector<CSortTri>   triSort;
+00121         static  std::vector<uint32>             triIndices;
+00122         triSort.clear();
+00123         triSort.resize(_NTriangles);
+00124         triIndices.resize(_NIndices);
+00125 
+00126 
+00127         // for all quadrants
+00128         for(uint quadrant=0; quadrant<NL3D_VEGETABLE_NUM_QUADRANT; quadrant++)
+00129         {
+00130                 // fill triSort with all ig info.
+00131                 //-------------
+00132                 CSortTri        *triPtr= &triSort[0];
+00133                 uint32          *triIdxPtr= &triIndices[0];
+00134                 uint            triId= 0;
+00135                 // for all igs in the sortBlock.
+00136                 ptrIg= _InstanceGroupList.begin();
+00137                 while(ptrIg)
+00138                 {
+00139                         CVegetableInstanceGroup::CVegetableRdrPass      &vegetRdrPass= ptrIg->_RdrPass[NL3D_VEGETABLE_RDRPASS_UNLIT_2SIDED_ZSORT];
+00140 
+00141                         // add only zsort rdrPass triangles.
+00142                         for(uint i=0; i<vegetRdrPass.NTriangles; i++, triPtr++, triId++)
+00143                         {
+00144                                 // QSort.
+00145                                 triPtr->Dist = ptrIg->_TriangleQuadrantOrders[quadrant][i];
+00146 
+00147                                 // copy tri info
+00148                                 triPtr->TriIndex= triId;
+00149                                         
+00150                                 // fill the triangle indices.
+00151                                 *(triIdxPtr++)= vegetRdrPass.TriangleIndices[i*3 + 0];
+00152                                 *(triIdxPtr++)= vegetRdrPass.TriangleIndices[i*3 + 1];
+00153                                 *(triIdxPtr++)= vegetRdrPass.TriangleIndices[i*3 + 2];
+00154                         }
+00155 
+00156                         // next Ig in the SortBlock
+00157                         ptrIg= (CVegetableInstanceGroup*)(ptrIg->Next);
+00158                 }
+00159 
+00160                 // sort the array according to distance
+00161                 //-------------
+00162                 // QSort.
+00163                 sort(triSort.begin(), triSort.end());
+00164 
+00165 
+00166                 // Fill result.
+00167                 //-------------
+00168                 // init quadrant ptr.
+00169                 _SortedTriangleIndices[quadrant]= _SortedTriangleArray.getPtr() + quadrant * _NIndices;
+00170 
+00171                 // fill the indices.
+00172                 uint32  *pIdx= _SortedTriangleIndices[quadrant];
+00173                 for(uint i=0; i<_NTriangles; i++)
+00174                 {
+00175                         uint32  idTriIdx= triSort[i].TriIndex * 3;
+00176                         *(pIdx++)= triIndices[idTriIdx+0];
+00177                         *(pIdx++)= triIndices[idTriIdx+1];
+00178                         *(pIdx++)= triIndices[idTriIdx+2];
+00179                 }
+00180         }
+00181 }
+00182 
+00183 
+00184 
+00185 
+00186 } // NL3D
+
vegetable_sort_block.cpp
