#include <psemek/app/application_base.hpp>
#include <psemek/app/default_application_factory.hpp>

#include <psemek/gfx/gl.hpp>
#include <psemek/gfx/mesh.hpp>
#include <psemek/gfx/program.hpp>
#include <psemek/gfx/painter.hpp>
#include <psemek/gfx/renderer/simple.hpp>
#include <psemek/gfx/error.hpp>

#include <psemek/math/camera.hpp>
#include <psemek/math/math.hpp>
#include <psemek/math/homogeneous.hpp>
#include <psemek/math/gauss.hpp>
#include <psemek/math/orientation.hpp>
#include <psemek/math/intersection.hpp>
#include <psemek/math/distance.hpp>

#include <psemek/cg/body/icosahedron.hpp>
#include <psemek/cg/body/box.hpp>
#include <psemek/cg/body/frustum.hpp>
#include <psemek/cg/body/prism.hpp>
#include <psemek/cg/convex/inside.hpp>
#include <psemek/cg/convex/separation.hpp>

#include <psemek/util/clock.hpp>
#include <psemek/util/to_string.hpp>
#include <psemek/util/moving_average.hpp>
#include <psemek/util/recursive.hpp>
#include <psemek/util/lru_cache.hpp>
#include <psemek/async/threadpool.hpp>

#include <fstream>
#include <iomanip>
#include <atomic>
#include <unordered_map>
#include <unordered_set>
#include <filesystem>

#include <zlib.h>

// TODO: use LRU cache for tile generation requests, combine with threadpool
// TODO: fix frustum culling
// TODO: fix seams at tile borders
// TODO: try a different coordinate system for closer tiles
// TODO: add space, stars, the sun
// TODO: add atmospheric glow

using namespace psemek;

template <typename Value, typename T>
struct smooth_updater
{
	smooth_updater(Value & value, T speed)
		: value_{value}
		, target_value_{value}
		, speed_{speed}
	{}

	smooth_updater & operator = (Value const & value)
	{
		target_value_ = value;
		return *this;
	}

	operator Value const & () const
	{
		return target_value_;
	}

	void update(T dt)
	{
		value_ += std::min(T{1}, dt * speed_) * (target_value_ - value_);
	}

private:
	Value & value_;
	Value target_value_;
	T speed_;
};

static const float exaggeration = 1.f;

struct height_provider
{
	float height_at(math::vector<float, 3> const & v);

	struct datum_id_hash
	{
		std::size_t operator() (std::pair<int, int> const & p) const
		{
			return ((p.first + 180) << 16) | (p.second + 90);
		}
	};

	std::mutex datums_mutex;
	std::unordered_map<std::pair<int, int>, std::unique_ptr<std::uint16_t[]>, datum_id_hash> datums;

	std::mutex no_datums_mutex;
	std::unordered_set<std::pair<int, int>, datum_id_hash> no_datums;
};

float height_provider::height_at(math::vector<float, 3> const & v)
{
	static std::filesystem::path const data_path = "/home/lisyarus/data/srtm/dem";

	float const lat = math::deg(std::asin(v[2]));

	float const lon = math::deg(std::atan2(v[0], -v[1]));

	int ilat = std::floor(lat);
	int ilon = std::floor(lon);

	auto id = std::make_pair(ilat, ilon);

	{
		std::lock_guard lock{no_datums_mutex};
		if (no_datums.count(id) > 0)
			return 0.f;
	}

	std::uint16_t const * values = nullptr;
	{
		std::lock_guard lock{datums_mutex};
		auto it = datums.find(id);
		if (it != datums.end())
			values = it->second.get();
	}

	if (!values)
	{
		{
			std::lock_guard lock{datums_mutex};
			if (datums.size() > 100)
				datums.clear();
		}

		std::ostringstream os;
		if (ilat >= 0)
			os << "N/" << std::setw(2) << std::setfill('0') << ilat << '/';
		else
			os << "S/" << std::setw(2) << std::setfill('0') << (-ilat) << '/';
		if (ilon >= 0)
			os << "E/" << std::setw(3) << std::setfill('0') << ilon << '/';
		else
			os << "W/" << std::setw(3) << std::setfill('0') << (-ilon) << '/';

		os << "data.zip";

		std::filesystem::path const filename = data_path / os.str();

		if (!std::filesystem::exists(filename) || !std::filesystem::is_regular_file(filename))
		{
			std::lock_guard lock{no_datums_mutex};
			no_datums.insert(id);
			return 0.f;
		}

		std::size_t zsize = std::filesystem::file_size(filename);

		std::ifstream ifs(filename, std::ios::binary);
		if (!ifs)
		{
			std::lock_guard lock{no_datums_mutex};
			no_datums.insert(id);
			return 0.f;
		}

		std::vector<char> zdata(zsize);
		ifs.read(zdata.data(), zdata.size());
		ifs.close();

		std::unique_ptr<std::uint16_t[]> data{new std::uint16_t[3601 * 3601]};

		z_stream infstream;
		infstream.zalloc = Z_NULL;
		infstream.zfree = Z_NULL;
		infstream.opaque = Z_NULL;
		// setup "b" as the input and "c" as the compressed output
		infstream.avail_in = zdata.size(); // size of input
		infstream.next_in = (Bytef *)zdata.data(); // input char array
		infstream.avail_out = 3601 * 3601 * 2; // size of output
		infstream.next_out = (Bytef *)data.get(); // output char array

		// the actual DE-compression work.
		inflateInit(&infstream);
		inflate(&infstream, Z_NO_FLUSH);
		inflateEnd(&infstream);

		{
			std::lock_guard lock{datums_mutex};
			auto res = datums.insert(std::make_pair(id, std::move(data)));
			values = res.first->second.get();
		}
	}

	auto at = [values](int lat, int lon) -> float
	{
		return (int)values[(3600 - lat) * 3601 + lon] - 32768;
	};

	int const tlat = math::clamp<int>(std::floor((lat - ilat) * 3600), {0, 3600 - 1});
	int const tlon = math::clamp<int>(std::floor((lon - ilon) * 3600), {0, 3600 - 1});

	float const mlat = (lat - ilat) * 3600.f - tlat;
	float const mlon = (lon - ilon) * 3600.f - tlon;

	float h00 = at(tlat, tlon);
	float h01 = at(tlat + 1, tlon);
	float h10 = at(tlat, tlon + 1);
	float h11 = at(tlat + 1, tlon + 1);

	return math::lerp(math::lerp(h00, h01, mlat), math::lerp(h10, h11, mlat), mlon);
}

static constexpr int node_size_log2 = 8;
static constexpr int node_size = 1 << node_size_log2;
static constexpr int node_child_depth = 1;
static constexpr int node_child_size = 1 << node_child_depth;
static constexpr int node_child_count = node_child_size * node_child_size;
static constexpr int max_child_level = 20 - node_size_log2 - node_child_depth;

struct node_cache
{
	static std::filesystem::path data_path() { return "/home/lisyarus/data/srtm/cache"; }

	std::optional<std::vector<std::int16_t>> load(std::size_t uid);
	void store(std::size_t uid, std::vector<std::int16_t> const & data);
};

std::optional<std::vector<std::int16_t>> node_cache::load(std::size_t uid)
{
	std::ostringstream oss;
	oss << std::hex << uid;

	std::ifstream file(data_path() / oss.str(), std::ios::binary);
	if (!file)
		return std::nullopt;

	std::vector<std::int16_t> data(((node_size + 2) * (node_size + 1)) / 2);
	file.read(reinterpret_cast<char *>(data.data()), data.size() * sizeof(data[0]));
	return data;
}

void node_cache::store(std::size_t uid, std::vector<std::int16_t> const & data)
{
	std::ostringstream oss;
	oss << std::hex << uid;

	std::ofstream file(data_path() / oss.str(), std::ios::binary);
	if (!file)
		return;

	file.write(reinterpret_cast<char const *>(data.data()), data.size() * sizeof(data[0]));
}

struct node
{
	math::vector<float, 3> v[3];
	math::interval<float> height_range;

	virtual bool draw(int level) = 0;
	virtual node * child(int id) = 0;
	virtual ~node() {}
};

struct node_controller
{
	node_controller();
	~node_controller();

	node * root(int f);

	std::size_t node_count() const { return node_count_; }

	std::size_t loader_queue_size() const { return loader_.task_count(); }

private:
	struct node_impl
		: node
	{
		node_controller * controller;
		gfx::array array;
		gfx::buffer height_buffer;
		std::unique_ptr<node> children[node_child_count];
		std::size_t uid;

		bool data_ready = false;
		async::future<std::vector<std::int16_t>> height_data_future;

		bool draw(int level) override;
		node * child(int id) override;

		void load_heights();
	};

	cg::icosahedron<float> icosahedron_;

	gfx::buffer index_buffer_;
	std::size_t index_counts_[node_size_log2 + 2];
	std::unique_ptr<node_impl> roots_[20];

	height_provider height_provider_;
	node_cache node_cache_;

	async::threadpool loader_{"load", 1};
	std::atomic<bool> cancel_ = false;

	std::size_t node_count_ = 0;

	std::unique_ptr<node_impl> make_node();
};

node_controller::node_controller()
	: icosahedron_{math::point<float, 3>::zero(), 1.f}
{
	std::vector<std::uint16_t> indices;
	index_counts_[0] = 0;
	for (std::size_t N = 0; N <= node_size_log2; ++N)
	{
		std::size_t step = 256 >> N;

		auto idx = [step](std::size_t i, std::size_t j) -> std::uint16_t
		{
			i *= step;
			j *= step;
			return (i * (i + 1)) / 2 + j;
		};

		for (std::size_t i = 0; i < (1 << N); ++i)
		{
			for (std::size_t j = 0; j <= i; ++j)
			{
				indices.push_back(idx(i + 1, j));
				indices.push_back(idx(i, j));
			}
			indices.push_back(idx(i + 1, i + 1));
			indices.push_back(0xffffu);
		}

		index_counts_[N + 1] = indices.size();
	}
	index_buffer_.load(indices, gl::STATIC_DRAW);
}

node_controller::~node_controller()
{
	cancel_ = true;
}

node * node_controller::root(int f)
{
	if (!roots_[f])
	{
		auto n = make_node();
		n->uid = (1 << 5) | f;

		auto face = cg::faces(icosahedron_)[f];
		n->v[0] = icosahedron_.vertices[face[0]] - math::point<float, 3>::zero();
		n->v[1] = icosahedron_.vertices[face[1]] - math::point<float, 3>::zero();
		n->v[2] = icosahedron_.vertices[face[2]] - math::point<float, 3>::zero();

		roots_[f] = std::move(n);
	}

	return roots_[f].get();
}

std::unique_ptr<node_controller::node_impl> node_controller::make_node()
{
	auto n = std::make_unique<node_controller::node_impl>();

	n->controller = this;
	n->array.bind();
	n->height_buffer.bind();
	gl::EnableVertexAttribArray(0);
	gl::VertexAttribPointer(0, 1, gl::SHORT, gl::FALSE, 0, nullptr);
	gl::BindBuffer(gl::ELEMENT_ARRAY_BUFFER, index_buffer_.id());

	++node_count_;

	return n;
}

bool node_controller::node_impl::draw(int level)
{
	if (!data_ready)
	{
		load_heights();

		if (!height_data_future.ready()) return false;

		auto height_data = height_data_future.get();

		for (auto h : height_data)
			height_range |= exaggeration * static_cast<float>(h);

		height_buffer.load(height_data, gl::STATIC_DRAW);
		height_data.clear();
		data_ready = true;
	}

	array.bind();
	std::size_t offset = controller->index_counts_[level];
	std::size_t count = controller->index_counts_[level + 1] - offset;
	gl::DrawElements(gl::TRIANGLE_STRIP, count, gl::UNSIGNED_SHORT, reinterpret_cast<void const *>(offset * sizeof(std::uint16_t)));

	return true;
}

node * node_controller::node_impl::child(int id)
{
	if (!children[id])
	{
		auto n = controller->make_node();
		n->uid = (uid << (2 * node_child_depth)) | id;

		int i0, j0, i1, j1, i2, j2;

		static constexpr int type_1_count = (node_child_size * (node_child_size + 1)) / 2;

		if (id < type_1_count)
		{
			int i = int(std::floor(0.5f * (sqrt(1.f + 8.f * id) - 1.f)));
			int j = id - (i * (i + 1)) / 2;

			i0 = i;
			j0 = j;
			i1 = i + 1;
			j1 = j + 1;
			i2 = i + 1;
			j2 = j;
		}
		else
		{
			int i = int(std::floor(0.5f * (sqrt(1.f + 8.f * (id - type_1_count)) - 1.f)));
			int j = id - type_1_count - (i * (i + 1)) / 2;

			i0 = i + 1;
			j0 = j;
			i1 = i + 1;
			j1 = j + 1;
			i2 = i + 2;
			j2 = j + 1;
		}

		auto at = [this](int i, int j)
		{
			float t0 = 1.f - (1.f * i) / (1.f * node_child_size);
			float t1 = (1.f * j) / (1.f * node_child_size);
			float t2 = 1.f - t0 - t1;

			return math::normalized(v[0] * t0 + v[1] * t1 + v[2] * t2);
		};

		n->v[0] = at(i0, j0);
		n->v[1] = at(i1, j1);
		n->v[2] = at(i2, j2);

		children[id] = std::move(n);
	}

	return children[id].get();
}

void node_controller::node_impl::load_heights()
{
	if (height_data_future)
		return;

	height_data_future = controller->loader_.dispatch(async::auto_cancel, [this]() -> std::vector<std::int16_t> {
		if (controller->cancel_) return {};

		auto cached = controller->node_cache_.load(uid);
		if (cached)
		{
			return std::move(*cached);
		}

		std::vector<std::int16_t> height_data(((node_size + 2) * (node_size + 1)) / 2, 0);

		auto * out = height_data.data();

		auto at = [this](int i, int j)
		{
			float t0 = 1.f - (1.f * i) / (1.f * node_size);
			float t1 = (1.f * j) / (1.f * node_size);
			float t2 = 1.f - t0 - t1;

			return math::normalized(v[0] * t0 + v[1] * t1 + v[2] * t2);
		};

		for (int i = 0; i <= node_size; ++i)
		{
			for (int j = 0; j <= i; ++j)
			{
				if (controller->cancel_) return {};

				*out++ = static_cast<std::int16_t>(controller->height_provider_.height_at(at(i, j)));
			}
		}

		controller->node_cache_.store(uid, height_data);

		return height_data;
	});
}

static char const tile_vs[] =
R"(#version 330

uniform mat4 u_transform;
uniform float u_exaggeration;

uniform int u_N;
uniform vec3 u_p0;
uniform vec3 u_p1;
uniform vec3 u_p2;

uniform sampler1D u_colormap;
uniform sampler1D u_colormap_neg;

uniform float u_far;

layout (location = 0) in float in_height;

out vec3 color;
out vec3 pos;

void main()
{
	int i = int(floor(0.5 * (sqrt(1.0 + 8.0 * gl_VertexID) - 1.0)));
	int j = gl_VertexID - (i * (i + 1)) / 2;

	float t0 = 1.0 - float(i) / float(u_N);
	float t1 = float(j) / float(u_N);
	float t2 = 1.0 - t0 - t1;

	vec3 p = normalize(u_p0 * t0 + u_p1 * t1 + u_p2 * t2) * (1.0 + u_exaggeration * in_height / 6400000.0);
	pos = p;
	gl_Position = u_transform * vec4(p, 1.0);
	float C = 1.0;
	gl_Position.z = (2.0 * log(C * gl_Position.w + 1.0) / log(C * u_far + 1.0) - 1.0) * gl_Position.w;
	color = (in_height > 0.0) ? texture(u_colormap, in_height / 8000.0).rgb : texture(u_colormap_neg, -in_height / 10000.0).rgb;
})";

static char const tile_close_gs[] =
R"(#version 330

layout (triangles) in;
layout (triangle_strip, max_vertices = 3) out;

in vec3 color[];
in vec3 pos[];

out vec3 g_color;
out vec3 g_normal;

void main()
{
	g_normal = normalize(cross(pos[1] - pos[0], pos[2] - pos[0]));

	for (int i = 0; i < 3; ++i)
	{
		g_color = color[i];
		gl_Position = gl_in[i].gl_Position;
		EmitVertex();
	}
	EndPrimitive();
})";

static char const tile_close_fs[] =
R"(#version 330

uniform vec3 u_light;

in vec3 g_color;
in vec3 g_normal;
out vec4 out_color;

void main()
{
	float l = max(0.2, dot(normalize(g_normal), u_light));
	out_color = vec4(pow(g_color * l, vec3(1.0 / 2.2)), 1.0);
})";

static char const tile_far_fs[] =
R"(#version 330

uniform vec3 u_light;

in vec3 color;
in vec3 pos;
out vec4 out_color;

void main()
{
	vec3 normal = cross(dFdx(pos), dFdy(pos));
	float l = max(0.2, dot(normalize(normal), u_light));
	out_color = vec4(pow(color * l, vec3(1.0 / 2.2)), 1.0);
})";

struct srtm_app
	: app::application_base
{
	srtm_app(options const &, context const &);

	void on_event(app::resize_event const & event) override;

	void on_event(app::mouse_move_event const & event) override;

	void update() override;
	void present() override;

	math::free_camera camera;
	math::matrix<float, 4, 4> camera_transform;
	bool camera_forward = false;

	node_controller nodes;

	gfx::program tile_close_program{tile_vs, tile_close_gs, tile_close_fs};
	gfx::program tile_far_program{tile_vs, tile_far_fs};
	gfx::texture_1d color_map;
	gfx::texture_1d color_map_neg;

	util::clock<std::chrono::duration<float>> frame_clock;
	util::moving_average<float> frame_dt_average{32};

	gfx::mesh selected_mesh;
	gfx::simple_renderer simple_renderer;

	gfx::painter painter;
};

srtm_app::srtm_app(options const &, context const & context)
{
	context.vsync(true);
	context.show_cursor(false);

	camera.fov_y = math::rad(45.f);
	camera.near_clip = 0.0001f;
	camera.far_clip = 10.f;
	camera.pos = {0.f, -10.f, 0.f};
	camera.rotateYZ(math::rad(-90.f));

	camera_transform = camera.transform();

	selected_mesh.setup<math::point<float, 3>>();

	{
		util::ndarray<gfx::color_rgb, 1> colors({16});

		auto * c = colors.data();

		*c++ = {0, 63, 0};
		*c++ = {0, 127, 0};
		*c++ = {63, 127, 0};
		*c++ = {127, 127, 0};
		*c++ = {95, 95, 0};
		*c++ = {63, 63, 0};
		*c++ = {95, 63, 0};
		*c++ = {127, 95, 0};
		*c++ = {127, 63, 0};
		*c++ = {127, 31, 0};
		*c++ = {127, 0, 0};
		*c++ = {95, 0, 0};
		*c++ = {63, 0, 0};
		*c++ = {191, 191, 191};
		*c++ = {159, 159, 191};
		*c++ = {127, 127, 191};
		color_map.load(colors);
		color_map.clamp();
		color_map.linear_filter();
	}

	{
		util::ndarray<gfx::color_rgb, 1> colors({5});

		colors(0) = {0, 63, 127};
		colors(1) = {0, 0, 127};
		colors(2) = {0, 0, 127};
		colors(3) = {0, 0, 127};
		colors(4) = {0, 127, 127};
		color_map_neg.load(colors);
		color_map_neg.clamp();
		color_map_neg.linear_filter();
	}
}

void srtm_app::on_event(app::resize_event const & event)
{
	app::application_base::on_event(event);

	camera.set_fov(camera.fov_y, (1.f * event.size[0]) / event.size[1]);
	camera_transform = camera.transform();
}

void srtm_app::on_event(app::mouse_move_event const & event)
{
	auto const old_mouse = state().mouse;

	app::application_base::on_event(event);

	auto const delta = event.position - old_mouse;
	camera.rotateZX(0.01f * delta[0]);
	camera.rotateYZ(0.01f * delta[1]);
}

void srtm_app::update()
{
	float dt = frame_clock.restart().count();
	frame_dt_average.push(dt);

	if (state().key_down.contains(app::keycode::Q))
	{
		camera.rotateXY(- 4.f * dt);
	}

	if (state().key_down.contains(app::keycode::E))
	{
		camera.rotateXY(4.f * dt);
	}

	float const camera_speed = std::min(5.f, math::distance(camera.pos, math::point<float, 3>::zero()) - 1.f);
	auto const camera_forward = camera.direction();

	auto const camera_up = camera.axis_y();
	auto const camera_right = camera.axis_x();

	if (state().key_down.contains(app::keycode::W))
	{
		camera.pos += camera_speed * dt * camera_forward;
	}

	if (state().key_down.contains(app::keycode::S))
	{
		camera.pos -= camera_speed * dt * camera_forward;
	}

	if (state().key_down.contains(app::keycode::D))
	{
		camera.pos += camera_speed * dt * camera_right;
	}

	if (state().key_down.contains(app::keycode::A))
	{
		camera.pos -= camera_speed * dt * camera_right;
	}

	if (state().key_down.contains(app::keycode::LSHIFT))
	{
		camera.pos += camera_speed * dt * camera_up;
	}

	if (state().key_down.contains(app::keycode::LCTRL))
	{
		camera.pos -= camera_speed * dt * camera_up;
	}

	camera_transform += (camera.transform() - camera_transform) * std::min(1.f, 10.f * dt);
}

namespace std
{

template <typename T>
std::ostream & operator << (std::ostream & os, std::vector<T> const & v)
{
	os << "[";
	bool first = true;
	for (auto const & x : v)
	{
		if (first)
			first = false;
		else
			os << ", ";
		os << x;
	}
	return os << "]";
}

}

void srtm_app::present()
{
	cg::icosahedron<float> icosahedron{math::point<float, 3>::zero(), 1.f};

	auto const & icosa_vertices = cg::vertices(icosahedron);
	auto const & icosa_faces = cg::faces(icosahedron);
	auto const icosa_side = math::distance(icosa_vertices[icosa_faces[0][0]], icosa_vertices[icosa_faces[0][1]]);

	std::vector<std::string> info;

//	gl::ClearColor(0.9f, 0.9f, 0.9f, 0.f);
	gl::ClearColor(0.0f, 0.0f, 0.0f, 0.f);
	gl::Clear(gl::COLOR_BUFFER_BIT | gl::DEPTH_BUFFER_BIT);

	gl::LineWidth(2.f);
	gl::PolygonMode(gl::FRONT_AND_BACK, gl::FILL);
	gl::PointSize(5.f);
	gl::Enable(gl::CULL_FACE);
	gl::Enable(gl::DEPTH_TEST);
	gl::DepthFunc(gl::LEQUAL);

	gl::Enable(gl::PRIMITIVE_RESTART);
	gl::PrimitiveRestartIndex(0xffffu);

	{
		auto d = math::distance(camera.pos, math::point<float, 3>::zero());
		camera.far_clip = std::sqrt(d * d + 1.f);
		camera.near_clip = (d > 2.f) ? d - 2.f : 0.0001f;
	}

//	auto const camera_transform = camera.transform();
	auto const camera_pos = camera.position();
	auto const camera_direction = camera.direction();

	info.push_back(util::to_string("Camera height: ", (math::distance(camera_pos, math::point<float, 3>::zero()) - 1.f) * 6400000.f, " m"));

	auto const frustum = cg::frustum(camera_transform);
	(void)frustum;

	auto light = math::normalized(math::vector{camera_pos[0]-camera_pos[1], camera_pos[1]+camera_pos[0], 0.f});

	tile_close_program.bind();
	tile_close_program["u_transform"] = camera_transform;
	tile_close_program["u_exaggeration"] = exaggeration;
	tile_close_program["u_N"] = static_cast<int>(node_size);
	tile_close_program["u_light"] = light;
	tile_close_program["u_colormap"] = 0;
	tile_close_program["u_colormap_neg"] = 1;
	tile_close_program["u_far"] = camera.far_clip;
	tile_far_program.bind();
	tile_far_program["u_transform"] = camera_transform;
	tile_far_program["u_exaggeration"] = exaggeration;
	tile_far_program["u_N"] = static_cast<int>(node_size);
	tile_far_program["u_light"] = light;
	tile_far_program["u_colormap"] = 0;
	tile_far_program["u_colormap_neg"] = 1;
	tile_far_program["u_far"] = camera.far_clip;
	gl::ActiveTexture(gl::TEXTURE0);
	color_map.bind();
	gl::ActiveTexture(gl::TEXTURE1);
	color_map_neg.bind();
	gl::ActiveTexture(gl::TEXTURE0);

	info.push_back(util::to_string("Camera pos: ", camera_pos));

	std::vector<math::point<float, 3>> selected_vertices;

	std::size_t rendered_tiles = 0;
	std::vector<std::size_t> id;
	auto visit = util::recursive([&](auto & self, node * n, int level = 0) -> bool
	{
		auto const & v = n->v;
		auto const o = math::point<float, 3>::zero();

		{
			bool culled = true;
			for (std::size_t i = 0; i < 3; ++i)
			{
				if (math::dot(v[i], math::normalized(camera_pos - o)) >= 0.f)
				{
					culled = false;
					break;
				}
			}
			if (culled)
				return true;
			(void)culled;
		}

		bool const flat = n->height_range.max == n->height_range.min;

		auto const m3 = (v[0] + v[1] + v[2]) / 3.f;
		auto const m = math::normalized(m3);
		auto const m0 = m * (n->height_range.empty() ? 0.f : n->height_range.min) / 6400000.f;
		auto const m1 = m * (n->height_range.empty() ? 1.f : flat ? n->height_range.min + 1.f : n->height_range.max) / 6400000.f + (m - m3);

		math::triangle<math::point<float, 3>> t{o + v[0] + m0, o + v[1] + m0, o + v[2] + m0};
		cg::triangular_prism<float> body{t, m1 - m0};

//		if (cg::separation(body, frustum).second > 0.f)
//			return true;

		bool const selected = math::intersect(math::ray{camera_pos, camera_direction}, t);

		float on_screen_unit;

		{
			auto edge = [](auto const & v0, auto const & v1, auto const & u) -> std::optional<float>
			{
				auto const n = math::normalized(math::cross(v0, v1));
				auto v = math::normalized(u - n * dot(u, n));
				if (math::dot(math::cross(v0, v), math::cross(v, v1)) >= 0.f)
					return math::length(v - u);
				return std::nullopt;
			};

			float distance = std::numeric_limits<float>::infinity();
			auto c = camera_pos - o;
			if (math::det(v[0], v[1], c) >= 0.f && math::det(v[1], v[2], c) >= 0.f && math::det(v[2], v[0], c) >= 0.f)
				distance = std::min(distance, math::length(c) - 1.f);
			else
			{
				if (auto d = edge(v[0], v[1], c); d)
					distance = std::min(distance, *d);
				if (auto d = edge(v[1], v[2], c); d)
					distance = std::min(distance, *d);
				if (auto d = edge(v[2], v[0], c); d)
					distance = std::min(distance, *d);
			}
			distance = std::min(distance, math::length(c - v[0]));
			distance = std::min(distance, math::length(c - v[1]));
			distance = std::min(distance, math::length(c - v[2]));

			on_screen_unit = state().size[0] / distance / std::tan(camera.fov_x / 2.f);
		}

		assert(on_screen_unit > 0.f);

		float const max_triangle_size = 5.f; // pixels

		float const side_length = icosa_side / (1 << (level * node_child_depth));

		int tile_n = std::ceil(std::log2(on_screen_unit * side_length / max_triangle_size));

		bool should_draw_children = !flat && level < max_child_level && tile_n > node_size_log2;
		bool all_children_drawn = true;

		if (selected && !should_draw_children)
		{
			auto const & vs = cg::vertices(body);
			auto const & es = cg::edges(body);

			for (auto const & e : es)
			{
				selected_vertices.push_back(vs[e[0]]);
				selected_vertices.push_back(vs[e[1]]);
			}
		}

		if (should_draw_children)
		{
			for (int id = 0; id < node_child_count; ++id)
				all_children_drawn &= self(n->child(id), level + 1);
		}

		if (!should_draw_children || !all_children_drawn)
		{
			tile_n = math::clamp(tile_n, {0, node_size_log2});

			++rendered_tiles;

			static gfx::color_4f colors[4]
			{
				gfx::black,
				gfx::dark(gfx::red).as_color_4f(),
				gfx::dark(gfx::green).as_color_4f(),
				gfx::blue
			};

			auto * program = (level == max_child_level) ? &tile_close_program : &tile_far_program;

			program->bind();
			(*program)["u_p0"] = v[0];
			(*program)["u_p1"] = v[1];
			(*program)["u_p2"] = v[2];
			(*program)["u_color"] = colors[tile_n % 4];

			return n->draw(tile_n);
		}

		return true;
	});

	gfx::check_error();

	for (int f = 0; f < 20; ++f)
	{
		visit(nodes.root(f));
	}

//	selected_mesh.load(selected_vertices, gl::LINES, gl::STREAM_DRAW);

//	simple_renderer.push(gfx::simple_renderer::render_state{&selected_mesh, gfx::white.as_color_rgba()});
//	simple_renderer.render(gfx::simple_renderer::render_options{camera_transform});

	int const width = state().size[0];
	int const height = state().size[1];

	info.push_back(util::to_string("Tiles: ", rendered_tiles));
	{
		float s = 10.f;
		painter.line({width / 2.f - s, height / 2.f}, {width / 2.f + s, height / 2.f}, 3.f, gfx::cyan, false);
		painter.line({width / 2.f, height / 2.f - s}, {width / 2.f, height / 2.f + s}, 3.f, gfx::cyan, false);
	}
	info.push_back(util::to_string("Nodes: ", nodes.node_count()));
	info.push_back(util::to_string("Tasks: ", nodes.loader_queue_size()));
	info.push_back(util::to_string("Selected: ", selected_mesh.index_count()));

	{
		info.insert(info.begin(), util::to_string("FPS: ", 1.f / frame_dt_average.average()));

		gfx::painter::text_options opts;
		opts.x = gfx::painter::x_align::left;
		opts.y = gfx::painter::y_align::top;
		opts.f = gfx::painter::font::font_9x12;
		opts.c = gfx::gray;
		opts.scale = {2.f, 2.f};

		for (int l = 0; l < info.size(); ++l)
		{
			painter.text({10.f + 1.f, 10.f + 24.f * l + 1.f}, info[l], opts);
		}

		opts.c = gfx::white;

		for (int l = 0; l < info.size(); ++l)
		{
			painter.text({10.f, 10.f + 24.f * l}, info[l], opts);
		}
	}

	gl::PolygonMode(gl::FRONT_AND_BACK, gl::FILL);
	gl::Enable(gl::BLEND);
	gl::BlendFunc(gl::SRC_ALPHA, gl::ONE_MINUS_SRC_ALPHA);
	gl::Disable(gl::DEPTH_TEST);
	painter.render(math::window_camera{width, height}.transform());
}

namespace psemek::app
{

	std::unique_ptr<application::factory> make_application_factory()
	{
		return default_application_factory<srtm_app>({.name = "SRTM example", .multisampling = 4});
	}

}
