1 /**************************************************************************
2 * newbucket.hxx -- new bucket routines for better world modeling
3 *
4 * Written by Curtis L. Olson, started February 1999.
5 *
6 * Copyright (C) 1999 Curtis L. Olson - http://www.flightgear.org/~curt/
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 *
22 * $Id$
23 **************************************************************************/
24
25
26 #ifdef HAVE_CONFIG_H
27 # include <simgear_config.h>
28 #endif
29
30 #include <cmath>
31 #include <cstdio> // some platforms need this for ::snprintf
32 #include <iostream>
33
34 #include <simgear/misc/sg_path.hxx>
35 #include <simgear/debug/logstream.hxx>
36
37 #include "newbucket.hxx"
38
39
40 // default constructor
SGBucket()41 SGBucket::SGBucket() :
42 lon(-1000),
43 lat(-1000),
44 x(0),
45 y(0)
46 {
47 }
48
isValid() const49 bool SGBucket::isValid() const
50 {
51 // The most northerly valid latitude is 89, not 90. There is no tile
52 // whose *bottom* latitude is 90. Similar there is no tile whose left egde
53 // is 180 longitude.
54 return (lon >= -180) &&
55 (lon < 180) &&
56 (lat >= -90) &&
57 (lat < 90) &&
58 (x < 8) && (y < 8);
59 }
60
make_bad()61 void SGBucket::make_bad()
62 {
63 lon = -1000;
64 lat = -1000;
65 }
66
67 #ifndef NO_DEPRECATED_API
68
69 // constructor for specified location
SGBucket(const double dlon,const double dlat)70 SGBucket::SGBucket(const double dlon, const double dlat) {
71 set_bucket(dlon, dlat);
72 }
73 #endif
74
SGBucket(const SGGeod & geod)75 SGBucket::SGBucket(const SGGeod& geod) {
76 innerSet(geod.getLongitudeDeg(),
77 geod.getLatitudeDeg());
78 }
79
80 // Parse a unique scenery tile index and find the lon, lat, x, and y
SGBucket(const long int bindex)81 SGBucket::SGBucket(const long int bindex) {
82 long int index = bindex;
83
84 lon = index >> 14;
85 index -= lon << 14;
86 lon -= 180;
87
88 lat = index >> 6;
89 index -= lat << 6;
90 lat -= 90;
91
92 y = index >> 3;
93 index -= y << 3;
94
95 x = index;
96 }
97
98 /* Calculate the greatest integral value less than
99 * or equal to the given value (floor(x)),
100 * but attribute coordinates close to the boundary to the next
101 * (increasing) integral
102 */
floorWithEpsilon(double x)103 static int floorWithEpsilon(double x)
104 {
105 return static_cast<int>(floor(x + SG_EPSILON));
106 }
107
108 #ifndef NO_DEPRECATED_API
109
set_bucket(double dlon,double dlat)110 void SGBucket::set_bucket(double dlon, double dlat)
111 {
112 innerSet(dlon, dlat);
113 }
114
115
set_bucket(const SGGeod & geod)116 void SGBucket::set_bucket(const SGGeod& geod)
117 {
118 innerSet(geod.getLongitudeDeg(), geod.getLatitudeDeg());
119 }
120
121 #endif
122
123 // Set the bucket params for the specified lat and lon
innerSet(double dlon,double dlat)124 void SGBucket::innerSet( double dlon, double dlat )
125 {
126 if ((dlon < -180.0) || (dlon >= 180.0)) {
127 SG_LOG(SG_TERRAIN, SG_WARN, "SGBucket::set_bucket: passed longitude:" << dlon);
128 dlon = SGMiscd::normalizePeriodic(-180.0, 180.0, dlon);
129 }
130
131 if ((dlat < -90.0) || (dlat > 90.0)) {
132 SG_LOG(SG_TERRAIN, SG_WARN, "SGBucket::set_bucket: passed latitude" << dlat);
133 dlat = SGMiscd::clip(dlat, -90.0, 90.0);
134 }
135
136 //
137 // longitude first
138 //
139 double span = sg_bucket_span( dlat );
140 // we do NOT need to special case lon=180 here, since
141 // normalizePeriodic will never return 180; it will
142 // return -180, which is what we want.
143 lon = floorWithEpsilon(dlon);
144
145 // find subdivision or super lon if needed
146 if ( span <= 1.0 ) {
147 /* We have more than one tile per degree of
148 * longitude, so we need an x offset.
149 */
150 x = floorWithEpsilon((dlon - lon) / span);
151 } else {
152 /* We have one or more degrees per tile,
153 * so we need to find the base longitude
154 * of that tile.
155 *
156 * First we calculate the integral base longitude
157 * (e.g. -85.5 => -86) and then find the greatest
158 * multiple of span that is less than or equal to
159 * that longitude.
160 *
161 * That way, the Greenwich Meridian is always
162 * a tile border.
163 */
164 lon=static_cast<int>(floor(lon / span) * span);
165 x = 0;
166 }
167
168 //
169 // then latitude
170 //
171 lat = floorWithEpsilon(dlat);
172
173 // special case when passing in the north pole point (possibly due to
174 // clipping latitude above). Ensures we generate a valid bucket in this
175 // scenario
176 if (lat == 90) {
177 lat = 89;
178 y = 7;
179 } else {
180 /* Latitude base and offset are easier, as
181 * tiles always are 1/8 degree of latitude wide.
182 */
183 y = floorWithEpsilon((dlat - lat) * 8);
184 }
185 }
186
187 // Build the path name for this bucket
gen_base_path() const188 std::string SGBucket::gen_base_path() const {
189 // long int index;
190 int top_lon, top_lat, main_lon, main_lat;
191 char hem, pole;
192 char raw_path[256];
193
194 top_lon = lon / 10;
195 main_lon = lon;
196 if ( (lon < 0) && (top_lon * 10 != lon) ) {
197 top_lon -= 1;
198 }
199 top_lon *= 10;
200 if ( top_lon >= 0 ) {
201 hem = 'e';
202 } else {
203 hem = 'w';
204 top_lon *= -1;
205 }
206 if ( main_lon < 0 ) {
207 main_lon *= -1;
208 }
209
210 top_lat = lat / 10;
211 main_lat = lat;
212 if ( (lat < 0) && (top_lat * 10 != lat) ) {
213 top_lat -= 1;
214 }
215 top_lat *= 10;
216 if ( top_lat >= 0 ) {
217 pole = 'n';
218 } else {
219 pole = 's';
220 top_lat *= -1;
221 }
222 if ( main_lat < 0 ) {
223 main_lat *= -1;
224 }
225
226 ::snprintf(raw_path, 256, "%c%03d%c%02d/%c%03d%c%02d",
227 hem, top_lon, pole, top_lat,
228 hem, main_lon, pole, main_lat);
229
230 return raw_path;
231 }
232
233
234 // return width of the tile in degrees
get_width() const235 double SGBucket::get_width() const {
236 return sg_bucket_span( get_center_lat() );
237 }
238
239
240 // return height of the tile in degrees
get_height() const241 double SGBucket::get_height() const {
242 return SG_BUCKET_SPAN;
243 }
244
get_highest_lat() const245 double SGBucket::get_highest_lat() const
246 {
247 unsigned char adjustedY = y;
248 if (lat >= 0) {
249 // tile is north of the equator, so we want the top edge. Add one
250 // to y to achieve this.
251 ++adjustedY;
252 }
253
254 return lat + (adjustedY / 8.0);
255 }
256
257
258 // return width of the tile in meters. This function is used by the
259 // tile-manager to estimate how many tiles are in the view distance, so
260 // we care about the smallest width, which occurs at the highest latitude.
get_width_m() const261 double SGBucket::get_width_m() const
262 {
263 double clat_rad = get_highest_lat() * SGD_DEGREES_TO_RADIANS;
264 double cos_lat = cos( clat_rad );
265 if (fabs(cos_lat) < SG_EPSILON) {
266 // happens for polar tiles, since we pass in a latitude of 90
267 // return an arbitrary small value so all tiles are loaded
268 return 10.0;
269 }
270
271 double local_radius = cos_lat * SG_EQUATORIAL_RADIUS_M;
272 double local_perimeter = local_radius * SGD_2PI;
273 double degree_width = local_perimeter / 360.0;
274
275 return get_width() * degree_width;
276 }
277
278
279 // return height of the tile in meters
get_height_m() const280 double SGBucket::get_height_m() const {
281 double perimeter = SG_EQUATORIAL_RADIUS_M * SGD_2PI;
282 double degree_height = perimeter / 360.0;
283
284 return SG_BUCKET_SPAN * degree_height;
285 }
286
siblings(int dx,int dy,std::vector<SGBucket> & buckets) const287 unsigned int SGBucket::siblings( int dx, int dy, std::vector<SGBucket>& buckets ) const
288 {
289 if (!isValid()) {
290 SG_LOG(SG_TERRAIN, SG_WARN, "SGBucket::sibling: requesting sibling of invalid bucket");
291 return 0;
292 }
293
294 double src_span = sg_bucket_span( get_center_lat() );
295
296 double clat = get_center_lat() + dy * SG_BUCKET_SPAN;
297 // return invalid here instead of clipping, so callers can discard
298 // invalid buckets without having to check if it's an existing one
299 if ((clat < -90.0) || (clat > 90.0)) {
300 return 0;
301 }
302
303 // find the lon span for the new latitude
304 double trg_span = sg_bucket_span( clat );
305
306 // if target span < src_span, return multiple buckets...
307 if ( trg_span < src_span ) {
308 // calc center longitude of westernmost sibling
309 double start_lon = get_center_lat() - src_span/2 + trg_span/2;
310
311 unsigned int num_buckets = src_span/trg_span;
312 for ( unsigned int x = 0; x < num_buckets; x++ ) {
313 double tmp = start_lon + x * trg_span;
314 tmp = SGMiscd::normalizePeriodic(-180.0, 180.0, tmp);
315
316 SGBucket b;
317 b.innerSet(tmp, clat);
318
319 buckets.push_back( b );
320 }
321 } else {
322 // just return the single sibling
323 double tmp = get_center_lon() + dx * trg_span;
324 tmp = SGMiscd::normalizePeriodic(-180.0, 180.0, tmp);
325
326 SGBucket b;
327 b.innerSet(tmp, clat);
328
329 buckets.push_back( b );
330 }
331
332 return buckets.size();
333 }
334
sibling(int dx,int dy) const335 SGBucket SGBucket::sibling(int dx, int dy) const
336 {
337 if (!isValid()) {
338 SG_LOG(SG_TERRAIN, SG_WARN, "SGBucket::sibling: requesting sibling of invalid bucket");
339 return SGBucket();
340 }
341
342 double clat = get_center_lat() + dy * SG_BUCKET_SPAN;
343 // return invalid here instead of clipping, so callers can discard
344 // invalid buckets without having to check if it's an existing one
345 if ((clat < -90.0) || (clat > 90.0)) {
346 return SGBucket();
347 }
348
349 // find the lon span for the new latitude
350 double span = sg_bucket_span( clat );
351
352 double tmp = get_center_lon() + dx * span;
353 tmp = SGMiscd::normalizePeriodic(-180.0, 180.0, tmp);
354
355 SGBucket b;
356 b.innerSet(tmp, clat);
357 return b;
358 }
359
gen_index_str() const360 std::string SGBucket::gen_index_str() const
361 {
362 char tmp[20];
363 ::snprintf(tmp, 20, "%ld",
364 (((long)lon + 180) << 14) + ((lat + 90) << 6)
365 + (y << 3) + x);
366 return (std::string)tmp;
367 }
368
369 #ifndef NO_DEPRECATED_API
370 // find the bucket which is offset by the specified tile units in the
371 // X & Y direction. We need the current lon and lat to resolve
372 // ambiguities when going from a wider tile to a narrower one above or
373 // below. This assumes that we are feeding in
sgBucketOffset(double dlon,double dlat,int dx,int dy)374 SGBucket sgBucketOffset( double dlon, double dlat, int dx, int dy ) {
375 SGBucket result( dlon, dlat );
376 double clat = result.get_center_lat() + dy * SG_BUCKET_SPAN;
377
378 // walk dy units in the lat direction
379 result.set_bucket( dlon, clat );
380
381 // find the lon span for the new latitude
382 double span = sg_bucket_span( clat );
383
384 // walk dx units in the lon direction
385 double tmp = dlon + dx * span;
386 while ( tmp < -180.0 ) {
387 tmp += 360.0;
388 }
389 while ( tmp >= 180.0 ) {
390 tmp -= 360.0;
391 }
392 result.set_bucket( tmp, clat );
393
394 return result;
395 }
396 #endif
397
398 // calculate the offset between two buckets
sgBucketDiff(const SGBucket & b1,const SGBucket & b2,int * dx,int * dy)399 void sgBucketDiff( const SGBucket& b1, const SGBucket& b2, int *dx, int *dy ) {
400
401 // Latitude difference
402 double c1_lat = b1.get_center_lat();
403 double c2_lat = b2.get_center_lat();
404 double diff_lat = c2_lat - c1_lat;
405
406 #ifdef HAVE_RINT
407 *dy = (int)rint( diff_lat / SG_BUCKET_SPAN );
408 #else
409 if ( diff_lat > 0 ) {
410 *dy = (int)( diff_lat / SG_BUCKET_SPAN + 0.5 );
411 } else {
412 *dy = (int)( diff_lat / SG_BUCKET_SPAN - 0.5 );
413 }
414 #endif
415
416 // longitude difference
417 double diff_lon=0.0;
418 double span=0.0;
419
420 SGBucket tmp_bucket;
421 // To handle crossing the bucket size boundary
422 // we need to account for different size buckets.
423
424 if ( sg_bucket_span(c1_lat) <= sg_bucket_span(c2_lat) )
425 {
426 span = sg_bucket_span(c1_lat);
427 } else {
428 span = sg_bucket_span(c2_lat);
429 }
430
431 diff_lon = b2.get_center_lon() - b1.get_center_lon();
432
433 if (diff_lon <0.0)
434 {
435 diff_lon -= b1.get_width()*0.5 + b2.get_width()*0.5 - span;
436 }
437 else
438 {
439 diff_lon += b1.get_width()*0.5 + b2.get_width()*0.5 - span;
440 }
441
442
443 #ifdef HAVE_RINT
444 *dx = (int)rint( diff_lon / span );
445 #else
446 if ( diff_lon > 0 ) {
447 *dx = (int)( diff_lon / span + 0.5 );
448 } else {
449 *dx = (int)( diff_lon / span - 0.5 );
450 }
451 #endif
452 }
453
sgGetBuckets(const SGGeod & min,const SGGeod & max,std::vector<SGBucket> & list)454 void sgGetBuckets( const SGGeod& min, const SGGeod& max, std::vector<SGBucket>& list ) {
455 double lon, lat, span;
456
457 for (lat = min.getLatitudeDeg(); lat < max.getLatitudeDeg()+SG_BUCKET_SPAN; lat += SG_BUCKET_SPAN) {
458 span = sg_bucket_span( lat );
459 for (lon = min.getLongitudeDeg(); lon <= max.getLongitudeDeg(); lon += span)
460 {
461 SGBucket b(SGGeod::fromDeg(lon, lat));
462 if (!b.isValid()) {
463 continue;
464 }
465
466 list.push_back(b);
467 }
468 }
469 }
470
operator <<(std::ostream & out,const SGBucket & b)471 std::ostream& operator<< ( std::ostream& out, const SGBucket& b )
472 {
473 return out << b.lon << ":" << (int)b.x << ", " << b.lat << ":" << (int)b.y;
474 }
475
476