Tile Index Scheme

From FlightGear wiki
Jump to: navigation, search

Scenery in FlightGear is composed of tiles, each associated with a tile index. The tiles are cut so that none of them is excessively large or small compared to other tiles regarding their actual size on the earth surface.

Each tile is defined by the geodetic coordinates of its northwest corner and its extends in degrees of geodetic latitude and longitude. We will refer to the latitude resp. longitude of the northwest corner as lat resp. lon. However, the index calculations should also work with any other position inside the tile.

The authoritative source for the tile index scheme is the definition of the class SGBucket in SimGear (simgear/bucket/newbucket.{hxx, cxx}).

Calculating the Tile Index

The tile index is composed of four parts

  • base longitude index (-180...179)
  • base latitude index (-90...89),
  • longitude offset (0...7), and
  • latitude offset (0...7).

Each degree of latitude is split up into 8 rows of tiles. Therefore the base latitude index and offset are directly derived from lat using the floor and trunc functions:

 base_y=floor(lat)
 y=trunc((lat-base_y)*8)

floor & trunc explained: http://www.cplusplus.com/reference/cmath/trunc/

The tiling in east-west direction is more complex. As the meridians converge towards the pole, the width of tile columns must be adapted based on latitude, as the following table shows (taken from sg_bucket_span in simgear/bucket/newbucket.hxx):

Latitude Range Tile Width (deg)
89 ≤ abs(lat) ≤ 90 360
88 ≤ abs(lat) < 89 8
86 ≤ abs(lat) < 88 4
83 ≤ abs(lat) < 86 2
76 ≤ abs(lat) < 83 1
62 ≤ abs(lat) < 76 0.5
22 ≤ abs(lat) < 62 0.25
0 ≤ abs(lat) < 22 0.125

Note that in latitudes north of N83 or south of S83 tiles span more than a single degree of latitude. The naive code for determining the base longitude index is therefore

 base_x=floor(floor(lon/tile_width)*tile_width)

However, in case of latitudes north of N89 or south of S89, the whole row of latitude is a single tile. For western longitudes base_x would be calculated as -360, which is out of range. Therefore, we need to cap base_x to the range -180...179.

 base_x=floor(floor(lon/tile_width)*tile_width)
 if base_x<-180
   base_x=-180
 x=floor((lon-base_x)/tile_width)

The final tile index is found by composing the base offsets and indices into a bit-field:

 index=((lon+180)<<14) + ((lat + 90) << 6) + (y << 3) + x

So here is the final code for calculating the index (using the width from the table above for tile_width)

 base_y=floor(lat)
 y=trunc((lat-base_y)*8)
 base_x=floor(floor(lon/tile_width)*tile_width)
 if base_x<-180
   base_x=-180
 x=floor((lon-base_x)/tile_width)

Inconsistency Issues

The scheme explained above is the same that is currently implemented in SimGear and as such used by TerraGear and FlightGear. However, for latitudes north of N88 and south of S88 this scheme is inconsistent.

First of all, for latitudes north of N89 and south of S89 inconsistent base longitude offsets are generated for western and eastern longitudes, even though this area is covered by a single tile. For western longitudes, the longitude offset is calculated as -180, while for eastern longitudes it is calculated as 0, leading to different tile indices for the same tile.

Secondly, in the range between 88 and 89 degrees of latitude tiles have a width of 8 degrees of longitude. As the Greenwhich Meridian effectively is a tile border, longitudes west of W176 will lead to a longitude offset of -184, which is then corrected to -180 by the currently implemented code.

This means that the points between W176 and W172 are associated with two tiles, the one at base index -180 and the one at base index -176.

The latter problem arises from the fact that 8, the width of the tiles in this area, is not a factor of 180.

One solution would be to define the meridian at W180 to be a tile border. As 360 is an integral multiple of 8 (and all other tile widths as defined in the table above), E180 would also be a tile border.

The calculation would be simplified to

 base_x=trunc(trunc((lon+180)/width))*width-180
 x=trunc((x-base_x)/width)