r_model_brush.cpp

Go to the documentation of this file.

/*
Copyright (C) 1997-2001 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

#include "r_local.h"
#include "r_lightmap.h"
#include "../../shared/parse.h"
#include "r_light.h"
#include "r_grass.h"

/*
===============================================================================
BRUSHMODEL LOADING
===============================================================================
*/

static const byte* mod_base;
static ipos3_t shift;
static model_t* r_worldmodel;

static void R_ModLoadLighting (const lump_t* l)
{
    /* map has no lightmap */
    if (l->filelen == 0)
        return;

    r_worldmodel->bsp.lightdata  = Mem_PoolAllocTypeN(byte, l->filelen, vid_lightPool);
    r_worldmodel->bsp.lightquant = *(const byte*) (mod_base + l->fileofs);
    memcpy(r_worldmodel->bsp.lightdata, mod_base + l->fileofs, l->filelen);
}

static void R_ModLoadVertexes (const lump_t* l)
{
    const dBspVertex_t* in = (const dBspVertex_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadVertexes: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    mBspVertex_t* out = Mem_PoolAllocTypeN(mBspVertex_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...verts: %i\n", count);

    r_worldmodel->bsp.vertexes = out;
    r_worldmodel->bsp.numvertexes = count;

    for (int i = 0; i < count; i++, in++, out++) {
        out->position[0] = LittleFloat(in->point[0]);
        out->position[1] = LittleFloat(in->point[1]);
        out->position[2] = LittleFloat(in->point[2]);
    }
}

static void R_ModLoadNormals (const lump_t* l)
{
    const dBspNormal_t* in = (const dBspNormal_t*)(mod_base + l->fileofs);
    if (l->filelen % sizeof(*in)) {
        Com_Error(ERR_DROP, "R_LoadNormals: Funny lump size in %s.", r_worldmodel->name);
    }
    int count = l->filelen / sizeof(*in);

    if (count != r_worldmodel->bsp.numvertexes) {  /* ensure sane normals count */
        Com_Error(ERR_DROP, "R_LoadNormals: unexpected normals count in %s: (%d != %d).",
                r_worldmodel->name, count, r_worldmodel->bsp.numvertexes);
    }

    mBspVertex_t* out = r_worldmodel->bsp.vertexes;

    for (int i = 0; i < count; i++, in++, out++) {
        out->normal[0] = LittleFloat(in->normal[0]);
        out->normal[1] = LittleFloat(in->normal[1]);
        out->normal[2] = LittleFloat(in->normal[2]);
    }
}

static inline float R_RadiusFromBounds (const vec3_t mins, const vec3_t maxs)
{
    vec3_t corner;

    for (int i = 0; i < 3; i++)
        corner[i] = fabsf(mins[i]) > fabsf(maxs[i]) ? fabsf(mins[i]) : fabsf(maxs[i]);

    return VectorLength(corner);
}


static void R_ModLoadSubmodels (const lump_t* l)
{
    const dBspModel_t* in = (const dBspModel_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadSubmodels: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    mBspHeader_t* out = Mem_PoolAllocTypeN(mBspHeader_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...submodels: %i\n", count);

    r_worldmodel->bsp.submodels = out;
    r_worldmodel->bsp.numsubmodels = count;

    for (int i = 0; i < count; i++, in++, out++) {
        /* spread the mins / maxs by a pixel */
        for (int j = 0; j < 3; j++) {
            out->hBox.mins[j] = LittleFloat(in->dbmBox.mins[j]) - 1.0f + (float)shift[j];
            out->hBox.maxs[j] = LittleFloat(in->dbmBox.maxs[j]) + 1.0f + (float)shift[j];
            out->origin[j] = LittleFloat(in->origin[j]) + (float)shift[j];
        }
        out->radius = R_RadiusFromBounds(out->hBox.mins, out->hBox.maxs);
        out->headnode = LittleLong(in->headnode);
        out->firstface = LittleLong(in->firstface);
        out->numfaces = LittleLong(in->numfaces);
    }
}

static void R_ModLoadEdges (const lump_t* l)
{
    const dBspEdge_t* in = (const dBspEdge_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadEdges: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    mBspEdge_t* out = Mem_PoolAllocTypeN(mBspEdge_t, count + 1, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...edges: %i\n", count);

    r_worldmodel->bsp.edges = out;
    r_worldmodel->bsp.numedges = count;

    for (int i = 0; i < count; i++, in++, out++) {
        out->v[0] = (unsigned short) LittleShort(in->v[0]);
        out->v[1] = (unsigned short) LittleShort(in->v[1]);
    }
}

static void R_ModLoadTexinfo (const char* mapZone, const lump_t* l)
{
    const dBspTexinfo_t* in = (const dBspTexinfo_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadTexinfo: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    mBspTexInfo_t* out = Mem_PoolAllocTypeN(mBspTexInfo_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...texinfo: %i\n", count);

    r_worldmodel->bsp.texinfo = out;
    r_worldmodel->bsp.numtexinfo = count;

    for (int i = 0; i < count; i++, in++, out++) {
        char name[MAX_QPATH];
        for (int j = 0; j < 3; j++) {
            out->uv[j] = LittleFloat(in->vecs[0][j]);
            out->vv[j] = LittleFloat(in->vecs[1][j]);
        }
        out->u_offset = LittleFloat(in->vecs[0][3]);
        out->v_offset = LittleFloat(in->vecs[1][3]);

        out->flags = LittleLong(in->surfaceFlags);

        /* exchange the textures with the ones that are needed for base assembly */
        if (Q_strvalid(mapZone) && strstr(in->texture, "tex_terrain/dummy"))
            Com_sprintf(name, sizeof(name), "textures/tex_terrain/%s", mapZone);
        else
            Com_sprintf(name, sizeof(name), "textures/%s", in->texture);

        out->image = R_FindImage(name, it_world);
    }
}

static void R_SetSurfaceExtents (mBspSurface_t* surf, const model_t* mod)
{
    vec3_t mins, maxs;
    vec2_t stmins, stmaxs;
    int i;
    const mBspTexInfo_t* tex;

    VectorSet(mins, 999999, 999999, 999999);
    VectorSet(maxs, -999999, -999999, -999999);

    Vector2Set(stmins, 999999, 999999);
    Vector2Set(stmaxs, -999999, -999999);

    tex = surf->texinfo;

    for (i = 0; i < surf->numedges; i++) {
        const int e = mod->bsp.surfedges[surf->firstedge + i];
        const mBspVertex_t* v;
        vec3_t position;
        if (e >= 0)
            v = &mod->bsp.vertexes[mod->bsp.edges[e].v[0]];
        else
            v = &mod->bsp.vertexes[mod->bsp.edges[-e].v[1]];

        VectorCopy(v->position, position);

        for (int j = 0; j < 3; j++) {  /* calculate mins, maxs */
            position[j] += (float)shift[j];
            if (position[j] > maxs[j])
                maxs[j] = position[j];
            if (position[j] < mins[j])
                mins[j] = position[j];
        }

        {  /* calculate stmins, stmaxs */
            const float valS = DotProduct(v->position, tex->uv) + tex->u_offset;
            const float valT = DotProduct(v->position, tex->vv) + tex->v_offset;
            stmins[0] = std::min(valS, stmins[0]);
            stmaxs[0] = std::max(valS, stmaxs[0]);
            stmins[1] = std::min(valT, stmins[1]);
            stmaxs[1] = std::max(valT, stmaxs[1]);
        }
    }

    surf->mbsBox.set(mins, maxs);
    surf->mbsBox.getCenter(surf->center);

    for (i = 0; i < 2; i++) {
        const int bmins = floor(stmins[i] / surf->lightmap_scale);
        const int bmaxs = ceil(stmaxs[i] / surf->lightmap_scale);

        surf->stmins[i] = bmins * surf->lightmap_scale;
        surf->stmaxs[i] = bmaxs * surf->lightmap_scale;

        surf->stcenter[i] = (surf->stmaxs[i] + surf->stmins[i]) / 2.0;
        surf->stextents[i] = (bmaxs - bmins) * surf->lightmap_scale;
    }
}

static void R_ModLoadSurfaces (bool day, const lump_t* l)
{
    const dBspSurface_t* in = (const dBspSurface_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadSurfaces: funny lump size in %s", r_worldmodel->name);
    int count = l->filelen / sizeof(*in);
    mBspSurface_t* out = Mem_PoolAllocTypeN(mBspSurface_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...faces: %i\n", count);

    r_worldmodel->bsp.surfaces = out;
    r_worldmodel->bsp.numsurfaces = count;

    for (int surfnum = 0; surfnum < count; surfnum++, in++, out++) {
        uint16_t planenum;
        int16_t side;
        int ti;
        int i;

        out->firstedge = LittleLong(in->firstedge);
        out->numedges = LittleShort(in->numedges);

        /* resolve plane */
        planenum = LittleShort(in->planenum);
        out->plane = r_worldmodel->bsp.planes + planenum;

        /* and sideness */
        side = LittleShort(in->side);
        if (side) {
            out->flags |= MSURF_PLANEBACK;
            VectorNegate(out->plane->normal, out->normal);
        } else {
            VectorCopy(out->plane->normal, out->normal);
        }

        ti = LittleShort(in->texinfo);
        if (ti < 0 || ti >= r_worldmodel->bsp.numtexinfo)
            Com_Error(ERR_DROP, "R_ModLoadSurfaces: bad texinfo number");
        out->texinfo = r_worldmodel->bsp.texinfo + ti;

        out->lightmap_scale = (1 << r_worldmodel->bsp.lightquant);

        /* and size, texcoords, etc */
        R_SetSurfaceExtents(out, r_worldmodel);

        if (!(out->texinfo->flags & SURF_WARP))
            out->flags |= MSURF_LIGHTMAP;

        /* lastly lighting info */
        if (day)
            i = LittleLong(in->lightofs[LIGHTMAP_DAY]);
        else
            i = LittleLong(in->lightofs[LIGHTMAP_NIGHT]);

        if (i == -1)
            out->samples = nullptr;
        else
            out->samples = r_worldmodel->bsp.lightdata + i;

        /* create lightmaps */
        R_CreateSurfaceLightmap(out);

        out->tile = r_numMapTiles - 1;
    }
}

static void R_ModLoadNodes (const lump_t* l)
{
    const dBspNode_t* in = (const dBspNode_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadNodes: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    mBspNode_t* out = Mem_PoolAllocTypeN(mBspNode_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...nodes: %i\n", count);

    r_worldmodel->bsp.nodes = out;
    r_worldmodel->bsp.numnodes = count;

    mBspNode_t* parent = nullptr;
    for (int i = 0; i < count; i++, in++, out++) {
        int j;
        const int p = LittleLong(in->planenum);

        /* skip special pathfinding nodes - they have a negative index */
        if (p == PLANENUM_LEAF) {
            /* in case of "special" pathfinding nodes (they don't have a plane)
             * we have to set this to nullptr */
            out->plane = nullptr;
            out->contents = CONTENTS_PATHFINDING_NODE;
            parent = nullptr;
        } else {
            out->plane = r_worldmodel->bsp.planes + p;
            /* differentiate from leafs */
            out->contents = CONTENTS_NODE;
            parent = out;
        }

        for (j = 0; j < 3; j++) {
            out->minmaxs.mins[j] = LittleShort(in->mins[j]) + (float)shift[j];
            out->minmaxs.maxs[j] = LittleShort(in->maxs[j]) + (float)shift[j];
        }

        out->firstsurface = LittleShort(in->firstface);
        out->numsurfaces = LittleShort(in->numfaces);

        for (j = 0; j < 2; j++) {
            const int p2 = LittleLong(in->children[j]);
            if (p2 > LEAFNODE) {
                assert(p2 < r_worldmodel->bsp.numnodes);
                out->children[j] = r_worldmodel->bsp.nodes + p2;
            } else {
                assert((LEAFNODE - p2) < r_worldmodel->bsp.numleafs);
                out->children[j] = (mBspNode_t*) (r_worldmodel->bsp.leafs + (LEAFNODE - p2));
            }
            out->children[j]->parent = parent;
        }
    }
}

static void R_ModLoadLeafs (const lump_t* l)
{
    const dBspLeaf_t* in = (const dBspLeaf_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadLeafs: funny lump size in %s", r_worldmodel->name);
    const int count = l->filelen / sizeof(*in);
    mBspLeaf_t* out = Mem_PoolAllocTypeN(mBspLeaf_t, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...leafs: %i\n", count);

    r_worldmodel->bsp.leafs = out;
    r_worldmodel->bsp.numleafs = count;

    for (int i = 0; i < count; i++, in++, out++) {
        for (int j = 0; j < 3; j++) {
            out->minmaxs.mins[j] = LittleShort(in->mins[j]) + (float)shift[j];
            out->minmaxs.maxs[j] = LittleShort(in->maxs[j]) + (float)shift[j];
        }

        out->contents = LittleLong(in->contentFlags);
    }
}

static void R_ModLoadSurfedges (const lump_t* l)
{
    const int* in = (const int*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadSurfedges: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    if (count < 1 || count >= MAX_MAP_SURFEDGES)
        Com_Error(ERR_DROP, "R_ModLoadSurfedges: bad surfedges count in %s: %i", r_worldmodel->name, count);

    int* const out = Mem_PoolAllocTypeN(int, count, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...surface edges: %i\n", count);

    r_worldmodel->bsp.surfedges = out;
    r_worldmodel->bsp.numsurfedges = count;

    for (int i = 0; i < count; i++)
        out[i] = LittleLong(in[i]);
}

static void R_ModLoadPlanes (const lump_t* l)
{
    const dBspPlane_t* in = (const dBspPlane_t*) (mod_base + l->fileofs);
    if (l->filelen % sizeof(*in))
        Com_Error(ERR_DROP, "R_ModLoadPlanes: funny lump size in %s", r_worldmodel->name);

    int count = l->filelen / sizeof(*in);
    cBspPlane_t* out = Mem_PoolAllocTypeN(cBspPlane_t, count * 2, vid_modelPool);
    Com_DPrintf(DEBUG_RENDERER, "...planes: %i\n", count);

    r_worldmodel->bsp.planes = out;
    r_worldmodel->bsp.numplanes = count;

    for (int i = 0; i < count; i++, in++, out++) {
        for (int j = 0; j < 3; j++)
            out->normal[j] = LittleFloat(in->normal[j]);
        out->dist = LittleFloat(in->dist);
        out->type = LittleLong(in->type);
    }
}

static void R_ModShiftTile (void)
{
    mBspVertex_t* vert;
    cBspPlane_t* plane;
    int i, j;

    /* we can't do this instantly, because of rounding errors on extents calculation */
    /* shift vertexes */
    for (i = 0, vert = r_worldmodel->bsp.vertexes; i < r_worldmodel->bsp.numvertexes; i++, vert++)
        for (j = 0; j < 3; j++)
            vert->position[j] += shift[j];

    /* shift planes */
    for (i = 0, plane = r_worldmodel->bsp.planes; i < r_worldmodel->bsp.numplanes; i++, plane++)
        for (j = 0; j < 3; j++)
            plane->dist += plane->normal[j] * shift[j];
}

static void R_LoadBspVertexArrays (model_t* mod)
{
    int i;
    int vertOfs, texCoordOfs, tangOfs;
    float* vecShifted;
    float soff, toff, s, t;
    float* point, *sdir, *tdir;
    vec4_t tangent;
    vec3_t binormal;
    mBspSurface_t* surf;
    mBspVertex_t* vert;
    int vertexCount, indexCount;

    vertOfs = texCoordOfs = tangOfs = 0;
    vertexCount = indexCount = 0;

    for (i = 0, surf = mod->bsp.surfaces; i < mod->bsp.numsurfaces; i++, surf++) {
        const int numedges = surf->numedges;
        vertexCount += numedges;
        if (numedges > 2) /* no triangles for degenerate polys */
            indexCount += (numedges - 2) * 3;
    }

    surf = mod->bsp.surfaces;

    /* allocate the vertex arrays */
    mod->bsp.texcoords   = Mem_PoolAllocTypeN(GLfloat, vertexCount * 2, vid_modelPool);
    mod->bsp.lmtexcoords = Mem_PoolAllocTypeN(GLfloat, vertexCount * 2, vid_modelPool);
    mod->bsp.verts       = Mem_PoolAllocTypeN(GLfloat, vertexCount * 3, vid_modelPool);
    mod->bsp.normals     = Mem_PoolAllocTypeN(GLfloat, vertexCount * 3, vid_modelPool);
    mod->bsp.tangents    = Mem_PoolAllocTypeN(GLfloat, vertexCount * 4, vid_modelPool);
    mod->bsp.indexes     = Mem_PoolAllocTypeN(glElementIndex_t, indexCount, vid_modelPool); /* Will be filled at the end of map loading, after building surface lists */

    for (i = 0; i < mod->bsp.numsurfaces; i++, surf++) {
        surf->index = vertOfs / 3;
        surf->firstTriangle = -1; /* Mark as "no triangles generated yet" */

        for (int j = 0; j < surf->numedges; j++) {
            const float* normal;
            const int index = mod->bsp.surfedges[surf->firstedge + j];

            /* vertex */
            if (index > 0) {  /* negative indices to differentiate which end of the edge */
                const mBspEdge_t* edge = &mod->bsp.edges[index];
                vert = &mod->bsp.vertexes[edge->v[0]];
            } else {
                const mBspEdge_t* edge = &mod->bsp.edges[-index];
                vert = &mod->bsp.vertexes[edge->v[1]];
            }

            point = vert->position;

            /* shift it for assembled maps */
            vecShifted = &mod->bsp.verts[vertOfs];
            /* origin (func_door, func_rotating) bmodels must not have shifted vertices,
             * they are translated by their entity origin value */
            if (surf->isOriginBrushModel)
                VectorCopy(point, vecShifted);
            else
                VectorAdd(point, shift, vecShifted);

            /* texture directional vectors and offsets */
            sdir = surf->texinfo->uv;
            soff = surf->texinfo->u_offset;

            tdir = surf->texinfo->vv;
            toff = surf->texinfo->v_offset;

            /* texture coordinates */
            s = DotProduct(point, sdir) + soff;
            s /= surf->texinfo->image->width;

            t = DotProduct(point, tdir) + toff;
            t /= surf->texinfo->image->height;

            mod->bsp.texcoords[texCoordOfs + 0] = s;
            mod->bsp.texcoords[texCoordOfs + 1] = t;

            if (surf->flags & MSURF_LIGHTMAP) {  /* lightmap coordinates */
                s = DotProduct(point, sdir) + soff;
                s -= surf->stmins[0];
                s += surf->light_s*  surf->lightmap_scale;
                s += surf->lightmap_scale / 2.0;
                s /= r_lightmaps.size * surf->lightmap_scale;

                t = DotProduct(point, tdir) + toff;
                t -= surf->stmins[1];
                t += surf->light_t*  surf->lightmap_scale;
                t += surf->lightmap_scale / 2.0;
                t /= r_lightmaps.size * surf->lightmap_scale;
            }

            mod->bsp.lmtexcoords[texCoordOfs + 0] = s;
            mod->bsp.lmtexcoords[texCoordOfs + 1] = t;

            /* normal vectors */
            if ((surf->texinfo->flags & SURF_PHONG) && VectorNotEmpty(vert->normal))
                normal = vert->normal; /* phong shaded */
            else
                normal = surf->normal; /* per plane */

            memcpy(&mod->bsp.normals[vertOfs], normal, sizeof(vec3_t));

            /* tangent vector */
            TangentVectors(normal, sdir, tdir, tangent, binormal);
            memcpy(&mod->bsp.tangents[tangOfs], tangent, sizeof(vec4_t));

            vertOfs += 3;
            texCoordOfs += 2;
            tangOfs += 4;
        }
    }

    R_ReallocateStateArrays(vertOfs / 3);

    if (qglBindBuffer) {
        /* and also the vertex buffer objects */
        qglGenBuffers(1, &mod->bsp.vertex_buffer);
        qglBindBuffer(GL_ARRAY_BUFFER, mod->bsp.vertex_buffer);
        qglBufferData(GL_ARRAY_BUFFER, vertOfs * sizeof(GLfloat), mod->bsp.verts, GL_STATIC_DRAW);

        qglGenBuffers(1, &mod->bsp.texcoord_buffer);
        qglBindBuffer(GL_ARRAY_BUFFER, mod->bsp.texcoord_buffer);
        qglBufferData(GL_ARRAY_BUFFER, texCoordOfs * sizeof(GLfloat), mod->bsp.texcoords, GL_STATIC_DRAW);

        qglGenBuffers(1, &mod->bsp.lmtexcoord_buffer);
        qglBindBuffer(GL_ARRAY_BUFFER, mod->bsp.lmtexcoord_buffer);
        qglBufferData(GL_ARRAY_BUFFER, texCoordOfs * sizeof(GLfloat), mod->bsp.lmtexcoords, GL_STATIC_DRAW);

        qglGenBuffers(1, &mod->bsp.normal_buffer);
        qglBindBuffer(GL_ARRAY_BUFFER, mod->bsp.normal_buffer);
        qglBufferData(GL_ARRAY_BUFFER, vertOfs * sizeof(GLfloat), mod->bsp.normals, GL_STATIC_DRAW);

        qglGenBuffers(1, &mod->bsp.tangent_buffer);
        qglBindBuffer(GL_ARRAY_BUFFER, mod->bsp.tangent_buffer);
        qglBufferData(GL_ARRAY_BUFFER, tangOfs * sizeof(GLfloat), mod->bsp.tangents, GL_STATIC_DRAW);

        qglBindBuffer(GL_ARRAY_BUFFER, 0);
    }
}

static void R_SortSurfacesArrays_ (mBspSurfaces_t* surfs, mBspSurfaces_t** r_sorted_surfaces)
{
    int i;

    for (i = 0; i < surfs->count; i++) {
        const int texindex = R_GetImageIndex(surfs->surfaces[i]->texinfo->image);
        if (texindex < 0 || texindex >= MAX_GL_TEXTURES)
            Com_Error(ERR_FATAL, "R_SortSurfacesArrays: bogus image pointer");
        R_AddSurfaceToArray(r_sorted_surfaces[texindex], surfs->surfaces[i]);
    }

    surfs->count = 0;

    for (i = 0; i < r_numImages; i++) {
        mBspSurfaces_t* sorted = r_sorted_surfaces[i];
        if (sorted && sorted->count) {
            for (int j = 0; j < sorted->count; j++)
                R_AddSurfaceToArray(surfs, sorted->surfaces[j]);

            sorted->count = 0;
        }
    }
}

static void R_SortSurfacesArrays (const model_t* mod)
{
    const mBspSurface_t* surf, *s;
    int i, ns;
    mBspSurfaces_t** r_sorted_surfaces = Mem_AllocTypeN(mBspSurfaces_t* , r_numImages);

    /* resolve the start surface and total surface count */
    s = &mod->bsp.surfaces[mod->bsp.firstmodelsurface];
    ns = mod->bsp.nummodelsurfaces;

    /* allocate the per-texture surfaces arrays and determine counts */
    for (i = 0, surf = s; i < ns; i++, surf++) {
        int index = R_GetImageIndex(surf->texinfo->image);
        mBspSurfaces_t* surfs = r_sorted_surfaces[index];
        if (!surfs) {  /* allocate it */
            surfs = Mem_PoolAllocType(mBspSurfaces_t, vid_modelPool);
            r_sorted_surfaces[index] = surfs;
        }

        surfs->count++;
    }

    /* allocate the surfaces pointers based on counts */
    for (i = 0; i < r_numImages; i++) {
        mBspSurfaces_t* surfs = r_sorted_surfaces[i];
        if (surfs) {
            surfs->surfaces = Mem_PoolAllocTypeN(mBspSurface_t*, surfs->count, vid_modelPool);
            surfs->count = 0;
        }
    }

    /* sort the model's surfaces arrays into the per-texture arrays */
    for (i = 0; i < NUM_SURFACES_ARRAYS; i++) {
        if (mod->bsp.sorted_surfaces[i]->count) {
            R_SortSurfacesArrays_(mod->bsp.sorted_surfaces[i], r_sorted_surfaces);
            Com_DPrintf(DEBUG_RENDERER, "%i: #%i surfaces\n", i, mod->bsp.sorted_surfaces[i]->count);
        }
    }

    /* free the per-texture surfaces arrays */
    for (i = 0; i < r_numImages; i++) {
        mBspSurfaces_t* surfs = r_sorted_surfaces[i];
        if (surfs) {
            Mem_Free(surfs->surfaces);
            Mem_Free(surfs);
        }
    }

    Mem_Free(r_sorted_surfaces);
}

static void R_LoadSurfacesArrays_ (model_t* mod)
{
    mBspSurface_t* surf, *s;
    int i, ns;

    /* allocate the surfaces array structures */
    for (i = 0; i < NUM_SURFACES_ARRAYS; i++)
        mod->bsp.sorted_surfaces[i] = Mem_PoolAllocType(mBspSurfaces_t, vid_modelPool);

    /* resolve the start surface and total surface count */
    s = &mod->bsp.surfaces[mod->bsp.firstmodelsurface];
    ns = mod->bsp.nummodelsurfaces;

    /* determine the maximum counts for each rendered type in order to
     * allocate only what is necessary for the specified model */
    for (i = 0, surf = s; i < ns; i++, surf++) {
        const mBspTexInfo_t* texinfo = surf->texinfo;
        const material_t* material = &texinfo->image->material;
        if (texinfo->flags & (SURF_BLEND33 | SURF_BLEND66)) {
            if (texinfo->flags & SURF_WARP)
                mod->bsp.blend_warp_surfaces->count++;
            else
                mod->bsp.blend_surfaces->count++;
        } else {
            if (texinfo->flags & SURF_WARP)
                mod->bsp.opaque_warp_surfaces->count++;
            else if (texinfo->flags & SURF_ALPHATEST)
                mod->bsp.alpha_test_surfaces->count++;
            else
                mod->bsp.opaque_surfaces->count++;
        }

        if (material->flags & STAGE_RENDER)
            mod->bsp.material_surfaces->count++;

        if (material->flags & STAGE_FLARE)
            mod->bsp.flare_surfaces->count++;
    }

    /* allocate the surfaces pointers based on the counts */
    for (i = 0; i < NUM_SURFACES_ARRAYS; i++) {
        mBspSurfaces_t* surfaces = mod->bsp.sorted_surfaces[i];
        if (surfaces->count) {
            surfaces->surfaces = Mem_PoolAllocTypeN(mBspSurface_t*, surfaces->count, vid_modelPool);
            surfaces->count = 0;
        }
    }

    /* iterate the surfaces again, populating the allocated arrays based
     * on primary render type */
    for (i = 0, surf = s; i < ns; i++, surf++) {
        const mBspTexInfo_t* texinfo = surf->texinfo;
        const material_t* material = &texinfo->image->material;
        if (texinfo->flags & (SURF_BLEND33 | SURF_BLEND66)) {
            if (texinfo->flags & SURF_WARP)
                R_AddSurfaceToArray(mod->bsp.blend_warp_surfaces, surf);
            else
                R_AddSurfaceToArray(mod->bsp.blend_surfaces, surf);
        } else {
            if (texinfo->flags & SURF_WARP)
                R_AddSurfaceToArray(mod->bsp.opaque_warp_surfaces, surf);
            else if (texinfo->flags & SURF_ALPHATEST)
                R_AddSurfaceToArray(mod->bsp.alpha_test_surfaces, surf);
            else
                R_AddSurfaceToArray(mod->bsp.opaque_surfaces, surf);
        }

        if (material->flags & STAGE_RENDER)
            R_AddSurfaceToArray(mod->bsp.material_surfaces, surf);

        if (material->flags & STAGE_FLARE)
            R_AddSurfaceToArray(mod->bsp.flare_surfaces, surf);
    }

    /* now sort them by texture */
    R_SortSurfacesArrays(mod);
}

static void R_LoadSurfacesArrays (void)
{
    int i;

    for (i = 0; i < r_numMapTiles; i++)
        R_LoadSurfacesArrays_(r_mapTiles[i]);

    for (i = 0; i < r_numModelsInline; i++)
        R_LoadSurfacesArrays_(&r_modelsInline[i]);
}

static int totalBspTriangles;

static void R_GenerateTriangleSoup_ (model_t* mod)
{
    mBspModel_t* bsp = &mod->bsp; /* can be aliased with baseTile, so beware */
    mBspModel_t* baseTile = &r_mapTiles[bsp->maptile]->bsp; 
    int tris = 0;

    Com_DPrintf(DEBUG_RENDERER, "Soup: model %i/%i\n", bsp->maptile, bsp->firstmodelsurface);

    for (int i = 0; i < NUM_SURFACES_ARRAYS; i++) {
        mBspSurfaces_t* surfaces = mod->bsp.sorted_surfaces[i];

        for (int j = 0; j < surfaces->count; j++) {
            mBspSurface_t* surf = surfaces->surfaces[j];

            if (surf->firstTriangle >= 0)
                continue; /* Already allocated */

            surf->firstTriangle = baseTile->numIndexes / 3;

            if (surf->numedges <= 2) {
                /* degenerate poly, no triangles */
                surf->numTriangles = 0;
            } else {
                /* Build triangle list for this surface */
                int numTris = surf->numedges - 2;
                surf->numTriangles = numTris;
                for (int k = 0; k < numTris; k++) {
                    /* k'th element of triangle fan */
                    baseTile->indexes[baseTile->numIndexes++] = surf->index;
                    baseTile->indexes[baseTile->numIndexes++] = surf->index + k + 1;
                    baseTile->indexes[baseTile->numIndexes++] = surf->index + k + 2;
                    tris++;
                }
            }
        }
    }

    totalBspTriangles += tris;
    Com_DPrintf(DEBUG_RENDERER, "                  surfs: %i tris: %i\n", bsp->nummodelsurfaces, tris);
}

static void R_GenerateTriangleSoup ()
{
    int i;

    totalBspTriangles = 0;

    for (i = 0; i < r_numMapTiles; i++)
        R_GenerateTriangleSoup_(r_mapTiles[i]);

    for (i = 0; i < r_numModelsInline; i++)
        R_GenerateTriangleSoup_(&r_modelsInline[i]);

    Com_Printf("World model: %i triangles\n", totalBspTriangles);

    /* Create buffer objects for indexes */
    if (qglBindBuffer) {
        for (i = 0; i < r_numMapTiles; i++) {
            mBspModel_t* bsp = &r_mapTiles[i]->bsp;

            qglGenBuffers(1, &bsp->index_buffer);
            qglBindBuffer(GL_ELEMENT_ARRAY_BUFFER, bsp->index_buffer);
            qglBufferData(GL_ELEMENT_ARRAY_BUFFER, bsp->numIndexes * sizeof(glElementIndex_t), bsp->indexes, GL_STATIC_DRAW);
        }

        qglBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
    }
}

static void R_SetModel (mBspNode_t* node, model_t* mod)
{
    node->model = mod;

    if (node->contents > CONTENTS_NODE)
        return;

    R_SetModel(node->children[0], mod);
    R_SetModel(node->children[1], mod);
}


static void R_RecursiveSetModel (mBspNode_t* node, model_t* mod)
{
    /* skip special pathfinding nodes */
    if (node->contents == CONTENTS_PATHFINDING_NODE) {
        R_RecursiveSetModel(node->children[0], mod);
        R_RecursiveSetModel(node->children[1], mod);
    } else {
        R_SetModel(node, mod);
    }
}

static void R_SetupSubmodels (void)
{
    int i, j;

    /* set up the submodels, the first 255 submodels are the models of the
     * different levels, don't care about them */
    for (i = NUM_REGULAR_MODELS; i < r_worldmodel->bsp.numsubmodels; i++) {
        model_t* mod = &r_modelsInline[r_numModelsInline];
        const mBspHeader_t* sub = &r_worldmodel->bsp.submodels[i];

        /* copy most info from world */
        *mod = *r_worldmodel;
        mod->type = mod_bsp_submodel;

        Com_sprintf(mod->name, sizeof(mod->name), "*%d", i);

        /* copy the rest from the submodel */
        mod->modBox.set(sub->hBox);
        mod->radius = sub->radius;

        mod->bsp.firstnode = sub->headnode;
        mod->bsp.nodes = &r_worldmodel->bsp.nodes[mod->bsp.firstnode];
        mod->bsp.maptile = r_numMapTiles - 1;
        if (mod->bsp.firstnode >= r_worldmodel->bsp.numnodes)
            Com_Error(ERR_DROP, "R_SetupSubmodels: Inline model %i has bad firstnode", i);

        R_RecursiveSetModel(mod->bsp.nodes, mod);

        mod->bsp.firstmodelsurface = sub->firstface;
        mod->bsp.nummodelsurfaces = sub->numfaces;

        /* submodel vertices of the surfaces must not be shifted in case of rmas */
        for (j = mod->bsp.firstmodelsurface; j < mod->bsp.firstmodelsurface + mod->bsp.nummodelsurfaces; j++) {
            mod->bsp.surfaces[j].isOriginBrushModel = (mod->bsp.surfaces[j].texinfo->flags & SURF_ORIGIN);
        }

        /*mod->bsp.numleafs = sub->visleafs;*/
        r_numModelsInline++;
    }
}

static void R_SetupWorldModel (void)
{
    int surfCount = r_worldmodel->bsp.numsurfaces;

#ifdef DEBUG
    /* validate surface allocation by submodels by checking the surface array range they are using */
    /* start with inverted range to simplify code */
    int first = surfCount, last = -1; /* @note range is [,) */
    /* first NUM_REGULAR_MODELS submodels are the models of the different levels, don't care about them */
    for (int i = NUM_REGULAR_MODELS; i < r_worldmodel->bsp.numsubmodels; i++) {
        const mBspHeader_t* sub = &r_worldmodel->bsp.submodels[i];
        int firstFace = sub->firstface;
        int lastFace = firstFace + sub->numfaces;

        if (lastFace <= firstFace)
            continue; /* empty submodel, ignore it */

        if (last >= 0 && (firstFace > last || lastFace < first))
            Com_Printf("Warning: submodels may not combine to contigous range in the surface array, some world geometry could be missing as a result (submodel %i)\n", i);

        if (firstFace < first)
            first = firstFace;

        if (lastFace > last)
            last = lastFace;

        Com_DPrintf(DEBUG_RENDERER, "Submodel %i, range %i..%i\n", i, firstFace, lastFace - 1);
    }
    surfCount = first;

    if (last >= 0 && last != r_worldmodel->bsp.numsurfaces)
        Com_Printf("Warning: %i surfaces are lost, some world geometry could be missing as a result\n", r_worldmodel->bsp.numsurfaces - last);
#else
    /* take a shortcut: assume that first submodel surfaces begin exactly after world model ones */
    if (NUM_REGULAR_MODELS < r_worldmodel->bsp.numsubmodels)
        surfCount = r_worldmodel->bsp.submodels[NUM_REGULAR_MODELS].firstface;
#endif
    Com_DPrintf(DEBUG_RENDERER, "World model, range 0..%i\n", surfCount - 1);

    r_worldmodel->bsp.firstmodelsurface = 0;
    r_worldmodel->bsp.nummodelsurfaces = surfCount;
}

static void R_ModAddMapTile (const char* name, const char* mapZone, bool day, int sX, int sY, int sZ)
{
    int i;
    byte* buffer;
    dBspHeader_t* header;
    const int lightingLump = day ? LUMP_LIGHTING_DAY : LUMP_LIGHTING_NIGHT;

    if (r_numMapTiles < 0 || r_numMapTiles >= MAX_MAPTILES)
        Com_Error(ERR_DROP, "R_ModAddMapTile: Too many map tiles");

    /* alloc model and tile */
    r_worldmodel = R_AllocModelSlot();
    r_mapTiles[r_numMapTiles++] = r_worldmodel;
    OBJZERO(*r_worldmodel);
    Com_sprintf(r_worldmodel->name, sizeof(r_worldmodel->name), "maps/%s.bsp", name);

    /* load the file */
    FS_LoadFile(r_worldmodel->name, &buffer);
    if (!buffer)
        Com_Error(ERR_DROP, "R_ModAddMapTile: %s not found", r_worldmodel->name);

    /* init */
    r_worldmodel->type = mod_bsp;
    r_worldmodel->bsp.maptile = r_numMapTiles - 1;

    /* prepare shifting */
    VectorSet(shift, sX * UNIT_SIZE, sY * UNIT_SIZE, sZ * UNIT_SIZE);

    /* test version */
    header = (dBspHeader_t*) buffer;
    i = LittleLong(header->version);
    if (i != BSPVERSION)
        Com_Error(ERR_DROP, "R_ModAddMapTile: %s has wrong version number (%i should be %i)", r_worldmodel->name, i, BSPVERSION);

    /* swap all the lumps */
    mod_base = (byte*) header;

    BSP_SwapHeader(header, r_worldmodel->name);

    /* load into heap */
    R_ModLoadVertexes(&header->lumps[LUMP_VERTEXES]);
    R_ModLoadNormals(&header->lumps[LUMP_NORMALS]);
    R_ModLoadEdges(&header->lumps[LUMP_EDGES]);
    R_ModLoadSurfedges(&header->lumps[LUMP_SURFEDGES]);
    R_ModLoadLighting(&header->lumps[lightingLump]);
    R_ModLoadPlanes(&header->lumps[LUMP_PLANES]);
    R_ModLoadTexinfo(mapZone, &header->lumps[LUMP_TEXINFO]);
    R_ModLoadSurfaces(day, &header->lumps[LUMP_FACES]);
    R_ModLoadLeafs(&header->lumps[LUMP_LEAFS]);
    R_ModLoadNodes(&header->lumps[LUMP_NODES]);
    R_ModLoadSubmodels(&header->lumps[LUMP_MODELS]);

    R_SetupSubmodels();
    R_SetupWorldModel();

    R_LoadBspVertexArrays(r_worldmodel);

    /* in case of random map assembly shift some vectors */
    if (VectorNotEmpty(shift))
        R_ModShiftTile();

    FS_FreeFile(buffer);
}

static void R_ModEndLoading (const char* mapName)
{
    R_EndBuildingLightmaps();
    R_LoadMaterials(mapName);
    R_LoadSurfacesArrays();
    R_GenerateTriangleSoup();
    R_GenerateGrass();
}

void R_ModBeginLoading (const char* tiles, bool day, const char* pos, const char* mapName, const char* mapZone)
{
    char name[MAX_VAR];
    char base[MAX_QPATH];

    assert(mapName);

    /* clear any lights leftover in the active list from previous maps */
    R_ClearStaticLights();
    /* remove all leftover grass */
    R_ClearGrass();

    /* init */
    R_BeginBuildingLightmaps();
    r_numModelsInline = 0;
    r_numMapTiles = 0;

    /* load tiles */
    while (tiles) {
        /* get tile name */
        const char* token = Com_Parse(&tiles);
        if (!tiles) {
            /* finish */
            R_ModEndLoading(mapName);
            return;
        }

        /* get base path */
        if (token[0] == '-') {
            Q_strncpyz(base, token + 1, sizeof(base));
            continue;
        }

        /* get tile name */
        if (token[0] == '+')
            Com_sprintf(name, sizeof(name), "%s%s", base, token + 1);
        else
            Q_strncpyz(name, token, sizeof(name));

        if (pos && pos[0]) {
            ipos3_t sh;
            /* get grid position and add a tile */
            for (int i = 0; i < 3; i++) {
                token = Com_Parse(&pos);
                if (!pos)
                    Com_Error(ERR_DROP, "R_ModBeginLoading: invalid positions\n");
                sh[i] = atoi(token);
            }
            if (sh[0] <= -(PATHFINDING_WIDTH / 2) || sh[0] >= PATHFINDING_WIDTH / 2)
                Com_Error(ERR_DROP, "R_ModBeginLoading: invalid x position given: %i\n", sh[0]);
            if (sh[1] <= -(PATHFINDING_WIDTH / 2) || sh[1] >= PATHFINDING_WIDTH / 2)
                Com_Error(ERR_DROP, "R_ModBeginLoading: invalid y position given: %i\n", sh[1]);
            if (sh[2] >= PATHFINDING_HEIGHT)
                Com_Error(ERR_DROP, "R_ModBeginLoading: invalid z position given: %i\n", sh[2]);
            R_ModAddMapTile(name, mapZone, day, sh[0], sh[1], sh[2]);
        } else {
            /* load only a single tile, if no positions are specified */
            R_ModAddMapTile(name, mapZone, day, 0, 0, 0);
            R_ModEndLoading(mapName);
            return;
        }
    }

    Com_Error(ERR_DROP, "R_ModBeginLoading: invalid tile names\n");
}

void R_ModReloadSurfacesArrays (void)
{
    for (int i = 0; i < r_numMapTiles; i++) {
        model_t* mod = r_mapTiles[i];
        const size_t size = lengthof(mod->bsp.sorted_surfaces);
        for (int j = 0; j < size; j++)
            if (mod->bsp.sorted_surfaces[j]) {
                Mem_Free(mod->bsp.sorted_surfaces[j]);
                mod->bsp.sorted_surfaces[j] = nullptr;
            }
    }
    R_LoadSurfacesArrays();
}