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/landscape_collision_grid.h"
+00029 #include <algorithm>
+00030 
+00031 
+00032 using namespace std;
+00033 using namespace NLMISC;
+00034 
+00035 namespace NL3D 
+00036 {
+00037 
+00038 
+00039 // ***************************************************************************
+00040 CLandscapeCollisionGrid::CLandscapeCollisionGrid(CVisualCollisionManager *owner)
+00041 {
+00042         _Owner= owner;
+00043         // reset list to NULL.
+00044         memset(_Grid, 0, NL_COLGRID_SIZE*NL_COLGRID_SIZE * sizeof(CVisualTileDescNode*));
+00045         _Cleared= true;
+00046 
+00047         // sizepower.
+00048         nlassert(isPowerOf2(NL_COLGRID_SIZE));
+00049         _SizePower= getPowerOf2(NL_COLGRID_SIZE);
+00050 }
+00051 
+00052 // ***************************************************************************
+00053 CLandscapeCollisionGrid::~CLandscapeCollisionGrid()
+00054 {
+00055         clear();
+00056 }
+00057 
+00058 // ***************************************************************************
+00059 void                    CLandscapeCollisionGrid::clear()
+00060 {
+00061         // already cleared? do nothing.
+00062         if(_Cleared)
+00063                 return;
+00064 
+00065         // Parse all quads.
+00066         sint    i;
+00067         for(i=0;i<NL_COLGRID_SIZE*NL_COLGRID_SIZE;i++)
+00068         {
+00069                 CVisualTileDescNode                     *ptr, *next;
+00070                 ptr= _Grid[i];
+00071 
+00072                 // delete list of node.
+00073                 while(ptr)
+00074                 {
+00075                         next= ptr->Next;
+00076                         _Owner->deleteVisualTileDescNode(ptr);
+00077                         ptr= next;
+00078                 }
+00079 
+00080                 // reset root.
+00081                 _Grid[i]= NULL;
+00082         }
+00083 
+00084         _Cleared= true;
+00085 }
+00086 
+00087 
+00088 // ***************************************************************************
+00089 struct  CVector2i
+00090 {
+00091         sint    x,y;
+00092 
+00093 };
+00094 
+00095 
+00096 // ***************************************************************************
+00097 // fastFloor function.
+00098 #ifdef NL_OS_WINDOWS
+00099 
+00100 // The magic constant value. support both positive and negative numbers.
+00101 static double   FastFloorMagicConst=pow(2,52)+pow(2,51);
+00102 static uint             FastFloorBkupCW;
+00103 // init float CW.
+00104 static inline void  fastFloorBegin()
+00105 {
+00106         FastFloorBkupCW= _controlfp(0, 0);
+00107         _controlfp( _RC_DOWN|_PC_53, _MCW_RC|_MCW_PC );
+00108 }
+00109 
+00110 // reset float CW.
+00111 static inline void  fastFloorEnd()
+00112 {
+00113         _controlfp(FastFloorBkupCW, _MCW_RC|_MCW_PC);
+00114 }
+00115 
+00116 // Force __stdcall to not pass parameters in registers.
+00117 static inline sint __stdcall fastFloor(float x)
+00118 {
+00119         sint32  QWord[2];
+00120         sint32  *Qw=QWord;
+00121         sint32  res;
+00122         __asm
+00123         {
+00124                 fld             x
+00125                 fadd    FastFloorMagicConst
+00126                 mov             ebx,Qw
+00127                 fstp    qword ptr [ebx]
+00128                 mov             eax,dword ptr [ebx]
+00129                 mov             res, eax
+00130         }
+00131 
+00132         return res;
+00133 }
+00134 
+00135 #else
+00136 static inline void  fastFloorBegin() {}
+00137 static inline void  fastFloorEnd() {}
+00138 static inline sint fastFloor(float x)
+00139 {
+00140         return (sint)floor(x);
+00141 }
+00142 #endif
+00143 
+00144 
+00145 
+00146 // ***************************************************************************
+00147 void                    CLandscapeCollisionGrid::build(const std::vector<CPatchQuadBlock*>      &quadBlocks, const CVector &delta)
+00148 {
+00149         sint    x,y;
+00150         static CVector2i        floorVals[NL_PATCH_BLOCK_MAX_VERTEX*NL_PATCH_BLOCK_MAX_VERTEX];
+00151 
+00152         // first clear
+00153         clear();
+00154 
+00155         // init for fast floor.
+00156         fastFloorBegin();
+00157 
+00158         // then fill.
+00159         _Cleared= false;
+00160         _Delta= delta;
+00161         // parse all quad blocks.
+00162         for(sint i=0; i<(sint)quadBlocks.size();i++)
+00163         {
+00164                 CPatchQuadBlock         &qb= *quadBlocks[i];
+00165                 sint            lenS= qb.PatchBlockId.S1 - qb.PatchBlockId.S0;
+00166                 sint            lenT= qb.PatchBlockId.T1 - qb.PatchBlockId.T0;
+00167 
+00168                 // First, floor all vertices of interest.
+00169                 for(y=0; y<lenT+1; y++)
+00170                 {
+00171                         for(x=0; x<lenS+1; x++)
+00172                         {
+00173                                 sint    id= y*NL_PATCH_BLOCK_MAX_VERTEX + x;
+00174                                 // Add delta, and floor to sint.
+00175                                 floorVals[id].x= fastFloor(qb.Vertices[id].x + delta.x);
+00176                                 floorVals[id].y= fastFloor(qb.Vertices[id].y + delta.y);
+00177                         }
+00178                 }
+00179 
+00180                 // Then compute min max for all quads, and insert quad id in the quadGrid.
+00181                 for(y=0; y<lenT; y++)
+00182                 {
+00183                         for(x=0; x<lenS; x++)
+00184                         {
+00185                                 sint    minx, maxx, miny, maxy;
+00186                                 sint    id= y*NL_PATCH_BLOCK_MAX_VERTEX + x;
+00187                                 // Compute min max of the 4 vertices.
+00188                                 minx= floorVals[id].x; maxx= floorVals[id].x;
+00189                                 miny= floorVals[id].y; maxy= floorVals[id].y;
+00190                                 id++;
+00191                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
+00192                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
+00193                                 id+= NL_PATCH_BLOCK_MAX_VERTEX;
+00194                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
+00195                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
+00196                                 id--;
+00197                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
+00198                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
+00199 
+00200                                 // store minmax in the quad.
+00201                                 sint    quadId= y*NL_PATCH_BLOCK_MAX_QUAD + x;
+00202                                 addQuadToGrid(i, quadId, minx, maxx, miny, maxy);
+00203                         }
+00204                 }
+00205         }
+00206 
+00207         // init for fast floor.
+00208         fastFloorEnd();
+00209 }
+00210 
+00211 
+00212 // ***************************************************************************
+00213 void                    CLandscapeCollisionGrid::addQuadToGrid(uint16 paBlockId, uint16 quadId, sint x0, sint x1, sint y0, sint y1)
+00214 {
+00215         // coordinate should be positive.
+00216         nlassert(x0>=0 && x1>=x0);
+00217         nlassert(y0>=0 && y1>=y0);
+00218 
+00219         // first, transform coordinate (in meters) in quadgrid eltSize (ie 2 meters).
+00220         x0= (x0>>1);            // floor().
+00221         x1= (x1>>1) + 1;        // equivalent of ceil().
+00222         y0= (y0>>1);            // floor().
+00223         y1= (y1>>1) + 1;        // equivalent of ceil().
+00224 
+00225         // setup bounds in quadgrid coordinate.
+00226         if(x1-x0>=NL_COLGRID_SIZE)
+00227                 x0=0, x1= NL_COLGRID_SIZE;
+00228         else
+00229         {
+00230                 x0&= NL_COLGRID_SIZE-1;
+00231                 x1&= NL_COLGRID_SIZE-1;
+00232                 if(x1<=x0)
+00233                         x1+=NL_COLGRID_SIZE;
+00234         }
+00235         if(y1-y0>=NL_COLGRID_SIZE)
+00236                 y0=0, y1= NL_COLGRID_SIZE;
+00237         else
+00238         {
+00239                 y0&= NL_COLGRID_SIZE-1;
+00240                 y1&= NL_COLGRID_SIZE-1;
+00241                 if(y1<=y0)
+00242                         y1+=NL_COLGRID_SIZE;
+00243         }
+00244 
+00245         // fill all cases with element.
+00246         sint    x,y;
+00247         for(y= y0;y<y1;y++)
+00248         {
+00249                 sint    xe,ye;
+00250                 ye= y &(NL_COLGRID_SIZE-1);
+00251                 for(x= x0;x<x1;x++)
+00252                 {
+00253                         xe= x &(NL_COLGRID_SIZE-1);
+00254                         // which case we add the element.
+00255                         sint gridId= (ye<<_SizePower)+xe;
+00256 
+00257                         // allocate element.
+00258                         CVisualTileDescNode             *elt= _Owner->newVisualTileDescNode();
+00259 
+00260                         // fill elt.
+00261                         elt->PatchQuadBlocId= paBlockId;
+00262                         elt->QuadId= quadId;
+00263 
+00264                         // bind elt to the list.
+00265                         elt->Next= _Grid[gridId];
+00266                         _Grid[gridId]= elt;
+00267                 }
+00268         }
+00269 }
+00270 
+00271 
+00272 // ***************************************************************************
+00273 CVisualTileDescNode                     *CLandscapeCollisionGrid::select(const NLMISC::CVector &pos)
+00274 {
+00275         // compute pos in the quadgrid.
+00276         CVector         localPos;
+00277         localPos= pos + _Delta;
+00278         // cases are 2x2 meters.
+00279         localPos/=2;
+00280 
+00281         // floor, bound in quadgrid coordinate.
+00282         sint    x,y;
+00283         x= (sint)floor(localPos.x);
+00284         y= (sint)floor(localPos.y);
+00285         x&= NL_COLGRID_SIZE-1;
+00286         y&= NL_COLGRID_SIZE-1;
+00287 
+00288         return _Grid[y*NL_COLGRID_SIZE+x];
+00289 }
+00290 
+00291 
+00292 
+00293 } // NL3D
+
landscape_collision_grid.cpp
