simgear/scene/tgdb/BucketBox.hxx

   1 // BucketBox.cxx -- Helper for on demand database paging.
   2 //
   3 // Copyright (C) 2010 - 2013  Mathias Froehlich
   4 //
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License as
   7 // published by the Free Software Foundation; either version 2 of the
   8 // License, or (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful, but
  11 // WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 // General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  18 //
  19
  20 #ifndef _BUCKETBOX_HXX
  21 #define _BUCKETBOX_HXX
  22
  23 #include <cassert>
  24 #include <istream>
  25 #include <ostream>
  26
  27 #include <simgear/bucket/newbucket.hxx>
  28 #include <simgear/math/SGGeometry.hxx>
  29
  30 namespace simgear {
  31
  32 #define Elements(x) (sizeof(x)/sizeof((x)[0]))
  33
  34 // 2*5*3*3 * 4 = 360
  35 static const unsigned _lonFactors[] = { 2, 5, 3, 3, 2, 2, /* sub degree */ 2, 2, 2 };
  36 // 3*3*5 * 4 = 180
  37 static const unsigned _latFactors[] = { 3, 5, 1, 3, 2, 2, /* sub degree */ 2, 2, 2 };
  38
  39 static unsigned product(const unsigned* factors, unsigned count)
  40 {
  41     unsigned index = 1;
  42     while (count--)
  43         index *= *factors++;
  44     return index;
  45 }
  46
  47 /// /Rectangular/ sub part of the earths surface.
  48 /// Stored with offset point in lon/lat and width and height.
  49 /// The values are stored in a fixed point format having 3 fractional
  50 /// bits which matches the SGBuckets maximum tile resolution.
  51 ///
  52 /// Notable /design/ decision:
  53 /// * The longitude maps to the interval [-180,180[.
  54 ///   The latitude maps to the interval [-90,90].
  55 ///   This works now that the tiles do no longer cut
  56 ///   neither the 180deg nor the 0deg boundary.
  57 /// * This is not meant to be an API class for simgear. This is
  58 ///   just an internal tool that I would like to keep in the SPT loader.
  59 ///   But I want to have coverage somehow tested with the usual unit
  60 ///   tests, which is the reason to have this file split out.
  61 ///
  62 class BucketBox {
  63 public:
  64     BucketBox()
  65     { _offset[0] = 0; _offset[1] = 0; _size[0] = 0; _size[1] = 0; }
  66     BucketBox(double lon, double lat, double width, double height)
  67     {
  68         _offset[0] = _longitudeDegToOffset(lon);
  69         _offset[1] = _latitudeDegToOffset(lat);
  70         _size[0] = _degToSize(width);
  71         _size[1] = _degToSize(height);
  72     }
  73     BucketBox(const BucketBox& bucketBox)
  74     {
  75         _offset[0] = bucketBox._offset[0];
  76         _offset[1] = bucketBox._offset[1];
  77         _size[0] = bucketBox._size[0];
  78         _size[1] = bucketBox._size[1];
  79     }
  80
  81     BucketBox& operator=(const BucketBox& bucketBox)
  82     {
  83         _offset[0] = bucketBox._offset[0];
  84         _offset[1] = bucketBox._offset[1];
  85         _size[0] = bucketBox._size[0];
  86         _size[1] = bucketBox._size[1];
  87         return *this;
  88     }
  89
  90     bool empty() const
  91     { return _size[0] == 0 || _size[1] == 0; }
  92
  93     unsigned getOffset(unsigned i) const
  94     { return _offset[i]; }
  95     void setOffset(unsigned i, unsigned offset)
  96     { _offset[i] = offset; }
  97
  98     unsigned getSize(unsigned i) const
  99     { return _size[i]; }
 100     void setSize(unsigned i, unsigned size)
 101     { _size[i] = size; }
 102
 103     double getLongitudeDeg() const
 104     { return _offsetToLongitudeDeg(_offset[0]); }
 105     void setLongitudeDeg(double lon)
 106     { _offset[0] = _longitudeDegToOffset(lon); }
 107
 108     double getLatitudeDeg() const
 109     { return _offsetToLatitudeDeg(_offset[1]); }
 110     void setLatitudeDeg(double lat)
 111     { _offset[1] = _latitudeDegToOffset(lat); }
 112
 113     double getWidthDeg() const
 114     { return _sizeToDeg(_size[0]); }
 115     void setWidthDeg(double width)
 116     { _size[0] = _degToSize(width); }
 117
 118     double getHeightDeg() const
 119     { return _sizeToDeg(_size[1]); }
 120     void setHeightDeg(double height)
 121     { _size[1] = _degToSize(height); }
 122
 123     bool getWidthIsBucketSize() const
 124     {
 125         if (_size[0] <= _bucketSpanAtOffset(_offset[1]))
 126             return true;
 127         return _size[0] <= _bucketSpanAtOffset(_offset[1] + _size[1] - 1);
 128     }
 129
 130     bool getHeightIsBucketSize() const
 131     { return _size[1] == 1; }
 132     bool getIsBucketSize() const
 133     { return getHeightIsBucketSize() && getWidthIsBucketSize(); }
 134
 135     SGBucket getBucket() const
 136     {
 137         // left align longitude offsets
 138         unsigned offset = _offset[0] - _offset[0] % _bucketSpanAtOffset(_offset[1]);
 139         return SGBucket(_offsetToLongitudeDeg(offset), _offsetToLatitudeDeg(_offset[1]));
 140     }
 141
 142     BucketBox getParentBox(unsigned level) const
 143     {
 144         BucketBox box;
 145         unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
 146         unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
 147         box._offset[0] = _offset[0] - _offset[0] % plon;
 148         box._offset[0] = _normalizeLongitude(box._offset[0]);
 149         box._offset[1] = _offset[1] - _offset[1] % plat;
 150         box._size[0] = plon;
 151         box._size[1] = plat;
 152
 153         return box;
 154     }
 155
 156     BucketBox getSubBoxHeight(unsigned j, unsigned level) const
 157     {
 158         assert(0 < level);
 159         BucketBox box;
 160         unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
 161         unsigned plat1 = plat*_latFactors[level - 1];
 162         box._offset[0] = _offset[0];
 163         box._offset[1] = _offset[1] - _offset[1] % plat1 + j*plat;
 164         box._size[0] = _size[0];
 165         box._size[1] = plat;
 166
 167         return box;
 168     }
 169
 170     BucketBox getSubBoxWidth(unsigned i, unsigned level) const
 171     {
 172         assert(0 < level);
 173         BucketBox box;
 174         unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
 175         unsigned plon1 = plon*_lonFactors[level - 1];
 176         box._offset[0] = _offset[0] - _offset[0] % plon1 + i*plon;
 177         box._offset[1] = _offset[1];
 178         box._size[0] = plon;
 179         box._size[1] = _size[1];
 180
 181         box._offset[0] = _normalizeLongitude(box._offset[0]);
 182
 183         return box;
 184     }
 185
 186     unsigned getWidthLevel() const
 187     { return _getLevel(_lonFactors, Elements(_lonFactors), _offset[0], _offset[0] + _size[0]); }
 188     unsigned getHeightLevel() const
 189     { return _getLevel(_latFactors, Elements(_latFactors), _offset[1], _offset[1] + _size[1]); }
 190
 191     unsigned getWidthIncrement(unsigned level) const
 192     {
 193         level = SGMisc<unsigned>::clip(level, 5, Elements(_lonFactors));
 194         return product(_lonFactors + level, Elements(_lonFactors) - level);
 195     }
 196     unsigned getHeightIncrement(unsigned level) const
 197     {
 198         level = SGMisc<unsigned>::clip(level, 5, Elements(_latFactors));
 199         return product(_latFactors + level, Elements(_latFactors) - level);
 200     }
 201
 202     unsigned getStartLevel() const
 203     {
 204         if (getWidthIsBucketSize())
 205             return getHeightLevel();
 206         return std::min(getWidthLevel(), getHeightLevel());
 207     }
 208
 209     SGSpheref getBoundingSphere() const
 210     {
 211         SGBoxf box;
 212         for (unsigned i = 0, incx = 10*8; incx != 0; i += incx) {
 213             for (unsigned j = 0, incy = 10*8; incy != 0; j += incy) {
 214                 box.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, -1000)));
 215                 box.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, 10000)));
 216                 incy = std::min(incy, _size[1] - j);
 217             }
 218             incx = std::min(incx, _size[0] - i);
 219         }
 220         SGSpheref sphere(box.getCenter(), 0);
 221         for (unsigned i = 0, incx = 10*8; incx != 0; i += incx) {
 222             for (unsigned j = 0, incy = 10*8; incy != 0; j += incy) {
 223                 float r2;
 224                 r2 = distSqr(sphere.getCenter(), SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, -1000)));
 225                 if (sphere.getRadius2() < r2)
 226                     sphere.setRadius(sqrt(r2));
 227                 r2 = distSqr(sphere.getCenter(), SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, 10000)));
 228                 if (sphere.getRadius2() < r2)
 229                     sphere.setRadius(sqrt(r2));
 230                 incy = std::min(incy, _size[1] - j);
 231             }
 232             incx = std::min(incx, _size[0] - i);
 233         }
 234         return sphere;
 235     }
 236
 237     // Split the current box into up to two boxes that do not cross the 360 deg border.
 238     unsigned periodicSplit(BucketBox bucketBoxList[2]) const
 239     {
 240         if (empty())
 241             return 0;
 242
 243         bucketBoxList[0] = *this;
 244         bucketBoxList[0]._offset[0] = _normalizeLongitude(bucketBoxList[0]._offset[0]);
 245         if (bucketBoxList[0]._offset[0] + bucketBoxList[0]._size[0] <= 360*8)
 246             return 1;
 247
 248         bucketBoxList[1] = bucketBoxList[0];
 249         bucketBoxList[0]._size[0] = 360*8 - bucketBoxList[0]._offset[0];
 250
 251         bucketBoxList[1]._offset[0] = 0;
 252         bucketBoxList[1]._size[0] = _size[0] - bucketBoxList[0]._size[0];
 253
 254         return 2;
 255     }
 256
 257     unsigned getSubDivision(BucketBox bucketBoxList[], unsigned bucketBoxListSize) const
 258     {
 259         unsigned numTiles = 0;
 260
 261         // Quad tree like structure in x and y direction
 262         unsigned widthLevel = getWidthLevel();
 263         unsigned heightLevel = getHeightLevel();
 264
 265         unsigned level;
 266         if (getWidthIsBucketSize()) {
 267             level = heightLevel;
 268         } else {
 269             level = std::min(widthLevel, heightLevel);
 270         }
 271         for (unsigned j = 0; j < _latFactors[level]; ++j) {
 272             BucketBox heightSplitBox = getSubBoxHeight(j, level + 1);
 273
 274             heightSplitBox = _intersection(*this, heightSplitBox);
 275             if (heightSplitBox.empty())
 276                 continue;
 277
 278             if (heightSplitBox.getWidthIsBucketSize()) {
 279                 bucketBoxList[numTiles++] = heightSplitBox;
 280                 assert(numTiles <= bucketBoxListSize);
 281             } else {
 282                 for (unsigned i = 0; i < _lonFactors[widthLevel]; ++i) {
 283                     BucketBox childBox = _intersection(heightSplitBox, heightSplitBox.getSubBoxWidth(i, widthLevel + 1));
 284                     if (childBox.empty())
 285                         continue;
 286
 287                     bucketBoxList[numTiles++] = childBox;
 288                     assert(numTiles <= bucketBoxListSize);
 289                 }
 290             }
 291         }
 292         return numTiles;
 293     }
 294
 295     unsigned getTileTriangles(unsigned i, unsigned j, unsigned width, unsigned height,
 296                               SGVec3f points[6], SGVec3f normals[6], SGVec2f texCoords[6]) const
 297     {
 298         unsigned numPoints = 0;
 299
 300         unsigned x0 = _offset[0] + i;
 301         unsigned x1 = x0 + width;
 302
 303         unsigned y0 = _offset[1] + j;
 304         unsigned y1 = y0 + height;
 305
 306         SGGeod p00 = _offsetToGeod(x0, y0, 0);
 307         SGVec3f v00 = SGVec3f::fromGeod(p00);
 308         SGVec3f n00 = SGQuatf::fromLonLat(p00).backTransform(SGVec3f(0, 0, -1));
 309         SGVec2f t00(x0*1.0/(360*8), y0*1.0/(180*8));
 310
 311         SGGeod p10 = _offsetToGeod(x1, y0, 0);
 312         SGVec3f v10 = SGVec3f::fromGeod(p10);
 313         SGVec3f n10 = SGQuatf::fromLonLat(p10).backTransform(SGVec3f(0, 0, -1));
 314         SGVec2f t10(x1*1.0/(360*8), y0*1.0/(180*8));
 315
 316         SGGeod p11 = _offsetToGeod(x1, y1, 0);
 317         SGVec3f v11 = SGVec3f::fromGeod(p11);
 318         SGVec3f n11 = SGQuatf::fromLonLat(p11).backTransform(SGVec3f(0, 0, -1));
 319         SGVec2f t11(x1*1.0/(360*8), y1*1.0/(180*8));
 320
 321         SGGeod p01 = _offsetToGeod(x0, y1, 0);
 322         SGVec3f v01 = SGVec3f::fromGeod(p01);
 323         SGVec3f n01 = SGQuatf::fromLonLat(p01).backTransform(SGVec3f(0, 0, -1));
 324         SGVec2f t01(x0*1.0/(360*8), y1*1.0/(180*8));
 325
 326         if (y0 != 0) {
 327             points[numPoints] = v00;
 328             normals[numPoints] = n00;
 329             texCoords[numPoints] = t00;
 330             ++numPoints;
 331
 332             points[numPoints] = v10;
 333             normals[numPoints] = n10;
 334             texCoords[numPoints] = t10;
 335             ++numPoints;
 336
 337             points[numPoints] = v01;
 338             normals[numPoints] = n01;
 339             texCoords[numPoints] = t01;
 340             ++numPoints;
 341         }
 342         if (y1 != 180*8) {
 343             points[numPoints] = v11;
 344             normals[numPoints] = n11;
 345             texCoords[numPoints] = t11;
 346             ++numPoints;
 347
 348             points[numPoints] = v01;
 349             normals[numPoints] = n01;
 350             texCoords[numPoints] = t01;
 351             ++numPoints;
 352
 353             points[numPoints] = v10;
 354             normals[numPoints] = n10;
 355             texCoords[numPoints] = t10;
 356             ++numPoints;
 357         }
 358         return numPoints;
 359     }
 360
 361 private:
 362     static unsigned _normalizeLongitude(unsigned offset)
 363     { return offset - (360*8)*(offset/(360*8)); }
 364
 365     static unsigned _longitudeDegToOffset(double lon)
 366     {
 367         unsigned offset = (unsigned)(8*(lon + 180) + 0.5);
 368         return _normalizeLongitude(offset);
 369     }
 370     static double _offsetToLongitudeDeg(unsigned offset)
 371     { return offset*0.125 - 180; }
 372
 373     static unsigned _latitudeDegToOffset(double lat)
 374     {
 375         if (lat < -90)
 376             return 0;
 377         unsigned offset = (unsigned)(8*(lat + 90) + 0.5);
 378         if (8*180 < offset)
 379             return 8*180;
 380         return offset;
 381     }
 382     static double _offsetToLatitudeDeg(unsigned offset)
 383     { return offset*0.125 - 90; }
 384
 385     static unsigned _degToSize(double deg)
 386     {
 387         if (deg <= 0)
 388             return 0;
 389         return (unsigned)(8*deg + 0.5);
 390     }
 391     static double _sizeToDeg(unsigned size)
 392     { return size*0.125; }
 393
 394     static unsigned _bucketSpanAtOffset(unsigned offset)
 395     { return (unsigned)(8*sg_bucket_span(_offsetToLatitudeDeg(offset) + 0.0625) + 0.5); }
 396
 397     static SGGeod _offsetToGeod(unsigned offset0, unsigned offset1, double elev)
 398     { return SGGeod::fromDegM(_offsetToLongitudeDeg(offset0), _offsetToLatitudeDeg(offset1), elev); }
 399
 400     static unsigned _getLevel(const unsigned factors[], unsigned nFactors, unsigned begin, unsigned end)
 401     {
 402         unsigned rbegin = end - 1;
 403         for (; 0 < nFactors;) {
 404             if (begin == rbegin)
 405                 break;
 406             --nFactors;
 407             begin /= factors[nFactors];
 408             rbegin /= factors[nFactors];
 409         }
 410
 411         return nFactors;
 412     }
 413
 414     static BucketBox _intersection(const BucketBox& box0, const BucketBox& box1)
 415     {
 416         BucketBox box;
 417         for (unsigned i = 0; i < 2; ++i) {
 418             box._offset[i] = std::max(box0._offset[i], box1._offset[i]);
 419             unsigned m = std::min(box0._offset[i] + box0._size[i], box1._offset[i] + box1._size[i]);
 420             if (m <= box._offset[i])
 421                 box._size[i] = 0;
 422             else
 423                 box._size[i] = m - box._offset[i];
 424         }
 425
 426         box._offset[0] = _normalizeLongitude(box._offset[0]);
 427
 428         return box;
 429     }
 430
 431     unsigned _offset[2];
 432     unsigned _size[2];
 433 };
 434
 435 inline bool
 436 operator==(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 437 {
 438     if (bucketBox0.getOffset(0) != bucketBox1.getOffset(0))
 439         return false;
 440     if (bucketBox0.getOffset(1) != bucketBox1.getOffset(1))
 441         return false;
 442     if (bucketBox0.getSize(0) != bucketBox1.getSize(0))
 443         return false;
 444     if (bucketBox0.getSize(1) != bucketBox1.getSize(1))
 445         return false;
 446     return true;
 447 }
 448
 449 inline bool
 450 operator!=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 451 { return !operator==(bucketBox0, bucketBox1); }
 452
 453 inline bool
 454 operator<(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 455 {
 456     if (bucketBox0.getOffset(0) < bucketBox1.getOffset(0)) return true;
 457     else if (bucketBox1.getOffset(0) < bucketBox0.getOffset(0)) return false;
 458     else if (bucketBox0.getOffset(1) < bucketBox1.getOffset(1)) return true;
 459     else if (bucketBox1.getOffset(1) < bucketBox0.getOffset(1)) return false;
 460     else if (bucketBox0.getSize(0) < bucketBox1.getSize(0)) return true;
 461     else if (bucketBox1.getSize(0) < bucketBox0.getSize(0)) return false;
 462     else return bucketBox0.getSize(1) < bucketBox1.getSize(1);
 463 }
 464
 465 inline bool
 466 operator>(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 467 { return operator<(bucketBox1, bucketBox0); }
 468
 469 inline bool
 470 operator<=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 471 { return !operator>(bucketBox0, bucketBox1); }
 472
 473 inline bool
 474 operator>=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 475 { return !operator<(bucketBox0, bucketBox1); }
 476
 477 /// Stream output operator.
 478 /// Note that this is not only used for pretty printing but also for
 479 /// generating the meta file names for on demand paging.
 480 /// So, don't modify unless you know where else this is used.
 481 template<typename char_type, typename traits_type>
 482 std::basic_ostream<char_type, traits_type>&
 483 operator<<(std::basic_ostream<char_type, traits_type>& os, const BucketBox& bucketBox)
 484 {
 485     double lon = bucketBox.getLongitudeDeg();
 486     if (lon < 0)
 487         os << "w" << -lon;
 488     else
 489         os << "e" << lon;
 490
 491     double lat = bucketBox.getLatitudeDeg();
 492     if (lat < -90)
 493         lat = -90;
 494     if (90 < lat)
 495         lat = 90;
 496     if (lat < 0)
 497         os << "s" << -lat;
 498     else
 499         os << "n" << lat;
 500
 501     os << "-" << bucketBox.getWidthDeg() << "x" << bucketBox.getHeightDeg();
 502     return os;
 503 }
 504
 505 /// Stream inout operator.
 506 /// Note that this is used for reading the meta file names for on demand paging.
 507 /// So, don't modify unless you know where else this is used.
 508 template<typename char_type, typename traits_type>
 509 std::basic_istream<char_type, traits_type>&
 510 operator>>(std::basic_istream<char_type, traits_type>& is, BucketBox& bucketBox)
 511 {
 512     char c;
 513     is >> c;
 514     if (is.fail())
 515         return is;
 516
 517     int sign = 0;
 518     if (c == 'w')
 519         sign = -1;
 520     else if (c == 'e')
 521         sign = 1;
 522     else {
 523         is.setstate(std::ios::failbit | is.rdstate());
 524         return is;
 525     }
 526
 527     double num;
 528     is >> num;
 529     if (is.fail()) {
 530         is.setstate(std::ios::failbit | is.rdstate());
 531         return is;
 532     }
 533     bucketBox.setLongitudeDeg(sign*num);
 534
 535     is >> c;
 536     if (is.fail())
 537         return is;
 538
 539     sign = 0;
 540     if (c == 's')
 541         sign = -1;
 542     else if (c == 'n')
 543         sign = 1;
 544     else {
 545         is.setstate(std::ios::failbit | is.rdstate());
 546         return is;
 547     }
 548
 549     is >> num;
 550     if (is.fail())
 551         return is;
 552     bucketBox.setLatitudeDeg(sign*num);
 553
 554     is >> c;
 555     if (is.fail())
 556         return is;
 557     if (c != '-'){
 558         is.setstate(std::ios::failbit | is.rdstate());
 559         return is;
 560     }
 561
 562     is >> num;
 563     if (is.fail())
 564         return is;
 565     bucketBox.setWidthDeg(SGMiscd::min(num, 360));
 566
 567     is >> c;
 568     if (is.fail())
 569         return is;
 570     if (c != 'x'){
 571         is.setstate(std::ios::failbit | is.rdstate());
 572         return is;
 573     }
 574
 575     is >> num;
 576     if (is.fail())
 577         return is;
 578     bucketBox.setHeightDeg(SGMiscd::min(num, 90 - bucketBox.getLatitudeDeg()));
 579
 580     return is;
 581 }
 582
 583 } // namespace simgear
 584
 585 #endif