ryzom/server/src/gpm_service/patat_grid.cpp

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   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
  18 #include "stdpch.h"
  19
  20 #include "patat_grid.h"
  21
  22 #include "nel/misc/aabbox.h"
  23 #include "nel/misc/file.h"
  24 #include "nel/misc/i_xml.h"
  25 #include "nel/misc/path.h"
  26 #include "nel/ligo/ligo_config.h"
  27
  28 using namespace std;
  29 using namespace NLMISC;
  30 using namespace NLLIGO;
  31
  32 extern NLLIGO::CLigoConfig LigoConfig;
  33
  34 /*
  35  * Constructor
  36  */
  37 CPatatGrid::CPatatGrid()
  38 {
  39 }
  40
  41 /*
  42  * Destructor
  43  */
  44 CPatatGrid::~CPatatGrid()
  45 {
  46 }
  47
  48
  49 /*
  50  * Init patat grid
  51  */
  52 void    CPatatGrid::init()
  53 {
  54         // allocate 1 free entry (for no zone entry)
  55         _PrimZones.resize(1);
  56         _EntryTable.resize(1);
  57         _SelectGrid.clear();
  58         _ZoneMap.clear();
  59         _FlagTable.clear();
  60         _EntryMap.clear();
  61         _FreeEntries.clear();
  62
  63         nlinfo("Initialized CPatatGrid, move grid is 1024x1024 uint16 (%.2f Mb)", (float)(sizeof(TEntryIndex)*1024*1024)/(1024.0f*1024.0f));
  64 }
  65
  66
  67 void    CPatatGrid::readPrimitive(IPrimitive *primitive, std::vector<uint32> &inFile)
  68 {
  69         if (dynamic_cast<CPrimZone*>(primitive) != NULL)
  70         {
  71                 // check good class
  72                 string  primName;
  73                 string  className;
  74                 if (primitive->getPropertyByName("name", primName) &&
  75                         primitive->getPropertyByName("class", className) &&
  76                         _PrimZoneFilters.find(className) != _PrimZoneFilters.end())
  77                 {
  78                         _ZoneMap.insert(TZoneMap::value_type(primName, (sint32)_PrimZones.size()));
  79                         inFile.push_back((uint32)_PrimZones.size());
  80                         _PrimZones.push_back(static_cast<CPrimZone&>(*primitive));
  81 //                      _PrimZones.back().Name = primName;
  82                 }
  83         }
  84
  85         // parse children
  86         uint    i;
  87         for (i=0; i<primitive->getNumChildren(); ++i)
  88         {
  89                 IPrimitive      *child;
  90
  91                 if (!primitive->getChild(child, i))
  92                         continue;
  93
  94                 readPrimitive(child, inFile);
  95         }
  96 }
  97
  98
  99 /*
 100  * Use patat prim file
 101  */
 102 void    CPatatGrid::usePrim(const string &primFile, std::vector<uint32> &inFile)
 103 {
 104 /*
 105         CIFile  f(CPath::lookup(primFile));
 106         CPrimRegion             region;
 107         CIXml                   xml;
 108         xml.init(f);
 109         region.serial(xml);
 110
 111         nlinfo("Loaded prim file '%s'", primFile.c_str());
 112
 113         uint    i;
 114         uint    firstPrimZone = _PrimZones.size();
 115         inFile.clear();
 116
 117         for (i=0; i<region.VZones.size(); ++i)
 118         {
 119                 if (_ZoneMap.find(region.VZones[i].Name) != _ZoneMap.end())
 120                 {
 121                         nlwarning("Prim zone %s (in file %s) already added, discarded", region.VZones[i].Name.c_str(), primFile.c_str());
 122                 }
 123                 else
 124                 {
 125                         _ZoneMap.insert(TZoneMap::value_type(region.VZones[i].Name, _PrimZones.size()));
 126                         inFile.push_back(_PrimZones.size());
 127                         _PrimZones.push_back(region.VZones[i]);
 128                 }
 129         }
 130 */
 131
 132         // lookup for primitive file
 133         CIFile          f(CPath::lookup(primFile));
 134         CIXml           xml;
 135
 136         CPrimitives     prims;
 137
 138         // load xml file
 139         xml.init(f);
 140         nlinfo("Loaded prim file '%s'", primFile.c_str());
 141
 142         // read nodes
 143         if (!prims.read(xml.getRootNode(), primFile.c_str(), LigoConfig))
 144         {
 145                 nlwarning("Can't use primitive file '%s', xml parse error",  primFile.c_str());
 146                 return;
 147         }
 148
 149         uint    i;
 150         uint    firstPrimZone = (uint)_PrimZones.size();
 151         inFile.clear();
 152
 153         // get CPrimNode
 154         CPrimNode       *primRootNode = prims.RootNode;
 155
 156         // read recursive node
 157         readPrimitive(primRootNode, inFile);
 158
 159         const uint32    maxGridEntryIndex = (1 << (sizeof(TEntryIndex)*8)) - 1;
 160
 161         _FlagTable.resize(_PrimZones.size(), false);
 162
 163         // for each patat, sample points (check they belong to the patat) and find the matching entry
 164         for (i=firstPrimZone; i<_PrimZones.size(); ++i)
 165         {
 166                 CPrimZone       &zone = _PrimZones[i];
 167
 168                 if (zone.VPoints.empty())
 169                         continue;
 170
 171                 // build bounding box
 172                 double  xmin = 1.0e10f, xmax = -xmin, ymin = xmin, ymax = xmax;
 173                 double  x, y;
 174
 175                 uint    j;
 176                 for (j=0; j<zone.VPoints.size(); ++j)
 177                 {
 178                         if (zone.VPoints[j].x < xmin)   xmin = zone.VPoints[j].x;
 179                         if (zone.VPoints[j].y < ymin)   ymin = zone.VPoints[j].y;
 180                         if (zone.VPoints[j].x > xmax)   xmax = zone.VPoints[j].x;
 181                         if (zone.VPoints[j].y > ymax)   ymax = zone.VPoints[j].y;
 182                 }
 183
 184                 xmin = _SelectGrid.round(xmin);
 185                 ymin = _SelectGrid.round(ymin);
 186                 xmax = _SelectGrid.round(xmax);
 187                 ymax = _SelectGrid.round(ymax);
 188
 189                 nlinfo("Sampling %d/%d (%d samples)", i-firstPrimZone+1, _PrimZones.size()-firstPrimZone, (sint)((xmax-xmin)/PatatGridResolution * (ymax-ymin)/PatatGridResolution));
 190
 191                 // sample zone
 192                 for (y=ymin; y<=ymax; y+=PatatGridResolution)
 193                 {
 194                         for (x=xmin; x<=xmax; x+=PatatGridResolution)
 195                         {
 196                                 CVector v((float)x, (float)y, 0.0f);
 197
 198                                 // check sampled point belongs to the patat
 199                                 if (!zone.contains(v))
 200                                         continue;
 201
 202                                 // get the entry index for this point
 203                                 TEntryIndex     index = (TEntryIndex)getEntryIndex(v);
 204                                 CEntry          &entry = _EntryTable[index];
 205
 206                                 // compute the new hash code for this point
 207                                 // basically, hash is previous hash code times zone number
 208                                 //uint32        hash = (index == 0) ? i : entry.HashCode * i;
 209
 210                                 // other hash function, assuming index0 entry has 0 hashcode.
 211                                 uint32  hash = (entry.HashCode<<4) + (entry.HashCode>>28) + i;
 212
 213                                 pair<TEntryMap::iterator, TEntryMap::iterator>  range;
 214                                 TEntryMap::iterator     it;
 215
 216                                 // get all entries with this hash code
 217                                 range = _EntryMap.equal_range(hash);
 218
 219                                 // check if selected entries match the new point
 220                                 for (it=range.first; it!=range.second; ++it)
 221                                 {
 222                                         CEntry  &selected = _EntryTable[(*it).second];
 223
 224                                         // selected must have one zone more than entry
 225                                         if (selected.Zones.size() != entry.Zones.size()+1)
 226                                                 continue;
 227
 228                                         uint    k;
 229                                         for (k=0; k<entry.Zones.size(); ++k)
 230                                                 if (entry.Zones[k] != selected.Zones[k])
 231                                                         break;
 232
 233                                         // if first zones of selected are different from entry, give up
 234                                         if (k != entry.Zones.size())
 235                                                 continue;
 236
 237                                         // if all zones in selected and extended entry matches, found good entry
 238                                         if (selected.Zones.back() == i)
 239                                                 break;
 240                                 }
 241
 242                                 // if found an entry matching for the point, set up the grid to point on the selected entry
 243                                 if (it != _EntryMap.end())
 244                                 {
 245                                         CEntry  &selected = _EntryTable[(*it).second];
 246                                         setEntryIndex(v, selected.EntryIndex);
 247
 248                                         --entry.NumSamples;
 249                                         ++selected.NumSamples;
 250
 251                                         // if no more samples point to this entry, free it and leave it _FreeEntries stack
 252                                         if (entry.EntryIndex != 0 && entry.NumSamples == 0)
 253                                         {
 254                                                 entry.HashCode = 0xffffffff;
 255                                                 entry.Zones.clear();
 256                                                 _FreeEntries.push_back(entry.EntryIndex);
 257                                         }
 258                                 }
 259                                 else
 260                                 {
 261                                         // else create a new entry
 262                                         uint32          newIndex = 0;
 263
 264                                         // use a freed entry if possible
 265                                         if (!_FreeEntries.empty())
 266                                         {
 267                                                 newIndex = _FreeEntries.front();
 268                                                 _FreeEntries.pop_front();
 269                                         }
 270                                         else
 271                                         {
 272                                                 newIndex = (uint32)_EntryTable.size();
 273                                                 _EntryTable.resize(newIndex+1);
 274                                         }
 275
 276                                         // reloads entry, as it might have be reallocated
 277                                         CEntry          &entry = _EntryTable[index];
 278
 279                                         // checks the index fits in table
 280                                         if (newIndex >= maxGridEntryIndex)
 281                                         {
 282                                                 nlerror("Error in PatatGrid build, type 'TEntryIndex' too short (%d bytes), use wider type !", sizeof(TEntryIndex));
 283                                         }
 284
 285                                         CEntry  &newEntry = _EntryTable[newIndex];
 286
 287                                         // inits new entry
 288                                         newEntry.EntryIndex = (TEntryIndex)newIndex;
 289                                         newEntry.HashCode = hash;
 290                                         newEntry.NumSamples = 1;
 291                                         newEntry.Zones = entry.Zones;
 292                                         newEntry.Zones.push_back(i);
 293
 294                                         // add entry to map
 295                                         _EntryMap.insert(TEntryMap::value_type(hash, (TEntryIndex)newIndex));
 296
 297                                         // points point to new entry
 298                                         setEntryIndex(v, newEntry.EntryIndex);
 299                                 }
 300                         }
 301                 }
 302         }
 303 }
 304
 305 /*
 306  * build patat grid
 307  */
 308 bool    CPatatGrid::diff(TEntryIndex previous, TEntryIndex next, vector<uint32> &in, vector<uint32> &out)
 309 {
 310         if (previous >= _EntryTable.size())
 311         {
 312                 nlwarning("Entry index %d out of bounds, assume empty zone", previous);
 313                 previous = 0;
 314         }
 315         if (next >= _EntryTable.size())
 316         {
 317                 nlwarning("Entry index %d out of bounds, assume empty zone", next);
 318                 next = 0;
 319         }
 320
 321         in.clear();
 322         out.clear();
 323
 324         if (previous == next)
 325                 return false;
 326
 327         CEntry  &p = _EntryTable[previous];
 328         CEntry  &n = _EntryTable[next];
 329
 330         uint    i;
 331
 332         // flag all of previous
 333         for (i=0; i<p.Zones.size(); ++i)
 334                 _FlagTable[p.Zones[i]] = true;
 335
 336         // check new
 337         for (i=0; i<n.Zones.size(); ++i)
 338         {
 339                 // if flag clear, a new zone
 340                 if (!_FlagTable[n.Zones[i]])
 341                         in.push_back(n.Zones[i]);
 342                 _FlagTable[n.Zones[i]] = false;
 343         }
 344
 345         // check previous
 346         for (i=0; i<p.Zones.size(); ++i)
 347         {
 348                 // if flag set (didn't change), a left zone
 349                 if (_FlagTable[p.Zones[i]])
 350                         out.push_back(p.Zones[i]);
 351                 _FlagTable[p.Zones[i]] = false;
 352         }
 353
 354         return (!in.empty() || !out.empty());
 355 }