Over the last week I wrote a tiny tileserver. This was to serve my home state’s digital cadastre as a background tileset for iD editing.

iD editor with DCDB background

The data comes from a ‘lite’ version of the Digital Cadastral Database (DCDB). This is released by the state of Queensland under a Creative Commons attribution licence that allows sharing and transformation. The requirement is that the string © State of Queensland (Department of Natural Resources and Mines) 2015 be used for attribution, and indicate if changes were made.

So, I’m using it to fine-tune the entry of OSM landuse polygons in my local area. This is important when park boundaries are obscured by trees, or to avoid parallax errors in rooflines when tracing dense commercial areas.

The results of my little tileserver program are very pleasing. Without any caching, I can view the entire state tile (20 million vertices) in about 6 seconds, and this is running on an old Asus Eee PC (1.6GHz Intel Atom). Tiles at regular zoom levels appear instantly. The tileserver is totally custom; when running it relies only on libc, pthreads and zlib deflate() at the end for PNGs. Hand-crafting everything with an eye for being a tileserver was a nice exercise, so I’ll tell you some of the highlights.

The combined polygon database and index file is about 230MB, which sits easily in memory. All 20 million vertices were pre-transformed from the WGS84 shapefile (using libshp to read) into the slippy maps projection. (Pre-processing takes about two minutes during build). The database is pre-sorted by polygon centroids on a Z-order curve. This reduces disk cache pressure, and probably helps with the D-cache lines.

The index is really a 16-deep binary space partition R-tree, with partitions selected to balance the leaves, which are delta-encoded polygon IDs packed using a scheme inspired by CBOR integers. Because it’s a BSP, the polygon search code (actually an iterator) sometimes has to follows both branches and this necessarily results in some duplicate polys returned. The draw code doesn’t check for duplicates because it turns out to be faster just to clip and/or redraw them.

Every PNG generated contains the required copyright message in a text chunk; the bulk of the PNG header is precomputed when the server starts up; only the IDAT chunk varies. The pixmap that I draw lines into is a PNG-format pixmap; each rows starts with a ‘filter’ byte. I did this because drawing directly into a PNG representation avoids a later pixmap transformation: I just pass the memory to zlib.

A custom http mainloop does all resource allocation for the search buffer and for zlib, but all threads share the same mmap’d database and avoid calling malloc. Handler threads are instead given a fixed-sized ‘pool’ (a bit like a dumbed down talloc) and the HTTP/1.1 protocol implemented is lean but understands connection reuse, but doesn’t do compression.

Some line corners look a bit broken because I don’t think I implemented Breselman’s line drawing algorithm correctly. I plan to change to Xiaolin Wu’s technique and raise the bit depth from 1 to 4 because the lines look too chunky.

But, for now I’m pretty happy with the result.

Comment from lyx on 18 May 2015 at 21:46

I don’t have the time for a detailed look at the moment, but my impression from reading your blog entry: That’s really cool stuff! Thanks for sharing

Login to leave a comment