path: root/kon/kon3d.c

/* SPDX-License-Identifier: MIT */
/*
 * kon3d.c
 *
 * Copyright (c) 2026 KonAki
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include "kon3d.h"

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*** private ***/

static void kon_quad_(kon_framebuffer_t *fb, kon_mat4_t vp, const kon_material_t *material, const kon_light_t *light,
		kon_vec3_t a, kon_vec3_t b, kon_vec3_t c, kon_vec3_t d, kon_vec3_t normal, kon_vec2_t uvA, kon_vec2_t uvC)
{
	kon_vertex_t va = { a, normal, uvA }, vb = { b, normal, KON_VEC2(uvC.x, uvA.y) };
	kon_vertex_t vc = { c, normal, uvC }, vd = { d, normal, KON_VEC2(uvA.x, uvC.y) };

	kon_drawTriangle3D(fb, vp, va, vb, vc, material, light, KON_RENDER_DEFAULT);
	kon_drawTriangle3D(fb, vp, va, vc, vd, material, light, KON_RENDER_DEFAULT);
}

/* a wall face seen from its open side, left and right are the bottom corners as the viewer sees them */
static void kon_wall_(kon_framebuffer_t *fb, kon_mat4_t vp, const kon_level3d_t *level, const kon_light_t *light,
		kon_vec3_t left, kon_vec3_t right, kon_vec3_t normal)
{
	float h = level->wallHeight;
	kon_vec3_t topRight = KON_VEC3(right.x, h, right.z), topLeft = KON_VEC3(left.x, h, left.z);

	kon_quad_(fb, vp, level->wall, light, left, right, topRight, topLeft, normal, KON_VEC2(0, h), KON_VEC2(1, 0));
}

static int kon_open_(const kon_level3d_t *level, int column, int row)
{
	uint16_t id = kon_tilemapAt(level->map, column, row);

	return id >= level->solidCount || !level->solid[id];
}

/*** body ***/

void kon_fpInit(kon_fp_t *fp, const kon_tilemap_t *map, int column, int row)
{
	float size = 12.0f;

	fp->eyeHeight = 0.6f;
	fp->yaw = 0.0f;
	fp->pitch = 0.0f;
	fp->sensitivity = 0.0015f;
	fp->speed = 2.5f;
	fp->turnSpeed = 2.0f;
	fp->fov = KON_DEG2RAD(60);
	fp->farZ = 40.0f;
	fp->forward = fp->strafe = fp->turn = 0;
	fp->feet = 0.0f;
	fp->fall = 0.0f;
	fp->maxSlope = 1.0f;
	fp->gravity = 20.0f;
	fp->body = KON_BOX2(((float)column + 0.5f) * (float)map->tileWidth - size * 0.5f, ((float)row + 0.5f) * (float)map->tileHeight - size * 0.5f, size, size);
}

int kon_fpEvent(kon_fp_t *fp, kon_program_t *program, const kon_event_t *ev)
{
	int down;

	if (ev->type == KON_EVENT_MOUSE_MOVE && kon_isMouseCaptured(program->window)) {
		fp->yaw += (float)ev->mouseDX * fp->sensitivity;
		fp->pitch -= (float)ev->mouseDY * fp->sensitivity;
		if (fp->pitch > 1.2f) fp->pitch = 1.2f;
		if (fp->pitch < -1.2f) fp->pitch = -1.2f;
		return 1;
	}
	if (ev->type == KON_EVENT_MOUSE_DOWN && !kon_isMouseCaptured(program->window)) {
		kon_setMouseCapture(program->window, true);
		return 1;
	}
	if (ev->type == KON_EVENT_KEY_DOWN && ev->key == KON_KEY_TAB) {
		kon_setMouseCapture(program->window, !kon_isMouseCaptured(program->window));
		return 1;
	}
	if (ev->type != KON_EVENT_KEY_DOWN && ev->type != KON_EVENT_KEY_UP) return 0;
	down = ev->type == KON_EVENT_KEY_DOWN;

	switch (ev->key) {
	case KON_KEY_W: case KON_KEY_UP: fp->forward = down ? 1 : (fp->forward > 0 ? 0 : fp->forward); break;
	case KON_KEY_S: case KON_KEY_DOWN: fp->forward = down ? -1 : (fp->forward < 0 ? 0 : fp->forward); break;
	case KON_KEY_D: fp->strafe = down ? 1 : (fp->strafe > 0 ? 0 : fp->strafe); break;
	case KON_KEY_A: fp->strafe = down ? -1 : (fp->strafe < 0 ? 0 : fp->strafe); break;
	case KON_KEY_RIGHT: fp->turn = down ? 1 : (fp->turn > 0 ? 0 : fp->turn); break;
	case KON_KEY_LEFT: fp->turn = down ? -1 : (fp->turn < 0 ? 0 : fp->turn); break;
	default: return 0;
	}
	return 1;
}

static float kon_groundAt_(const kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain)
{
	return kon_terrainHeight(terrain, (fp->body.x + fp->body.w * 0.5f) / (float)map->tileWidth, (fp->body.y + fp->body.h * 0.5f) / (float)map->tileHeight);
}

/* going up more than maxSlope allows, from the ground height before the move to the one at the body now */
static int kon_tooSteep_(const kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain, float before, float oldX, float oldY)
{
	float dx = (fp->body.x - oldX) / (float)map->tileWidth, dy = (fp->body.y - oldY) / (float)map->tileHeight;
	float run = sqrtf(dx * dx + dy * dy);

	return run > 0.0f && kon_groundAt_(fp, map, terrain) - before > fp->maxSlope * run;
}

void kon_fpPlace(kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain)
{
	fp->feet = terrain ? kon_groundAt_(fp, map, terrain) : 0.0f;
	fp->fall = 0.0f;
}

void kon_fpUpdate(kon_fp_t *fp, kon_program_t *program, const kon_tilemap_t *map, const uint8_t *solid, int solidCount, const kon_terrain_t *terrain, double dt)
{
	float step = fp->speed * (float)dt * (float)map->tileWidth;
	float fx = sinf(fp->yaw), fz = -cosf(fp->yaw);
	float dx = (fx * (float)fp->forward - fz * (float)fp->strafe) * step;
	float dz = (fz * (float)fp->forward + fx * (float)fp->strafe) * step;
	float oldX = fp->body.x, oldY = fp->body.y, ground = 0.0f, before = 0.0f;

	if (kon_debugConsoleOpen(program->debug) && kon_isMouseCaptured(program->window)) kon_setMouseCapture(program->window, false);

	fp->yaw += (float)fp->turn * fp->turnSpeed * (float)dt;
	if (terrain) before = kon_groundAt_(fp, map, terrain);
	kon_tilemapMove(map, &fp->body, dx, dz, solid, solidCount);

	if (!terrain) return;

	/* too steep to climb, try sliding along it on one axis before giving up */
	if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) {
		float newX = fp->body.x, newY = fp->body.y;

		fp->body.x = newX;
		fp->body.y = oldY;
		if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) {
			fp->body.x = oldX;
			fp->body.y = newY;
			if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) fp->body.y = oldY;
		}
	}

	ground = kon_groundAt_(fp, map, terrain);
	if (fp->feet < ground) {
		float t = (float)dt * 18.0f;

		fp->feet += (ground - fp->feet) * (t > 1.0f ? 1.0f : t);
		fp->fall = 0.0f;
	} else if (fp->feet > ground) {
		fp->fall += fp->gravity * (float)dt;
		fp->feet -= fp->fall * (float)dt;
		if (fp->feet <= ground) {
			fp->feet = ground;
			fp->fall = 0.0f;
		}
	}
}

kon_vec3_t kon_fpEye(const kon_fp_t *fp, const kon_tilemap_t *map)
{
	return KON_VEC3((fp->body.x + fp->body.w * 0.5f) / (float)map->tileWidth, fp->feet + fp->eyeHeight, (fp->body.y + fp->body.h * 0.5f) / (float)map->tileHeight);
}

kon_camera_t kon_fpCamera(const kon_fp_t *fp, const kon_tilemap_t *map)
{
	kon_camera_t camera = kon_cameraDefault();
	kon_vec3_t eye = kon_fpEye(fp, map);

	camera.position = eye;
	camera.target = KON_VEC3(eye.x + sinf(fp->yaw) * cosf(fp->pitch), eye.y + sinf(fp->pitch), eye.z - cosf(fp->yaw) * cosf(fp->pitch));
	camera.fov = fp->fov;
	camera.nearZ = 0.05f;
	camera.farZ = fp->farZ;
	return camera;
}

#if defined(KON_DEVELOPER) && defined(KON_MODULE_DEBUG)

static void kon_cmdWhere_(kon_debug_t *debug, void *user, int argc, char **argv)
{
	kon_fp_t *fp = user;

	(void)argc; (void)argv;
	kon_debugLog(debug, "x %.1f  y %.1f  yaw %.2f  pitch %.2f", (double)fp->body.x, (double)fp->body.y, (double)fp->yaw, (double)fp->pitch);
}

void kon_fpDebug(kon_fp_t *fp, kon_debug_t *debug)
{
	kon_debugVar(debug, "sens", KON_VAR_FLOAT, &fp->sensitivity);
	kon_debugVar(debug, "speed", KON_VAR_FLOAT, &fp->speed);
	kon_debugVar(debug, "eye", KON_VAR_FLOAT, &fp->eyeHeight);
	kon_debugCommand(debug, "where", "print where you stand in map pixels", kon_cmdWhere_, fp);
}

#else

void kon_fpDebug(kon_fp_t *fp, kon_debug_t *debug)
{
	(void)fp; (void)debug;
}

#endif

/*** drawing ***/

void kon_drawLevel(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_level3d_t *level, const kon_light_t *light)
{
	const kon_tilemap_t *map = level->map;
	kon_mat4_t vp = kon_cameraViewProjection(camera, fb->width, fb->height);
	float fx = camera->target.x - camera->position.x, fz = camera->target.z - camera->position.z;
	float flat = sqrtf(fx * fx + fz * fz), reach = camera->farZ + 1.0f;
	float w = (float)map->columns, d = (float)map->rows, h = level->wallHeight;
	int row, column;

	/* looking straight up or down there is no direction to cull against */
	if (flat > 0.001f) {
		fx /= flat;
		fz /= flat;
	}

	for (row = 0; row < map->rows; row++) {
		for (column = 0; column < map->columns; column++) {
			float x = (float)column, z = (float)row;
			float dx = x + 0.5f - camera->position.x, dz = z + 0.5f - camera->position.z;

			if (kon_open_(level, column, row)) continue;
			if (dx * dx + dz * dz > reach * reach) continue;
			if (flat > 0.001f && dx * fx + dz * fz < -2.0f) continue;

			if (kon_open_(level, column, row - 1)) kon_wall_(fb, vp, level, light, KON_VEC3(x + 1, 0, z), KON_VEC3(x, 0, z), KON_VEC3(0, 0, -1));
			if (kon_open_(level, column, row + 1)) kon_wall_(fb, vp, level, light, KON_VEC3(x, 0, z + 1), KON_VEC3(x + 1, 0, z + 1), KON_VEC3(0, 0, 1));
			if (kon_open_(level, column - 1, row)) kon_wall_(fb, vp, level, light, KON_VEC3(x, 0, z), KON_VEC3(x, 0, z + 1), KON_VEC3(-1, 0, 0));
			if (kon_open_(level, column + 1, row)) kon_wall_(fb, vp, level, light, KON_VEC3(x + 1, 0, z + 1), KON_VEC3(x + 1, 0, z), KON_VEC3(1, 0, 0));
		}
	}

	if (level->floor) kon_quad_(fb, vp, level->floor, light, KON_VEC3(0, 0, 0), KON_VEC3(0, 0, d), KON_VEC3(w, 0, d), KON_VEC3(w, 0, 0),
		KON_VEC3(0, 1, 0), KON_VEC2(0, 0), KON_VEC2(w, d));
	if (level->ceiling) kon_quad_(fb, vp, level->ceiling, light, KON_VEC3(0, h, 0), KON_VEC3(w, h, 0), KON_VEC3(w, h, d), KON_VEC3(0, h, d),
		KON_VEC3(0, -1, 0), KON_VEC2(0, 0), KON_VEC2(w, d));
}

/*** terrain ***/

static float *kon_corner_(const kon_terrain_t *terrain, int column, int row)
{
	return &terrain->heights[(size_t)row * (size_t)(terrain->columns + 1) + (size_t)column];
}

static void kon_chunkBounds_(kon_terrain_t *terrain, int cx, int cz)
{
	int x0 = cx * terrain->chunk, z0 = cz * terrain->chunk;
	int x1 = x0 + terrain->chunk, z1 = z0 + terrain->chunk;
	float low, high;
	int x, z;

	if (x1 > terrain->columns) x1 = terrain->columns;
	if (z1 > terrain->rows) z1 = terrain->rows;
	low = high = *kon_corner_(terrain, x0, z0);
	for (z = z0; z <= z1; z++) {
		for (x = x0; x <= x1; x++) {
			float h = *kon_corner_(terrain, x, z);

			if (h < low) low = h;
			if (h > high) high = h;
		}
	}
	terrain->chunkMin[cz * terrain->chunkColumns + cx] = low;
	terrain->chunkMax[cz * terrain->chunkColumns + cx] = high;
}

/* every chunk that has a corner inside the cell rectangle, a corner on a border belongs to both chunks */
static void kon_boundsAround_(kon_terrain_t *terrain, int x0, int z0, int x1, int z1)
{
	int cx0 = (x0 - 1) / terrain->chunk, cx1 = x1 / terrain->chunk;
	int cz0 = (z0 - 1) / terrain->chunk, cz1 = z1 / terrain->chunk;
	int cx, cz;

	if (x0 < 1) cx0 = 0;
	if (z0 < 1) cz0 = 0;
	if (cx1 >= terrain->chunkColumns) cx1 = terrain->chunkColumns - 1;
	if (cz1 >= terrain->chunkRows) cz1 = terrain->chunkRows - 1;
	for (cz = cz0; cz <= cz1; cz++) {
		for (cx = cx0; cx <= cx1; cx++) kon_chunkBounds_(terrain, cx, cz);
	}
}

kon_terrain_t *kon_terrainCreate(int columns, int rows)
{
	kon_terrain_t *terrain;
	size_t chunks;

	if (columns < 1 || rows < 1 || columns > 4096 || rows > 4096) return NULL;
	terrain = calloc(1, sizeof(kon_terrain_t));
	if (!terrain) return NULL;

	terrain->columns = columns;
	terrain->rows = rows;
	terrain->chunk = 16;
	terrain->chunkColumns = (columns + terrain->chunk - 1) / terrain->chunk;
	terrain->chunkRows = (rows + terrain->chunk - 1) / terrain->chunk;
	chunks = (size_t)terrain->chunkColumns * (size_t)terrain->chunkRows;

	terrain->heights = calloc((size_t)(columns + 1) * (size_t)(rows + 1), sizeof(float));
	terrain->chunkMin = calloc(chunks, sizeof(float));
	terrain->chunkMax = calloc(chunks, sizeof(float));
	if (!terrain->heights || !terrain->chunkMin || !terrain->chunkMax) {
		kon_terrainFree(terrain);
		return NULL;
	}
	return terrain;
}

void kon_terrainFree(kon_terrain_t *terrain)
{
	if (!terrain) return;
	free(terrain->heights);
	free(terrain->chunkMin);
	free(terrain->chunkMax);
	free(terrain);
}

float kon_terrainCorner(const kon_terrain_t *terrain, int column, int row)
{
	if (!terrain || column < 0 || row < 0 || column > terrain->columns || row > terrain->rows) return 0.0f;
	return *kon_corner_(terrain, column, row);
}

void kon_terrainSetCorner(kon_terrain_t *terrain, int column, int row, float height)
{
	if (!terrain || column < 0 || row < 0 || column > terrain->columns || row > terrain->rows) return;
	*kon_corner_(terrain, column, row) = height;
	kon_boundsAround_(terrain, column, row, column, row);
}

float kon_terrainHeight(const kon_terrain_t *terrain, float x, float z)
{
	float fx, fz, a, b, c, d;
	int column, row;

	if (!terrain) return 0.0f;
	if (x < 0.0f) x = 0.0f;
	if (z < 0.0f) z = 0.0f;
	if (x > (float)terrain->columns) x = (float)terrain->columns;
	if (z > (float)terrain->rows) z = (float)terrain->rows;

	column = (int)x;
	row = (int)z;
	if (column >= terrain->columns) column = terrain->columns - 1;
	if (row >= terrain->rows) row = terrain->rows - 1;
	fx = x - (float)column;
	fz = z - (float)row;

	a = *kon_corner_(terrain, column, row);
	b = *kon_corner_(terrain, column + 1, row);
	c = *kon_corner_(terrain, column + 1, row + 1);
	d = *kon_corner_(terrain, column, row + 1);

	/* the cell is split from its top left corner to its bottom right one */
	if (fz >= fx) return a + (d - a) * fz + (c - d) * fx;
	return a + (b - a) * fx + (c - b) * fz;
}

void kon_terrainRaise(kon_terrain_t *terrain, float x, float z, float radius, float amount)
{
	int x0, x1, z0, z1, column, row;

	if (!terrain || radius <= 0.0f) return;
	x0 = (int)floorf(x - radius);
	x1 = (int)ceilf(x + radius);
	z0 = (int)floorf(z - radius);
	z1 = (int)ceilf(z + radius);
	if (x0 < 0) x0 = 0;
	if (z0 < 0) z0 = 0;
	if (x1 > terrain->columns) x1 = terrain->columns;
	if (z1 > terrain->rows) z1 = terrain->rows;
	if (x0 > x1 || z0 > z1) return;

	for (row = z0; row <= z1; row++) {
		for (column = x0; column <= x1; column++) {
			float dx = (float)column - x, dz = (float)row - z;
			float f = 1.0f - sqrtf(dx * dx + dz * dz) / radius;

			if (f <= 0.0f) continue;
			*kon_corner_(terrain, column, row) += amount * f * f * (3.0f - 2.0f * f);
		}
	}
	kon_boundsAround_(terrain, x0, z0, x1, z1);
}

void kon_terrainFill(kon_terrain_t *terrain, float height)
{
	int i, count;

	if (!terrain) return;
	count = (terrain->columns + 1) * (terrain->rows + 1);
	for (i = 0; i < count; i++) terrain->heights[i] = height;
	kon_boundsAround_(terrain, 0, 0, terrain->columns, terrain->rows);
}

int kon_terrainRay(const kon_terrain_t *terrain, kon_vec3_t origin, kon_vec3_t direction, float maxDistance, kon_vec3_t *hit)
{
	float length = sqrtf(direction.x * direction.x + direction.y * direction.y + direction.z * direction.z);
	float step = 0.1f, t, from = 0.0f;
	int i;

	if (!terrain || length < 0.0001f) return 0;
	direction = KON_VEC3(direction.x / length, direction.y / length, direction.z / length);

	for (t = step; t <= maxDistance; t += step) {
		float x = origin.x + direction.x * t, y = origin.y + direction.y * t, z = origin.z + direction.z * t;

		if (x < 0.0f || z < 0.0f || x > (float)terrain->columns || z > (float)terrain->rows) {
			from = t;
			continue;
		}
		if (y > kon_terrainHeight(terrain, x, z)) {
			from = t;
			continue;
		}

		/* it went under between from and t, narrow it down */
		for (i = 0; i < 10; i++) {
			float mid = (from + t) * 0.5f;

			if (origin.y + direction.y * mid > kon_terrainHeight(terrain, origin.x + direction.x * mid, origin.z + direction.z * mid)) from = mid;
			else t = mid;
		}
		if (hit) {
			hit->x = origin.x + direction.x * t;
			hit->z = origin.z + direction.z * t;
			hit->y = kon_terrainHeight(terrain, hit->x, hit->z);
		}
		return 1;
	}
	return 0;
}

int kon_terrainSave(const kon_terrain_t *terrain, const char *path)
{
	FILE *file;
	int column, row;

	if (!terrain || !path) return 1;
	file = fopen(path, "w");
	if (!file) return 1;

	fprintf(file, "kter %d %d\n", terrain->columns, terrain->rows);
	for (row = 0; row <= terrain->rows; row++) {
		for (column = 0; column <= terrain->columns; column++) fprintf(file, column ? " %.4f" : "%.4f", (double)*kon_corner_(terrain, column, row));
		fputc('\n', file);
	}
	return fclose(file) != 0;
}

kon_terrain_t *kon_terrainLoad(const char *path)
{
	kon_terrain_t *terrain;
	FILE *file;
	char magic[8];
	int columns, rows, column, row;

	if (!path) return NULL;
	file = fopen(path, "r");
	if (!file) return NULL;

	if (fscanf(file, "%7s %d %d", magic, &columns, &rows) != 3 || strcmp(magic, "kter") != 0) {
		fclose(file);
		return NULL;
	}
	terrain = kon_terrainCreate(columns, rows);
	if (!terrain) {
		fclose(file);
		return NULL;
	}

	for (row = 0; row <= rows; row++) {
		for (column = 0; column <= columns; column++) {
			float h;

			if (fscanf(file, "%f", &h) != 1) {
				kon_terrainFree(terrain);
				fclose(file);
				return NULL;
			}
			*kon_corner_(terrain, column, row) = h;
		}
	}
	fclose(file);
	kon_boundsAround_(terrain, 0, 0, columns, rows);
	return terrain;
}

/* the six planes of the view, pointing inwards, from the rows of the view projection matrix */
static void kon_frustum_(kon_mat4_t vp, float planes[6][4])
{
	const float *m = vp.m;
	int i, j;

	for (j = 0; j < 4; j++) {
		planes[0][j] = m[j * 4 + 3] + m[j * 4 + 0];
		planes[1][j] = m[j * 4 + 3] - m[j * 4 + 0];
		planes[2][j] = m[j * 4 + 3] + m[j * 4 + 1];
		planes[3][j] = m[j * 4 + 3] - m[j * 4 + 1];
		planes[4][j] = m[j * 4 + 3] + m[j * 4 + 2];
		planes[5][j] = m[j * 4 + 3] - m[j * 4 + 2];
	}
	for (i = 0; i < 6; i++) {
		float length = sqrtf(planes[i][0] * planes[i][0] + planes[i][1] * planes[i][1] + planes[i][2] * planes[i][2]);

		for (j = 0; j < 4 && length > 0.0f; j++) planes[i][j] /= length;
	}
}

static int kon_sphereVisible_(float planes[6][4], float x, float y, float z, float radius)
{
	int i;

	for (i = 0; i < 6; i++) {
		if (planes[i][0] * x + planes[i][1] * y + planes[i][2] * z + planes[i][3] < -radius) return 0;
	}
	return 1;
}

void kon_drawTerrain(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_terrain_t *terrain, const kon_light_t *light)
{
	kon_mat4_t vp = kon_cameraViewProjection(camera, fb->width, fb->height);
	float planes[6][4];
	int cx, cz;

	if (!terrain || !terrain->material) return;
	kon_frustum_(vp, planes);

	for (cz = 0; cz < terrain->chunkRows; cz++) {
		for (cx = 0; cx < terrain->chunkColumns; cx++) {
			int x0 = cx * terrain->chunk, z0 = cz * terrain->chunk;
			int x1 = x0 + terrain->chunk, z1 = z0 + terrain->chunk;
			float low = terrain->chunkMin[cz * terrain->chunkColumns + cx], high = terrain->chunkMax[cz * terrain->chunkColumns + cx];
			float halfW, halfD, halfH, radius;
			int x, z;

			if (x1 > terrain->columns) x1 = terrain->columns;
			if (z1 > terrain->rows) z1 = terrain->rows;
			halfW = (float)(x1 - x0) * 0.5f;
			halfD = (float)(z1 - z0) * 0.5f;
			halfH = (high - low) * 0.5f;
			radius = sqrtf(halfW * halfW + halfD * halfD + halfH * halfH);
			if (!kon_sphereVisible_(planes, (float)x0 + halfW, low + halfH, (float)z0 + halfD, radius)) continue;

			for (z = z0; z < z1; z++) {
				for (x = x0; x < x1; x++) {
					float ha = *kon_corner_(terrain, x, z), hb = *kon_corner_(terrain, x + 1, z);
					float hc = *kon_corner_(terrain, x + 1, z + 1), hd = *kon_corner_(terrain, x, z + 1);
					kon_vec3_t a = KON_VEC3((float)x, ha, (float)z), b = KON_VEC3((float)x + 1, hb, (float)z);
					kon_vec3_t c = KON_VEC3((float)x + 1, hc, (float)z + 1), d = KON_VEC3((float)x, hd, (float)z + 1);
					kon_vec3_t upper = kon_vec3Normalize(KON_VEC3(hd - hc, 1.0f, ha - hd)), lower = kon_vec3Normalize(KON_VEC3(ha - hb, 1.0f, hb - hc));
					kon_vertex_t va = { a, upper, KON_VEC2((float)x, (float)z) }, vd = { d, upper, KON_VEC2((float)x, (float)z + 1) }, vc = { c, upper, KON_VEC2((float)x + 1, (float)z + 1) };
					kon_vertex_t wa = { a, lower, va.uv }, wc = { c, lower, vc.uv }, wb = { b, lower, KON_VEC2((float)x + 1, (float)z) };

					kon_drawTriangle3D(fb, vp, va, vd, vc, terrain->material, light, KON_RENDER_DEFAULT);
					kon_drawTriangle3D(fb, vp, wa, wc, wb, terrain->material, light, KON_RENDER_DEFAULT);
				}
			}
		}
	}
}

#if defined(KON_DEVELOPER) && defined(KON_MODULE_DEBUG)

static void kon_cmdTerrainSave_(kon_debug_t *debug, void *user, int argc, char **argv)
{
	if (argc < 2) {
		kon_debugLog(debug, "tsave file");
		return;
	}
	if (kon_terrainSave(user, argv[1]) == 0) kon_debugLog(debug, "saved %s", argv[1]);
	else kon_debugLog(debug, "could not save %s", argv[1]);
}

/* loads into the same struct so whatever points at the terrain keeps working */
static void kon_cmdTerrainLoad_(kon_debug_t *debug, void *user, int argc, char **argv)
{
	kon_terrain_t *terrain = user, *loaded;
	const kon_material_t *material = terrain->material;

	if (argc < 2) {
		kon_debugLog(debug, "tload file");
		return;
	}
	loaded = kon_terrainLoad(argv[1]);
	if (!loaded) {
		kon_debugLog(debug, "could not load %s", argv[1]);
		return;
	}

	free(terrain->heights);
	free(terrain->chunkMin);
	free(terrain->chunkMax);
	*terrain = *loaded;
	terrain->material = material;
	free(loaded);
	kon_debugLog(debug, "loaded %s", argv[1]);
}

static void kon_cmdTerrainFill_(kon_debug_t *debug, void *user, int argc, char **argv)
{
	kon_terrainFill(user, argc > 1 ? (float)atof(argv[1]) : 0.0f);
	kon_debugLog(debug, "filled");
}

void kon_terrainDebug(kon_terrain_t *terrain, kon_debug_t *debug)
{
	kon_debugCommand(debug, "tsave", "tsave file: write the terrain as text", kon_cmdTerrainSave_, terrain);
	kon_debugCommand(debug, "tload", "tload file: read a terrain back", kon_cmdTerrainLoad_, terrain);
	kon_debugCommand(debug, "tfill", "tfill height: flatten everything", kon_cmdTerrainFill_, terrain);
}

#else

void kon_terrainDebug(kon_terrain_t *terrain, kon_debug_t *debug)
{
	(void)terrain; (void)debug;
}

#endif

float kon_distanceFade(float distance, float falloff)
{
	return 1.0f / (1.0f + distance * falloff);
}