nel/src/pacs/chain.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 "stdpacs.h"
  18
  19 #include "nel/pacs/chain.h"
  20
  21 using namespace std;
  22 using namespace NLMISC;
  23
  24
  25 // Functions for vertices comparison.
  26 // total order relation
  27 static inline bool      isStrictlyLess(const CVector &a, const CVector &b)
  28 {
  29         if (a.x < b.x)  return true;
  30         if (a.x > b.x)  return false;
  31         if (a.y < b.y)  return true;
  32         if (a.y > b.y)  return false;
  33         if (a.z < b.y)  return true;
  34         return false;
  35 }
  36
  37 static inline bool      isStrictlyGreater(const CVector &a, const CVector &b)
  38 {
  39         if (a.x > b.x)  return true;
  40         if (a.x < b.x)  return false;
  41         if (a.y > b.y)  return true;
  42         if (a.y < b.y)  return false;
  43         if (a.z > b.y)  return true;
  44         return false;
  45 }
  46
  47 static inline bool      isEqual(const CVector &a, const CVector &b)
  48 {
  49         return (a == b);
  50 }
  51
  52
  53 // COrderedChain3f methods implementation
  54
  55 void    NLPACS::COrderedChain3f::serial(NLMISC::IStream &f)
  56 {
  57         /*
  58         Version 0:
  59                 - base version.
  60         */
  61         (void)f.serialVersion(0);
  62
  63         f.serialCont(_Vertices);
  64         f.serial(_Forward);
  65         f.serial(_ParentId);
  66         f.serial(_IndexInParent);
  67 }
  68
  69 // end of COrderedChain3f methods implementation
  70
  71 // COrderedChain methods implementation
  72
  73 // translates the ordered chain by the vector translation
  74 void    NLPACS::COrderedChain::translate(const CVector &translation)
  75 {
  76         uint    i;
  77         CVector2s       translat;
  78         translat.pack(translation);
  79         for (i=0; i<_Vertices.size(); ++i)
  80                 _Vertices[i] += translat;
  81 }
  82
  83 //
  84 void    NLPACS::COrderedChain::traverse(sint from, sint to, bool forward, vector<NLPACS::CVector2s> &path) const
  85 {
  86         sint    i;
  87         if (forward)
  88         {
  89                 if (from < 0)   from = 0;
  90                 if (to < 0)             to = (sint)_Vertices.size()-1;
  91
  92                 for (i=from+1; i<=to; ++i)
  93                         path.push_back(_Vertices[i]);
  94         }
  95         else
  96         {
  97                 if (from < 0)   from = (sint)_Vertices.size()-2;
  98                 if (to < 0)             to = -1;
  99
 100                 for (i=from; i>to; --i)
 101                         path.push_back(_Vertices[i]);
 102         }
 103 }
 104
 105 //
 106 float   NLPACS::COrderedChain::distance(const CVector &position) const
 107 {
 108         float           minDist = 1.0e10f;
 109         uint            i;
 110         CVector2f       pos = CVector2f(position);
 111
 112         for (i=0; i+1<_Vertices.size(); ++i)
 113         {
 114                 CVector2f       a = _Vertices[i].unpack(),
 115                                         b = _Vertices[i+1].unpack();
 116
 117                 CVector2f       d = (b-a);
 118                 float           len = d.norm();
 119                 d /= len;
 120                 CVector2f       n = CVector2f(d.y, -d.x);
 121
 122                 float           l = (pos-a)*d;
 123                 float           dist;
 124
 125                 if (l < 0.0f)
 126                 {
 127                         dist = (pos-a).norm();
 128                 }
 129                 else if (l > len)
 130                 {
 131                         dist = (pos-b).norm();
 132                 }
 133                 else
 134                 {
 135                         dist = (float)fabs((pos-a)*n);
 136                 }
 137
 138                 if (dist < minDist)
 139                 {
 140                         minDist = dist;
 141                 }
 142         }
 143
 144         return minDist;
 145 }
 146
 147
 148 // serializes the ordered chain
 149 void    NLPACS::COrderedChain::serial(NLMISC::IStream &f)
 150 {
 151         /*
 152         Version 0:
 153                 - base version.
 154         Version 1:
 155                 - added _Min and _Max vectors
 156         */
 157         sint    ver= f.serialVersion(1);
 158
 159         f.serialCont(_Vertices);
 160         f.serial(_Forward);
 161         f.serial(_ParentId);
 162         f.serial(_IndexInParent);
 163         f.serial(_Length);
 164
 165         if (ver >= 1)
 166         {
 167                 f.serial(_Min, _Max);
 168         }
 169         else if (f.isReading() && !_Vertices.empty())
 170         {
 171                 uint    i;
 172                 _Max = _Min = _Vertices[0];
 173                 for (i=1; i<_Vertices.size(); ++i)
 174                 {
 175                         _Min.minof(_Min, _Vertices[i]);
 176                         _Max.maxof(_Max, _Vertices[i]);
 177                 }
 178         }
 179 }
 180
 181 // end of COrderedChain methods implementation
 182
 183
 184 // CChain methods implementation
 185
 186 // builds the CChain from a list of vertices and a left and right surfaces id.
 187 // the chains vector is the vector where to store generated ordered chains.
 188 // thisId is the current id of the CChain, and edge is the number of the edge the CChain belongs to (-1
 189 // if none.)
 190 void    NLPACS::CChain::make(const vector<CVector> &vertices, sint32 left, sint32 right, vector<COrderedChain> &chains, uint16 thisId,
 191                                                          vector<COrderedChain3f> &fullChains, vector<uint> &useOChainId)
 192 {
 193         sint            first = 0, last = 0, i;
 194
 195         _Left = left;
 196         _Right = right;
 197         _Length = 0.0f;
 198
 199         // splits the vertices list in ordered sub chains.
 200         while (first < (sint)vertices.size()-1)
 201         {
 202                 last = first+1;
 203                 bool    forward = isStrictlyLess(vertices[first], vertices[last]);
 204
 205                 // first checks if the subchain goes forward or backward.
 206                 if (forward)
 207                         for (; last < (sint)vertices.size() && isStrictlyLess(vertices[last-1], vertices[last]); ++last)
 208                                 ;
 209                 else
 210                         for (; last < (sint)vertices.size() && isStrictlyGreater(vertices[last-1], vertices[last]); ++last)
 211                                 ;
 212                 --last;
 213
 214                 // inserts the new subchain id within the CChain.
 215                 uint32  subChainId;
 216
 217                 if (useOChainId.empty())
 218                 {
 219                         subChainId = (uint32)chains.size();
 220                         if (subChainId > 65535)
 221                                 nlerror("in NLPACS::CChain::make(): reached the maximum number of ordered chains");
 222
 223                         chains.resize(chains.size()+1);
 224                         fullChains.resize(fullChains.size()+1);
 225                 }
 226                 else
 227                 {
 228                         subChainId = useOChainId.back();
 229                         useOChainId.pop_back();
 230                 }
 231
 232                 _SubChains.push_back((uint16)subChainId);
 233
 234                 // and creates a new COrderedChain
 235                 COrderedChain3f &subchain3f = fullChains[subChainId];
 236                 subchain3f._Vertices.reserve(last-first+1);
 237                 subchain3f._Forward = forward;
 238                 subchain3f._ParentId = thisId;
 239                 subchain3f._IndexInParent = uint16(_SubChains.size()-1);
 240
 241                 // and then copies the vertices (sorted, btw!)
 242                 if (forward)
 243                         for (i=first; i<=last; ++i)
 244                                 subchain3f._Vertices.push_back(vertices[i]);
 245                 else
 246                         for (i=last; i>=first; --i)
 247                                 subchain3f._Vertices.push_back(vertices[i]);
 248
 249                 first = last;
 250
 251                 COrderedChain   &subchain = chains[subChainId];
 252                 subchain.pack(subchain3f);
 253                 subchain.computeMinMax();
 254
 255                 float   length = 0.0f;
 256                 for (i=0; i<(sint)subchain._Vertices.size()-1; ++i)
 257                         length += (subchain._Vertices[i+1]-subchain._Vertices[i]).norm();
 258
 259                 subchain._Length = length;
 260                 _Length += length;
 261         }
 262 }
 263
 264 // serializes the CChain
 265 void    NLPACS::CChain::serial(NLMISC::IStream &f)
 266 {
 267         /*
 268         Version 0:
 269                 - base version.
 270         */
 271         (void)f.serialVersion(0);
 272
 273         f.serialCont(_SubChains);
 274         f.serial(_Left, _Right);
 275         f.serial(_StartTip, _StopTip);
 276         f.serial(_Length);
 277         f.serial(_LeftLoop, _LeftLoopIndex);
 278         f.serial(_RightLoop, _RightLoopIndex);
 279 }
 280
 281
 282
 283 // unifiies the chain
 284 void    NLPACS::CChain::unify(vector<NLPACS::COrderedChain> &ochains)
 285 {
 286         CVector2s       snap;
 287         uint            i;
 288
 289         snap = (ochains[_SubChains[0]].isForward()) ? ochains[_SubChains[0]]._Vertices.back() : ochains[_SubChains[0]]._Vertices.front();
 290
 291         for (i=1; i<_SubChains.size(); ++i)
 292         {
 293                 if (ochains[_SubChains[i]].isForward())
 294                 {
 295                         if (ochains[_SubChains[i]]._Vertices.front() != snap)
 296                                 nlwarning("ochain %d and %d are not stuck together", _SubChains[i-1], _SubChains[i]);
 297                         ochains[_SubChains[i]]._Vertices.front() = snap;
 298                         snap = ochains[_SubChains[i]]._Vertices.back();
 299                 }
 300                 else
 301                 {
 302                         if (ochains[_SubChains[i]]._Vertices.back() != snap)
 303                                 nlwarning("ochain %d and %d are not stuck together", _SubChains[i-1], _SubChains[i]);
 304                         ochains[_SubChains[i]]._Vertices.back() = snap;
 305                         snap = ochains[_SubChains[i]]._Vertices.front();
 306                 }
 307         }
 308
 309 }
 310
 311 //
 312 void    NLPACS::CChain::setStartVector(const NLPACS::CVector2s &v, vector<NLPACS::COrderedChain> &ochains)
 313 {
 314         if (ochains[_SubChains.front()].isForward())
 315                 ochains[_SubChains.front()]._Vertices.front() = v;
 316         else
 317                 ochains[_SubChains.front()]._Vertices.back() = v;
 318 }
 319
 320 //
 321 void    NLPACS::CChain::setStopVector(const NLPACS::CVector2s &v, vector<NLPACS::COrderedChain> &ochains)
 322 {
 323         if (ochains[_SubChains.back()].isForward())
 324                 ochains[_SubChains.back()]._Vertices.back() = v;
 325         else
 326                 ochains[_SubChains.back()]._Vertices.front() = v;
 327 }
 328
 329 //
 330 NLPACS::CVector2s       NLPACS::CChain::getStartVector(vector<NLPACS::COrderedChain> &ochains)
 331 {
 332         if (ochains[_SubChains.front()].isForward())
 333                 return ochains[_SubChains.front()]._Vertices.front();
 334         else
 335                 return ochains[_SubChains.front()]._Vertices.back();
 336 }
 337
 338 //
 339 NLPACS::CVector2s       NLPACS::CChain::getStopVector(vector<NLPACS::COrderedChain> &ochains)
 340 {
 341         if (ochains[_SubChains.back()].isForward())
 342                 return ochains[_SubChains.back()]._Vertices.back();
 343         else
 344                 return ochains[_SubChains.back()]._Vertices.front();
 345 }
 346
 347 // end of CChain methods implementation
 348