[OSM-dev] Blank Tiles at z23 and Deeper

[jpk]

On Wed, Oct 10, 2012 at 4:11 AM, Kai Krueger <kakrueger at gmail.com> wrote:
> mod_tile by default uses a "directory hash" which mixes X and Y coordinates
> into a 40 bit "hash function" and then splits that into a 5 level deep
> directory structure.

Ah-ha, I see how this works now.

>
> Why it normally breaks only at Z23 and not at Z21 I am not entirely sure,
> but possibly if you look at Australia, it might already break in Z21,
> whereas Alaska might still work in Z23 (because it simply cuts of zero
> padding).

So I had that thought too.  I tried it, and it looks l like tiles in
Australia work down to z22 and then go blank at z23, just like I've
been seeing in North America.  (However, you were right.  z21 and z22
are busted, but in a subtle way.  See below.)

>
> So for Z30 to work, you will either need to extend the directory hash
> function to 60 bits, or you use the non hashed directory structure.
>
> The appropriate function is xyz_to_path in dir_utils.c (
> https://github.com/openstreetmap/mod_tile/blob/master/dir_utils.c#L68 )

Now, a couple things.
First, the hash function:

So from my understanding of the hash function, it takes the four
least-significant bits from the x and y coordinates, and stuffs them
together like:
x3,x2,x1,x0,y3,y2,y1,y0
That byte is stored in hash[0].  Then it shifts the four
least-significant bits off the right side of x and y, then does it
again four more times for a total of five.  (5x4=20 bits used for the
x and y coordinates each in the hash function.)  Then the directory
names come from the decimal representation of each element in the hash
array.

So in the case of z21, x and y might be 21 bits long.  If they are,
only the first twenty bits are used, and the extra one gets ignored.
So the problem is there would be a collision.  More than one x/y
coordinate in z21 can result in the same hash array.  So if you render
21/1929845/1258235.png (in Australia), it'll get cached in the same
hash directory as 21/881269/209659.png (somewhere well NW of
Australia), which is bogus.

I tested this, and it turns out to be the case.  When you request a
tile at >= z21, and then go to another tile who's hash collides with
the other tile, you get the other tile from the cache.  So whichever
of the tiles gets rendered first gets served for all the tile's that
hash to the same thing.  This seems easy enough to fix by making the
hash array a little longer, and the hash directories a little deeper.
(Going from 5 to 8 would bump the limit up from 20 to 32).

Second, the blank tiles:

The hash directory thing is good, and I can get that sorted (yay,
progress!), but it doesn't explain all the sea-colored tiles at >=z23
for tiles that aren't yet cached.  From what I gather looking at
mod_tile/renderd source, I see mapnik render the tile first, based on
the z/x/y coordinates, and then the hashing and caching stuff happens
after.  Is that right?  If so, it would seem that the problem lies
somewhere in there.  Any pointers as I start looking in that
direction?

Thanks!
jpk

>
> Kai
>
>
> jpk wrote
>> On Tue, Oct 9, 2012 at 10:21 AM, Frederik Ramm <
>
>> frederik@
>
>> > wrote:
>>> Hi,
>>>
>>> On Tue, 9 Oct 2012 00:21:25 -0400
>>> jpk <
>
>> _@
>
>>> wrote:
>>>> In any case, I set up my tile server for
>>>> this purpose.  I changed the #define MAX_ZOOM to 30 in mod_tile's
>>>> render_config.h, and set MAXZOOM in renderd.conf to 30.  That's enough
>>>> to get the tile server to serve tiles down to z30 instead of 404'ing.
>>>
>>> But the directory structure used to store the metatiles supports only 20
>>> bits for x and y, so i would expect that on z21 and above you'll not be
>>> able to retrieve tiles from your server (or maybe see the same tile
>>> not matter what coordinates you use)... or are you using someting other
>>> than mod_tile?
>>>
>>> Bye
>>> Frederik
>>>
>>>
>>> _______________________________________________
>>> dev mailing list
>>>
>
>> dev@
>
>>> http://lists.openstreetmap.org/listinfo/dev
>>
>> I am indeed using mod_tile (r28702).
>>
>> Here's what I'm seeing at z17, 19, 20, 21, 22, and 23.  So you can see
>> 21 and 22 are working.  All tiles at zoom levels 23 and greater,
>> though, are that solid green-ish color.
>> http://imgur.com/a/qCXAx#0
>>
>> Although, you may be on to something.  Can you elaborate on "the
>> directory structure used to store the metatiles supports only 20 bits
>> for x and y"?  I see in /var/lib/mod_tile there are directories that
>> look like the correspond to zoom levles, but stuff that doesn't look
>> like x/y directories (like if you generate some tiles with gdal2tiles
>> or a similar tool). The mod_tile README talks a little bit about the
>> directory structure, and the limitations of using the z/x/y.png
>> structure, but I'm still not sure what's going on there and what would
>> break at higher zoom levels.
>>
>> Thanks!
>> jpk
>>
>> --
>> john p. kiffmeyer
>>
>> _______________________________________________
>> dev mailing list
>
>> dev@
>
>> http://lists.openstreetmap.org/listinfo/dev
>
>
>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Blank-Tiles-at-z23-and-Deeper-tp5729539p5729724.html
> Sent from the Developer Discussion mailing list archive at Nabble.com.
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/dev



-- 
john p. kiffmeyer