]> git.mxchange.org Git - simgear.git/blob - simgear/scene/tgdb/BucketBox.hxx
SG part of fix for TerraSync models.
[simgear.git] / 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 <iomanip>
26 #include <ostream>
27 #include <sstream>
28
29 #include <simgear/bucket/newbucket.hxx>
30 #include <simgear/math/SGGeometry.hxx>
31
32 namespace simgear {
33
34 #define Elements(x) (sizeof(x)/sizeof((x)[0]))
35
36 // 2*5*3*3 * 4 = 360
37 static const unsigned _lonFactors[] = { 2, 5, 3, 3, 2, 2, /* sub degree */ 2, 2, 2 };
38 // 3*3*5 * 4 = 180
39 static const unsigned _latFactors[] = { 3, 5, 1, 3, 2, 2, /* sub degree */ 2, 2, 2 };
40
41 static unsigned product(const unsigned* factors, unsigned count)
42 {
43     unsigned index = 1;
44     while (count--)
45         index *= *factors++;
46     return index;
47 }
48
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.
53 ///
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.
63 ///
64 class BucketBox {
65 public:
66     BucketBox()
67     { _offset[0] = 0; _offset[1] = 0; _size[0] = 0; _size[1] = 0; }
68     BucketBox(double lon, double lat, double width, double height)
69     {
70         _offset[0] = _longitudeDegToOffset(lon);
71         _offset[1] = _latitudeDegToOffset(lat);
72         _size[0] = _degToSize(width);
73         _size[1] = _degToSize(height);
74     }
75     BucketBox(const BucketBox& bucketBox)
76     {
77         _offset[0] = bucketBox._offset[0];
78         _offset[1] = bucketBox._offset[1];
79         _size[0] = bucketBox._size[0];
80         _size[1] = bucketBox._size[1];
81     }
82
83     BucketBox& operator=(const BucketBox& bucketBox)
84     {
85         _offset[0] = bucketBox._offset[0];
86         _offset[1] = bucketBox._offset[1];
87         _size[0] = bucketBox._size[0];
88         _size[1] = bucketBox._size[1];
89         return *this;
90     }
91
92     bool empty() const
93     { return _size[0] == 0 || _size[1] == 0; }
94
95     unsigned getOffset(unsigned i) const
96     { return _offset[i]; }
97     void setOffset(unsigned i, unsigned offset)
98     { _offset[i] = offset; }
99
100     unsigned getSize(unsigned i) const
101     { return _size[i]; }
102     void setSize(unsigned i, unsigned size)
103     { _size[i] = size; }
104
105     double getLongitudeDeg() const
106     { return _offsetToLongitudeDeg(_offset[0]); }
107     void setLongitudeDeg(double lon)
108     { _offset[0] = _longitudeDegToOffset(lon); }
109
110     double getLatitudeDeg() const
111     { return _offsetToLatitudeDeg(_offset[1]); }
112     void setLatitudeDeg(double lat)
113     { _offset[1] = _latitudeDegToOffset(lat); }
114
115     double getWidthDeg() const
116     { return _sizeToDeg(_size[0]); }
117     void setWidthDeg(double width)
118     { _size[0] = _degToSize(width); }
119
120     double getHeightDeg() const
121     { return _sizeToDeg(_size[1]); }
122     void setHeightDeg(double height)
123     { _size[1] = _degToSize(height); }
124
125     bool getWidthIsBucketSize() const
126     {
127         if (_size[0] <= _bucketSpanAtOffset(_offset[1]))
128             return true;
129         return _size[0] <= _bucketSpanAtOffset(_offset[1] + _size[1] - 1);
130     }
131
132     bool getHeightIsBucketSize() const
133     { return _size[1] == 1; }
134     bool getIsBucketSize() const
135     { return getHeightIsBucketSize() && getWidthIsBucketSize(); }
136
137     SGBucket getBucket() const
138     {
139         // left align longitude offsets
140         unsigned offset = _offset[0] - _offset[0] % _bucketSpanAtOffset(_offset[1]);
141         return SGBucket(_offsetToLongitudeDeg(offset), _offsetToLatitudeDeg(_offset[1]));
142     }
143
144     BucketBox getParentBox(unsigned level) const
145     {
146         BucketBox box;
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;
152         box._size[0] = plon;
153         box._size[1] = plat;
154
155         return box;
156     }
157
158     BucketBox getSubBoxHeight(unsigned j, unsigned level) const
159     {
160         assert(0 < level);
161         BucketBox box;
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];
167         box._size[1] = plat;
168
169         return box;
170     }
171
172     BucketBox getSubBoxWidth(unsigned i, unsigned level) const
173     {
174         assert(0 < level);
175         BucketBox box;
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];
180         box._size[0] = plon;
181         box._size[1] = _size[1];
182
183         box._offset[0] = _normalizeLongitude(box._offset[0]);
184     
185         return box;
186     }
187
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]); }
192
193     unsigned getWidthIncrement(unsigned level) const
194     {
195         level = SGMisc<unsigned>::clip(level, 5, Elements(_lonFactors));
196         return product(_lonFactors + level, Elements(_lonFactors) - level);
197     }
198     unsigned getHeightIncrement(unsigned level) const
199     {
200         level = SGMisc<unsigned>::clip(level, 5, Elements(_latFactors));
201         return product(_latFactors + level, Elements(_latFactors) - level);
202     }
203
204     unsigned getStartLevel() const
205     {
206         if (getWidthIsBucketSize())
207             return getHeightLevel();
208         return std::min(getWidthLevel(), getHeightLevel());
209     }
210
211     SGSpheref getBoundingSphere() const
212     {
213         SGBoxf box;
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);
219             }
220             incx = std::min(incx, _size[0] - i);
221         }
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) {
225                 float r2;
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);
233             }
234             incx = std::min(incx, _size[0] - i);
235         }
236         return sphere;
237     }
238
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
241     {
242         if (empty())
243             return 0;
244
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)
248             return 1;
249
250         bucketBoxList[1] = bucketBoxList[0];
251         bucketBoxList[0]._size[0] = 360*8 - bucketBoxList[0]._offset[0];
252
253         bucketBoxList[1]._offset[0] = 0;
254         bucketBoxList[1]._size[0] = _size[0] - bucketBoxList[0]._size[0];
255
256         return 2;
257     }
258
259     unsigned getSubDivision(BucketBox bucketBoxList[], unsigned bucketBoxListSize) const
260     {
261         unsigned numTiles = 0;
262     
263         // Quad tree like structure in x and y direction
264         unsigned widthLevel = getWidthLevel();
265         unsigned heightLevel = getHeightLevel();
266         
267         unsigned level;
268         if (getWidthIsBucketSize()) {
269             level = heightLevel;
270         } else {
271             level = std::min(widthLevel, heightLevel);
272         }
273         for (unsigned j = 0; j < _latFactors[level]; ++j) {
274             BucketBox heightSplitBox = getSubBoxHeight(j, level + 1);
275       
276             heightSplitBox = _intersection(*this, heightSplitBox);
277             if (heightSplitBox.empty())
278                 continue;
279       
280             if (heightSplitBox.getWidthIsBucketSize()) {
281                 bucketBoxList[numTiles++] = heightSplitBox;
282                 assert(numTiles <= bucketBoxListSize);
283             } else {
284                 for (unsigned i = 0; i < _lonFactors[widthLevel]; ++i) {
285                     BucketBox childBox = _intersection(heightSplitBox, heightSplitBox.getSubBoxWidth(i, widthLevel + 1));
286                     if (childBox.empty())
287                         continue;
288           
289                     bucketBoxList[numTiles++] = childBox;
290                     assert(numTiles <= bucketBoxListSize);
291                 }
292             }
293         }
294         return numTiles;
295     }
296   
297     unsigned getTileTriangles(unsigned i, unsigned j, unsigned width, unsigned height,
298                               SGVec3f points[6], SGVec3f normals[6], SGVec2f texCoords[6]) const
299     {
300         unsigned numPoints = 0;
301
302         unsigned x0 = _offset[0] + i;
303         unsigned x1 = x0 + width;
304
305         unsigned y0 = _offset[1] + j;
306         unsigned y1 = y0 + height;
307     
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));
312
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));
317
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));
322
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));
327     
328         if (y0 != 0) {
329             points[numPoints] = v00;
330             normals[numPoints] = n00;
331             texCoords[numPoints] = t00;
332             ++numPoints;
333
334             points[numPoints] = v10;
335             normals[numPoints] = n10;
336             texCoords[numPoints] = t10;
337             ++numPoints;
338
339             points[numPoints] = v01;
340             normals[numPoints] = n01;
341             texCoords[numPoints] = t01;
342             ++numPoints;
343         }
344         if (y1 != 180*8) {
345             points[numPoints] = v11;
346             normals[numPoints] = n11;
347             texCoords[numPoints] = t11;
348             ++numPoints;
349
350             points[numPoints] = v01;
351             normals[numPoints] = n01;
352             texCoords[numPoints] = t01;
353             ++numPoints;
354
355             points[numPoints] = v10;
356             normals[numPoints] = n10;
357             texCoords[numPoints] = t10;
358             ++numPoints;
359         }
360         return numPoints;
361     }
362
363 private:
364     static unsigned _normalizeLongitude(unsigned offset)
365     { return offset - (360*8)*(offset/(360*8)); }
366
367     static unsigned _longitudeDegToOffset(double lon)
368     {
369         unsigned offset = (unsigned)(8*(lon + 180) + 0.5);
370         return _normalizeLongitude(offset);
371     }
372     static double _offsetToLongitudeDeg(unsigned offset)
373     { return offset*0.125 - 180; }
374
375     static unsigned _latitudeDegToOffset(double lat)
376     {
377         if (lat < -90)
378             return 0;
379         unsigned offset = (unsigned)(8*(lat + 90) + 0.5);
380         if (8*180 < offset)
381             return 8*180;
382         return offset;
383     }
384     static double _offsetToLatitudeDeg(unsigned offset)
385     { return offset*0.125 - 90; }
386
387     static unsigned _degToSize(double deg)
388     {
389         if (deg <= 0)
390             return 0;
391         return (unsigned)(8*deg + 0.5);
392     }
393     static double _sizeToDeg(unsigned size)
394     { return size*0.125; }
395
396     static unsigned _bucketSpanAtOffset(unsigned offset)
397     { return (unsigned)(8*sg_bucket_span(_offsetToLatitudeDeg(offset) + 0.0625) + 0.5); }
398
399     static SGGeod _offsetToGeod(unsigned offset0, unsigned offset1, double elev)
400     { return SGGeod::fromDegM(_offsetToLongitudeDeg(offset0), _offsetToLatitudeDeg(offset1), elev); }
401   
402     static unsigned _getLevel(const unsigned factors[], unsigned nFactors, unsigned begin, unsigned end)
403     {
404         unsigned rbegin = end - 1;
405         for (; 0 < nFactors;) {
406             if (begin == rbegin)
407                 break;
408             --nFactors;
409             begin /= factors[nFactors];
410             rbegin /= factors[nFactors];
411         }
412
413         return nFactors;
414     }
415
416     static BucketBox _intersection(const BucketBox& box0, const BucketBox& box1)
417     {
418         BucketBox box;
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])
423                 box._size[i] = 0;
424             else
425                 box._size[i] = m - box._offset[i];
426         }
427
428         box._offset[0] = _normalizeLongitude(box._offset[0]);
429
430         return box;
431     }
432
433     unsigned _offset[2];
434     unsigned _size[2];
435 };
436
437 inline bool
438 operator==(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
439 {
440     if (bucketBox0.getOffset(0) != bucketBox1.getOffset(0))
441         return false;
442     if (bucketBox0.getOffset(1) != bucketBox1.getOffset(1))
443         return false;
444     if (bucketBox0.getSize(0) != bucketBox1.getSize(0))
445         return false;
446     if (bucketBox0.getSize(1) != bucketBox1.getSize(1))
447         return false;
448     return true;
449 }
450
451 inline bool
452 operator!=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
453 { return !operator==(bucketBox0, bucketBox1); }
454
455 inline bool
456 operator<(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
457 {
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);
465 }
466
467 inline bool
468 operator>(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
469 { return operator<(bucketBox1, bucketBox0); }
470
471 inline bool
472 operator<=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
473 { return !operator>(bucketBox0, bucketBox1); }
474
475 inline bool
476 operator>=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
477 { return !operator<(bucketBox0, bucketBox1); }
478
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)
486 {
487     std::basic_stringstream<char_type, traits_type> ss;
488
489     double minSize = std::min(bucketBox.getWidthDeg(), bucketBox.getHeightDeg());
490     
491     unsigned fieldPrecision = 0;
492     if (minSize <= 0.125) {
493         fieldPrecision = 3;
494     } else if (minSize <= 0.25) {
495         fieldPrecision = 2;
496     } else if (minSize <= 0.5) {
497         fieldPrecision = 1;
498     }
499
500     unsigned lonFieldWidth = 3;
501     if (fieldPrecision)
502         lonFieldWidth += 1 + fieldPrecision;
503
504     ss << std::fixed << std::setfill('0') << std::setprecision(fieldPrecision);
505
506     double lon = bucketBox.getLongitudeDeg();
507     if (lon < 0)
508         ss << "w" << std::setw(lonFieldWidth) << -lon << std::setw(0);
509     else
510         ss << "e" << std::setw(lonFieldWidth) << lon << std::setw(0);
511     
512     unsigned latFieldWidth = 2;
513     if (fieldPrecision)
514         latFieldWidth += 1 + fieldPrecision;
515
516     double lat = bucketBox.getLatitudeDeg();
517     if (lat < -90)
518         lat = -90;
519     if (90 < lat)
520         lat = 90;
521     if (lat < 0)
522         ss << "s" << std::setw(latFieldWidth) << -lat << std::setw(0);
523     else
524         ss << "n" << std::setw(latFieldWidth) << lat << std::setw(0);
525     
526     ss << "-" << bucketBox.getWidthDeg() << "x" << bucketBox.getHeightDeg();
527
528     return os << ss.str();
529 }
530
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)
537 {
538     char c;
539     is >> c;
540     if (is.fail())
541         return is;
542
543     int sign = 0;
544     if (c == 'w')
545         sign = -1;
546     else if (c == 'e')
547         sign = 1;
548     else {
549         is.setstate(std::ios::failbit | is.rdstate());
550         return is;
551     }
552     
553     double num;
554     is >> num;
555     if (is.fail()) {
556         is.setstate(std::ios::failbit | is.rdstate());
557         return is;
558     }
559     bucketBox.setLongitudeDeg(sign*num);
560     
561     is >> c;
562     if (is.fail())
563         return is;
564     
565     sign = 0;
566     if (c == 's')
567         sign = -1;
568     else if (c == 'n')
569         sign = 1;
570     else {
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.setLatitudeDeg(sign*num);
579     
580     is >> c;
581     if (is.fail())
582         return is;
583     if (c != '-'){
584         is.setstate(std::ios::failbit | is.rdstate());
585         return is;
586     }
587     
588     is >> num;
589     if (is.fail())
590         return is;
591     bucketBox.setWidthDeg(SGMiscd::min(num, 360));
592     
593     is >> c;
594     if (is.fail())
595         return is;
596     if (c != 'x'){
597         is.setstate(std::ios::failbit | is.rdstate());
598         return is;
599     }
600     
601     is >> num;
602     if (is.fail())
603         return is;
604     bucketBox.setHeightDeg(SGMiscd::min(num, 90 - bucketBox.getLatitudeDeg()));
605
606     return is;
607 }
608
609 } // namespace simgear
610
611 #endif