nel/src/3d/landscape_collision_grid.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/landscape_collision_grid.h"
  20 #include "nel/misc/fast_floor.h"
  21 #include <algorithm>
  22
  23
  24 using namespace std;
  25 using namespace NLMISC;
  26
  27 #ifdef DEBUG_NEW
  28 #define new DEBUG_NEW
  29 #endif
  30
  31 namespace NL3D
  32 {
  33
  34
  35 // ***************************************************************************
  36 CLandscapeCollisionGrid::CLandscapeCollisionGrid(CVisualCollisionManager *owner)
  37 {
  38         _Owner= owner;
  39         // reset list to NULL.
  40         memset(_Grid, 0, NL_COLGRID_SIZE*NL_COLGRID_SIZE * sizeof(CVisualTileDescNode*));
  41         _Cleared= true;
  42
  43         // sizepower.
  44         nlassert(isPowerOf2(NL_COLGRID_SIZE));
  45         _SizePower= getPowerOf2(NL_COLGRID_SIZE);
  46 }
  47
  48 // ***************************************************************************
  49 CLandscapeCollisionGrid::~CLandscapeCollisionGrid()
  50 {
  51         clear();
  52 }
  53
  54 // ***************************************************************************
  55 void                    CLandscapeCollisionGrid::clear()
  56 {
  57         // already cleared? do nothing.
  58         if(_Cleared)
  59                 return;
  60
  61         // Parse all quads.
  62         sint    i;
  63         for(i=0;i<NL_COLGRID_SIZE*NL_COLGRID_SIZE;i++)
  64         {
  65                 CVisualTileDescNode                     *ptr, *next;
  66                 ptr= _Grid[i];
  67
  68                 // delete list of node.
  69                 while(ptr)
  70                 {
  71                         next= ptr->Next;
  72                         _Owner->deleteVisualTileDescNode(ptr);
  73                         ptr= next;
  74                 }
  75
  76                 // reset root.
  77                 _Grid[i]= NULL;
  78         }
  79
  80         _Cleared= true;
  81 }
  82
  83
  84 // ***************************************************************************
  85 struct  CVector2i
  86 {
  87         sint    x,y;
  88
  89 };
  90
  91
  92 // ***************************************************************************
  93 void                    CLandscapeCollisionGrid::build(const std::vector<CPatchQuadBlock*>      &quadBlocks, const CVector &delta)
  94 {
  95         sint    x,y;
  96         static CVector2i        floorVals[NL_PATCH_BLOCK_MAX_VERTEX*NL_PATCH_BLOCK_MAX_VERTEX];
  97
  98         // first clear
  99         clear();
 100
 101         // init for fast floor.
 102         OptFastFloorBegin();
 103
 104         // then fill.
 105         _Cleared= false;
 106         _Delta= delta;
 107         // parse all quad blocks.
 108         for(sint i=0; i<(sint)quadBlocks.size();i++)
 109         {
 110                 CPatchQuadBlock         &qb= *quadBlocks[i];
 111                 sint            lenS= qb.PatchBlockId.S1 - qb.PatchBlockId.S0;
 112                 sint            lenT= qb.PatchBlockId.T1 - qb.PatchBlockId.T0;
 113
 114                 // First, floor all vertices of interest.
 115                 for(y=0; y<lenT+1; y++)
 116                 {
 117                         for(x=0; x<lenS+1; x++)
 118                         {
 119                                 sint    id= y*NL_PATCH_BLOCK_MAX_VERTEX + x;
 120                                 // Add delta, and floor to sint.
 121                                 floorVals[id].x= OptFastFloor(qb.Vertices[id].x + delta.x);
 122                                 floorVals[id].y= OptFastFloor(qb.Vertices[id].y + delta.y);
 123                         }
 124                 }
 125
 126                 // Then compute min max for all quads, and insert quad id in the quadGrid.
 127                 for(y=0; y<lenT; y++)
 128                 {
 129                         for(x=0; x<lenS; x++)
 130                         {
 131                                 sint    minx, maxx, miny, maxy;
 132                                 sint    id= y*NL_PATCH_BLOCK_MAX_VERTEX + x;
 133                                 // Compute min max of the 4 vertices.
 134                                 minx= floorVals[id].x; maxx= floorVals[id].x;
 135                                 miny= floorVals[id].y; maxy= floorVals[id].y;
 136                                 id++;
 137                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
 138                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
 139                                 id+= NL_PATCH_BLOCK_MAX_VERTEX;
 140                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
 141                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
 142                                 id--;
 143                                 minx= min(minx, floorVals[id].x); maxx= max(maxx, floorVals[id].x);
 144                                 miny= min(miny, floorVals[id].y); maxy= max(maxy, floorVals[id].y);
 145
 146                                 // store minmax in the quad.
 147                                 sint    quadId= y*NL_PATCH_BLOCK_MAX_QUAD + x;
 148                                 addQuadToGrid(i, quadId, minx, maxx, miny, maxy);
 149                         }
 150                 }
 151         }
 152
 153         // init for fast floor.
 154         OptFastFloorEnd();
 155 }
 156
 157
 158 // ***************************************************************************
 159 void                    CLandscapeCollisionGrid::addQuadToGrid(uint16 paBlockId, uint16 quadId, sint x0, sint x1, sint y0, sint y1)
 160 {
 161         // coordinate should be positive.
 162         nlassert(x0>=0 && x1>=x0);
 163         nlassert(y0>=0 && y1>=y0);
 164
 165         // first, transform coordinate (in meters) in quadgrid eltSize (ie 2 meters).
 166         x0= (x0>>1);            // floor().
 167         x1= (x1>>1) + 1;        // equivalent of ceil().
 168         y0= (y0>>1);            // floor().
 169         y1= (y1>>1) + 1;        // equivalent of ceil().
 170
 171         // setup bounds in quadgrid coordinate.
 172         if(x1-x0>=NL_COLGRID_SIZE)
 173                 x0=0, x1= NL_COLGRID_SIZE;
 174         else
 175         {
 176                 x0&= NL_COLGRID_SIZE-1;
 177                 x1&= NL_COLGRID_SIZE-1;
 178                 if(x1<=x0)
 179                         x1+=NL_COLGRID_SIZE;
 180         }
 181         if(y1-y0>=NL_COLGRID_SIZE)
 182                 y0=0, y1= NL_COLGRID_SIZE;
 183         else
 184         {
 185                 y0&= NL_COLGRID_SIZE-1;
 186                 y1&= NL_COLGRID_SIZE-1;
 187                 if(y1<=y0)
 188                         y1+=NL_COLGRID_SIZE;
 189         }
 190
 191         // fill all cases with element.
 192         sint    x,y;
 193         for(y= y0;y<y1;y++)
 194         {
 195                 sint    xe,ye;
 196                 ye= y &(NL_COLGRID_SIZE-1);
 197                 for(x= x0;x<x1;x++)
 198                 {
 199                         xe= x &(NL_COLGRID_SIZE-1);
 200                         // which case we add the element.
 201                         sint gridId= (ye<<_SizePower)+xe;
 202
 203                         // allocate element.
 204                         CVisualTileDescNode             *elt= _Owner->newVisualTileDescNode();
 205
 206                         // fill elt.
 207                         elt->PatchQuadBlocId= paBlockId;
 208                         elt->QuadId= quadId;
 209
 210                         // bind elt to the list.
 211                         elt->Next= _Grid[gridId];
 212                         _Grid[gridId]= elt;
 213                 }
 214         }
 215 }
 216
 217
 218 // ***************************************************************************
 219 CVisualTileDescNode                     *CLandscapeCollisionGrid::select(const NLMISC::CVector &pos)
 220 {
 221         // compute pos in the quadgrid.
 222         CVector         localPos;
 223         localPos= pos + _Delta;
 224         // cases are 2x2 meters.
 225         localPos/=2;
 226
 227         // floor, bound in quadgrid coordinate.
 228         sint    x,y;
 229         x= (sint)floor(localPos.x);
 230         y= (sint)floor(localPos.y);
 231         x&= NL_COLGRID_SIZE-1;
 232         y&= NL_COLGRID_SIZE-1;
 233
 234         return _Grid[y*NL_COLGRID_SIZE+x];
 235 }
 236
 237
 238
 239 } // NL3D