Building a tilemap display in VVVV

Hi everyone, I was hoping to get some input as to how I go about building/patching the following:

I’m trying to build a multiscreen (9x HD) map viewer, using tilemaps rendered with Tilemill (http://mapbox.com/tilemill/) Which allow you to generate your own custom maps based on Openstreetmap (http://openstreetmap) data. For now i’m not that interested in the multiscreen part, that is, I hope the multiscreen part comes down to just boygrouping a number of clients, running a map display patch.

At the moment i’m stuck trying to figure out how to implement the actual map display. Here’s what i’ve got so far:

Using Tilemill I am able to generate an ‘image-pyramid’, which is a (the) set of tiles that online map systems like Google Maps / OSM / Bing maps use. The way this works is that they basically fit the entire world into a square 256x256 and each zoom level squares the amount of tiles, like this:

level 0:
[ ]( ) (at level 0 the entire world fits in one 256x256 bitmap)

level 1:
[ ]( )[ ]( ) (entire world in a 512x512 image consisting of 4 tiles)
[ ]( )[ ]( )

level 2:
[ ]( )[ ]( )[ ]( )[ ]( ) (entire world in a 1024x1024 image consisting of 16 tiles)
[ ]( )[ ]( )[ ]( )[ ]( )
[ ]( )[ ]( )[ ]( )[ ]( )
[ ]( )[ ]( )[ ]( )[ ]( )
 
level 3: This would be a 2048x2048 image of 64 tiles

So at the moment I have a patch that can show these 4 zoomlevels, but I need help with building some sort of visibility determination (figuring out which tiles should be visible and be loaded into memory / vram) I’ve looked at some javascript implementations such as http://polymaps.org/ex/tiles.html which shows how the polymaps library determines the visibile tiles based on a polygon-fill algorithm. Now I have some experience in JS/Processing/AS3, but no formal training in CS, so i suck at figuring out algorithms by reading some else’s code, so if there’s anyone around that can explain how the algorithm works, and could give me some pointers as to how to patch this in VVVV it would be much appreciated.

Here’s what I managed to put together:

(I’m assuming a 1024x768 screensize)

  • I need some sort of Origin Point (0,0) for the map
  • I need a rectangle that represents the visible area, with the dimensions of the screen size (0,0) - (1024,768)
  • Some way to check where the top left corner of the screen is in relation to the origin of the map.
  • I need some sort of way to figure out which tiles are visible in the visible area.

Now the difficult part is in the final bullet, how can I build a test that would tell me which tiles would be visible?

I’ve attached what I managed to get working up until now, It includes textures for the first 4 zoomlevels (0-3).

*update, I managed to remove the renderer from the patch I put up here. Upload a new zip with proper patch.

Basic patch that shows level 0-3, with tiles (textures) included. (346.5 kB)

hey jasper. Didn’t get a chance to look at your patch to closely, but check out View Frustum culling- might be an easy fix for what you need.

MapResearch_VFC.v4p (21.9 kB)

Hey everyoneishappy, thanks for that example, it seems like View Frustum culling is definately a step in the right direction, I need to experiment a bit more to also get it to generate the right texture ID’s, but this helped a ton!

Thanks!

Turns out frustum culling isn’t the way to go. You end up with huge spreads at high zoom levels (>12). I’m now approaching it from another angle… generating ID’s first.

This was quite helpful:

http://msdn.microsoft.com/en-us/library/bb259689.aspx

I’ll post an update with patches later!

hui, i have to do quite similar stuff… but can soonest work on that in appr. 10 days.

so, thanks for the msdn-link. i think the ideal solution for this problem would be a plugin that is fed with zoomlevel, coordinates and information on the tiles. then the plugin could give some ids of images that should be (pre)loaded.

my 2 cents so far…

Hey sebl, I spent today with a pen and some graphing paper trying to figure this out, and now i’ve got a set of patches that generate the proper ID’s; specifically the ID’s of the tiles that are visible in the viewport at a certain zoomlevel. I still have to do some work on moving the map around and building smooth zooming, but I’m guessing that shouldn’t be too hard once I get my head around the way that VVVV’s transform matrices work.

The entire thing is up on GitHub:
https://github.com/Jasper2-0/TilemapDisplay , have a look if you want, and perhaps it covers some of the work you have to do. The patch is missing a subfolder called ‘tiles’, which hold the first 8 zoomlevels.
(About 220MB of data). Just send me a tweet @Jasper2_0 and I’ll provide a download link for you.

I agree that performance-wise a plugin would probably be best, but when it comes to determining ID’s that isn’t really the bottleneck. What this thing really needs is some clever way of preloading/caching textures (Still have to look into that), And (haven’t had a look at this) if this TileMap Node would support the MBTiles format (http://mapbox.com/developers/mbtiles/ , https://github.com/mapbox/mbtiles-spec), so that all the maps can be efficiently stored and retrieved from a SQLite database, instead of ga gazillion bazillion files in a folder.

So, progress! Now back to wrapping my head around these matrices…

yes, why not use an external tile “storage”…

i did some research in styling your own osm-maps and render them as tiles, so i need this quadrillion tiles on my hdd or a proper network storage.

anyway, looking forward to deep digger into that.

hello, again…

so, at the moment i’m generating a bunch of tiles with maperative (http://maperitive.net/). do you see any advantages in tilemill?

the best concept i’ve seen so far is the quadkey stuff from microsoft (link upwards). what i like most, is that wherever you are, you could easily distinguish some tiles to preload…

for example you are showing tile 13 - then you could preload tile 1, 130, 131, 132 and 133 - so, if the user changes the zoom level there should be no lag or nonloaded tiles. only thing to check is the tile-neighbours (for our little example here these should be 10, 11, 12 30 and 31).

so, next step will be one little plugin to get all the quadkeys based on x, y and zoomlevel.

i don’t understand how the tiles are placed in subfolders atm. and if that’s compatible with the quadkeys concept. … they are in tilejson format now, what seems to be (at least a bit) different. http://mapbox.com/wax/tilejson.html
how does tilemill do that?

i think, the display of the bitmaps will be an easy job if all the above is done…

this could come quite handy then:

public static string TileXYToQuadKey(int tileX, int tileY, int levelOfDetail)
        {
            StringBuilder quadKey = new StringBuilder();
            for (int i = levelOfDetail; i > 0; i--)
            {
                char digit = '0';
                int mask = 1 << (i - 1);
                if ((tileX & mask) != 0)
                {
                    digit++;
                }
                if ((tileY & mask) != 0)
                {
                    digit++;
                    digit++;
                }
                quadKey.Append(digit);
            }
            return quadKey.ToString();
        }

        public static void QuadKeyToTileXY(string quadKey, out int tileX, out int tileY, out int levelOfDetail)
        {
            tileX = tileY = 0;
            levelOfDetail = quadKey.Length;
            for (int i = levelOfDetail; i > 0; i--)
            {
                int mask = 1 << (i - 1);
                switch (quadKey[levelOfDetail - i](levelOfDetail - i))
                {
                    case '0':
                        break;

                    case '1':
                        tileX |= mask;
                        break;

                    case '2':
                        tileY |= mask;
                        break;

                    case '3':
                        tileX |= mask;
                        tileY |= mask;
                        break;

                    default:
                        throw new ArgumentException("Invalid QuadKey digit sequence.");
                }
            }
        }

so, i’m curious about your opinion

cheers

Hey Sebl, there are quite a few advantages of working with Tilemill over Maperitive.

But to get there I need to back up a bit, and explain a bit more about the project
I’m working on. I’m building an interactive atlas that will run on multiple screens
(which is why I’m using VVVV (boygrouping+direct3d+designerfriendly way of programming ‘yes please!’))
so I was looking at a ways to render high zoom levels of urban areas in tiles, and also looking at ways
to do custom cartography. Bassically trying to piece together an open software stack that would
allow me to work on the atlas. I ended up looking at work by Mike Migurksi (http://mike.teczno.com/) of Stamen, and Openstreetmap. Now, the main tileset for OSM is rendered using a tool called Mapnik (http://www.mapnik.org), developed by Artem Pavlenko, and the neat thing about Mapnik, is that it can render maps from a geo-database (PostGIS). Using the database, and a planet dataset you can render the entire world in tilemaps, if you were inclined to. Now, i’m specifically interested in metropolitan areas, in my case Rotterdam (Netherlands). Migurski makes extracts of the OSM planet dataset available via (http://metro.teczno.com/) and these datasets are updated periodically. This way you can keep your map current, (download a fresh extract, update your database, render tiles; voila! updated map)

Tilemill figures into this, because it is built on top of Mapnik (Artem, Mapniks author works for Mapbox http://mapbox.com/about/team/#artem-pavlenko).
So by using Tilemill you have a visual frontend (with a css like styling language) that designers can use, instead of the very verbose styling language and commandline interface that Mapnik itself uses. Also, Tilemill suports rendering from a PostGIS database, instead of working with XML OSM extracts the way Maperitive does.

Now, since I have this smallish cluster of PC’s that would be running the atlas during the day, it sort of makes sense to put this cluster to other uses, when it’s not being used such as rendering tiles. This is still something that I have to have some CS students take a look at, but the general thought is to do all this data/rendering stuff during the night. Since this would be something networked / cluster based
it would make sense to go with a commandline tool like Mapnik. However, I want to have my Design students work on new maps, or datasets etc, so I needed a tool that was (relatively) designer friendly, hence Tilemill. That way, the work the design students do with the GUI, can be integrated with the commandline setup.

(sory for the overly long answer, it’s also a way of documenting what i’ve been up to until now)

I think the quadkey stuff would help with preloading textures, however, as far as I can determine, only Bing maps is using this way of indexing. If you want to look at the way OSM does it, have a look here: http://wiki.openstreetmap.org/wiki/Slippy_map_tilenames it also explains the way
that the folders are ordered. And it provides a different way for calculating the subtiles…

At the moment i’m at the start of the academic year (yay) so my time to work in it is limited, but a plugin seems like the way to go, the stuff I put up on github should all be folded into that. I haven’t programmed any C# before, but I have experience with Java (writing Processing stuff in Eclipse, because I would get fed up with P5’s training wheels).

I’ll have a look at it over the weekend…

Ok, I took a closer look at Tilemill and have to say that it’s an easy and fast tool to generate your own map stylings. thanks for your deep explanations.

As a source for shapefiles, i found that: http://downloads.cloudmade.com/ and was really satisfied.

But there’s one last question i have on Tilemill - the exporting:
The only Tile-exporting option i see is the export as MBTiles. The Concept behind this format is really clever and there are tools, implementations and specs on github. But i don’t see a fast way of using a *.mbtiles in vvvv.

Perhaps we should have a long-term goal like a plugin that’s spitting out textures out of a *.mbtiles database. But as a first step, i think we will reach a usable system faster, if we have a tile-based folderstructure (Slippy_map_tilenames based) like you had in your example above.

So, did you export *.mbtiles first and then extracted the single tiles or is there another way?

You can export / extract all the information from an .mbtiles file using https://github.com/mapbox/mbutil
It also exports a ton of JSON files that we wouldn’t need at the moment, so you could recursively delete those.

You then end up with the proper folder structure in the Z/X/Y.png format

FYI:

i found this nice c# project, what is almost exactly the same we want to achieve plus some other goodies: http://viswaug.wordpress.com/2011/06/28/mbtilesviewer/

you can find the sources in the comments - it compiles here and is not that hard to understand.

i’ll try to wrap this thing in a plugin that connects directly to my .mbtiles file and spits a texture out.

if you also want to go this way, we should connect github-wise and do a nice contribution…

only thing to check is any licensing stuff - i didn’t find info about that for now… probably will contact the developer

little progress over here:

so, this little plugin connects to a mbtiles file (that is a sqlite db) and reads tiles matching the given levels/cols/rows.

sadly i didn’t figure out how to put the obtained byte array into a slimDX texture by now, but in theory it works.

MBTilesViewer.rar (949.6 kB)

plupp:… no text …

MBTilesViewer_120831.rar (931.1 kB)

Hi Sebl,

I had to drop the project for a few weeks, start of the academic year and all that. Anyhow, this last week I finally had more time to devote to the project. I had a look at your plugin work from the end of august. It looks like it’s working great, but the performance of the patch is quite a drag on my machine (running on a 2.7gh mac-mini) The patch you posted hovers between 30 and 40 fps on this machine, is this because of some sort of conversion going from SQL to a texture? The behaviour is quite erratic, sometimes running at 60fps, then dropping down to 30fps after which in a while it backs up to 60.

I proceeded with building a map display using directories with png textures, and that’s running at a full 60fps, but there are some weird issues when running fullscreen:

  • Reset Cache gets triggered every +/- 30 frames, which makes the display freeze. This does not happen in windowed mode, even if I scale up the window to the entire screen and hide the window-chrome with ctrl+8. Any thoughts on what might be triggering the cache-reset?

  • Issues when returning from fullscreen. When I alt+enter back from fullscreen to windowed mode, vvvv freezes the last fullscreen frame and i get my cursor back, but not a desktop / patching interface. Could this be due to Aero? (Win7) I’ve disabled this at the moment.

I’m currently running the map display in a 2x2 boygroup setup and I must say that the effect of viewing fluid maps in 60fps on that amount of pixels is really impressive. My focus is currently on building seamless zoom into the tileviewer, but that might take some work. But I’d like to resolve those two issues first. Any thoughts on that?

Hey Jasper,

we should meet on skype or similar… my skype nick is “hoogle”.

cheers