diff options
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | kon/konsector.c | 957 | ||||
| -rw-r--r-- | kon/konsector.h | 948 | ||||
| -rw-r--r-- | src/impl/konsector.c | 2 |
4 files changed, 952 insertions, 958 deletions
@@ -53,6 +53,9 @@ $(OBJDIR)/koninput.o: $(SRCDIR)/impl/koninput.c $(KONDIR)/koninput.h $(KONDIR)/k $(OBJDIR)/konfont.o: $(SRCDIR)/impl/konfont.c $(KONDIR)/konfont.h $(KONDIR)/konsofren.h $(EXTDIR)/stb_truetype.h $(COMPILE) $(SRCDIR)/impl/konfont.c -o $@ +$(OBJDIR)/konsector.o: $(SRCDIR)/impl/konsector.c $(KONDIR)/konsector.h $(KONDIR)/konsofren.h $(KONDIR)/konmath.h + $(COMPILE) $(SRCDIR)/impl/konsector.c -o $@ + $(OBJDIR)/kontoml.o: $(SRCDIR)/impl/kontoml.c $(KONDIR)/kontoml.h $(COMPILE) $(SRCDIR)/impl/kontoml.c -o $@ diff --git a/kon/konsector.c b/kon/konsector.c deleted file mode 100644 index c18425c..0000000 --- a/kon/konsector.c +++ /dev/null @@ -1,957 +0,0 @@ -/* SPDX-License-Identifier: MIT */ -/* - * konsector.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 "konsector.h" - -#include <math.h> -#include <stdarg.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#define WORD_LENGTH 128 -#define MAX_FILE (16 * 1024 * 1024) - -/*** private ***/ - -typedef struct kon_builder { - kon_sectorMap_t *map; - int vertexCap, sectorCap, lineCap, indexCap, edgeCap, quadCap, entityCap, textureCap; - int *sectorLine; /* the line each sector was written on, for the errors found afterwards */ - int line; - char *error; - size_t errorSize; -} kon_builder_t; - -static int kon_fail_(kon_builder_t *b, int line, const char *format, ...) -{ - va_list args; - int used = 0; - - if (b->error && b->errorSize > 0) { - if (line > 0) used = snprintf(b->error, b->errorSize, "line %d: ", line); - if (used < 0 || (size_t)used >= b->errorSize) used = 0; - va_start(args, format); - vsnprintf(b->error + used, b->errorSize - (size_t)used, format, args); - va_end(args); - } - return 0; -} - -static int kon_grow_(void **array, int *capacity, size_t size, int needed) -{ - void *bigger; - int cap = *capacity; - - if (needed <= cap) return 1; - if (cap < 8) cap = 8; - while (cap < needed) cap *= 2; - bigger = realloc(*array, (size_t)cap * size); - if (!bigger) return 0; - *array = bigger; - *capacity = cap; - return 1; -} - -/* the next word of a line, NULL at the end of it. the line ends at a newline or a #. the word is copied into out */ -static const char *kon_word_(const char *p, char *out, size_t size) -{ - size_t n = 0; - - while (*p == ' ' || *p == '\t' || *p == '\r') p++; - if (*p == '\0' || *p == '\n' || *p == '#') return NULL; - while (*p != '\0' && *p != ' ' && *p != '\t' && *p != '\r' && *p != '\n' && *p != '#') { - if (n + 1 < size) out[n++] = *p; - p++; - } - out[n] = '\0'; - return p; -} - -static int kon_number_(const char *word, double *value) -{ - char *end; - - if (*word == '\0') return 0; - *value = strtod(word, &end); - return *end == '\0' && isfinite(*value); -} - -static int kon_texture_(kon_builder_t *b, const char *name, int *index) -{ - kon_sectorMap_t *map = b->map; - int i; - - if (strcmp(name, "-") == 0) { - *index = -1; - return 1; - } - for (i = 0; i < map->textureCount; i++) { - if (strcmp(map->textures[i], name) == 0) { - *index = i; - return 1; - } - } - if (strlen(name) >= KON_NAME_LENGTH) return 0; - if (!kon_grow_((void **)&map->textures, &b->textureCap, sizeof(map->textures[0]), map->textureCount + 1)) return 0; - strcpy(map->textures[map->textureCount], name); - *index = map->textureCount++; - return 1; -} - -static double kon_area_(const kon_sectorMap_t *map, const kon_sector_t *sector) -{ - double sum = 0.0; - int i; - - for (i = 0; i < sector->count; i++) { - kon_vec2_t a = map->vertices[map->indices[sector->first + i]]; - kon_vec2_t b = map->vertices[map->indices[sector->first + (i + 1) % sector->count]]; - - sum += (double)a.x * (double)b.y - (double)b.x * (double)a.y; - } - return sum * 0.5; -} - -static double kon_side_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p) -{ - return ((double)b.x - (double)a.x) * ((double)p.y - (double)a.y) - ((double)b.y - (double)a.y) * ((double)p.x - (double)a.x); -} - -static int kon_onSegment_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p) -{ - return p.x >= (a.x < b.x ? a.x : b.x) && p.x <= (a.x > b.x ? a.x : b.x) && p.y >= (a.y < b.y ? a.y : b.y) && p.y <= (a.y > b.y ? a.y : b.y); -} - -/* touching counts as crossing */ -static int kon_crossing_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t d) -{ - double d1 = kon_side_(a, b, c), d2 = kon_side_(a, b, d), d3 = kon_side_(c, d, a), d4 = kon_side_(c, d, b); - - if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return 1; - if (d1 == 0 && kon_onSegment_(a, b, c)) return 1; - if (d2 == 0 && kon_onSegment_(a, b, d)) return 1; - if (d3 == 0 && kon_onSegment_(c, d, a)) return 1; - if (d4 == 0 && kon_onSegment_(c, d, b)) return 1; - return 0; -} - -static int kon_checkSector_(kon_builder_t *b, int s) -{ - kon_sectorMap_t *map = b->map; - kon_sector_t *sector = &map->sectors[s]; - int line = b->sectorLine[s], i, j; - double area; - - if (sector->count < 3) return kon_fail_(b, line, "sector %d needs at least 3 corners", s); - if (!(sector->ceiling > sector->floor)) return kon_fail_(b, line, "sector %d has a ceiling that is not above its floor", s); - - for (i = 0; i < sector->count; i++) { - kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); - - if (p.x == q.x && p.y == q.y) return kon_fail_(b, line, "sector %d has an edge with no length at corner %d", s, i); - } - - for (i = 0; i < sector->count; i++) { - for (j = i + 2; j < sector->count; j++) { - if (i == 0 && j == sector->count - 1) continue; - if (kon_crossing_(kon_sectorCorner(map, s, i), kon_sectorCorner(map, s, i + 1), kon_sectorCorner(map, s, j), kon_sectorCorner(map, s, j + 1))) { - return kon_fail_(b, line, "sector %d crosses itself, edges %d and %d touch", s, i, j); - } - } - } - - area = kon_area_(map, sector); - if (area == 0.0) return kon_fail_(b, line, "sector %d has no area", s); - - /* the shoelace sum is positive going clockwise on a plan with z pointing down, the format wants the other way round */ - if (area > 0.0) { - int *c = &map->indices[sector->first]; - kon_sectorEdge_t *e = &map->edges[sector->first]; - - for (i = 0, j = sector->count - 1; i < j; i++, j--) { - int t = c[i]; - - c[i] = c[j]; - c[j] = t; - } - /* the corners are reversed, so edge n now runs along old edge count - 2 - n backwards. the closing edge stays the closing edge */ - for (i = 0, j = sector->count - 2; i < j; i++, j--) { - kon_sectorEdge_t t = e[i]; - - e[i] = e[j]; - e[j] = t; - } - } - return 1; -} - -static int kon_samePoint_(kon_vec2_t a, kon_vec2_t b) -{ - return a.x == b.x && a.y == b.y; -} - -static int kon_linkPortals_(kon_builder_t *b) -{ - kon_sectorMap_t *map = b->map; - int s, t, i, j; - - for (s = 0; s < map->sectorCount; s++) { - for (i = 0; i < map->sectors[s].count; i++) { - kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); - - map->edges[map->sectors[s].first + i].portal = -1; - for (t = 0; t < map->sectorCount; t++) { - if (t == s) continue; - for (j = 0; j < map->sectors[t].count; j++) { - kon_vec2_t u = kon_sectorCorner(map, t, j), v = kon_sectorCorner(map, t, j + 1); - - if (kon_samePoint_(p, u) && kon_samePoint_(q, v)) { - return kon_fail_(b, b->sectorLine[s], "sectors %d and %d overlap along an edge, they run the same way", s, t); - } - if (kon_samePoint_(p, v) && kon_samePoint_(q, u)) map->edges[map->sectors[s].first + i].portal = t; - } - } - } - } - return 1; -} - -/*** loading ***/ - -static int kon_parseSector_(kon_builder_t *b, const char *p) -{ - kon_sectorMap_t *map = b->map; - kon_sector_t *sector; - char word[WORD_LENGTH], value[WORD_LENGTH]; - double floorHeight, ceilingHeight, number; - int line = b->line; - - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &floorHeight)) return kon_fail_(b, line, "sector needs a floor height"); - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &ceilingHeight)) return kon_fail_(b, line, "sector needs a ceiling height"); - - if (!kon_grow_((void **)&map->sectors, &b->sectorCap, sizeof(*map->sectors), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory"); - if (!kon_grow_((void **)&b->sectorLine, &b->lineCap, sizeof(int), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory"); - sector = &map->sectors[map->sectorCount]; - memset(sector, 0, sizeof(*sector)); - sector->floor = (float)floorHeight; - sector->ceiling = (float)ceilingHeight; - sector->light = 1.0f; - sector->floorTexture = sector->ceilingTexture = sector->wallTexture = -1; - sector->first = map->indexCount; - b->sectorLine[map->sectorCount] = line; - - /* key value pairs until the colon */ - for (;;) { - if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "sector needs a colon before its corners"); - if (strcmp(word, ":") == 0) break; - if (kon_number_(word, &number)) return kon_fail_(b, line, "the corners of a sector come after a colon"); - if (!(p = kon_word_(p, value, sizeof(value)))) return kon_fail_(b, line, "%s needs a value", word); - - if (strcmp(word, "light") == 0) { - if (!kon_number_(value, &number) || number < 0.0 || number > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1"); - sector->light = (float)number; - } else if (strcmp(word, "floor") == 0) { - if (!kon_texture_(b, value, §or->floorTexture)) return kon_fail_(b, line, "bad texture name %s", value); - } else if (strcmp(word, "ceiling") == 0) { - if (!kon_texture_(b, value, §or->ceilingTexture)) return kon_fail_(b, line, "bad texture name %s", value); - } else if (strcmp(word, "wall") == 0) { - if (!kon_texture_(b, value, §or->wallTexture)) return kon_fail_(b, line, "bad texture name %s", value); - } else { - return kon_fail_(b, line, "unknown sector setting %s", word); - } - } - - while ((p = kon_word_(p, word, sizeof(word)))) { - if (!kon_number_(word, &number) || number != floor(number) || number < 0.0 || number >= (double)map->vertexCount) { - return kon_fail_(b, line, "%s is not a vertex that was defined above", word); - } - if (!kon_grow_((void **)&map->indices, &b->indexCap, sizeof(int), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory"); - if (!kon_grow_((void **)&map->edges, &b->edgeCap, sizeof(*map->edges), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory"); - map->indices[map->indexCount] = (int)number; - map->edges[map->indexCount].portal = -1; - map->edges[map->indexCount].texture = -1; - map->indexCount++; - } - sector->count = map->indexCount - sector->first; - map->sectorCount++; - return 1; -} - -static int kon_parseQuad_(kon_builder_t *b, const char *p) -{ - kon_sectorMap_t *map = b->map; - kon_sectorQuad_t *quad; - char word[WORD_LENGTH]; - double v[12]; - int i, line = b->line; - - if (!kon_grow_((void **)&map->quads, &b->quadCap, sizeof(*map->quads), map->quadCount + 1)) return kon_fail_(b, 0, "out of memory"); - quad = &map->quads[map->quadCount]; - memset(quad, 0, sizeof(*quad)); - quad->light = 1.0f; - - if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "quad needs a texture"); - if (!kon_texture_(b, word, &quad->texture)) return kon_fail_(b, line, "bad texture name %s", word); - for (i = 0; i < 12; i++) { - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "quad needs 12 numbers, x y z for each of its 4 corners"); - } - for (i = 0; i < 4; i++) quad->corners[i] = KON_VEC3((float)v[i * 3], (float)v[i * 3 + 1], (float)v[i * 3 + 2]); - - while ((p = kon_word_(p, word, sizeof(word)))) { - if (strcmp(word, "double") == 0) { - quad->doubleSided = 1; - } else if (strcmp(word, "light") == 0) { - double light; - - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &light) || light < 0.0 || light > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1"); - quad->light = (float)light; - } else { - return kon_fail_(b, line, "unknown quad setting %s", word); - } - } - map->quadCount++; - return 1; -} - -static int kon_parseEntity_(kon_builder_t *b, const char *p) -{ - kon_sectorMap_t *map = b->map; - kon_entity_t *entity; - char word[WORD_LENGTH]; - double v[4]; - int i, line = b->line; - - if (!kon_grow_((void **)&map->entities, &b->entityCap, sizeof(*map->entities), map->entityCount + 1)) return kon_fail_(b, 0, "out of memory"); - entity = &map->entities[map->entityCount]; - memset(entity, 0, sizeof(*entity)); - entity->sector = -1; - - if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "entity needs a kind"); - if (strlen(word) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the kind %s is too long", word); - strcpy(entity->kind, word); - - for (i = 0; i < 4; i++) { - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "entity needs x y z and an angle"); - } - entity->position = KON_VEC3((float)v[0], (float)v[1], (float)v[2]); - entity->angle = (float)(v[3] * 3.14159265358979323846 / 180.0); - - while ((p = kon_word_(p, word, sizeof(word)))) { - char *equals = strchr(word, '='); - - if (!equals || equals == word) return kon_fail_(b, line, "%s should be written key=value", word); - *equals++ = '\0'; - - if (strcmp(word, "name") == 0 || strcmp(word, "target") == 0) { - char *dest = word[0] == 'n' ? entity->name : entity->target; - - if (strlen(equals) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the %s %s is too long", word, equals); - strcpy(dest, equals); - } else { - if (entity->propCount >= KON_ENTITY_PROPS) return kon_fail_(b, line, "an entity can have %d settings at most", KON_ENTITY_PROPS); - if (strlen(word) >= sizeof(entity->props[0].key) || strlen(equals) >= sizeof(entity->props[0].value)) return kon_fail_(b, line, "the setting %s is too long", word); - strcpy(entity->props[entity->propCount].key, word); - strcpy(entity->props[entity->propCount].value, equals); - entity->propCount++; - } - } - map->entityCount++; - return 1; -} - -static int kon_parseLine_(kon_builder_t *b, const char *p, int *started) -{ - kon_sectorMap_t *map = b->map; - char word[WORD_LENGTH]; - double number, x, z; - int line = b->line; - - if (!(p = kon_word_(p, word, sizeof(word)))) return 1; - - if (!*started) { - if (strcmp(word, "kmap") != 0) return kon_fail_(b, line, "a map starts with \"kmap 1\""); - if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &number) || number != 1.0) return kon_fail_(b, line, "this reads kmap version 1"); - *started = 1; - return 1; - } - - if (strcmp(word, "v") == 0) { - char a[WORD_LENGTH], c[WORD_LENGTH]; - - if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !kon_number_(a, &x) || !kon_number_(c, &z)) return kon_fail_(b, line, "v needs x and z"); - if (!kon_grow_((void **)&map->vertices, &b->vertexCap, sizeof(*map->vertices), map->vertexCount + 1)) return kon_fail_(b, 0, "out of memory"); - map->vertices[map->vertexCount++] = KON_VEC2((float)x, (float)z); - return 1; - } - if (strcmp(word, "sector") == 0) return kon_parseSector_(b, p); - if (strcmp(word, "quad") == 0) return kon_parseQuad_(b, p); - if (strcmp(word, "entity") == 0) return kon_parseEntity_(b, p); - if (strcmp(word, "edge") == 0) { - char a[WORD_LENGTH], c[WORD_LENGTH], name[WORD_LENGTH]; - double s, n; - - if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !(p = kon_word_(p, name, sizeof(name))) || !kon_number_(a, &s) || !kon_number_(c, &n)) { - return kon_fail_(b, line, "edge needs a sector, an edge number and a texture"); - } - if (s < 0 || s >= map->sectorCount || s != floor(s)) return kon_fail_(b, line, "there is no sector %s above", a); - if (n < 0 || n >= map->sectors[(int)s].count || n != floor(n)) return kon_fail_(b, line, "sector %s has no edge %s", a, c); - if (!kon_texture_(b, name, &map->edges[map->sectors[(int)s].first + (int)n].texture)) return kon_fail_(b, line, "bad texture name %s", name); - return 1; - } - return kon_fail_(b, line, "unknown word %s", word); -} - -kon_sectorMap_t *kon_sectorParse(const char *text, char *error, size_t errorSize) -{ - kon_builder_t b; - kon_sectorMap_t *map; - const char *p = text; - int started = 0, i; - - if (error && errorSize > 0) error[0] = '\0'; - if (!text) return NULL; - map = calloc(1, sizeof(*map)); - if (!map) return NULL; - memset(&b, 0, sizeof(b)); - b.map = map; - b.error = error; - b.errorSize = errorSize; - - while (*p != '\0') { - b.line++; - if (!kon_parseLine_(&b, p, &started)) goto bad; - while (*p != '\0' && *p != '\n') p++; - if (*p == '\n') p++; - } - - if (!started) { - kon_fail_(&b, 0, "the map is empty, it should start with \"kmap 1\""); - goto bad; - } - for (i = 0; i < map->sectorCount; i++) { - if (!kon_checkSector_(&b, i)) goto bad; - } - if (!kon_linkPortals_(&b)) goto bad; - for (i = 0; i < map->entityCount; i++) map->entities[i].sector = kon_sectorAt(map, map->entities[i].position.x, map->entities[i].position.z, -1); - - free(b.sectorLine); - return map; - -bad: - free(b.sectorLine); - kon_sectorFree(map); - return NULL; -} - -kon_sectorMap_t *kon_sectorLoad(const char *path, char *error, size_t errorSize) -{ - kon_sectorMap_t *map; - FILE *file; - char *text; - long size; - - if (error && errorSize > 0) error[0] = '\0'; - file = path ? fopen(path, "rb") : NULL; - if (!file) { - if (error && errorSize > 0) snprintf(error, errorSize, "could not open %s", path ? path : "(null)"); - return NULL; - } - fseek(file, 0, SEEK_END); - size = ftell(file); - fseek(file, 0, SEEK_SET); - if (size < 0 || size > MAX_FILE) { - fclose(file); - if (error && errorSize > 0) snprintf(error, errorSize, "%s is too big for a map", path); - return NULL; - } - text = malloc((size_t)size + 1); - if (!text) { - fclose(file); - return NULL; - } - if (fread(text, 1, (size_t)size, file) != (size_t)size) { - free(text); - fclose(file); - if (error && errorSize > 0) snprintf(error, errorSize, "could not read %s", path); - return NULL; - } - text[size] = '\0'; - fclose(file); - - map = kon_sectorParse(text, error, errorSize); - free(text); - return map; -} - -void kon_sectorFree(kon_sectorMap_t *map) -{ - if (!map) return; - free(map->vertices); - free(map->sectors); - free(map->indices); - free(map->edges); - free(map->quads); - free(map->entities); - free(map->textures); - free(map); -} - -int kon_sectorSave(const kon_sectorMap_t *map, const char *path) -{ - FILE *file; - int i, j; - - if (!map || !path) return 1; - file = fopen(path, "w"); - if (!file) return 1; - - fprintf(file, "kmap 1\n\n"); - for (i = 0; i < map->vertexCount; i++) fprintf(file, "v %.9g %.9g\n", (double)map->vertices[i].x, (double)map->vertices[i].y); - fputc('\n', file); - - for (i = 0; i < map->sectorCount; i++) { - const kon_sector_t *s = &map->sectors[i]; - - fprintf(file, "sector %.9g %.9g light %.9g floor %s ceiling %s wall %s :", (double)s->floor, (double)s->ceiling, (double)s->light, - s->floorTexture >= 0 ? map->textures[s->floorTexture] : "-", s->ceilingTexture >= 0 ? map->textures[s->ceilingTexture] : "-", - s->wallTexture >= 0 ? map->textures[s->wallTexture] : "-"); - for (j = 0; j < s->count; j++) fprintf(file, " %d", map->indices[s->first + j]); - fputc('\n', file); - } - for (i = 0; i < map->sectorCount; i++) { - for (j = 0; j < map->sectors[i].count; j++) { - int texture = map->edges[map->sectors[i].first + j].texture; - - if (texture >= 0) fprintf(file, "edge %d %d %s\n", i, j, map->textures[texture]); - } - } - fputc('\n', file); - - for (i = 0; i < map->quadCount; i++) { - const kon_sectorQuad_t *q = &map->quads[i]; - - fprintf(file, "quad %s", q->texture >= 0 ? map->textures[q->texture] : "-"); - for (j = 0; j < 4; j++) fprintf(file, " %.9g %.9g %.9g", (double)q->corners[j].x, (double)q->corners[j].y, (double)q->corners[j].z); - if (q->doubleSided) fprintf(file, " double"); - if (q->light != 1.0f) fprintf(file, " light %.9g", (double)q->light); - fputc('\n', file); - } - if (map->quadCount > 0) fputc('\n', file); - - for (i = 0; i < map->entityCount; i++) { - const kon_entity_t *e = &map->entities[i]; - - fprintf(file, "entity %s %.9g %.9g %.9g %.9g", e->kind, (double)e->position.x, (double)e->position.y, (double)e->position.z, (double)e->angle * 180.0 / 3.14159265358979323846); - if (e->name[0]) fprintf(file, " name=%s", e->name); - if (e->target[0]) fprintf(file, " target=%s", e->target); - for (j = 0; j < e->propCount; j++) fprintf(file, " %s=%s", e->props[j].key, e->props[j].value); - fputc('\n', file); - } - return fclose(file) != 0; -} - -/*** looking things up ***/ - -kon_vec2_t kon_sectorCorner(const kon_sectorMap_t *map, int sector, int n) -{ - const kon_sector_t *s = &map->sectors[sector]; - - return map->vertices[map->indices[s->first + n % s->count]]; -} - -int kon_sectorWallTexture(const kon_sectorMap_t *map, int sector, int edge) -{ - int texture = map->edges[map->sectors[sector].first + edge].texture; - - return texture >= 0 ? texture : map->sectors[sector].wallTexture; -} - -int kon_sectorTextureIndex(const kon_sectorMap_t *map, const char *name) -{ - int i; - - for (i = 0; i < map->textureCount; i++) { - if (strcmp(map->textures[i], name) == 0) return i; - } - return -1; -} - -static int kon_inside_(const kon_sectorMap_t *map, int sector, float x, float z) -{ - int i, count = map->sectors[sector].count, inside = 0; - - for (i = 0; i < count; i++) { - kon_vec2_t a = kon_sectorCorner(map, sector, i), b = kon_sectorCorner(map, sector, i + 1); - - if ((a.y > z) != (b.y > z) && x < (b.x - a.x) * (z - a.y) / (b.y - a.y) + a.x) inside = !inside; - } - return inside; -} - -int kon_sectorAt(const kon_sectorMap_t *map, float x, float z, int hint) -{ - int i; - - if (!map) return -1; - if (hint >= 0 && hint < map->sectorCount) { - const kon_sector_t *s = &map->sectors[hint]; - - if (kon_inside_(map, hint, x, z)) return hint; - for (i = 0; i < s->count; i++) { - int next = map->edges[s->first + i].portal; - - if (next >= 0 && kon_inside_(map, next, x, z)) return next; - } - } - for (i = 0; i < map->sectorCount; i++) { - if (kon_inside_(map, i, x, z)) return i; - } - return -1; -} - -/*** entities ***/ - -int kon_entityFind(const kon_sectorMap_t *map, const char *name) -{ - int i; - - if (!map || !name || !name[0]) return -1; - for (i = 0; i < map->entityCount; i++) { - if (strcmp(map->entities[i].name, name) == 0) return i; - } - return -1; -} - -int kon_entityTargets(const kon_sectorMap_t *map, const char *name, int *out, int max) -{ - int i, total = 0; - - if (!map || !name || !name[0]) return 0; - for (i = 0; i < map->entityCount; i++) { - if (strcmp(map->entities[i].name, name) != 0) continue; - if (out && total < max) out[total] = i; - total++; - } - return total; -} - -const char *kon_entityString(const kon_entity_t *entity, const char *key, const char *fallback) -{ - int i; - - for (i = 0; entity && i < entity->propCount; i++) { - if (strcmp(entity->props[i].key, key) == 0) return entity->props[i].value; - } - return fallback; -} - -float kon_entityFloat(const kon_entity_t *entity, const char *key, float fallback) -{ - const char *text = kon_entityString(entity, key, NULL); - double value; - - return text && kon_number_(text, &value) ? (float)value : fallback; -} - -int kon_entityInt(const kon_entity_t *entity, const char *key, int fallback) -{ - const char *text = kon_entityString(entity, key, NULL); - double value; - - return text && kon_number_(text, &value) ? (int)value : fallback; -} - -/*** drawing ***/ - -typedef struct kon_sectorTri { - kon_vertex_t v[3]; - int texture; - float light; - int twoSided; -} kon_sectorTri_t; - -struct kon_sectorMesh { - const kon_sectorMap_t *map; - int triCount, triCap; - kon_sectorTri_t *tris; - int *first, *count; /* the triangles of each sector, the quads come after all of them */ - kon_vec3_t *center; - float *radius; - int quadFirst; -}; - -static int kon_addTriangle_(kon_sectorMesh_t *mesh, kon_vertex_t a, kon_vertex_t b, kon_vertex_t c, int texture, float light, int twoSided) -{ - kon_sectorTri_t *t; - - if (!kon_grow_((void **)&mesh->tris, &mesh->triCap, sizeof(*mesh->tris), mesh->triCount + 1)) return 0; - t = &mesh->tris[mesh->triCount++]; - t->v[0] = a; - t->v[1] = b; - t->v[2] = c; - t->texture = texture; - t->light = light; - t->twoSided = twoSided; - return 1; -} - -static kon_vertex_t kon_vertex_(float x, float y, float z, kon_vec3_t normal, float u, float v) -{ - kon_vertex_t r; - - r.position = KON_VEC3(x, y, z); - r.normal = normal; - r.uv = KON_VEC2(u, v); - return r; -} - -/* a wall seen from inside the room: left is the corner on the viewer's left, u counts from there, v from the top of the world so - textures line up from room to room */ -static int kon_addWall_(kon_sectorMesh_t *mesh, kon_vec2_t left, kon_vec2_t right, float low, float high, kon_vec3_t normal, float length, int texture) -{ - kon_vertex_t bl = kon_vertex_(left.x, low, left.y, normal, 0.0f, -low), br = kon_vertex_(right.x, low, right.y, normal, length, -low); - kon_vertex_t tr = kon_vertex_(right.x, high, right.y, normal, length, -high), tl = kon_vertex_(left.x, high, left.y, normal, 0.0f, -high); - - return kon_addTriangle_(mesh, bl, br, tr, texture, 1.0f, 0) && kon_addTriangle_(mesh, bl, tr, tl, texture, 1.0f, 0); -} - -/* is p inside the triangle abc, corners themselves do not count */ -static int kon_inTriangle_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t p) -{ - double d1 = kon_side_(a, b, p), d2 = kon_side_(b, c, p), d3 = kon_side_(c, a, p); - int negative = d1 < 0 || d2 < 0 || d3 < 0, positive = d1 > 0 || d2 > 0 || d3 > 0; - - if (kon_samePoint_(p, a) || kon_samePoint_(p, b) || kon_samePoint_(p, c)) return 0; - return !(negative && positive); -} - -/* cuts the corners off one at a time. a corner can go when it turns the right way and no other corner is inside the triangle it makes. - out gets 3 * (n - 2) corner numbers, in the same winding as the polygon */ -static int kon_triangulate_(const kon_sectorMap_t *map, int sector, int *out) -{ - int n = map->sectors[sector].count, left = n, produced = 0, i; - int *list = malloc((size_t)n * sizeof(int)); - - if (!list) return 0; - for (i = 0; i < n; i++) list[i] = i; - - while (left > 3) { - int found = -1, k; - - for (k = 0; k < left && found < 0; k++) { - int ia = list[(k + left - 1) % left], ib = list[k], ic = list[(k + 1) % left], m, blocked = 0; - kon_vec2_t a = kon_sectorCorner(map, sector, ia), b = kon_sectorCorner(map, sector, ib), c = kon_sectorCorner(map, sector, ic); - - /* these polygons run the wrong way for the usual maths because z points down, so a corner that bends the right way is negative */ - if (kon_side_(a, b, c) >= 0) continue; - for (m = 0; m < left && !blocked; m++) { - if (list[m] != ia && list[m] != ib && list[m] != ic && kon_inTriangle_(a, b, c, kon_sectorCorner(map, sector, list[m]))) blocked = 1; - } - if (!blocked) found = k; - } - - /* a polygon with flat corners can leave no clean ear, take any corner that does not bend the wrong way, then any at all */ - for (k = 0; k < left && found < 0; k++) { - kon_vec2_t a = kon_sectorCorner(map, sector, list[(k + left - 1) % left]), b = kon_sectorCorner(map, sector, list[k]), c = kon_sectorCorner(map, sector, list[(k + 1) % left]); - - if (kon_side_(a, b, c) == 0) found = k; - } - if (found < 0) found = 0; - - out[produced++] = list[(found + left - 1) % left]; - out[produced++] = list[found]; - out[produced++] = list[(found + 1) % left]; - memmove(&list[found], &list[found + 1], (size_t)(left - found - 1) * sizeof(int)); - left--; - } - out[produced++] = list[0]; - out[produced++] = list[1]; - out[produced++] = list[2]; - free(list); - return 1; -} - -static int kon_buildSector_(kon_sectorMesh_t *mesh, int s) -{ - const kon_sectorMap_t *map = mesh->map; - const kon_sector_t *sector = &map->sectors[s]; - kon_vec3_t up = KON_VEC3(0, 1, 0), down = KON_VEC3(0, -1, 0); - int *ears = malloc((size_t)(sector->count - 2) * 3 * sizeof(int)); - int i, ok = 1; - - if (!ears) return 0; - if (!kon_triangulate_(map, s, ears)) { - free(ears); - return 0; - } - - for (i = 0; i < sector->count - 2 && ok; i++) { - kon_vec2_t p[3]; - int k; - - for (k = 0; k < 3; k++) p[k] = kon_sectorCorner(map, s, ears[i * 3 + k]); - ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->floor, p[0].y, up, p[0].x, p[0].y), kon_vertex_(p[1].x, sector->floor, p[1].y, up, p[1].x, p[1].y), - kon_vertex_(p[2].x, sector->floor, p[2].y, up, p[2].x, p[2].y), sector->floorTexture, 1.0f, 0); - if (ok) ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->ceiling, p[0].y, down, p[0].x, p[0].y), kon_vertex_(p[2].x, sector->ceiling, p[2].y, down, p[2].x, p[2].y), - kon_vertex_(p[1].x, sector->ceiling, p[1].y, down, p[1].x, p[1].y), sector->ceilingTexture, 1.0f, 0); - } - free(ears); - - for (i = 0; i < sector->count && ok; i++) { - kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); - float dx = q.x - p.x, dz = q.y - p.y, length = sqrtf(dx * dx + dz * dz); - kon_vec3_t inward = KON_VEC3(dz / length, 0.0f, -dx / length); - int portal = map->edges[sector->first + i].portal, texture = kon_sectorWallTexture(map, s, i); - - /* seen from inside the room the corner p is on the right and q on the left */ - if (portal < 0) { - ok = kon_addWall_(mesh, q, p, sector->floor, sector->ceiling, inward, length, texture); - } else { - const kon_sector_t *other = &map->sectors[portal]; - float lowTop = other->floor < sector->ceiling ? other->floor : sector->ceiling; - float highBottom = other->ceiling > sector->floor ? other->ceiling : sector->floor; - - if (other->floor > sector->floor) ok = kon_addWall_(mesh, q, p, sector->floor, lowTop, inward, length, texture); - if (ok && other->ceiling < sector->ceiling) ok = kon_addWall_(mesh, q, p, highBottom, sector->ceiling, inward, length, texture); - } - } - return ok; -} - -kon_sectorMesh_t *kon_sectorBuild(const kon_sectorMap_t *map) -{ - kon_sectorMesh_t *mesh; - int s, i, k; - - if (!map) return NULL; - mesh = calloc(1, sizeof(*mesh)); - if (!mesh) return NULL; - mesh->map = map; - mesh->first = calloc((size_t)map->sectorCount + 1, sizeof(int)); - mesh->count = calloc((size_t)map->sectorCount + 1, sizeof(int)); - mesh->center = calloc((size_t)map->sectorCount + 1, sizeof(kon_vec3_t)); - mesh->radius = calloc((size_t)map->sectorCount + 1, sizeof(float)); - if (!mesh->first || !mesh->count || !mesh->center || !mesh->radius) goto bad; - - for (s = 0; s < map->sectorCount; s++) { - const kon_sector_t *sector = &map->sectors[s]; - float minX = 1e30f, maxX = -1e30f, minZ = 1e30f, maxZ = -1e30f, hx, hz, hy; - - mesh->first[s] = mesh->triCount; - if (!kon_buildSector_(mesh, s)) goto bad; - mesh->count[s] = mesh->triCount - mesh->first[s]; - - for (i = 0; i < sector->count; i++) { - kon_vec2_t p = kon_sectorCorner(map, s, i); - - if (p.x < minX) minX = p.x; - if (p.x > maxX) maxX = p.x; - if (p.y < minZ) minZ = p.y; - if (p.y > maxZ) maxZ = p.y; - } - hx = (maxX - minX) * 0.5f; - hz = (maxZ - minZ) * 0.5f; - hy = (sector->ceiling - sector->floor) * 0.5f; - mesh->center[s] = KON_VEC3(minX + hx, sector->floor + hy, minZ + hz); - mesh->radius[s] = sqrtf(hx * hx + hy * hy + hz * hz); - } - - mesh->quadFirst = mesh->triCount; - for (i = 0; i < map->quadCount; i++) { - const kon_sectorQuad_t *q = &map->quads[i]; - kon_vec3_t right = kon_vec3Sub(q->corners[1], q->corners[0]), top = kon_vec3Sub(q->corners[3], q->corners[0]); - kon_vec3_t normal = kon_vec3Normalize(kon_vec3Cross(right, top)); - kon_vertex_t v[4]; - - for (k = 0; k < 4; k++) { - static const float u[4] = { 0, 1, 1, 0 }, w[4] = { 1, 1, 0, 0 }; - - v[k] = kon_vertex_(q->corners[k].x, q->corners[k].y, q->corners[k].z, normal, u[k], w[k]); - } - if (!kon_addTriangle_(mesh, v[0], v[1], v[2], q->texture, q->light, q->doubleSided) || !kon_addTriangle_(mesh, v[0], v[2], v[3], q->texture, q->light, q->doubleSided)) goto bad; - } - return mesh; - -bad: - kon_sectorMeshFree(mesh); - return NULL; -} - -void kon_sectorMeshFree(kon_sectorMesh_t *mesh) -{ - if (!mesh) return; - free(mesh->tris); - free(mesh->first); - free(mesh->count); - free(mesh->center); - free(mesh->radius); - free(mesh); -} - -static void kon_drawRange_(kon_framebuffer_t *fb, kon_mat4_t vp, const kon_sectorMesh_t *mesh, int from, int count, const kon_material_t *materials, int materialCount, const kon_light_t *light, float sectorLight) -{ - static const kon_material_t grey = { NULL, 0xFF808080, KON_FILTER_NEAREST, NULL }; - kon_light_t lit; - int i; - - if (light) { - lit = *light; - lit.ambient *= sectorLight; - lit.intensity *= sectorLight; - } - for (i = from; i < from + count; i++) { - const kon_sectorTri_t *t = &mesh->tris[i]; - const kon_material_t *material = t->texture >= 0 && t->texture < materialCount ? &materials[t->texture] : &grey; - kon_renderFlags_t flags = t->twoSided ? KON_RENDER_DEPTH : KON_RENDER_DEFAULT; - - if (light && t->light != 1.0f) { - kon_light_t quadLight = lit; - - quadLight.ambient = light->ambient * t->light; - quadLight.intensity = light->intensity * t->light; - kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, &quadLight, flags); - } else { - kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, light ? &lit : NULL, flags); - } - } -} - -void kon_sectorDraw(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_sectorMesh_t *mesh, const kon_material_t *materials, int materialCount, const kon_light_t *light) -{ - kon_mat4_t vp; - kon_frustum_t frustum; - int s; - - if (!fb || !camera || !mesh) return; - vp = kon_cameraViewProjection(camera, fb->width, fb->height); - frustum = kon_frustumFromMatrix(vp); - - for (s = 0; s < mesh->map->sectorCount; s++) { - if (!kon_frustumSphere(&frustum, mesh->center[s], mesh->radius[s])) continue; - kon_drawRange_(fb, vp, mesh, mesh->first[s], mesh->count[s], materials, materialCount, light, mesh->map->sectors[s].light); - } - kon_drawRange_(fb, vp, mesh, mesh->quadFirst, mesh->triCount - mesh->quadFirst, materials, materialCount, light, 1.0f); -} diff --git a/kon/konsector.h b/kon/konsector.h index 2c816e1..c7a71e3 100644 --- a/kon/konsector.h +++ b/kon/konsector.h @@ -23,6 +23,15 @@ * SOFTWARE. */ +/* a map made of rooms: loading, saving, looking things up, building a mesh and drawing it. it needs konsofren.h and konmath.h next to it + * and nothing else, so it is copy and paste like the other single header libs. in exactly one .c file: + * + * #define KONSOFREN_IMPLEMENTATION (once, wherever konsofren is) + * #define KONSECTOR_IMPLEMENTATION + * #include "konsector.h" + * + * a map can come from a file or from a string in your own source, kon_sectorParse takes the text either way */ + #ifndef KONSECTOR_H #define KONSECTOR_H @@ -157,4 +166,941 @@ const char *kon_entityString(const kon_entity_t *entity, const char *key, const float kon_entityFloat(const kon_entity_t *entity, const char *key, float fallback); int kon_entityInt(const kon_entity_t *entity, const char *key, int fallback); -#endif +/*** implementation ***/ + +#ifdef KONSECTOR_IMPLEMENTATION + +#include <math.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define WORD_LENGTH 128 +#define MAX_FILE (16 * 1024 * 1024) + +/*** private ***/ + +typedef struct kon_builder { + kon_sectorMap_t *map; + int vertexCap, sectorCap, lineCap, indexCap, edgeCap, quadCap, entityCap, textureCap; + int *sectorLine; /* the line each sector was written on, for the errors found afterwards */ + int line; + char *error; + size_t errorSize; +} kon_builder_t; + +static int kon_fail_(kon_builder_t *b, int line, const char *format, ...) +{ + va_list args; + int used = 0; + + if (b->error && b->errorSize > 0) { + if (line > 0) used = snprintf(b->error, b->errorSize, "line %d: ", line); + if (used < 0 || (size_t)used >= b->errorSize) used = 0; + va_start(args, format); + vsnprintf(b->error + used, b->errorSize - (size_t)used, format, args); + va_end(args); + } + return 0; +} + +static int kon_grow_(void **array, int *capacity, size_t size, int needed) +{ + void *bigger; + int cap = *capacity; + + if (needed <= cap) return 1; + if (cap < 8) cap = 8; + while (cap < needed) cap *= 2; + bigger = realloc(*array, (size_t)cap * size); + if (!bigger) return 0; + *array = bigger; + *capacity = cap; + return 1; +} + +/* the next word of a line, NULL at the end of it. the line ends at a newline or a #. the word is copied into out */ +static const char *kon_word_(const char *p, char *out, size_t size) +{ + size_t n = 0; + + while (*p == ' ' || *p == '\t' || *p == '\r') p++; + if (*p == '\0' || *p == '\n' || *p == '#') return NULL; + while (*p != '\0' && *p != ' ' && *p != '\t' && *p != '\r' && *p != '\n' && *p != '#') { + if (n + 1 < size) out[n++] = *p; + p++; + } + out[n] = '\0'; + return p; +} + +static int kon_number_(const char *word, double *value) +{ + char *end; + + if (*word == '\0') return 0; + *value = strtod(word, &end); + return *end == '\0' && isfinite(*value); +} + +static int kon_texture_(kon_builder_t *b, const char *name, int *index) +{ + kon_sectorMap_t *map = b->map; + int i; + + if (strcmp(name, "-") == 0) { + *index = -1; + return 1; + } + for (i = 0; i < map->textureCount; i++) { + if (strcmp(map->textures[i], name) == 0) { + *index = i; + return 1; + } + } + if (strlen(name) >= KON_NAME_LENGTH) return 0; + if (!kon_grow_((void **)&map->textures, &b->textureCap, sizeof(map->textures[0]), map->textureCount + 1)) return 0; + strcpy(map->textures[map->textureCount], name); + *index = map->textureCount++; + return 1; +} + +static double kon_area_(const kon_sectorMap_t *map, const kon_sector_t *sector) +{ + double sum = 0.0; + int i; + + for (i = 0; i < sector->count; i++) { + kon_vec2_t a = map->vertices[map->indices[sector->first + i]]; + kon_vec2_t b = map->vertices[map->indices[sector->first + (i + 1) % sector->count]]; + + sum += (double)a.x * (double)b.y - (double)b.x * (double)a.y; + } + return sum * 0.5; +} + +static double kon_side_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p) +{ + return ((double)b.x - (double)a.x) * ((double)p.y - (double)a.y) - ((double)b.y - (double)a.y) * ((double)p.x - (double)a.x); +} + +static int kon_onSegment_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p) +{ + return p.x >= (a.x < b.x ? a.x : b.x) && p.x <= (a.x > b.x ? a.x : b.x) && p.y >= (a.y < b.y ? a.y : b.y) && p.y <= (a.y > b.y ? a.y : b.y); +} + +/* touching counts as crossing */ +static int kon_crossing_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t d) +{ + double d1 = kon_side_(a, b, c), d2 = kon_side_(a, b, d), d3 = kon_side_(c, d, a), d4 = kon_side_(c, d, b); + + if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return 1; + if (d1 == 0 && kon_onSegment_(a, b, c)) return 1; + if (d2 == 0 && kon_onSegment_(a, b, d)) return 1; + if (d3 == 0 && kon_onSegment_(c, d, a)) return 1; + if (d4 == 0 && kon_onSegment_(c, d, b)) return 1; + return 0; +} + +static int kon_checkSector_(kon_builder_t *b, int s) +{ + kon_sectorMap_t *map = b->map; + kon_sector_t *sector = &map->sectors[s]; + int line = b->sectorLine[s], i, j; + double area; + + if (sector->count < 3) return kon_fail_(b, line, "sector %d needs at least 3 corners", s); + if (!(sector->ceiling > sector->floor)) return kon_fail_(b, line, "sector %d has a ceiling that is not above its floor", s); + + for (i = 0; i < sector->count; i++) { + kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); + + if (p.x == q.x && p.y == q.y) return kon_fail_(b, line, "sector %d has an edge with no length at corner %d", s, i); + } + + for (i = 0; i < sector->count; i++) { + for (j = i + 2; j < sector->count; j++) { + if (i == 0 && j == sector->count - 1) continue; + if (kon_crossing_(kon_sectorCorner(map, s, i), kon_sectorCorner(map, s, i + 1), kon_sectorCorner(map, s, j), kon_sectorCorner(map, s, j + 1))) { + return kon_fail_(b, line, "sector %d crosses itself, edges %d and %d touch", s, i, j); + } + } + } + + area = kon_area_(map, sector); + if (area == 0.0) return kon_fail_(b, line, "sector %d has no area", s); + + /* the shoelace sum is positive going clockwise on a plan with z pointing down, the format wants the other way round */ + if (area > 0.0) { + int *c = &map->indices[sector->first]; + kon_sectorEdge_t *e = &map->edges[sector->first]; + + for (i = 0, j = sector->count - 1; i < j; i++, j--) { + int t = c[i]; + + c[i] = c[j]; + c[j] = t; + } + /* the corners are reversed, so edge n now runs along old edge count - 2 - n backwards. the closing edge stays the closing edge */ + for (i = 0, j = sector->count - 2; i < j; i++, j--) { + kon_sectorEdge_t t = e[i]; + + e[i] = e[j]; + e[j] = t; + } + } + return 1; +} + +static int kon_samePoint_(kon_vec2_t a, kon_vec2_t b) +{ + return a.x == b.x && a.y == b.y; +} + +static int kon_linkPortals_(kon_builder_t *b) +{ + kon_sectorMap_t *map = b->map; + int s, t, i, j; + + for (s = 0; s < map->sectorCount; s++) { + for (i = 0; i < map->sectors[s].count; i++) { + kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); + + map->edges[map->sectors[s].first + i].portal = -1; + for (t = 0; t < map->sectorCount; t++) { + if (t == s) continue; + for (j = 0; j < map->sectors[t].count; j++) { + kon_vec2_t u = kon_sectorCorner(map, t, j), v = kon_sectorCorner(map, t, j + 1); + + if (kon_samePoint_(p, u) && kon_samePoint_(q, v)) { + return kon_fail_(b, b->sectorLine[s], "sectors %d and %d overlap along an edge, they run the same way", s, t); + } + if (kon_samePoint_(p, v) && kon_samePoint_(q, u)) map->edges[map->sectors[s].first + i].portal = t; + } + } + } + } + return 1; +} + +/*** loading ***/ + +static int kon_parseSector_(kon_builder_t *b, const char *p) +{ + kon_sectorMap_t *map = b->map; + kon_sector_t *sector; + char word[WORD_LENGTH], value[WORD_LENGTH]; + double floorHeight, ceilingHeight, number; + int line = b->line; + + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &floorHeight)) return kon_fail_(b, line, "sector needs a floor height"); + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &ceilingHeight)) return kon_fail_(b, line, "sector needs a ceiling height"); + + if (!kon_grow_((void **)&map->sectors, &b->sectorCap, sizeof(*map->sectors), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory"); + if (!kon_grow_((void **)&b->sectorLine, &b->lineCap, sizeof(int), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory"); + sector = &map->sectors[map->sectorCount]; + memset(sector, 0, sizeof(*sector)); + sector->floor = (float)floorHeight; + sector->ceiling = (float)ceilingHeight; + sector->light = 1.0f; + sector->floorTexture = sector->ceilingTexture = sector->wallTexture = -1; + sector->first = map->indexCount; + b->sectorLine[map->sectorCount] = line; + + /* key value pairs until the colon */ + for (;;) { + if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "sector needs a colon before its corners"); + if (strcmp(word, ":") == 0) break; + if (kon_number_(word, &number)) return kon_fail_(b, line, "the corners of a sector come after a colon"); + if (!(p = kon_word_(p, value, sizeof(value)))) return kon_fail_(b, line, "%s needs a value", word); + + if (strcmp(word, "light") == 0) { + if (!kon_number_(value, &number) || number < 0.0 || number > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1"); + sector->light = (float)number; + } else if (strcmp(word, "floor") == 0) { + if (!kon_texture_(b, value, §or->floorTexture)) return kon_fail_(b, line, "bad texture name %s", value); + } else if (strcmp(word, "ceiling") == 0) { + if (!kon_texture_(b, value, §or->ceilingTexture)) return kon_fail_(b, line, "bad texture name %s", value); + } else if (strcmp(word, "wall") == 0) { + if (!kon_texture_(b, value, §or->wallTexture)) return kon_fail_(b, line, "bad texture name %s", value); + } else { + return kon_fail_(b, line, "unknown sector setting %s", word); + } + } + + while ((p = kon_word_(p, word, sizeof(word)))) { + if (!kon_number_(word, &number) || number != floor(number) || number < 0.0 || number >= (double)map->vertexCount) { + return kon_fail_(b, line, "%s is not a vertex that was defined above", word); + } + if (!kon_grow_((void **)&map->indices, &b->indexCap, sizeof(int), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory"); + if (!kon_grow_((void **)&map->edges, &b->edgeCap, sizeof(*map->edges), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory"); + map->indices[map->indexCount] = (int)number; + map->edges[map->indexCount].portal = -1; + map->edges[map->indexCount].texture = -1; + map->indexCount++; + } + sector->count = map->indexCount - sector->first; + map->sectorCount++; + return 1; +} + +static int kon_parseQuad_(kon_builder_t *b, const char *p) +{ + kon_sectorMap_t *map = b->map; + kon_sectorQuad_t *quad; + char word[WORD_LENGTH]; + double v[12]; + int i, line = b->line; + + if (!kon_grow_((void **)&map->quads, &b->quadCap, sizeof(*map->quads), map->quadCount + 1)) return kon_fail_(b, 0, "out of memory"); + quad = &map->quads[map->quadCount]; + memset(quad, 0, sizeof(*quad)); + quad->light = 1.0f; + + if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "quad needs a texture"); + if (!kon_texture_(b, word, &quad->texture)) return kon_fail_(b, line, "bad texture name %s", word); + for (i = 0; i < 12; i++) { + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "quad needs 12 numbers, x y z for each of its 4 corners"); + } + for (i = 0; i < 4; i++) quad->corners[i] = KON_VEC3((float)v[i * 3], (float)v[i * 3 + 1], (float)v[i * 3 + 2]); + + while ((p = kon_word_(p, word, sizeof(word)))) { + if (strcmp(word, "double") == 0) { + quad->doubleSided = 1; + } else if (strcmp(word, "light") == 0) { + double light; + + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &light) || light < 0.0 || light > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1"); + quad->light = (float)light; + } else { + return kon_fail_(b, line, "unknown quad setting %s", word); + } + } + map->quadCount++; + return 1; +} + +static int kon_parseEntity_(kon_builder_t *b, const char *p) +{ + kon_sectorMap_t *map = b->map; + kon_entity_t *entity; + char word[WORD_LENGTH]; + double v[4]; + int i, line = b->line; + + if (!kon_grow_((void **)&map->entities, &b->entityCap, sizeof(*map->entities), map->entityCount + 1)) return kon_fail_(b, 0, "out of memory"); + entity = &map->entities[map->entityCount]; + memset(entity, 0, sizeof(*entity)); + entity->sector = -1; + + if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "entity needs a kind"); + if (strlen(word) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the kind %s is too long", word); + strcpy(entity->kind, word); + + for (i = 0; i < 4; i++) { + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "entity needs x y z and an angle"); + } + entity->position = KON_VEC3((float)v[0], (float)v[1], (float)v[2]); + entity->angle = (float)(v[3] * 3.14159265358979323846 / 180.0); + + while ((p = kon_word_(p, word, sizeof(word)))) { + char *equals = strchr(word, '='); + + if (!equals || equals == word) return kon_fail_(b, line, "%s should be written key=value", word); + *equals++ = '\0'; + + if (strcmp(word, "name") == 0 || strcmp(word, "target") == 0) { + char *dest = word[0] == 'n' ? entity->name : entity->target; + + if (strlen(equals) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the %s %s is too long", word, equals); + strcpy(dest, equals); + } else { + if (entity->propCount >= KON_ENTITY_PROPS) return kon_fail_(b, line, "an entity can have %d settings at most", KON_ENTITY_PROPS); + if (strlen(word) >= sizeof(entity->props[0].key) || strlen(equals) >= sizeof(entity->props[0].value)) return kon_fail_(b, line, "the setting %s is too long", word); + strcpy(entity->props[entity->propCount].key, word); + strcpy(entity->props[entity->propCount].value, equals); + entity->propCount++; + } + } + map->entityCount++; + return 1; +} + +static int kon_parseLine_(kon_builder_t *b, const char *p, int *started) +{ + kon_sectorMap_t *map = b->map; + char word[WORD_LENGTH]; + double number, x, z; + int line = b->line; + + if (!(p = kon_word_(p, word, sizeof(word)))) return 1; + + if (!*started) { + if (strcmp(word, "kmap") != 0) return kon_fail_(b, line, "a map starts with \"kmap 1\""); + if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &number) || number != 1.0) return kon_fail_(b, line, "this reads kmap version 1"); + *started = 1; + return 1; + } + + if (strcmp(word, "v") == 0) { + char a[WORD_LENGTH], c[WORD_LENGTH]; + + if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !kon_number_(a, &x) || !kon_number_(c, &z)) return kon_fail_(b, line, "v needs x and z"); + if (!kon_grow_((void **)&map->vertices, &b->vertexCap, sizeof(*map->vertices), map->vertexCount + 1)) return kon_fail_(b, 0, "out of memory"); + map->vertices[map->vertexCount++] = KON_VEC2((float)x, (float)z); + return 1; + } + if (strcmp(word, "sector") == 0) return kon_parseSector_(b, p); + if (strcmp(word, "quad") == 0) return kon_parseQuad_(b, p); + if (strcmp(word, "entity") == 0) return kon_parseEntity_(b, p); + if (strcmp(word, "edge") == 0) { + char a[WORD_LENGTH], c[WORD_LENGTH], name[WORD_LENGTH]; + double s, n; + + if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !(p = kon_word_(p, name, sizeof(name))) || !kon_number_(a, &s) || !kon_number_(c, &n)) { + return kon_fail_(b, line, "edge needs a sector, an edge number and a texture"); + } + if (s < 0 || s >= map->sectorCount || s != floor(s)) return kon_fail_(b, line, "there is no sector %s above", a); + if (n < 0 || n >= map->sectors[(int)s].count || n != floor(n)) return kon_fail_(b, line, "sector %s has no edge %s", a, c); + if (!kon_texture_(b, name, &map->edges[map->sectors[(int)s].first + (int)n].texture)) return kon_fail_(b, line, "bad texture name %s", name); + return 1; + } + return kon_fail_(b, line, "unknown word %s", word); +} + +kon_sectorMap_t *kon_sectorParse(const char *text, char *error, size_t errorSize) +{ + kon_builder_t b; + kon_sectorMap_t *map; + const char *p = text; + int started = 0, i; + + if (error && errorSize > 0) error[0] = '\0'; + if (!text) return NULL; + map = calloc(1, sizeof(*map)); + if (!map) return NULL; + memset(&b, 0, sizeof(b)); + b.map = map; + b.error = error; + b.errorSize = errorSize; + + while (*p != '\0') { + b.line++; + if (!kon_parseLine_(&b, p, &started)) goto bad; + while (*p != '\0' && *p != '\n') p++; + if (*p == '\n') p++; + } + + if (!started) { + kon_fail_(&b, 0, "the map is empty, it should start with \"kmap 1\""); + goto bad; + } + for (i = 0; i < map->sectorCount; i++) { + if (!kon_checkSector_(&b, i)) goto bad; + } + if (!kon_linkPortals_(&b)) goto bad; + for (i = 0; i < map->entityCount; i++) map->entities[i].sector = kon_sectorAt(map, map->entities[i].position.x, map->entities[i].position.z, -1); + + free(b.sectorLine); + return map; + +bad: + free(b.sectorLine); + kon_sectorFree(map); + return NULL; +} + +kon_sectorMap_t *kon_sectorLoad(const char *path, char *error, size_t errorSize) +{ + kon_sectorMap_t *map; + FILE *file; + char *text; + long size; + + if (error && errorSize > 0) error[0] = '\0'; + file = path ? fopen(path, "rb") : NULL; + if (!file) { + if (error && errorSize > 0) snprintf(error, errorSize, "could not open %s", path ? path : "(null)"); + return NULL; + } + fseek(file, 0, SEEK_END); + size = ftell(file); + fseek(file, 0, SEEK_SET); + if (size < 0 || size > MAX_FILE) { + fclose(file); + if (error && errorSize > 0) snprintf(error, errorSize, "%s is too big for a map", path); + return NULL; + } + text = malloc((size_t)size + 1); + if (!text) { + fclose(file); + return NULL; + } + if (fread(text, 1, (size_t)size, file) != (size_t)size) { + free(text); + fclose(file); + if (error && errorSize > 0) snprintf(error, errorSize, "could not read %s", path); + return NULL; + } + text[size] = '\0'; + fclose(file); + + map = kon_sectorParse(text, error, errorSize); + free(text); + return map; +} + +void kon_sectorFree(kon_sectorMap_t *map) +{ + if (!map) return; + free(map->vertices); + free(map->sectors); + free(map->indices); + free(map->edges); + free(map->quads); + free(map->entities); + free(map->textures); + free(map); +} + +int kon_sectorSave(const kon_sectorMap_t *map, const char *path) +{ + FILE *file; + int i, j; + + if (!map || !path) return 1; + file = fopen(path, "w"); + if (!file) return 1; + + fprintf(file, "kmap 1\n\n"); + for (i = 0; i < map->vertexCount; i++) fprintf(file, "v %.9g %.9g\n", (double)map->vertices[i].x, (double)map->vertices[i].y); + fputc('\n', file); + + for (i = 0; i < map->sectorCount; i++) { + const kon_sector_t *s = &map->sectors[i]; + + fprintf(file, "sector %.9g %.9g light %.9g floor %s ceiling %s wall %s :", (double)s->floor, (double)s->ceiling, (double)s->light, + s->floorTexture >= 0 ? map->textures[s->floorTexture] : "-", s->ceilingTexture >= 0 ? map->textures[s->ceilingTexture] : "-", + s->wallTexture >= 0 ? map->textures[s->wallTexture] : "-"); + for (j = 0; j < s->count; j++) fprintf(file, " %d", map->indices[s->first + j]); + fputc('\n', file); + } + for (i = 0; i < map->sectorCount; i++) { + for (j = 0; j < map->sectors[i].count; j++) { + int texture = map->edges[map->sectors[i].first + j].texture; + + if (texture >= 0) fprintf(file, "edge %d %d %s\n", i, j, map->textures[texture]); + } + } + fputc('\n', file); + + for (i = 0; i < map->quadCount; i++) { + const kon_sectorQuad_t *q = &map->quads[i]; + + fprintf(file, "quad %s", q->texture >= 0 ? map->textures[q->texture] : "-"); + for (j = 0; j < 4; j++) fprintf(file, " %.9g %.9g %.9g", (double)q->corners[j].x, (double)q->corners[j].y, (double)q->corners[j].z); + if (q->doubleSided) fprintf(file, " double"); + if (q->light != 1.0f) fprintf(file, " light %.9g", (double)q->light); + fputc('\n', file); + } + if (map->quadCount > 0) fputc('\n', file); + + for (i = 0; i < map->entityCount; i++) { + const kon_entity_t *e = &map->entities[i]; + + fprintf(file, "entity %s %.9g %.9g %.9g %.9g", e->kind, (double)e->position.x, (double)e->position.y, (double)e->position.z, (double)e->angle * 180.0 / 3.14159265358979323846); + if (e->name[0]) fprintf(file, " name=%s", e->name); + if (e->target[0]) fprintf(file, " target=%s", e->target); + for (j = 0; j < e->propCount; j++) fprintf(file, " %s=%s", e->props[j].key, e->props[j].value); + fputc('\n', file); + } + return fclose(file) != 0; +} + +/*** looking things up ***/ + +kon_vec2_t kon_sectorCorner(const kon_sectorMap_t *map, int sector, int n) +{ + const kon_sector_t *s = &map->sectors[sector]; + + return map->vertices[map->indices[s->first + n % s->count]]; +} + +int kon_sectorWallTexture(const kon_sectorMap_t *map, int sector, int edge) +{ + int texture = map->edges[map->sectors[sector].first + edge].texture; + + return texture >= 0 ? texture : map->sectors[sector].wallTexture; +} + +int kon_sectorTextureIndex(const kon_sectorMap_t *map, const char *name) +{ + int i; + + for (i = 0; i < map->textureCount; i++) { + if (strcmp(map->textures[i], name) == 0) return i; + } + return -1; +} + +static int kon_inside_(const kon_sectorMap_t *map, int sector, float x, float z) +{ + int i, count = map->sectors[sector].count, inside = 0; + + for (i = 0; i < count; i++) { + kon_vec2_t a = kon_sectorCorner(map, sector, i), b = kon_sectorCorner(map, sector, i + 1); + + if ((a.y > z) != (b.y > z) && x < (b.x - a.x) * (z - a.y) / (b.y - a.y) + a.x) inside = !inside; + } + return inside; +} + +int kon_sectorAt(const kon_sectorMap_t *map, float x, float z, int hint) +{ + int i; + + if (!map) return -1; + if (hint >= 0 && hint < map->sectorCount) { + const kon_sector_t *s = &map->sectors[hint]; + + if (kon_inside_(map, hint, x, z)) return hint; + for (i = 0; i < s->count; i++) { + int next = map->edges[s->first + i].portal; + + if (next >= 0 && kon_inside_(map, next, x, z)) return next; + } + } + for (i = 0; i < map->sectorCount; i++) { + if (kon_inside_(map, i, x, z)) return i; + } + return -1; +} + +/*** entities ***/ + +int kon_entityFind(const kon_sectorMap_t *map, const char *name) +{ + int i; + + if (!map || !name || !name[0]) return -1; + for (i = 0; i < map->entityCount; i++) { + if (strcmp(map->entities[i].name, name) == 0) return i; + } + return -1; +} + +int kon_entityTargets(const kon_sectorMap_t *map, const char *name, int *out, int max) +{ + int i, total = 0; + + if (!map || !name || !name[0]) return 0; + for (i = 0; i < map->entityCount; i++) { + if (strcmp(map->entities[i].name, name) != 0) continue; + if (out && total < max) out[total] = i; + total++; + } + return total; +} + +const char *kon_entityString(const kon_entity_t *entity, const char *key, const char *fallback) +{ + int i; + + for (i = 0; entity && i < entity->propCount; i++) { + if (strcmp(entity->props[i].key, key) == 0) return entity->props[i].value; + } + return fallback; +} + +float kon_entityFloat(const kon_entity_t *entity, const char *key, float fallback) +{ + const char *text = kon_entityString(entity, key, NULL); + double value; + + return text && kon_number_(text, &value) ? (float)value : fallback; +} + +int kon_entityInt(const kon_entity_t *entity, const char *key, int fallback) +{ + const char *text = kon_entityString(entity, key, NULL); + double value; + + return text && kon_number_(text, &value) ? (int)value : fallback; +} + +/*** drawing ***/ + +typedef struct kon_sectorTri { + kon_vertex_t v[3]; + int texture; + float light; + int twoSided; +} kon_sectorTri_t; + +struct kon_sectorMesh { + const kon_sectorMap_t *map; + int triCount, triCap; + kon_sectorTri_t *tris; + int *first, *count; /* the triangles of each sector, the quads come after all of them */ + kon_vec3_t *center; + float *radius; + int quadFirst; +}; + +static int kon_addTriangle_(kon_sectorMesh_t *mesh, kon_vertex_t a, kon_vertex_t b, kon_vertex_t c, int texture, float light, int twoSided) +{ + kon_sectorTri_t *t; + + if (!kon_grow_((void **)&mesh->tris, &mesh->triCap, sizeof(*mesh->tris), mesh->triCount + 1)) return 0; + t = &mesh->tris[mesh->triCount++]; + t->v[0] = a; + t->v[1] = b; + t->v[2] = c; + t->texture = texture; + t->light = light; + t->twoSided = twoSided; + return 1; +} + +static kon_vertex_t kon_vertex_(float x, float y, float z, kon_vec3_t normal, float u, float v) +{ + kon_vertex_t r; + + r.position = KON_VEC3(x, y, z); + r.normal = normal; + r.uv = KON_VEC2(u, v); + return r; +} + +/* a wall seen from inside the room: left is the corner on the viewer's left, u counts from there, v from the top of the world so + textures line up from room to room */ +static int kon_addWall_(kon_sectorMesh_t *mesh, kon_vec2_t left, kon_vec2_t right, float low, float high, kon_vec3_t normal, float length, int texture) +{ + kon_vertex_t bl = kon_vertex_(left.x, low, left.y, normal, 0.0f, -low), br = kon_vertex_(right.x, low, right.y, normal, length, -low); + kon_vertex_t tr = kon_vertex_(right.x, high, right.y, normal, length, -high), tl = kon_vertex_(left.x, high, left.y, normal, 0.0f, -high); + + return kon_addTriangle_(mesh, bl, br, tr, texture, 1.0f, 0) && kon_addTriangle_(mesh, bl, tr, tl, texture, 1.0f, 0); +} + +/* is p inside the triangle abc, corners themselves do not count */ +static int kon_inTriangle_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t p) +{ + double d1 = kon_side_(a, b, p), d2 = kon_side_(b, c, p), d3 = kon_side_(c, a, p); + int negative = d1 < 0 || d2 < 0 || d3 < 0, positive = d1 > 0 || d2 > 0 || d3 > 0; + + if (kon_samePoint_(p, a) || kon_samePoint_(p, b) || kon_samePoint_(p, c)) return 0; + return !(negative && positive); +} + +/* cuts the corners off one at a time. a corner can go when it turns the right way and no other corner is inside the triangle it makes. + out gets 3 * (n - 2) corner numbers, in the same winding as the polygon */ +static int kon_triangulate_(const kon_sectorMap_t *map, int sector, int *out) +{ + int n = map->sectors[sector].count, left = n, produced = 0, i; + int *list = malloc((size_t)n * sizeof(int)); + + if (!list) return 0; + for (i = 0; i < n; i++) list[i] = i; + + while (left > 3) { + int found = -1, k; + + for (k = 0; k < left && found < 0; k++) { + int ia = list[(k + left - 1) % left], ib = list[k], ic = list[(k + 1) % left], m, blocked = 0; + kon_vec2_t a = kon_sectorCorner(map, sector, ia), b = kon_sectorCorner(map, sector, ib), c = kon_sectorCorner(map, sector, ic); + + /* these polygons run the wrong way for the usual maths because z points down, so a corner that bends the right way is negative */ + if (kon_side_(a, b, c) >= 0) continue; + for (m = 0; m < left && !blocked; m++) { + if (list[m] != ia && list[m] != ib && list[m] != ic && kon_inTriangle_(a, b, c, kon_sectorCorner(map, sector, list[m]))) blocked = 1; + } + if (!blocked) found = k; + } + + /* a polygon with flat corners can leave no clean ear, take any corner that does not bend the wrong way, then any at all */ + for (k = 0; k < left && found < 0; k++) { + kon_vec2_t a = kon_sectorCorner(map, sector, list[(k + left - 1) % left]), b = kon_sectorCorner(map, sector, list[k]), c = kon_sectorCorner(map, sector, list[(k + 1) % left]); + + if (kon_side_(a, b, c) == 0) found = k; + } + if (found < 0) found = 0; + + out[produced++] = list[(found + left - 1) % left]; + out[produced++] = list[found]; + out[produced++] = list[(found + 1) % left]; + memmove(&list[found], &list[found + 1], (size_t)(left - found - 1) * sizeof(int)); + left--; + } + out[produced++] = list[0]; + out[produced++] = list[1]; + out[produced++] = list[2]; + free(list); + return 1; +} + +static int kon_buildSector_(kon_sectorMesh_t *mesh, int s) +{ + const kon_sectorMap_t *map = mesh->map; + const kon_sector_t *sector = &map->sectors[s]; + kon_vec3_t up = KON_VEC3(0, 1, 0), down = KON_VEC3(0, -1, 0); + int *ears = malloc((size_t)(sector->count - 2) * 3 * sizeof(int)); + int i, ok = 1; + + if (!ears) return 0; + if (!kon_triangulate_(map, s, ears)) { + free(ears); + return 0; + } + + for (i = 0; i < sector->count - 2 && ok; i++) { + kon_vec2_t p[3]; + int k; + + for (k = 0; k < 3; k++) p[k] = kon_sectorCorner(map, s, ears[i * 3 + k]); + ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->floor, p[0].y, up, p[0].x, p[0].y), kon_vertex_(p[1].x, sector->floor, p[1].y, up, p[1].x, p[1].y), + kon_vertex_(p[2].x, sector->floor, p[2].y, up, p[2].x, p[2].y), sector->floorTexture, 1.0f, 0); + if (ok) ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->ceiling, p[0].y, down, p[0].x, p[0].y), kon_vertex_(p[2].x, sector->ceiling, p[2].y, down, p[2].x, p[2].y), + kon_vertex_(p[1].x, sector->ceiling, p[1].y, down, p[1].x, p[1].y), sector->ceilingTexture, 1.0f, 0); + } + free(ears); + + for (i = 0; i < sector->count && ok; i++) { + kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1); + float dx = q.x - p.x, dz = q.y - p.y, length = sqrtf(dx * dx + dz * dz); + kon_vec3_t inward = KON_VEC3(dz / length, 0.0f, -dx / length); + int portal = map->edges[sector->first + i].portal, texture = kon_sectorWallTexture(map, s, i); + + /* seen from inside the room the corner p is on the right and q on the left */ + if (portal < 0) { + ok = kon_addWall_(mesh, q, p, sector->floor, sector->ceiling, inward, length, texture); + } else { + const kon_sector_t *other = &map->sectors[portal]; + float lowTop = other->floor < sector->ceiling ? other->floor : sector->ceiling; + float highBottom = other->ceiling > sector->floor ? other->ceiling : sector->floor; + + if (other->floor > sector->floor) ok = kon_addWall_(mesh, q, p, sector->floor, lowTop, inward, length, texture); + if (ok && other->ceiling < sector->ceiling) ok = kon_addWall_(mesh, q, p, highBottom, sector->ceiling, inward, length, texture); + } + } + return ok; +} + +kon_sectorMesh_t *kon_sectorBuild(const kon_sectorMap_t *map) +{ + kon_sectorMesh_t *mesh; + int s, i, k; + + if (!map) return NULL; + mesh = calloc(1, sizeof(*mesh)); + if (!mesh) return NULL; + mesh->map = map; + mesh->first = calloc((size_t)map->sectorCount + 1, sizeof(int)); + mesh->count = calloc((size_t)map->sectorCount + 1, sizeof(int)); + mesh->center = calloc((size_t)map->sectorCount + 1, sizeof(kon_vec3_t)); + mesh->radius = calloc((size_t)map->sectorCount + 1, sizeof(float)); + if (!mesh->first || !mesh->count || !mesh->center || !mesh->radius) goto bad; + + for (s = 0; s < map->sectorCount; s++) { + const kon_sector_t *sector = &map->sectors[s]; + float minX = 1e30f, maxX = -1e30f, minZ = 1e30f, maxZ = -1e30f, hx, hz, hy; + + mesh->first[s] = mesh->triCount; + if (!kon_buildSector_(mesh, s)) goto bad; + mesh->count[s] = mesh->triCount - mesh->first[s]; + + for (i = 0; i < sector->count; i++) { + kon_vec2_t p = kon_sectorCorner(map, s, i); + + if (p.x < minX) minX = p.x; + if (p.x > maxX) maxX = p.x; + if (p.y < minZ) minZ = p.y; + if (p.y > maxZ) maxZ = p.y; + } + hx = (maxX - minX) * 0.5f; + hz = (maxZ - minZ) * 0.5f; + hy = (sector->ceiling - sector->floor) * 0.5f; + mesh->center[s] = KON_VEC3(minX + hx, sector->floor + hy, minZ + hz); + mesh->radius[s] = sqrtf(hx * hx + hy * hy + hz * hz); + } + + mesh->quadFirst = mesh->triCount; + for (i = 0; i < map->quadCount; i++) { + const kon_sectorQuad_t *q = &map->quads[i]; + kon_vec3_t right = kon_vec3Sub(q->corners[1], q->corners[0]), top = kon_vec3Sub(q->corners[3], q->corners[0]); + kon_vec3_t normal = kon_vec3Normalize(kon_vec3Cross(right, top)); + kon_vertex_t v[4]; + + for (k = 0; k < 4; k++) { + static const float u[4] = { 0, 1, 1, 0 }, w[4] = { 1, 1, 0, 0 }; + + v[k] = kon_vertex_(q->corners[k].x, q->corners[k].y, q->corners[k].z, normal, u[k], w[k]); + } + if (!kon_addTriangle_(mesh, v[0], v[1], v[2], q->texture, q->light, q->doubleSided) || !kon_addTriangle_(mesh, v[0], v[2], v[3], q->texture, q->light, q->doubleSided)) goto bad; + } + return mesh; + +bad: + kon_sectorMeshFree(mesh); + return NULL; +} + +void kon_sectorMeshFree(kon_sectorMesh_t *mesh) +{ + if (!mesh) return; + free(mesh->tris); + free(mesh->first); + free(mesh->count); + free(mesh->center); + free(mesh->radius); + free(mesh); +} + +static void kon_drawRange_(kon_framebuffer_t *fb, kon_mat4_t vp, const kon_sectorMesh_t *mesh, int from, int count, const kon_material_t *materials, int materialCount, const kon_light_t *light, float sectorLight) +{ + static const kon_material_t grey = { NULL, 0xFF808080, KON_FILTER_NEAREST, NULL }; + kon_light_t lit; + int i; + + if (light) { + lit = *light; + lit.ambient *= sectorLight; + lit.intensity *= sectorLight; + } + for (i = from; i < from + count; i++) { + const kon_sectorTri_t *t = &mesh->tris[i]; + const kon_material_t *material = t->texture >= 0 && t->texture < materialCount ? &materials[t->texture] : &grey; + kon_renderFlags_t flags = t->twoSided ? KON_RENDER_DEPTH : KON_RENDER_DEFAULT; + + if (light && t->light != 1.0f) { + kon_light_t quadLight = lit; + + quadLight.ambient = light->ambient * t->light; + quadLight.intensity = light->intensity * t->light; + kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, &quadLight, flags); + } else { + kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, light ? &lit : NULL, flags); + } + } +} + +void kon_sectorDraw(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_sectorMesh_t *mesh, const kon_material_t *materials, int materialCount, const kon_light_t *light) +{ + kon_mat4_t vp; + kon_frustum_t frustum; + int s; + + if (!fb || !camera || !mesh) return; + vp = kon_cameraViewProjection(camera, fb->width, fb->height); + frustum = kon_frustumFromMatrix(vp); + + for (s = 0; s < mesh->map->sectorCount; s++) { + if (!kon_frustumSphere(&frustum, mesh->center[s], mesh->radius[s])) continue; + kon_drawRange_(fb, vp, mesh, mesh->first[s], mesh->count[s], materials, materialCount, light, mesh->map->sectors[s].light); + } + kon_drawRange_(fb, vp, mesh, mesh->quadFirst, mesh->triCount - mesh->quadFirst, materials, materialCount, light, 1.0f); +} + +#endif /* KONSECTOR_IMPLEMENTATION */ + +#endif /* KONSECTOR_H */ diff --git a/src/impl/konsector.c b/src/impl/konsector.c new file mode 100644 index 0000000..692ca2b --- /dev/null +++ b/src/impl/konsector.c @@ -0,0 +1,2 @@ +#define KONSECTOR_IMPLEMENTATION +#include "konsector.h" |