rename llmr => mbgl

26 files changed, 2273 insertions, 0 deletions

diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp
new file mode 100644
index 0000000000..748d3d8f5f
--- /dev/null
+++ b/include/mbgl/util/clip_ids.hpp
@@ -0,0 +1,19 @@
+#ifndef MBGL_UTIL_CLIP_IDS
+#define MBGL_UTIL_CLIP_IDS
+
+#include <mbgl/map/tile.hpp>
+#include <list>
+#include <set>
+#include <map>
+
+namespace mbgl {
+
+static constexpr uint8_t clipMask[9] { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF };
+
+void updateClipIDs(const std::list<Tile *> &array);
+
+std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array);
+
+}
+
+#endif
diff --git a/include/mbgl/util/constants.hpp b/include/mbgl/util/constants.hpp
new file mode 100644
index 0000000000..89e8af2ef1
--- /dev/null
+++ b/include/mbgl/util/constants.hpp
@@ -0,0 +1,33 @@
+#ifndef MBGL_UTIL_CONSTANTS
+#define MBGL_UTIL_CONSTANTS
+
+#include <cmath>
+
+#include "vec.hpp"
+
+namespace mbgl {
+
+namespace util {
+
+extern const float tileSize;
+
+}
+
+namespace debug {
+
+extern const bool tileParseWarnings;
+extern const bool styleParseWarnings;
+extern const bool spriteWarnings;
+extern const bool renderWarnings;
+extern const bool renderTree;
+extern const bool labelTextMissingWarning;
+extern const bool missingFontStackWarning;
+extern const bool missingFontFaceWarning;
+extern const bool glyphWarning;
+extern const bool shapingWarning;
+
+}
+
+}
+
+#endif
diff --git a/include/mbgl/util/enum.hpp b/include/mbgl/util/enum.hpp
new file mode 100644
index 0000000000..195aaab5a5
--- /dev/null
+++ b/include/mbgl/util/enum.hpp
@@ -0,0 +1,55 @@
+#ifndef MBGL_UTIL_ENUM
+#define MBGL_UTIL_ENUM
+
+#include <iosfwd>
+#include <string>
+
+namespace mbgl {
+
+template <typename Type>
+struct EnumValue {
+    const Type value;
+    const char *name;
+};
+
+template <typename EnumName, const EnumValue<EnumName> *names, const size_t length>
+struct Enum {
+    using Type = EnumName;
+    Type value;
+    static const constexpr size_t l = length;
+private:
+    static constexpr inline bool compare(const char *a, const char *b) {
+        return *a == *b && (*a == '\0' || compare(a + 1, b + 1));
+    }
+    static constexpr inline const char *lookup_type(Type e, EnumValue<Type> const * const l, size_t r) {
+        return r == 0 ? "" : l->value == e ? l->name : lookup_type(e, l + 1, r - 1);
+    }
+    static constexpr inline Type lookup_name(const char *n, EnumValue<Type> const * const l, size_t r) {
+        return r == 0 ? Type(-1) : compare(l->name, n) ? l->value : lookup_name(n, l + 1, r - 1);
+    }
+public:
+    inline constexpr Enum(const char *n) : value(lookup_name(n, names, length)) {}
+    inline constexpr Enum(const std::string &n) : value(lookup_name(n.c_str(), names, length)) {}
+    inline constexpr Enum(Type t) : value(t) {}
+
+    inline void operator=(const char *n) { value = lookup_name(n, names, length); }
+    inline void operator=(const std::string &n) { *this = n.c_str(); }
+    inline void operator=(Type t) { value = t; }
+
+    inline constexpr bool valid() const { return value != Type(-1); }
+
+    inline constexpr const char *c_str() const { return lookup_type(value, names, length); }
+    inline std::string str() const { return c_str(); }
+
+    inline constexpr operator Type() const { return value; }
+};
+
+#define MBGL_DEFINE_ENUM_CLASS(name, type, strings...) \
+    const constexpr ::mbgl::EnumValue<type> type##_names[] = strings; \
+    using name = ::mbgl::Enum<type, type##_names, sizeof(type##_names) / sizeof(::mbgl::EnumValue<type>)>; \
+    inline std::ostream& operator<<(std::ostream& os, type t) { return os << name(t).str(); }
+
+}
+
+#endif
+
diff --git a/include/mbgl/util/error.hpp b/include/mbgl/util/error.hpp
new file mode 100644
index 0000000000..99e27f770c
--- /dev/null
+++ b/include/mbgl/util/error.hpp
@@ -0,0 +1,20 @@
+#ifndef MBGL_UTIL_ERROR
+#define MBGL_UTIL_ERROR
+
+#include <stdexcept>
+#include <string>
+
+namespace mbgl {
+namespace error {
+
+struct style_parse : std::exception {
+    inline style_parse(size_t offset, const char *msg) : offset(offset), msg(msg) {}
+    inline const char* what() const noexcept { return msg.c_str(); }
+    const size_t offset;
+    const std::string msg;
+};
+}
+
+}
+
+#endif
\ No newline at end of file
diff --git a/include/mbgl/util/image.hpp b/include/mbgl/util/image.hpp
new file mode 100644
index 0000000000..dc8f6a8150
--- /dev/null
+++ b/include/mbgl/util/image.hpp
@@ -0,0 +1,36 @@
+#ifndef MBGL_UTIL_IMAGE
+#define MBGL_UTIL_IMAGE
+
+#include <string>
+#include <cstring>
+#include <stdexcept>
+
+namespace mbgl {
+namespace util {
+
+std::string compress_png(int width, int height, void *rgba, bool flip = false);
+
+
+class Image {
+public:
+    Image(const std::string &img, bool flip = false);
+    ~Image();
+
+    inline const char *getData() const { return img; }
+    inline uint32_t getWidth() const { return width; }
+    inline uint32_t getHeight() const { return height; }
+
+private:
+    // loaded image dimensions
+    uint32_t width = 0, height = 0;
+
+    // the raw image data
+    char *img = nullptr;
+
+};
+
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/io.hpp b/include/mbgl/util/io.hpp
new file mode 100644
index 0000000000..e95fc16d9d
--- /dev/null
+++ b/include/mbgl/util/io.hpp
@@ -0,0 +1,15 @@
+#ifndef MBGL_UTIL_IO
+#define MBGL_UTIL_IO
+
+#include <string>
+
+namespace mbgl {
+namespace util {
+
+void write_file(const std::string &filename, const std::string &data);
+std::string read_file(const std::string &filename);
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/mat4.hpp b/include/mbgl/util/mat4.hpp
new file mode 100644
index 0000000000..4279113d21
--- /dev/null
+++ b/include/mbgl/util/mat4.hpp
@@ -0,0 +1,45 @@
+// This is an incomplete port of http://glmatrix.net/
+//
+// Copyright (c) 2013 Brandon Jones, Colin MacKenzie IV
+//
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors be held liable for any damages arising from the
+// use of this software.
+//
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+//
+// 1. The origin of this software must not be misrepresented; you must not claim
+//    that you wrote the original software. If you use this software in a
+//    product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+//
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+//
+// 3. This notice may not be removed or altered from any source distribution.
+
+#ifndef MBGL_UTIL_MAT4
+#define MBGL_UTIL_MAT4
+
+#include <array>
+
+namespace mbgl {
+
+typedef std::array<float, 16> mat4;
+
+namespace matrix {
+
+void identity(mat4& out);
+void ortho(mat4& out, float left, float right, float bottom, float top, float near, float far);
+void copy(mat4& out, const mat4& a);
+void translate(mat4& out, const mat4& a, float x, float y, float z);
+void rotate_z(mat4& out, const mat4& a, float rad);
+void scale(mat4& out, const mat4& a, float x, float y, float z);
+void multiply(mat4& out, const mat4& a, const mat4& b);
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp
new file mode 100644
index 0000000000..277fdc8fc3
--- /dev/null
+++ b/include/mbgl/util/math.hpp
@@ -0,0 +1,115 @@
+#ifndef MBGL_UTIL_MATH
+#define MBGL_UTIL_MATH
+
+#include <cmath>
+#include <array>
+
+#include "vec.hpp"
+
+namespace mbgl {
+namespace util {
+
+
+template <typename T>
+inline T max(T a, T b) {
+    return b > a ? b : a;
+}
+
+template <typename T>
+inline T max(T a, T b, T c) {
+    return max(max(a, b), c);
+}
+
+template <typename T>
+inline T max(T a, T b, T c, T d) {
+    return max(max(a, b), max(c, d));
+}
+
+template <typename T>
+inline T min(T a, T b) {
+    return b < a ? b : a;
+}
+
+template <typename T>
+inline T min(T a, T b, T c) {
+    return min(min(a, b), c);
+}
+
+template <typename T>
+inline T min(T a, T b, T c, T d) {
+    return min(min(a, b), min(c, d));
+}
+
+// Find the angle of the two vectors, solving the formula for the cross product
+// a x b = |a||b|sin(θ) for θ.
+template <typename T = double, typename S>
+inline T angle_between(S ax, S ay, S bx, S by) {
+    return std::atan2((ax * by - ay * bx), ax * bx + ay * by);
+}
+
+template <typename T = double, typename S>
+inline T angle_between(const vec2<S>& a, const vec2<S>& b) {
+    return angle_between(a.x, a.y, b.x, b.y);
+}
+
+template <typename T = double, typename S>
+inline T angle_to(const vec2<S>& a, const vec2<S>& b) {
+    return std::atan2(a.y - b.y, a.x - b.x);
+}
+
+template <typename T, typename S1, typename S2>
+inline T interp(S1 a, S2 b, T t) {
+    return (a * ((T)1 - t)) + (b * t);
+}
+
+// Reflect an angle around 0 degrees
+template <typename T>
+inline std::array<T, 2> flip(const std::array<T, 2>& c) {
+    return {{
+        static_cast<T>(2 * M_PI - c[0]),
+        static_cast<T>(2 * M_PI - c[1])
+    }};
+}
+
+template <typename T, typename S1, typename S2>
+inline vec2<T> normal(const S1& a, const S2& b) {
+    T dx = b.x - a.x;
+    T dy = b.y - a.y;
+    T c = std::sqrt(dx * dx + dy * dy);
+    return { dx / c, dy / c };
+}
+
+template <typename T, typename S1, typename S2>
+inline T dist(const S1& a, const S2& b) {
+    T dx = b.x - a.x;
+    T dy = b.y - a.y;
+    T c = std::sqrt(dx * dx + dy * dy);
+    return c;
+}
+
+template <typename T>
+inline T length(T a, T b) {
+    return std::sqrt(a * a + b * b);
+}
+
+// Take the magnitude of vector a.
+template <typename T = double, typename S>
+inline T mag(const S& a) {
+    return std::sqrt(a.x * a.x + a.y * a.y);
+}
+
+template <typename T>
+T clamp(T value, T min, T max) {
+    return value < min ? min : (value > max ? max : value);
+}
+
+template <typename T>
+T smoothstep(T edge0, T edge1, T x) {
+    T t = clamp((x - edge0) / (edge1 - edge0), T(0), T(1));
+    return t * t * (T(3) - T(2) * t);
+}
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/noncopyable.hpp b/include/mbgl/util/noncopyable.hpp
new file mode 100644
index 0000000000..ada701efc6
--- /dev/null
+++ b/include/mbgl/util/noncopyable.hpp
@@ -0,0 +1,23 @@
+#ifndef MBGL_UTIL_NONCOPYABLE
+#define MBGL_UTIL_NONCOPYABLE
+
+namespace mbgl { namespace util {
+
+namespace non_copyable_
+{
+
+class noncopyable
+{
+protected:
+    constexpr noncopyable() = default;
+    ~noncopyable() = default;
+    noncopyable( noncopyable const& ) = delete;
+    noncopyable& operator=(noncopyable const& ) = delete;
+};
+}
+
+typedef non_copyable_::noncopyable noncopyable;
+
+}}
+
+#endif
diff --git a/include/mbgl/util/pbf.hpp b/include/mbgl/util/pbf.hpp
new file mode 100644
index 0000000000..1f78a0072f
--- /dev/null
+++ b/include/mbgl/util/pbf.hpp
@@ -0,0 +1,184 @@
+#ifndef MBGL_UTIL_PBF
+#define MBGL_UTIL_PBF
+
+/*
+ * Some parts are from upb - a minimalist implementation of protocol buffers.
+ *
+ * Copyright (c) 2008-2011 Google Inc.  See LICENSE for details.
+ * Author: Josh Haberman <jhaberman@gmail.com>
+ */
+
+#include <string>
+#include <cstring>
+
+namespace mbgl {
+
+struct pbf {
+    struct exception : std::exception { const char *what() const noexcept { return "pbf exception"; } };
+    struct unterminated_varint_exception : exception { const char *what() const noexcept { return "pbf unterminated varint exception"; } };
+    struct varint_too_long_exception : exception { const char *what() const noexcept { return "pbf varint too long exception"; } };
+    struct unknown_field_type_exception : exception { const char *what() const noexcept { return "pbf unknown field type exception"; } };
+    struct end_of_buffer_exception : exception { const char *what() const noexcept { return "pbf end of buffer exception"; } };
+
+    inline pbf(const unsigned char *data, size_t length);
+    inline pbf();
+
+    inline operator bool() const;
+
+    inline bool next();
+    inline bool next(uint32_t tag);
+    template <typename T = uint32_t> inline T varint();
+    template <typename T = uint32_t> inline T svarint();
+
+    template <typename T = uint32_t, int bytes = 4> inline T fixed();
+    inline float float32();
+    inline double float64();
+
+    inline std::string string();
+    inline bool boolean();
+
+    inline pbf message();
+
+    inline void skip();
+    inline void skipValue(uint32_t val);
+    inline void skipBytes(uint32_t bytes);
+
+    const uint8_t *data = nullptr;
+    const uint8_t *end = nullptr;
+    uint32_t value = 0;
+    uint32_t tag = 0;
+};
+
+pbf::pbf(const unsigned char *data, size_t length)
+    : data(data),
+      end(data + length),
+      value(0),
+      tag(0) {
+}
+
+pbf::pbf()
+    : data(nullptr),
+      end(nullptr),
+      value(0),
+      tag(0) {
+}
+
+
+pbf::operator bool() const {
+    return data < end;
+}
+
+bool pbf::next() {
+    if (data < end) {
+        value = static_cast<uint32_t>(varint());
+        tag = value >> 3;
+        return true;
+    }
+    return false;
+}
+
+bool pbf::next(uint32_t requested_tag) {
+    while (next()) {
+        if (tag == requested_tag) {
+            return true;
+        } else {
+            skip();
+        }
+    }
+    return false;
+}
+
+template <typename T>
+T pbf::varint() {
+    uint8_t byte = 0x80;
+    T result = 0;
+    int bitpos;
+    for (bitpos = 0; bitpos < 70 && (byte & 0x80); bitpos += 7) {
+        if (data >= end) {
+            throw unterminated_varint_exception();
+        }
+        result |= ((T)(byte = *data) & 0x7F) << bitpos;
+
+        data++;
+    }
+    if (bitpos == 70 && (byte & 0x80)) {
+        throw varint_too_long_exception();
+    }
+
+    return result;
+}
+
+template <typename T>
+T pbf::svarint() {
+    T n = varint<T>();
+    return (n >> 1) ^ -(T)(n & 1);
+}
+
+template <typename T, int bytes>
+T pbf::fixed() {
+    skipBytes(bytes);
+    T result;
+    memcpy(&result, data - bytes, bytes);
+    return result;
+}
+
+float pbf::float32() {
+    return fixed<float, 4>();
+}
+
+double pbf::float64() {
+    return fixed<double, 8>();
+}
+
+std::string pbf::string() {
+    uint32_t bytes = static_cast<uint32_t>(varint());
+    const char *string = reinterpret_cast<const char*>(data);
+    skipBytes(bytes);
+    return std::string(string, bytes);
+}
+
+bool pbf::boolean() {
+    skipBytes(1);
+    return *(bool *)(data - 1);
+}
+
+pbf pbf::message() {
+    uint32_t bytes = static_cast<uint32_t>(varint());
+    const uint8_t *pos = data;
+    skipBytes(bytes);
+    return pbf(pos, bytes);
+}
+
+void pbf::skip() {
+    skipValue(value);
+}
+
+void pbf::skipValue(uint32_t val) {
+    switch (val & 0x7) {
+        case 0: // varint
+            varint();
+            break;
+        case 1: // 64 bit
+            skipBytes(8);
+            break;
+        case 2: // string/message
+            skipBytes(static_cast<uint32_t>(varint()));
+            break;
+        case 5: // 32 bit
+            skipBytes(4);
+            break;
+        default:
+            throw unknown_field_type_exception();
+    }
+}
+
+void pbf::skipBytes(uint32_t bytes) {
+    if (data + bytes > end) {
+        throw end_of_buffer_exception();
+    }
+    data += bytes;
+}
+
+} // end namespace mbgl
+
+#endif
diff --git a/include/mbgl/util/raster.hpp b/include/mbgl/util/raster.hpp
new file mode 100644
index 0000000000..04c85169e2
--- /dev/null
+++ b/include/mbgl/util/raster.hpp
@@ -0,0 +1,70 @@
+#ifndef MBGL_UTIL_RASTER
+#define MBGL_UTIL_RASTER
+
+#include <mbgl/util/transition.hpp>
+#include <mbgl/util/texturepool.hpp>
+#include <mbgl/util/image.hpp>
+
+#include <string>
+#include <mutex>
+#include <memory>
+
+typedef struct uv_loop_s uv_loop_t;
+
+namespace mbgl {
+
+class Raster : public std::enable_shared_from_this<Raster> {
+
+public:
+    Raster(const std::shared_ptr<Texturepool> &texturepool);
+    ~Raster();
+
+    // load image data
+    bool load(const std::string &img);
+
+    // bind current texture
+    void bind(bool linear = false);
+
+    // loaded status
+    bool isLoaded() const;
+
+    // transitions
+    void beginFadeInTransition();
+    bool needsTransition() const;
+    void updateTransitions(timestamp now);
+
+public:
+    // loaded image dimensions
+    uint32_t width = 0, height = 0;
+
+    // has been uploaded to texture
+    bool textured = false;
+
+    // the uploaded texture
+    uint32_t texture = 0;
+
+    // texture opacity
+    double opacity = 0;
+
+private:
+    mutable std::mutex mtx;
+
+    // raw pixels have been loaded
+    bool loaded = false;
+
+    // shared texture pool
+    std::shared_ptr<Texturepool> texturepool;
+
+    // min/mag filter
+    uint32_t filter = 0;
+
+    // the raw pixels
+    std::unique_ptr<util::Image> img;
+
+    // fade in transition
+    std::shared_ptr<util::transition> fade_transition = nullptr;
+};
+
+}
+
+#endif
diff --git a/include/mbgl/util/rect.hpp b/include/mbgl/util/rect.hpp
new file mode 100644
index 0000000000..a216b8e145
--- /dev/null
+++ b/include/mbgl/util/rect.hpp
@@ -0,0 +1,21 @@
+#ifndef MBGL_UTIL_RECT
+#define MBGL_UTIL_RECT
+
+namespace mbgl {
+
+template <typename T>
+struct Rect {
+    explicit Rect(T x, T y, T w, T h) : x(x), y(y), w(w), h(h) {}
+    T x = 0, y = 0;
+    T w = 0, h = 0;
+
+    template <typename Number>
+    Rect operator *(Number value) const {
+        return Rect(x * value, y * value, w * value, h * value);
+    }
+
+    operator bool() const { return w == 0 || h == 0; }
+};
+}
+
+#endif
diff --git a/include/mbgl/util/recursive_wrapper.hpp b/include/mbgl/util/recursive_wrapper.hpp
new file mode 100644
index 0000000000..a616805c0f
--- /dev/null
+++ b/include/mbgl/util/recursive_wrapper.hpp
@@ -0,0 +1,127 @@
+#ifndef MAPBOX_UTIL_VARIANT_RECURSIVE_WRAPPER_HPP
+#define MAPBOX_UTIL_VARIANT_RECURSIVE_WRAPPER_HPP
+
+#include <utility>
+
+namespace mbgl { namespace util {
+
+template <typename T>
+class recursive_wrapper
+{
+public:
+    using type = T;
+private:
+
+    T* p_;
+
+public:
+
+    ~recursive_wrapper();
+    recursive_wrapper();
+
+    recursive_wrapper(recursive_wrapper const& operand);
+    recursive_wrapper(T const& operand);
+    recursive_wrapper(recursive_wrapper&& operand);
+    recursive_wrapper(T&& operand);
+
+private:
+
+    void assign(const T& rhs);
+
+public:
+
+    inline recursive_wrapper& operator=(recursive_wrapper const& rhs)
+    {
+        assign( rhs.get() );
+        return *this;
+    }
+
+    inline recursive_wrapper& operator=(T const& rhs)
+    {
+        assign( rhs );
+        return *this;
+    }
+
+    inline void swap(recursive_wrapper& operand) noexcept
+    {
+        T* temp = operand.p_;
+        operand.p_ = p_;
+        p_ = temp;
+    }
+
+
+    recursive_wrapper& operator=(recursive_wrapper&& rhs) noexcept
+    {
+        swap(rhs);
+        return *this;
+    }
+
+    recursive_wrapper& operator=(T&& rhs)
+    {
+        get() = std::move(rhs);
+        return *this;
+    }
+
+
+public:
+
+    T& get() { return *get_pointer(); }
+    const T& get() const { return *get_pointer(); }
+    T* get_pointer() { return p_; }
+    const T* get_pointer() const { return p_; }
+    operator T const&() const { return this->get(); }
+    operator T&() { return this->get(); }
+};
+
+template <typename T>
+recursive_wrapper<T>::~recursive_wrapper()
+{
+    delete p_;
+}
+
+template <typename T>
+recursive_wrapper<T>::recursive_wrapper()
+    : p_(new T)
+{
+}
+
+template <typename T>
+recursive_wrapper<T>::recursive_wrapper(recursive_wrapper const& operand)
+    : p_(new T( operand.get() ))
+{
+}
+
+template <typename T>
+recursive_wrapper<T>::recursive_wrapper(T const& operand)
+    : p_(new T(operand))
+{
+}
+
+template <typename T>
+recursive_wrapper<T>::recursive_wrapper(recursive_wrapper&& operand)
+    : p_(operand.p_)
+{
+    operand.p_ = nullptr;
+}
+
+template <typename T>
+recursive_wrapper<T>::recursive_wrapper(T&& operand)
+    : p_(new T( std::move(operand) ))
+{
+}
+
+template <typename T>
+void recursive_wrapper<T>::assign(const T& rhs)
+{
+    this->get() = rhs;
+}
+
+template <typename T>
+inline void swap(recursive_wrapper<T>& lhs, recursive_wrapper<T>& rhs) noexcept
+{
+    lhs.swap(rhs);
+}
+
+}}
+
+#endif // MAPBOX_UTIL_VARIANT_RECURSIVE_WRAPPER_HPP
diff --git a/include/mbgl/util/std.hpp b/include/mbgl/util/std.hpp
new file mode 100644
index 0000000000..051f89bb60
--- /dev/null
+++ b/include/mbgl/util/std.hpp
@@ -0,0 +1,38 @@
+#ifndef MBGL_UTIL_STD
+#define MBGL_UTIL_STD
+
+#include <memory>
+
+namespace std {
+
+// C++14 backfill from http://herbsutter.com/gotw/_102/
+template<typename T, typename ...Args>
+::std::unique_ptr<T> make_unique(Args&& ...args) {
+    return ::std::unique_ptr<T>(new T(::std::forward<Args>(args)...));
+}
+
+}
+
+namespace mbgl {
+namespace util {
+
+template <typename Container, typename ForwardIterator, typename Predicate>
+void erase_if(Container &container, ForwardIterator it, const ForwardIterator end, Predicate pred) {
+    while (it != end) {
+        if (pred(*it)) {
+            container.erase(it++);
+        } else {
+            ++it;
+        }
+    }
+}
+
+template <typename Container, typename Predicate>
+void erase_if(Container &container, Predicate pred) {
+    erase_if(container, container.begin(), container.end(), pred);
+}
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/string.hpp b/include/mbgl/util/string.hpp
new file mode 100644
index 0000000000..f17d55cec3
--- /dev/null
+++ b/include/mbgl/util/string.hpp
@@ -0,0 +1,24 @@
+#ifndef MBGL_UTIL_STRING
+#define MBGL_UTIL_STRING
+
+#include <string>
+
+namespace mbgl {
+namespace util {
+
+template<size_t max, typename... Args>
+inline std::string sprintf(const char *msg, Args... args) {
+    char res[max];
+    int len = snprintf(res, sizeof(res), msg, args...);
+    return std::string(res, len);
+}
+
+template<size_t max, typename... Args>
+inline std::string sprintf(const std::string &msg, Args... args) {
+    return sprintf<max>(msg.c_str(), args...);
+}
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/texturepool.hpp b/include/mbgl/util/texturepool.hpp
new file mode 100644
index 0000000000..566d8c1750
--- /dev/null
+++ b/include/mbgl/util/texturepool.hpp
@@ -0,0 +1,25 @@
+#ifndef MBGL_UTIL_TEXTUREPOOL
+#define MBGL_UTIL_TEXTUREPOOL
+
+#include <mbgl/util/noncopyable.hpp>
+#include <mbgl/platform/gl.hpp>
+
+#include <set>
+#include <mutex>
+
+namespace mbgl {
+
+class Texturepool : private util::noncopyable {
+
+public:
+    GLuint getTextureID();
+    void removeTextureID(GLuint texture_id);
+    void clearTextureIDs();
+
+private:
+    std::set<GLuint> texture_ids;
+};
+
+}
+
+#endif
diff --git a/include/mbgl/util/threadpool.hpp b/include/mbgl/util/threadpool.hpp
new file mode 100644
index 0000000000..497d4e3083
--- /dev/null
+++ b/include/mbgl/util/threadpool.hpp
@@ -0,0 +1,45 @@
+#ifndef MBGL_UTIL_THREADPOOL
+#define MBGL_UTIL_THREADPOOL
+
+#include <pthread.h>
+#include <forward_list>
+#include <queue>
+
+namespace mbgl {
+namespace util {
+
+class Threadpool {
+private:
+    class Worker {
+    public:
+        Worker(Threadpool& pool);
+        ~Worker();
+        static void *loop(void *ptr);
+
+    private:
+        Threadpool& pool;
+        pthread_t thread;
+    };
+
+public:
+    Threadpool(int max_workers = 4);
+    typedef void (*Callback)(void *);
+    void add(Callback callback, void *data);
+
+private:
+    typedef std::pair<Callback, void *> Task;
+    const int max_workers;
+    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
+    pthread_cond_t condition = PTHREAD_COND_INITIALIZER;
+    std::forward_list<Worker> workers;
+    int worker_count = 0;
+    std::queue<Task> tasks;
+};
+
+extern std::unique_ptr<Threadpool> threadpool;
+
+}
+}
+
+#endif
+
diff --git a/include/mbgl/util/time.hpp b/include/mbgl/util/time.hpp
new file mode 100644
index 0000000000..eacee2c982
--- /dev/null
+++ b/include/mbgl/util/time.hpp
@@ -0,0 +1,42 @@
+#ifndef MBGL_UTIL_TIME
+#define MBGL_UTIL_TIME
+
+#include <uv.h>
+
+namespace mbgl {
+
+typedef uint64_t timestamp;
+
+namespace util {
+
+
+// Returns time in nanoseconds since an arbitrary point in the past. This has
+// no relation to the current time, but is continuously increasing, so
+// comparisons between different timestamps produce meaningful values.
+inline timestamp now() {
+    return uv_hrtime();
+}
+}
+
+// used for time conversions
+constexpr timestamp operator"" _nanoseconds (long double ns) { return ns; }
+constexpr timestamp operator"" _nanosecond (long double ns) { return ns; }
+constexpr timestamp operator"" _microseconds (long double us) { return us * 1e3; }
+constexpr timestamp operator"" _microsecond (long double us) { return us * 1e3; }
+constexpr timestamp operator"" _milliseconds (long double ms) { return ms * 1e6; }
+constexpr timestamp operator"" _millisecond (long double ms) { return ms * 1e6; }
+constexpr timestamp operator"" _seconds (long double s) { return s * 1e9; }
+constexpr timestamp operator"" _second (long double s) { return s * 1e9; }
+
+constexpr timestamp operator"" _nanoseconds (unsigned long long ns) { return ns; }
+constexpr timestamp operator"" _nanosecond (unsigned long long ns) { return ns; }
+constexpr timestamp operator"" _microseconds (unsigned long long us) { return us * 1e3; }
+constexpr timestamp operator"" _microsecond (unsigned long long us) { return us * 1e3; }
+constexpr timestamp operator"" _milliseconds (unsigned long long ms) { return ms * 1e6; }
+constexpr timestamp operator"" _millisecond (unsigned long long ms) { return ms * 1e6; }
+constexpr timestamp operator"" _seconds (unsigned long long s) { return s * 1e9; }
+constexpr timestamp operator"" _second (unsigned long long s) { return s * 1e9; }
+
+}
+
+#endif
diff --git a/include/mbgl/util/timer.hpp b/include/mbgl/util/timer.hpp
new file mode 100644
index 0000000000..8171c2f5d1
--- /dev/null
+++ b/include/mbgl/util/timer.hpp
@@ -0,0 +1,40 @@
+#ifndef MBGL_UTIL_TIMER
+#define MBGL_UTIL_TIMER
+
+#include <mbgl/platform/event.hpp>
+
+#include <string>
+
+namespace mbgl {
+namespace util {
+
+#ifndef DISABLE_TIMER
+class timer {
+public:
+    timer(Event event = Event::General);
+    timer(EventSeverity severity, Event event = Event::General);
+    timer(const std::string &name, Event event = Event::General);
+    timer(const std::string &name, EventSeverity severity, Event event = Event::General);
+    void report(const std::string &name);
+    ~timer();
+
+private:
+    const std::string name;
+    EventSeverity severity = EventSeverity::Debug;
+    Event event = Event::General;
+    uint64_t start;
+};
+#else
+class timer {
+    inline timer(Event event = Event::General);
+    inline timer(EventSeverity severity, Event event = Event::General);
+    inline timer(const std::string &name, Event event = Event::General);
+    inline timer(const std::string &name, EventSeverity severity, Event event = Event::General);
+    inline void report(const std::string &name) {}
+    inline ~timer() {}
+};
+#endif
+}
+}
+
+#endif
diff --git a/include/mbgl/util/token.hpp b/include/mbgl/util/token.hpp
new file mode 100644
index 0000000000..a794e0489c
--- /dev/null
+++ b/include/mbgl/util/token.hpp
@@ -0,0 +1,52 @@
+#ifndef MBGL_UTIL_TOKEN
+#define MBGL_UTIL_TOKEN
+
+#ifdef __linux__
+#include <boost/regex.hpp>
+namespace regex_impl = boost;
+#else
+#include <regex>
+namespace regex_impl = std;
+#endif
+
+#include <map>
+
+namespace mbgl {
+namespace util {
+
+namespace detail {
+const regex_impl::regex tokenRegex("\\{(\\w+)\\}");
+const regex_impl::sregex_token_iterator tokensEnd = regex_impl::sregex_token_iterator();
+}
+
+template <typename Lookup>
+std::string replaceTokens(const std::string &source, const Lookup &lookup) {
+    std::string result;
+    result.reserve(source.size());
+
+    bool token = false;
+    for (auto token_it = regex_impl::sregex_token_iterator(source.begin(), source.end(),
+                                                           detail::tokenRegex, {-1, 1});
+        token_it != detail::tokensEnd; ++token_it, token = !token) {
+        if (!token_it->matched) {
+            continue;
+        }
+
+        result += token ? lookup(token_it->str()) : token_it->str();
+    }
+
+    return result;
+}
+
+template <typename T>
+inline std::string replaceTokens(const std::string &source, const std::map<std::string, T> &properties) {
+    return replaceTokens(source, [&properties](const std::string &token) -> std::string {
+        const auto it_prop = properties.find(token);
+        return it_prop != properties.end() ? toString(it_prop->second) : "";
+    });
+}
+
+} // end namespace util
+} // end namespace mbgl
+
+#endif
diff --git a/include/mbgl/util/transition.hpp b/include/mbgl/util/transition.hpp
new file mode 100644
index 0000000000..b12527124e
--- /dev/null
+++ b/include/mbgl/util/transition.hpp
@@ -0,0 +1,84 @@
+#ifndef MBGL_UTIL_TRANSITION
+#define MBGL_UTIL_TRANSITION
+
+#include <mbgl/util/noncopyable.hpp>
+#include <mbgl/util/time.hpp>
+#include <mbgl/style/types.hpp>
+
+namespace mbgl {
+namespace util {
+
+class transition : private noncopyable {
+public:
+    enum state {
+        running,
+        complete
+    };
+
+    inline transition(timestamp start, timestamp duration)
+        : start(start),
+          duration(duration) {}
+
+    inline float progress(timestamp now) const {
+        if (duration == 0) return 1;
+        if (start > now) return 0;
+
+        return (float)(now - start) / duration;
+    }
+
+    virtual state update(timestamp now) const = 0;
+    virtual ~transition();
+
+protected:
+    double interpolateDouble(double from, double to, double t) const;
+    float interpolateFloat(float from, float to, double t) const;
+    Color interpolateColor(Color from, Color to, double t) const;
+    std::array<float, 2> interpolateFloatArray(std::array<float, 2> from, std::array<float, 2> to, double t) const;
+
+protected:
+    const timestamp start, duration;
+};
+
+template <typename T>
+class ease_transition : public transition {
+public:
+    ease_transition(T from, T to, T& value, timestamp start, timestamp duration)
+        : transition(start, duration),
+          from(from),
+          to(to),
+          value(value) {}
+
+    state update(timestamp now) const;
+
+private:
+    const T from, to;
+    T& value;
+
+};
+
+template <typename T>
+class timeout : public transition {
+public:
+    timeout(T final_value, T& value, timestamp start, timestamp duration)
+        : transition(start, duration),
+          final_value(final_value),
+          value(value) {}
+
+    state update(timestamp now) const {
+        if (progress(now) >= 1) {
+            value = final_value;
+            return complete;
+        } else {
+            return running;
+        }
+    }
+
+private:
+    const T final_value;
+    T& value;
+};
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/unitbezier.hpp b/include/mbgl/util/unitbezier.hpp
new file mode 100644
index 0000000000..095e15f809
--- /dev/null
+++ b/include/mbgl/util/unitbezier.hpp
@@ -0,0 +1,121 @@
+/*
+ * Copyright (C) 2008 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef MBGL_UTIL_UNITBEZIER
+#define MBGL_UTIL_UNITBEZIER
+
+#include <cmath>
+
+namespace mbgl {
+namespace util {
+
+struct UnitBezier {
+    UnitBezier(double p1x, double p1y, double p2x, double p2y) {
+        // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1).
+        cx = 3.0 * p1x;
+        bx = 3.0 * (p2x - p1x) - cx;
+        ax = 1.0 - cx - bx;
+
+        cy = 3.0 * p1y;
+        by = 3.0 * (p2y - p1y) - cy;
+        ay = 1.0 - cy - by;
+    }
+
+    double sampleCurveX(double t) {
+        // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
+        return ((ax * t + bx) * t + cx) * t;
+    }
+
+    double sampleCurveY(double t) {
+        return ((ay * t + by) * t + cy) * t;
+    }
+
+    double sampleCurveDerivativeX(double t) {
+        return (3.0 * ax * t + 2.0 * bx) * t + cx;
+    }
+
+    // Given an x value, find a parametric value it came from.
+    double solveCurveX(double x, double epsilon) {
+        double t0;
+        double t1;
+        double t2;
+        double x2;
+        double d2;
+        int i;
+
+        // First try a few iterations of Newton's method -- normally very fast.
+        for (t2 = x, i = 0; i < 8; ++i) {
+            x2 = sampleCurveX(t2) - x;
+            if (fabs (x2) < epsilon)
+                return t2;
+            d2 = sampleCurveDerivativeX(t2);
+            if (fabs(d2) < 1e-6)
+                break;
+            t2 = t2 - x2 / d2;
+        }
+
+        // Fall back to the bisection method for reliability.
+        t0 = 0.0;
+        t1 = 1.0;
+        t2 = x;
+
+        if (t2 < t0)
+            return t0;
+        if (t2 > t1)
+            return t1;
+
+        while (t0 < t1) {
+            x2 = sampleCurveX(t2);
+            if (fabs(x2 - x) < epsilon)
+                return t2;
+            if (x > x2)
+                t0 = t2;
+            else
+                t1 = t2;
+            t2 = (t1 - t0) * .5 + t0;
+        }
+
+        // Failure.
+        return t2;
+    }
+
+    double solve(double x, double epsilon) {
+        return sampleCurveY(solveCurveX(x, epsilon));
+    }
+
+private:
+    double ax;
+    double bx;
+    double cx;
+
+    double ay;
+    double by;
+    double cy;
+};
+
+}
+}
+
+#endif
diff --git a/include/mbgl/util/utf.hpp b/include/mbgl/util/utf.hpp
new file mode 100644
index 0000000000..5dfc4ad2d1
--- /dev/null
+++ b/include/mbgl/util/utf.hpp
@@ -0,0 +1,50 @@
+#ifndef MBGL_UTIL_UTF
+#define MBGL_UTIL_UTF
+
+#include <memory>
+
+// g++/libstdc++ is missing c++11 codecvt support
+#ifdef __linux__
+#pragma GCC diagnostic push
+#ifndef __clang__
+#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
+#endif
+#include <boost/locale.hpp>
+#pragma GCC diagnostic pop
+#else
+#include <codecvt>
+#include <locale>
+#endif
+
+namespace mbgl {
+
+namespace util {
+
+#ifdef __linux__
+
+class utf8_to_utf32 {
+ public:
+    explicit utf8_to_utf32() {}
+    std::u32string convert(std::string const& utf8) {
+        return boost::locale::conv::utf_to_utf<char32_t>(utf8);
+    }
+};
+
+#else
+
+class utf8_to_utf32 {
+ public:
+    explicit utf8_to_utf32()
+        : utf32conv_() {}
+    std::u32string convert(std::string const& utf8) {
+        return utf32conv_.from_bytes(utf8);
+    }
+ private:
+    std::wstring_convert<std::codecvt_utf8<char32_t>, char32_t> utf32conv_;
+};
+
+#endif
+
+}}
+
+#endif
diff --git a/include/mbgl/util/uv.hpp b/include/mbgl/util/uv.hpp
new file mode 100644
index 0000000000..f36da83e4d
--- /dev/null
+++ b/include/mbgl/util/uv.hpp
@@ -0,0 +1,141 @@
+#ifndef MBGL_UTIL_UV
+#define MBGL_UTIL_UV
+
+#include <uv.h>
+#include <functional>
+#include <cassert>
+
+#ifdef __clang__
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wunused-parameter"
+#endif
+
+#include <boost/lockfree/queue.hpp>
+
+#ifdef __clang__
+#pragma clang diagnostic pop
+#endif
+
+
+namespace uv {
+
+class loop {
+public:
+    inline loop() : l(uv_loop_new()) {}
+    inline ~loop() { uv_loop_delete(l); }
+
+    inline uv_loop_t *operator*() { return l; }
+
+private:
+    uv_loop_t *l;
+};
+
+class mutex {
+public:
+    inline mutex() {
+        if (uv_mutex_init(&mtx) != 0) {
+            throw std::runtime_error("failed to initialize mutex");
+        }
+    }
+    inline ~mutex() { uv_mutex_destroy(&mtx); }
+    inline void lock() { uv_mutex_lock(&mtx); }
+    inline void unlock() { uv_mutex_unlock(&mtx); }
+
+private:
+    uv_mutex_t mtx;
+};
+
+class lock {
+public:
+    lock(mutex &mtx) : mtx(mtx) { mtx.lock(); }
+    ~lock() { mtx.unlock(); }
+
+private:
+    mutex &mtx;
+};
+
+class rwlock {
+public:
+    inline rwlock() {
+        if (uv_rwlock_init(&mtx) != 0) {
+            throw std::runtime_error("failed to initialize read-write lock");
+        }
+    }
+    inline ~rwlock() { uv_rwlock_destroy(&mtx); }
+    inline void rdlock() { uv_rwlock_rdlock(&mtx); }
+    inline void wrlock() { uv_rwlock_wrlock(&mtx); }
+    inline void rdunlock() { uv_rwlock_rdunlock(&mtx); }
+    inline void wrunlock() { uv_rwlock_wrunlock(&mtx); }
+
+private:
+    uv_rwlock_t mtx;
+};
+
+class readlock {
+public:
+    inline readlock(rwlock &mtx) : mtx(mtx) { mtx.rdlock(); }
+    inline ~readlock() { mtx.rdunlock(); }
+
+private:
+    rwlock &mtx;
+};
+
+class writelock {
+public:
+    inline writelock(rwlock &mtx) : mtx(mtx) { mtx.wrlock(); }
+    inline ~writelock() { mtx.wrunlock(); }
+
+private:
+    rwlock &mtx;
+};
+
+class once {
+public:
+    typedef void (*callback)();
+    void operator()(void (*callback)(void)) {
+        uv_once(&o, callback);
+    }
+
+private:
+    uv_once_t o = UV_ONCE_INIT;
+};
+
+template <typename T>
+class work {
+public:
+    typedef void (*work_callback)(T &object);
+    typedef void (*after_work_callback)(T &object);
+
+    template<typename... Args>
+    work(const std::shared_ptr<loop> &loop, work_callback work_cb, after_work_callback after_work_cb, Args&&... args)
+        : loop(loop),
+          data(std::forward<Args>(args)...),
+          work_cb(work_cb),
+          after_work_cb(after_work_cb) {
+        req.data = this;
+        uv_queue_work(**loop, &req, do_work, after_work);
+    }
+
+private:
+    static void do_work(uv_work_t *req) {
+        work<T> *w = static_cast<work<T> *>(req->data);
+        w->work_cb(w->data);
+    }
+
+    static void after_work(uv_work_t *req, int) {
+        work<T> *w = static_cast<work<T> *>(req->data);
+        w->after_work_cb(w->data);
+        delete w;
+    }
+
+private:
+    std::shared_ptr<uv::loop> loop;
+    uv_work_t req;
+    T data;
+    work_callback work_cb;
+    after_work_callback after_work_cb;
+};
+
+}
+
+#endif
diff --git a/include/mbgl/util/variant.hpp b/include/mbgl/util/variant.hpp
new file mode 100644
index 0000000000..ddc82ee311
--- /dev/null
+++ b/include/mbgl/util/variant.hpp
@@ -0,0 +1,731 @@
+#ifndef MAPBOX_UTIL_VARIANT_HPP
+#define MAPBOX_UTIL_VARIANT_HPP
+
+#include <utility>
+#include <typeinfo>
+#include <type_traits>
+#include <algorithm> // std::move/swap
+#include <stdexcept> // runtime_error
+#include <new> // operator new
+#include <cstddef> // size_t
+#include <iosfwd>
+#include <string>
+
+#include "recursive_wrapper.hpp"
+
+#ifdef _MSC_VER
+ // http://msdn.microsoft.com/en-us/library/z8y1yy88.aspx
+ #ifdef NDEBUG
+  #define VARIANT_INLINE __forceinline
+ #else
+  #define VARIANT_INLINE __declspec(noinline)
+ #endif
+#else
+ #ifdef NDEBUG
+  #define VARIANT_INLINE inline __attribute__((always_inline))
+ #else
+  #define VARIANT_INLINE __attribute__((noinline))
+ #endif
+#endif
+
+#define VARIANT_MAJOR_VERSION 0
+#define VARIANT_MINOR_VERSION 1
+#define VARIANT_PATCH_VERSION 0
+
+// translates to 100
+#define VARIANT_VERSION (VARIANT_MAJOR_VERSION*100000) + (VARIANT_MINOR_VERSION*100) + (VARIANT_PATCH_VERSION)
+
+namespace mbgl { namespace util { namespace detail {
+
+static constexpr std::size_t invalid_value = std::size_t(-1);
+
+template <typename T, typename...Types>
+struct direct_type;
+
+template <typename T, typename First, typename...Types>
+struct direct_type<T, First, Types...>
+{
+    static constexpr std::size_t index = std::is_same<T, First>::value
+        ? sizeof...(Types) : direct_type<T, Types...>::index;
+};
+
+template <typename T>
+struct direct_type<T>
+{
+    static constexpr std::size_t index = invalid_value;
+};
+
+template <typename T, typename...Types>
+struct convertible_type;
+
+template <typename T, typename First, typename...Types>
+struct convertible_type<T, First, Types...>
+{
+    static constexpr std::size_t index = std::is_convertible<T, First>::value
+        ? sizeof...(Types) : convertible_type<T, Types...>::index;
+};
+
+template <typename T>
+struct convertible_type<T>
+{
+    static constexpr std::size_t index = invalid_value;
+};
+
+template <typename T, typename...Types>
+struct value_traits
+{
+    static constexpr std::size_t direct_index = direct_type<T, Types...>::index;
+    static constexpr std::size_t index =
+        (direct_index == invalid_value) ? convertible_type<T, Types...>::index : direct_index;
+};
+
+template <typename T, typename...Types>
+struct is_valid_type;
+
+template <typename T, typename First, typename... Types>
+struct is_valid_type<T, First, Types...>
+{
+    static constexpr bool value = std::is_convertible<T, First>::value
+        || is_valid_type<T, Types...>::value;
+};
+
+template <typename T>
+struct is_valid_type<T> : std::false_type {};
+
+template <std::size_t N, typename ... Types>
+struct select_type
+{
+    static_assert(N < sizeof...(Types), "index out of bounds");
+};
+
+template <std::size_t N, typename T, typename ... Types>
+struct select_type<N, T, Types...>
+{
+    using type = typename select_type<N - 1, Types...>::type;
+};
+
+template <typename T, typename ... Types>
+struct select_type<0, T, Types...>
+{
+    using type = T;
+};
+
+} // namespace detail
+
+// static visitor
+template <typename R = void>
+struct static_visitor
+{
+    using result_type = R;
+protected:
+    static_visitor() {}
+    ~static_visitor() {}
+};
+
+
+template <std::size_t arg1, std::size_t ... others>
+struct static_max;
+
+template <std::size_t arg>
+struct static_max<arg>
+{
+    static const std::size_t value = arg;
+};
+
+template <std::size_t arg1, std::size_t arg2, std::size_t ... others>
+struct static_max<arg1, arg2, others...>
+{
+    static const std::size_t value = arg1 >= arg2 ? static_max<arg1, others...>::value :
+        static_max<arg2, others...>::value;
+};
+
+template<typename... Types>
+struct variant_helper;
+
+template<typename T, typename... Types>
+struct variant_helper<T, Types...>
+{
+    VARIANT_INLINE static void destroy(const std::size_t id, void * data)
+    {
+        if (id == sizeof...(Types))
+        {
+            reinterpret_cast<T*>(data)->~T();
+        }
+        else
+        {
+            variant_helper<Types...>::destroy(id, data);
+        }
+    }
+
+    VARIANT_INLINE static void move(const std::size_t old_id, void * old_value, void * new_value)
+    {
+        if (old_id == sizeof...(Types))
+        {
+            new (new_value) T(std::move(*reinterpret_cast<T*>(old_value)));
+            //std::memcpy(new_value, old_value, sizeof(T));
+            // ^^  DANGER: this should only be considered for relocatable types e.g built-in types
+            // Also, I don't see any measurable performance benefit just yet
+        }
+        else
+        {
+            variant_helper<Types...>::move(old_id, old_value, new_value);
+        }
+    }
+
+    VARIANT_INLINE static void copy(const std::size_t old_id, const void * old_value, void * new_value)
+    {
+        if (old_id == sizeof...(Types))
+        {
+            new (new_value) T(*reinterpret_cast<const T*>(old_value));
+        }
+        else
+        {
+            variant_helper<Types...>::copy(old_id, old_value, new_value);
+        }
+    }
+};
+
+template<> struct variant_helper<>
+{
+    VARIANT_INLINE static void destroy(const std::size_t, void *) {}
+    VARIANT_INLINE static void move(const std::size_t, void *, void *) {}
+    VARIANT_INLINE static void copy(const std::size_t, const void *, void *) {}
+};
+
+namespace detail {
+
+template <typename T>
+struct unwrapper
+{
+    T const& operator() (T const& obj) const
+    {
+        return obj;
+    }
+
+    T& operator() (T & obj) const
+    {
+        return obj;
+    }
+};
+
+
+template <typename T>
+struct unwrapper<recursive_wrapper<T>>
+{
+    auto operator() (recursive_wrapper<T> const& obj) const
+        -> typename recursive_wrapper<T>::type const&
+    {
+        return obj.get();
+    }
+};
+
+
+template <typename F, typename V, typename...Types>
+struct dispatcher;
+
+template <typename F, typename V, typename T, typename...Types>
+struct dispatcher<F, V, T, Types...>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const& v, F f)
+    {
+        if (v.get_type_index() == sizeof...(Types))
+        {
+            return f(unwrapper<T>()(v. template get<T>()));
+        }
+        else
+        {
+            return dispatcher<F, V, Types...>::apply_const(v, f);
+        }
+    }
+
+    VARIANT_INLINE static result_type apply(V & v, F f)
+    {
+        if (v.get_type_index() == sizeof...(Types))
+        {
+            return f(unwrapper<T>()(v. template get<T>()));
+        }
+        else
+        {
+            return dispatcher<F, V, Types...>::apply(v, f);
+        }
+    }
+};
+
+template<typename F, typename V>
+struct dispatcher<F, V>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const&, F)
+    {
+        throw std::runtime_error(std::string("unary dispatch: FAIL ") + typeid(V).name());
+    }
+
+    VARIANT_INLINE static result_type apply(V &, F)
+    {
+        throw std::runtime_error(std::string("unary dispatch: FAIL ") + typeid(V).name());
+    }
+};
+
+
+template <typename F, typename V, typename T, typename...Types>
+struct binary_dispatcher_rhs;
+
+template <typename F, typename V, typename T0, typename T1, typename...Types>
+struct binary_dispatcher_rhs<F, V, T0, T1, Types...>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const& lhs, V const& rhs, F f)
+    {
+        if (rhs.get_type_index() == sizeof...(Types)) // call binary functor
+        {
+            return f(unwrapper<T0>()(lhs. template get<T0>()),
+                     unwrapper<T1>()(rhs. template get<T1>()));
+        }
+        else
+        {
+            return binary_dispatcher_rhs<F, V, T0, Types...>::apply_const(lhs, rhs, f);
+        }
+    }
+
+    VARIANT_INLINE static result_type apply(V & lhs, V & rhs, F f)
+    {
+        if (rhs.get_type_index() == sizeof...(Types)) // call binary functor
+        {
+            return f(unwrapper<T0>()(lhs. template get<T0>()),
+                     unwrapper<T1>()(rhs. template get<T1>()));
+        }
+        else
+        {
+            return binary_dispatcher_rhs<F, V, T0, Types...>::apply(lhs, rhs, f);
+        }
+    }
+
+};
+
+template<typename F, typename V, typename T>
+struct binary_dispatcher_rhs<F, V, T>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const&, V const&, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+    VARIANT_INLINE static result_type apply(V &, V &, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+};
+
+
+template <typename F, typename V, typename T, typename...Types>
+struct binary_dispatcher_lhs;
+
+template <typename F, typename V, typename T0, typename T1, typename...Types>
+struct binary_dispatcher_lhs<F, V, T0, T1, Types...>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const& lhs, V const& rhs, F f)
+    {
+        if (lhs.get_type_index() == sizeof...(Types)) // call binary functor
+        {
+            return f(lhs. template get<T1>(), rhs. template get<T0>());
+        }
+        else
+        {
+            return binary_dispatcher_lhs<F, V, T0, Types...>::apply_const(lhs, rhs, f);
+        }
+    }
+
+    VARIANT_INLINE static result_type apply(V & lhs, V & rhs, F f)
+    {
+        if (lhs.get_type_index() == sizeof...(Types)) // call binary functor
+        {
+            return f(lhs. template get<T1>(), rhs. template get<T0>());
+        }
+        else
+        {
+            return binary_dispatcher_lhs<F, V, T0, Types...>::apply(lhs, rhs, f);
+        }
+    }
+
+};
+
+template<typename F, typename V, typename T>
+struct binary_dispatcher_lhs<F, V, T>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const&, V const&, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+
+    VARIANT_INLINE static result_type apply(V &, V &, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+};
+
+template <typename F, typename V, typename...Types>
+struct binary_dispatcher;
+
+template <typename F, typename V, typename T, typename...Types>
+struct binary_dispatcher<F, V, T, Types...>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const& v0, V const& v1, F f)
+    {
+        if (v0.get_type_index() == sizeof...(Types))
+        {
+            if (v0.get_type_index() == v1.get_type_index())
+            {
+                return f(v0. template get<T>(), v1. template get<T>()); // call binary functor
+            }
+            else
+            {
+                return binary_dispatcher_rhs<F, V, T, Types...>::apply_const(v0, v1, f);
+            }
+        }
+        else if (v1.get_type_index() == sizeof...(Types))
+        {
+            return binary_dispatcher_lhs<F, V, T, Types...>::apply_const(v0, v1, f);
+        }
+        return binary_dispatcher<F, V, Types...>::apply_const(v0, v1, f);
+    }
+
+    VARIANT_INLINE static result_type apply(V & v0, V & v1, F f)
+    {
+        if (v0.get_type_index() == sizeof...(Types))
+        {
+            if (v0.get_type_index() == v1.get_type_index())
+            {
+                return f(v0. template get<T>(), v1. template get<T>()); // call binary functor
+            }
+            else
+            {
+                return binary_dispatcher_rhs<F, V, T, Types...>::apply(v0, v1, f);
+            }
+        }
+        else if (v1.get_type_index() == sizeof...(Types))
+        {
+            return binary_dispatcher_lhs<F, V, T, Types...>::apply(v0, v1, f);
+        }
+        return binary_dispatcher<F, V, Types...>::apply(v0, v1, f);
+    }
+};
+
+template<typename F, typename V>
+struct binary_dispatcher<F, V>
+{
+    using result_type = typename F::result_type;
+    VARIANT_INLINE static result_type apply_const(V const&, V const&, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+
+    VARIANT_INLINE static result_type apply(V &, V &, F)
+    {
+        throw std::runtime_error("binary dispatch: FAIL");
+    }
+};
+
+// comparator functors
+struct equal_comp
+{
+    template <typename T>
+    bool operator()(T const& lhs, T const& rhs) const
+    {
+        return lhs == rhs;
+    }
+};
+
+struct less_comp
+{
+    template <typename T>
+    bool operator()(T const& lhs, T const& rhs) const
+    {
+        return lhs < rhs;
+    }
+};
+
+template <typename Variant, typename Comp>
+class comparer : public static_visitor<bool>
+{
+public:
+    explicit comparer(Variant const& lhs) noexcept
+        : lhs_(lhs) {}
+    comparer& operator=(comparer const&) = delete;
+    // visitor
+    template<typename T>
+    bool operator()(T const& rhs_content) const
+    {
+        T const& lhs_content = lhs_.template get<T>();
+        return Comp()(lhs_content, rhs_content);
+    }
+private:
+    Variant const& lhs_;
+};
+
+// operator<< helper
+template <typename Out>
+class printer : public static_visitor<>
+{
+public:
+    explicit printer(Out & out)
+        : out_(out) {}
+    printer& operator=(printer const&) = delete;
+
+// visitor
+    template <typename T>
+    void operator()(T const& operand) const
+    {
+        out_ << operand;
+    }
+private:
+    Out & out_;
+};
+
+} // namespace detail
+
+template<typename... Types>
+class variant
+{
+private:
+
+    static const std::size_t data_size = static_max<sizeof(Types)...>::value;
+    static const std::size_t data_align = static_max<alignof(Types)...>::value;
+
+    using data_type = typename std::aligned_storage<data_size, data_align>::type;
+    using helper_type = variant_helper<Types...>;
+
+    std::size_t type_index;
+    data_type data;
+
+public:
+
+    VARIANT_INLINE variant()
+        : type_index(sizeof...(Types) - 1)
+    {
+        new (&data) typename detail::select_type<0, Types...>::type();
+    }
+
+    template <typename T, class = typename std::enable_if<
+                         detail::is_valid_type<T, Types...>::value>::type>
+    VARIANT_INLINE explicit variant(T const& val) noexcept
+        : type_index(detail::value_traits<T, Types...>::index)
+    {
+        constexpr std::size_t index = sizeof...(Types) - detail::value_traits<T, Types...>::index - 1;
+        using target_type = typename detail::select_type<index, Types...>::type;
+        new (&data) target_type(val);
+    }
+
+    template <typename T, class = typename std::enable_if<
+                          detail::is_valid_type<T, Types...>::value>::type>
+    VARIANT_INLINE variant(T && val) noexcept
+        : type_index(detail::value_traits<T, Types...>::index)
+    {
+        constexpr std::size_t index = sizeof...(Types) - detail::value_traits<T, Types...>::index - 1;
+        using target_type = typename detail::select_type<index, Types...>::type;
+        new (&data) target_type(std::forward<T>(val)); // nothrow
+    }
+
+    VARIANT_INLINE variant(variant<Types...> const& old)
+        : type_index(old.type_index)
+    {
+        helper_type::copy(old.type_index, &old.data, &data);
+    }
+
+    VARIANT_INLINE variant(variant<Types...>&& old) noexcept
+        : type_index(old.type_index)
+    {
+        helper_type::move(old.type_index, &old.data, &data);
+    }
+
+    friend void swap(variant<Types...> & first, variant<Types...> & second)
+    {
+        using std::swap; //enable ADL
+        swap(first.type_index, second.type_index);
+        swap(first.data, second.data);
+    }
+
+    VARIANT_INLINE variant<Types...>& operator=(variant<Types...> other)
+    {
+        swap(*this, other);
+        return *this;
+    }
+
+    // conversions
+    // move-assign
+    template <typename T>
+    VARIANT_INLINE variant<Types...>& operator=(T && rhs) noexcept
+    {
+        variant<Types...> temp(std::move(rhs));
+        swap(*this, temp);
+        return *this;
+    }
+
+    // copy-assign
+    template <typename T>
+    VARIANT_INLINE variant<Types...>& operator=(T const& rhs)
+    {
+        variant<Types...> temp(rhs);
+        swap(*this, temp);
+        return *this;
+    }
+
+    template<typename T>
+    VARIANT_INLINE bool is() const
+    {
+        return (type_index == detail::direct_type<T, Types...>::index);
+    }
+
+    VARIANT_INLINE bool valid() const
+    {
+        return (type_index != detail::invalid_value);
+    }
+
+    template<typename T, typename... Args>
+    VARIANT_INLINE void set(Args&&... args)
+    {
+        helper_type::destroy(type_index, &data);
+        new (&data) T(std::forward<Args>(args)...);
+        type_index = detail::direct_type<T, Types...>::index;
+    }
+
+    template<typename T>
+    VARIANT_INLINE T& get()
+    {
+        if (type_index == detail::direct_type<T, Types...>::index)
+        {
+            return *reinterpret_cast<T*>(&data);
+        }
+        else
+        {
+            throw std::runtime_error("in get()");
+        }
+    }
+
+    template<typename T>
+    VARIANT_INLINE T const& get() const
+    {
+        if (type_index == detail::direct_type<T, Types...>::index)
+        {
+            return *reinterpret_cast<T const*>(&data);
+        }
+        else
+        {
+            throw std::runtime_error("in get()");
+        }
+    }
+
+    VARIANT_INLINE std::size_t get_type_index() const
+    {
+        return type_index;
+    }
+
+    // visitor
+    // unary
+    template <typename F, typename V>
+    auto VARIANT_INLINE
+    static visit(V const& v, F f)
+        -> decltype(detail::dispatcher<F, V, Types...>::apply_const(v, f))
+    {
+        return detail::dispatcher<F, V, Types...>::apply_const(v, f);
+    }
+    // non-const
+    template <typename F, typename V>
+    auto VARIANT_INLINE
+    static visit(V & v, F f)
+        -> decltype(detail::dispatcher<F, V, Types...>::apply(v, f))
+    {
+        return detail::dispatcher<F, V, Types...>::apply(v, f);
+    }
+
+    // binary
+    // const
+    template <typename F, typename V>
+    auto VARIANT_INLINE
+    static binary_visit(V const& v0, V const& v1, F f)
+        -> decltype(detail::binary_dispatcher<F, V, Types...>::apply_const(v0, v1, f))
+    {
+        return detail::binary_dispatcher<F, V, Types...>::apply_const(v0, v1, f);
+    }
+    // non-const
+    template <typename F, typename V>
+    auto VARIANT_INLINE
+    static binary_visit(V& v0, V& v1, F f)
+        -> decltype(detail::binary_dispatcher<F, V, Types...>::apply(v0, v1, f))
+    {
+        return detail::binary_dispatcher<F, V, Types...>::apply(v0, v1, f);
+    }
+
+    ~variant() noexcept
+    {
+        helper_type::destroy(type_index, &data);
+    }
+
+    // comparison operators
+    // equality
+    VARIANT_INLINE bool operator==(variant const& rhs) const
+    {
+        if (this->get_type_index() != rhs.get_type_index())
+            return false;
+        detail::comparer<variant, detail::equal_comp> visitor(*this);
+        return visit(rhs, visitor);
+    }
+    // less than
+    VARIANT_INLINE bool operator<(variant const& rhs) const
+    {
+        if (this->get_type_index() != rhs.get_type_index())
+        {
+            return this->get_type_index() < rhs.get_type_index();
+            // ^^ borrowed from boost::variant
+        }
+        detail::comparer<variant, detail::less_comp> visitor(*this);
+        return visit(rhs, visitor);
+    }
+};
+
+// unary visitor interface
+
+// const
+template <typename V, typename F>
+auto VARIANT_INLINE static apply_visitor(F f, V const& v) -> decltype(V::visit(v, f))
+{
+    return V::visit(v, f);
+}
+// non-const
+template <typename V, typename F>
+auto VARIANT_INLINE static apply_visitor(F f, V & v) -> decltype(V::visit(v, f))
+{
+    return V::visit(v, f);
+}
+
+// binary visitor interface
+// const
+template <typename V, typename F>
+auto VARIANT_INLINE static apply_visitor(F f, V const& v0, V const& v1) -> decltype(V::binary_visit(v0, v1, f))
+{
+    return V::binary_visit(v0, v1, f);
+}
+// non-const
+template <typename V, typename F>
+auto VARIANT_INLINE static apply_visitor(F f, V & v0, V & v1) -> decltype(V::binary_visit(v0, v1, f))
+{
+    return V::binary_visit(v0, v1, f);
+}
+
+
+// operator<<
+template <typename charT, typename traits, typename Variant>
+VARIANT_INLINE std::basic_ostream<charT, traits>&
+operator<< (std::basic_ostream<charT, traits>& out, Variant const& rhs)
+{
+    detail::printer<std::basic_ostream<charT, traits>> visitor(out);
+    apply_visitor(visitor, rhs);
+    return out;
+}
+
+}}
+
+#endif  // MAPBOX_UTIL_VARIANT_HPP
diff --git a/include/mbgl/util/vec.hpp b/include/mbgl/util/vec.hpp
new file mode 100644
index 0000000000..0b9bf63d53
--- /dev/null
+++ b/include/mbgl/util/vec.hpp
@@ -0,0 +1,117 @@
+#ifndef MBGL_UTIL_VEC
+#define MBGL_UTIL_VEC
+
+#include <limits>
+#include <type_traits>
+#include <cmath>
+#include <cstdint>
+#include <array>
+
+namespace mbgl {
+
+template <typename T = double>
+struct vec2 {
+    struct null {};
+    typedef T Type;
+
+    T x, y;
+
+    inline vec2() {}
+
+    template<typename U = T, typename std::enable_if<std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
+    inline vec2(null) : x(std::numeric_limits<T>::quiet_NaN()), y(std::numeric_limits<T>::quiet_NaN()) {}
+
+    template<typename U = T, typename std::enable_if<!std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
+    inline vec2(null) : x(std::numeric_limits<T>::min()), y(std::numeric_limits<T>::min()) {}
+
+    inline vec2(const vec2& o) : x(o.x), y(o.y) {}
+
+    template<typename U>
+    inline vec2(const U& u) : x(u.x), y(u.y) {}
+
+    inline vec2(T x, T y) : x(x), y(y) {}
+
+    inline bool operator==(const vec2& rhs) const {
+        return x == rhs.x && y == rhs.y;
+    }
+
+    template <typename O>
+    inline typename std::enable_if<std::is_arithmetic<O>::value, vec2>::type
+    operator*(O o) const {
+        return {x * o, y * o};
+    }
+
+    template <typename O>
+    inline typename std::enable_if<std::is_arithmetic<O>::value, vec2>::type &
+    operator*=(O o) {
+        x *= o;
+        y *= o;
+    }
+
+    inline vec2<T> operator *(const std::array<float, 16>& matrix) {
+        return { x * matrix[0] + y * matrix[4] + matrix[12], x * matrix[1] + y * matrix[5] + matrix[13] };
+    }
+
+    template <typename O>
+    inline typename std::enable_if<std::is_arithmetic<O>::value, vec2>::type
+    operator-(O o) const {
+        return {x - o, y - o};
+    }
+
+    template <typename O>
+    inline typename std::enable_if<!std::is_arithmetic<O>::value, vec2>::type
+    operator-(const O &o) const {
+        return {x - o.x, y - o.y};
+    }
+
+    template <typename M>
+    inline vec2 matMul(const M &m) const {
+        return {m[0] * x + m[1] * y, m[2] * x + m[3] * y};
+    }
+
+    template<typename U = T, typename std::enable_if<std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
+    inline operator bool() const {
+        return !isnan(x) && !isnan(y);
+    }
+
+    template<typename U = T, typename std::enable_if<!std::numeric_limits<U>::has_quiet_NaN, int>::type = 0>
+    inline operator bool() const {
+        return x != std::numeric_limits<T>::min() && y != std::numeric_limits<T>::min();
+    }
+};
+
+template <typename T = double>
+struct vec3 {
+    T x, y, z;
+
+    inline vec3() {}
+    inline vec3(const vec3& o) : x(o.x), y(o.y), z(o.z) {}
+    inline vec3(T x, T y, T z) : x(x), y(y), z(z) {}
+    inline bool operator==(const vec3& rhs) const {
+        return x == rhs.x && y == rhs.y && z == rhs.z;
+    }
+};
+
+template <typename T = double>
+struct vec4 {
+    T x, y, z, w;
+
+    inline vec4() {}
+    inline vec4(const vec4& o) : x(o.x), y(o.y), z(o.z), w(o.w) {}
+    inline vec4(T x, T y, T z, T w) : x(x), y(y), z(z), w(w) {}
+    inline bool operator==(const vec4& rhs) const {
+        return x == rhs.x && y == rhs.y && z == rhs.z && w == rhs.w;
+    }
+};
+
+
+struct box {
+    vec2<double> tl, tr, bl, br;
+    vec2<double> center;
+};
+
+typedef vec2<int16_t> Coordinate;
+
+}
+
+#endif