1 // BucketBox.cxx -- Helper for on demand database paging.
3 // Copyright (C) 2010 - 2013 Mathias Froehlich
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.
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.
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.
20 #ifndef _BUCKETBOX_HXX
21 #define _BUCKETBOX_HXX
29 #include <simgear/bucket/newbucket.hxx>
30 #include <simgear/math/SGGeometry.hxx>
34 #define Elements(x) (sizeof(x)/sizeof((x)[0]))
37 static const unsigned _lonFactors[] = { 2, 5, 3, 3, 2, 2, /* sub degree */ 2, 2, 2 };
39 static const unsigned _latFactors[] = { 3, 5, 1, 3, 2, 2, /* sub degree */ 2, 2, 2 };
41 static unsigned product(const unsigned* factors, unsigned count)
49 /// /Rectangular/ sub part of the earths surface.
50 /// Stored with offset point in lon/lat and width and height.
51 /// The values are stored in a fixed point format having 3 fractional
52 /// bits which matches the SGBuckets maximum tile resolution.
54 /// Notable /design/ decision:
55 /// * The longitude maps to the interval [-180,180[.
56 /// The latitude maps to the interval [-90,90].
57 /// This works now that the tiles do no longer cut
58 /// neither the 180deg nor the 0deg boundary.
59 /// * This is not meant to be an API class for simgear. This is
60 /// just an internal tool that I would like to keep in the SPT loader.
61 /// But I want to have coverage somehow tested with the usual unit
62 /// tests, which is the reason to have this file split out.
67 { _offset[0] = 0; _offset[1] = 0; _size[0] = 0; _size[1] = 0; }
68 BucketBox(double lon, double lat, double width, double height)
70 _offset[0] = _longitudeDegToOffset(lon);
71 _offset[1] = _latitudeDegToOffset(lat);
72 _size[0] = _degToSize(width);
73 _size[1] = _degToSize(height);
75 BucketBox(const BucketBox& bucketBox)
77 _offset[0] = bucketBox._offset[0];
78 _offset[1] = bucketBox._offset[1];
79 _size[0] = bucketBox._size[0];
80 _size[1] = bucketBox._size[1];
83 BucketBox& operator=(const BucketBox& bucketBox)
85 _offset[0] = bucketBox._offset[0];
86 _offset[1] = bucketBox._offset[1];
87 _size[0] = bucketBox._size[0];
88 _size[1] = bucketBox._size[1];
93 { return _size[0] == 0 || _size[1] == 0; }
95 unsigned getOffset(unsigned i) const
96 { return _offset[i]; }
97 void setOffset(unsigned i, unsigned offset)
98 { _offset[i] = offset; }
100 unsigned getSize(unsigned i) const
102 void setSize(unsigned i, unsigned size)
105 double getLongitudeDeg() const
106 { return _offsetToLongitudeDeg(_offset[0]); }
107 void setLongitudeDeg(double lon)
108 { _offset[0] = _longitudeDegToOffset(lon); }
110 double getLatitudeDeg() const
111 { return _offsetToLatitudeDeg(_offset[1]); }
112 void setLatitudeDeg(double lat)
113 { _offset[1] = _latitudeDegToOffset(lat); }
115 double getWidthDeg() const
116 { return _sizeToDeg(_size[0]); }
117 void setWidthDeg(double width)
118 { _size[0] = _degToSize(width); }
120 double getHeightDeg() const
121 { return _sizeToDeg(_size[1]); }
122 void setHeightDeg(double height)
123 { _size[1] = _degToSize(height); }
125 bool getWidthIsBucketSize() const
127 if (_size[0] <= _bucketSpanAtOffset(_offset[1]))
129 return _size[0] <= _bucketSpanAtOffset(_offset[1] + _size[1] - 1);
132 bool getHeightIsBucketSize() const
133 { return _size[1] == 1; }
134 bool getIsBucketSize() const
135 { return getHeightIsBucketSize() && getWidthIsBucketSize(); }
137 SGBucket getBucket() const
139 // left align longitude offsets
140 unsigned offset = _offset[0] - _offset[0] % _bucketSpanAtOffset(_offset[1]);
141 return SGBucket(_offsetToLongitudeDeg(offset), _offsetToLatitudeDeg(_offset[1]));
144 BucketBox getParentBox(unsigned level) const
147 unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
148 unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
149 box._offset[0] = _offset[0] - _offset[0] % plon;
150 box._offset[0] = _normalizeLongitude(box._offset[0]);
151 box._offset[1] = _offset[1] - _offset[1] % plat;
158 BucketBox getSubBoxHeight(unsigned j, unsigned level) const
162 unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
163 unsigned plat1 = plat*_latFactors[level - 1];
164 box._offset[0] = _offset[0];
165 box._offset[1] = _offset[1] - _offset[1] % plat1 + j*plat;
166 box._size[0] = _size[0];
172 BucketBox getSubBoxWidth(unsigned i, unsigned level) const
176 unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
177 unsigned plon1 = plon*_lonFactors[level - 1];
178 box._offset[0] = _offset[0] - _offset[0] % plon1 + i*plon;
179 box._offset[1] = _offset[1];
181 box._size[1] = _size[1];
183 box._offset[0] = _normalizeLongitude(box._offset[0]);
188 unsigned getWidthLevel() const
189 { return _getLevel(_lonFactors, Elements(_lonFactors), _offset[0], _offset[0] + _size[0]); }
190 unsigned getHeightLevel() const
191 { return _getLevel(_latFactors, Elements(_latFactors), _offset[1], _offset[1] + _size[1]); }
193 unsigned getWidthIncrement(unsigned level) const
195 level = SGMisc<unsigned>::clip(level, 5, Elements(_lonFactors));
196 return product(_lonFactors + level, Elements(_lonFactors) - level);
198 unsigned getHeightIncrement(unsigned level) const
200 level = SGMisc<unsigned>::clip(level, 5, Elements(_latFactors));
201 return product(_latFactors + level, Elements(_latFactors) - level);
204 unsigned getStartLevel() const
206 if (getWidthIsBucketSize())
207 return getHeightLevel();
208 return std::min(getWidthLevel(), getHeightLevel());
211 SGSpheref getBoundingSphere() const
214 for (unsigned i = 0, incx = 10*8; incx != 0; i += incx) {
215 for (unsigned j = 0, incy = 10*8; incy != 0; j += incy) {
216 box.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, -1000)));
217 box.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, 10000)));
218 incy = std::min(incy, _size[1] - j);
220 incx = std::min(incx, _size[0] - i);
222 SGSpheref sphere(box.getCenter(), 0);
223 for (unsigned i = 0, incx = 10*8; incx != 0; i += incx) {
224 for (unsigned j = 0, incy = 10*8; incy != 0; j += incy) {
226 r2 = distSqr(sphere.getCenter(), SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, -1000)));
227 if (sphere.getRadius2() < r2)
228 sphere.setRadius(sqrt(r2));
229 r2 = distSqr(sphere.getCenter(), SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, 10000)));
230 if (sphere.getRadius2() < r2)
231 sphere.setRadius(sqrt(r2));
232 incy = std::min(incy, _size[1] - j);
234 incx = std::min(incx, _size[0] - i);
239 // Split the current box into up to two boxes that do not cross the 360 deg border.
240 unsigned periodicSplit(BucketBox bucketBoxList[2]) const
245 bucketBoxList[0] = *this;
246 bucketBoxList[0]._offset[0] = _normalizeLongitude(bucketBoxList[0]._offset[0]);
247 if (bucketBoxList[0]._offset[0] + bucketBoxList[0]._size[0] <= 360*8)
250 bucketBoxList[1] = bucketBoxList[0];
251 bucketBoxList[0]._size[0] = 360*8 - bucketBoxList[0]._offset[0];
253 bucketBoxList[1]._offset[0] = 0;
254 bucketBoxList[1]._size[0] = _size[0] - bucketBoxList[0]._size[0];
259 unsigned getSubDivision(BucketBox bucketBoxList[], unsigned bucketBoxListSize) const
261 unsigned numTiles = 0;
263 // Quad tree like structure in x and y direction
264 unsigned widthLevel = getWidthLevel();
265 unsigned heightLevel = getHeightLevel();
268 if (getWidthIsBucketSize()) {
271 level = std::min(widthLevel, heightLevel);
273 for (unsigned j = 0; j < _latFactors[level]; ++j) {
274 BucketBox heightSplitBox = getSubBoxHeight(j, level + 1);
276 heightSplitBox = _intersection(*this, heightSplitBox);
277 if (heightSplitBox.empty())
280 if (heightSplitBox.getWidthIsBucketSize()) {
281 bucketBoxList[numTiles++] = heightSplitBox;
282 assert(numTiles <= bucketBoxListSize);
284 for (unsigned i = 0; i < _lonFactors[widthLevel]; ++i) {
285 BucketBox childBox = _intersection(heightSplitBox, heightSplitBox.getSubBoxWidth(i, widthLevel + 1));
286 if (childBox.empty())
289 bucketBoxList[numTiles++] = childBox;
290 assert(numTiles <= bucketBoxListSize);
297 unsigned getTileTriangles(unsigned i, unsigned j, unsigned width, unsigned height,
298 SGVec3f points[6], SGVec3f normals[6], SGVec2f texCoords[6]) const
300 unsigned numPoints = 0;
302 unsigned x0 = _offset[0] + i;
303 unsigned x1 = x0 + width;
305 unsigned y0 = _offset[1] + j;
306 unsigned y1 = y0 + height;
308 SGGeod p00 = _offsetToGeod(x0, y0, 0);
309 SGVec3f v00 = SGVec3f::fromGeod(p00);
310 SGVec3f n00 = SGQuatf::fromLonLat(p00).backTransform(SGVec3f(0, 0, -1));
311 SGVec2f t00(x0*1.0/(360*8), y0*1.0/(180*8));
313 SGGeod p10 = _offsetToGeod(x1, y0, 0);
314 SGVec3f v10 = SGVec3f::fromGeod(p10);
315 SGVec3f n10 = SGQuatf::fromLonLat(p10).backTransform(SGVec3f(0, 0, -1));
316 SGVec2f t10(x1*1.0/(360*8), y0*1.0/(180*8));
318 SGGeod p11 = _offsetToGeod(x1, y1, 0);
319 SGVec3f v11 = SGVec3f::fromGeod(p11);
320 SGVec3f n11 = SGQuatf::fromLonLat(p11).backTransform(SGVec3f(0, 0, -1));
321 SGVec2f t11(x1*1.0/(360*8), y1*1.0/(180*8));
323 SGGeod p01 = _offsetToGeod(x0, y1, 0);
324 SGVec3f v01 = SGVec3f::fromGeod(p01);
325 SGVec3f n01 = SGQuatf::fromLonLat(p01).backTransform(SGVec3f(0, 0, -1));
326 SGVec2f t01(x0*1.0/(360*8), y1*1.0/(180*8));
329 points[numPoints] = v00;
330 normals[numPoints] = n00;
331 texCoords[numPoints] = t00;
334 points[numPoints] = v10;
335 normals[numPoints] = n10;
336 texCoords[numPoints] = t10;
339 points[numPoints] = v01;
340 normals[numPoints] = n01;
341 texCoords[numPoints] = t01;
345 points[numPoints] = v11;
346 normals[numPoints] = n11;
347 texCoords[numPoints] = t11;
350 points[numPoints] = v01;
351 normals[numPoints] = n01;
352 texCoords[numPoints] = t01;
355 points[numPoints] = v10;
356 normals[numPoints] = n10;
357 texCoords[numPoints] = t10;
364 static unsigned _normalizeLongitude(unsigned offset)
365 { return offset - (360*8)*(offset/(360*8)); }
367 static unsigned _longitudeDegToOffset(double lon)
369 unsigned offset = (unsigned)(8*(lon + 180) + 0.5);
370 return _normalizeLongitude(offset);
372 static double _offsetToLongitudeDeg(unsigned offset)
373 { return offset*0.125 - 180; }
375 static unsigned _latitudeDegToOffset(double lat)
379 unsigned offset = (unsigned)(8*(lat + 90) + 0.5);
384 static double _offsetToLatitudeDeg(unsigned offset)
385 { return offset*0.125 - 90; }
387 static unsigned _degToSize(double deg)
391 return (unsigned)(8*deg + 0.5);
393 static double _sizeToDeg(unsigned size)
394 { return size*0.125; }
396 static unsigned _bucketSpanAtOffset(unsigned offset)
397 { return (unsigned)(8*sg_bucket_span(_offsetToLatitudeDeg(offset) + 0.0625) + 0.5); }
399 static SGGeod _offsetToGeod(unsigned offset0, unsigned offset1, double elev)
400 { return SGGeod::fromDegM(_offsetToLongitudeDeg(offset0), _offsetToLatitudeDeg(offset1), elev); }
402 static unsigned _getLevel(const unsigned factors[], unsigned nFactors, unsigned begin, unsigned end)
404 unsigned rbegin = end - 1;
405 for (; 0 < nFactors;) {
409 begin /= factors[nFactors];
410 rbegin /= factors[nFactors];
416 static BucketBox _intersection(const BucketBox& box0, const BucketBox& box1)
419 for (unsigned i = 0; i < 2; ++i) {
420 box._offset[i] = std::max(box0._offset[i], box1._offset[i]);
421 unsigned m = std::min(box0._offset[i] + box0._size[i], box1._offset[i] + box1._size[i]);
422 if (m <= box._offset[i])
425 box._size[i] = m - box._offset[i];
428 box._offset[0] = _normalizeLongitude(box._offset[0]);
438 operator==(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
440 if (bucketBox0.getOffset(0) != bucketBox1.getOffset(0))
442 if (bucketBox0.getOffset(1) != bucketBox1.getOffset(1))
444 if (bucketBox0.getSize(0) != bucketBox1.getSize(0))
446 if (bucketBox0.getSize(1) != bucketBox1.getSize(1))
452 operator!=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
453 { return !operator==(bucketBox0, bucketBox1); }
456 operator<(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
458 if (bucketBox0.getOffset(0) < bucketBox1.getOffset(0)) return true;
459 else if (bucketBox1.getOffset(0) < bucketBox0.getOffset(0)) return false;
460 else if (bucketBox0.getOffset(1) < bucketBox1.getOffset(1)) return true;
461 else if (bucketBox1.getOffset(1) < bucketBox0.getOffset(1)) return false;
462 else if (bucketBox0.getSize(0) < bucketBox1.getSize(0)) return true;
463 else if (bucketBox1.getSize(0) < bucketBox0.getSize(0)) return false;
464 else return bucketBox0.getSize(1) < bucketBox1.getSize(1);
468 operator>(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
469 { return operator<(bucketBox1, bucketBox0); }
472 operator<=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
473 { return !operator>(bucketBox0, bucketBox1); }
476 operator>=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
477 { return !operator<(bucketBox0, bucketBox1); }
479 /// Stream output operator.
480 /// Note that this is not only used for pretty printing but also for
481 /// generating the meta file names for on demand paging.
482 /// So, don't modify unless you know where else this is used.
483 template<typename char_type, typename traits_type>
484 std::basic_ostream<char_type, traits_type>&
485 operator<<(std::basic_ostream<char_type, traits_type>& os, const BucketBox& bucketBox)
487 std::basic_stringstream<char_type, traits_type> ss;
489 double minSize = std::min(bucketBox.getWidthDeg(), bucketBox.getHeightDeg());
491 unsigned fieldPrecision = 0;
492 if (minSize <= 0.125) {
494 } else if (minSize <= 0.25) {
496 } else if (minSize <= 0.5) {
500 unsigned lonFieldWidth = 3;
502 lonFieldWidth += 1 + fieldPrecision;
504 ss << std::fixed << std::setfill('0') << std::setprecision(fieldPrecision);
506 double lon = bucketBox.getLongitudeDeg();
508 ss << "w" << std::setw(lonFieldWidth) << -lon << std::setw(0);
510 ss << "e" << std::setw(lonFieldWidth) << lon << std::setw(0);
512 unsigned latFieldWidth = 2;
514 latFieldWidth += 1 + fieldPrecision;
516 double lat = bucketBox.getLatitudeDeg();
522 ss << "s" << std::setw(latFieldWidth) << -lat << std::setw(0);
524 ss << "n" << std::setw(latFieldWidth) << lat << std::setw(0);
526 ss << "-" << bucketBox.getWidthDeg() << "x" << bucketBox.getHeightDeg();
528 return os << ss.str();
531 /// Stream inout operator.
532 /// Note that this is used for reading the meta file names for on demand paging.
533 /// So, don't modify unless you know where else this is used.
534 template<typename char_type, typename traits_type>
535 std::basic_istream<char_type, traits_type>&
536 operator>>(std::basic_istream<char_type, traits_type>& is, BucketBox& bucketBox)
549 is.setstate(std::ios::failbit | is.rdstate());
556 is.setstate(std::ios::failbit | is.rdstate());
559 bucketBox.setLongitudeDeg(sign*num);
571 is.setstate(std::ios::failbit | is.rdstate());
578 bucketBox.setLatitudeDeg(sign*num);
584 is.setstate(std::ios::failbit | is.rdstate());
591 bucketBox.setWidthDeg(SGMiscd::min(num, 360));
597 is.setstate(std::ios::failbit | is.rdstate());
604 bucketBox.setHeightDeg(SGMiscd::min(num, 90 - bucketBox.getLatitudeDeg()));
609 } // namespace simgear