simgear/scene/tgdb/BucketBox.hxx

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