r_grass.cpp

Go to the documentation of this file.

/*
Copyright (C) 2013-2020 UFO: Alien Invasion.

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_grass.h"

#define GRASS_MARK -956 /* arbitrary number from top of my head -- Sandro */

#define TRIS_PER_CLUMP 10
#define MAX_CLUMPS 2046

#define MAX_CLUMP_TRIS (TRIS_PER_CLUMP * MAX_CLUMPS)

struct Clump {
    int firstTriangle, numTriangles; /* populated only when actual geometry is generated */
    vec3_t position;
    vec3_t normal;
    float rotation;
    int level;
};

static int clumpCount = 0;
static Clump clumps[MAX_CLUMPS];

static int clumpsForLevel[PATHFINDING_HEIGHT] = {0};
static int clumpTrianglesForLevel[PATHFINDING_HEIGHT] = {0};

static int clumpTriangleCount = 0;

/* gfv -- grass fragment vertex */
static vec3_t gfv_pos[MAX_CLUMP_TRIS * 3];
static vec2_t gfv_texcoord[MAX_CLUMP_TRIS * 3];

void R_ClearGrass ()
{
    clumpCount = 0;
    clumpTriangleCount = 0;
    OBJZERO(clumpsForLevel);
    OBJZERO(clumpTrianglesForLevel);
}

static void R_PlantGrass (Clump& clump)
{
    if (clumpTriangleCount + TRIS_PER_CLUMP >= MAX_CLUMP_TRIS) {
        clump.firstTriangle = clumpTriangleCount;
        clump.numTriangles = 0;
        return;
    }

    clump.firstTriangle = clumpTriangleCount;
    clump.numTriangles = 0; /* safeguard */

    vec3_t rot[3]; /* rotation matrix for the plant */
#define xt (rot[0])
#define yt (rot[1])
#define zt (rot[2])

#if 0
    /* horisontal planting */
    VectorSet(xt, 1, 0, 0);
    VectorSet(zt, 0, 0, 1);
#else
    /* normal-based planting */

    /* we can calculate the downslope vector and use it instead;
     * a bit more of math, but call allow us to create plants that interact with the slope in various ways */
    VectorCopy(clump.normal, zt);
    VectorSet(xt, zt[2], 0.0, -zt[0]); /* short-circuit CrossProduct(yaxis, normal, xt) since it degenerates to a simple shuffle */
    VectorNormalizeFast(xt);
#endif

    /* generate geometry */
#if 0
    /* prebuilt mesh or debug grass marker */

    /* randomly rotate plant around the base */
    RotatePointAroundVector(yt, zt, xt, frand() * 360);
    CrossProduct(yt, zt, xt);

    /* randomly mirror the plant, too */
    if (rand() & 1)
        VectorInverse(yt);

    /* marker */
    vec_t* ptr = gfv_pos[clumpTriangleCount * 3];
    VectorMA(clump.position, 1, zt, ptr);
    VectorMA(ptr, 16, yt, ptr + 3);
    VectorMA(ptr, 16, xt, ptr + 6);

    vec_t* texc = gfv_texcoord[clumpTriangleCount * 3];
    Vector2Set(texc, 0, 0);
    Vector2Set(texc + 2, 1, 0);
    Vector2Set(texc + 4, 0, 1);

    clumpTriangleCount++;
#else
    /* programmatically generated clump */
    CrossProduct(zt, xt, yt);
    for (int i = 0; i < TRIS_PER_CLUMP; i += 2) {
        vec3_t sdir, tdir;
        vec2_t sprrot;
        vec3_t tmp;

        sprrot[0] = frand() * 360;
        sprrot[1] = frand() * 60 + 15;

        PolarToVec(sprrot, tmp);
        VectorRotate(rot, tmp, tdir);

        sprrot[0] += 90;
        sprrot[1] = 0;

        PolarToVec(sprrot, tmp);
        VectorRotate(rot, tmp, sdir);
#if 0
        /* debug marker */
        vec_t* ptr = gfv_pos[clumpTriangleCount * 3];
        VectorCopy(clump.position, ptr);
        VectorMA(ptr, 16, sdir, ptr + 3);
        VectorMA(ptr, 16, tdir, ptr + 6);

        vec_t* texc = gfv_texcoord[clumpTriangleCount * 3];
        Vector2Set(texc, 0, 0);
        Vector2Set(texc + 2, 1, 0);
        Vector2Set(texc + 4, 0, 1);

        clumpTriangleCount++;
#else
        /* billboard sprite */
        vec_t* ptr = gfv_pos[clumpTriangleCount * 3];
        VectorCopy(clump.position, ptr);
        VectorMA(clump.position, -24, sdir, ptr); /* quad vertex 0 */
        VectorMA(ptr, 32, tdir, ptr + 3); /* quad vertex 1 */
        VectorMA(ptr + 3, 48, sdir, ptr + 6); /* quad vertex 2 */

        VectorCopy(ptr, ptr + 9); /* quad vertex 0 */
        VectorCopy(ptr + 6, ptr + 12); /* quad vertex 2 */
        VectorMA(ptr + 6, -32, tdir, ptr + 15); /* quad vertex 3 */

        vec_t* texc = gfv_texcoord[clumpTriangleCount * 3];
        Vector2Set(texc, 0, 1);
        Vector2Set(texc + 2, 0, 0);
        Vector2Set(texc + 4, 1, 0);

        Vector2Set(texc + 6, 0, 1);
        Vector2Set(texc + 8, 1, 0);
        Vector2Set(texc + 12, 1, 1);

        clumpTriangleCount += 2;
#endif
    }
#endif

#undef xt
#undef yt
#undef zt
    clump.numTriangles = clumpTriangleCount - clump.firstTriangle;
}

static void R_AddClump (const vec3_t pos, const vec3_t normal, int level)
{
    if (clumpCount >= MAX_CLUMPS)
        return;

    Clump& cp = clumps[clumpCount];

    VectorCopy(pos, cp.position);
    VectorCopy(normal, cp.normal);

    cp.rotation = frand() * 360;
    cp.level = level;

    clumpCount++;
}

static int ClumpOrder (const void* a, const void* b)
{
    const Clump* pa = static_cast <const Clump*>(a);
    const Clump* pb = static_cast <const Clump*>(b);

    if (pa->level != pb->level)
        return pa->level - pb->level;

    return 0;
}

static void R_OrganizeClumps ()
{
    qsort(clumps, clumpCount, sizeof(Clump), ClumpOrder);

    int lastLevel = 0, i;
    for (i = 0; i < clumpCount; i++)
        while (lastLevel < clumps[i].level) {
            clumpsForLevel[lastLevel] = i;
            lastLevel++;
        }

    while (lastLevel < PATHFINDING_HEIGHT) {
        clumpsForLevel[lastLevel] = i;
        lastLevel++;
    }
}

void R_GenerateGrass ()
{
    float density = 1.0f; /* count of clumps per 32x32 unit tile */
    double area = 0.0; /* float does not provide enough mantissa precision for this; also note that area is doubled */

    Com_Printf("Planting grass ...\n");

    /* 1st pass: walk through all brushes and determine which surfaces to use and their total area */
    for (int tile = 0; tile < r_numMapTiles; tile++) {
        /* ignore weaponclip, actorclip and stepon */
        for (int i = 0; i <= LEVEL_LASTVISIBLE; i++) {
            const mBspModel_t* const bspModel = &r_mapTiles[tile]->bsp;
            const mBspHeader_t* const header = &bspModel->submodels[i];

            if (!header->numfaces)
                continue;

            for (int j = 0; j < header->numfaces; j++) {
                mBspSurface_t* const surf = &bspModel->surfaces[header->firstface + j];
                const cBspPlane_t* const plane = surf->plane;

                if (surf->frame == GRASS_MARK)
                    continue; /* already processed it */

                if (!(surf->texinfo->flags & SURF_FOLIAGE))
                    continue; /* not tagged as overgrown */

                if (surf->firstTriangle < 0 || surf->numTriangles == 0)
                    continue; /* no geometry for this surface, skip it */

                /* reject way too inclined or downward facing planes */
                if (plane->normal[2] < 0.5f) /* cutoff angle is 60 degrees */
                    continue;

                /* walk triangle list and sum areas */
                double surfArea = 0.0;

                for (int k = 0; k < surf->numTriangles; k++) {
                    const int vofs = (k + surf->firstTriangle) * 3;
                    const int indo = bspModel->indexes[vofs]  & 0xffff;
                    const int inda = bspModel->indexes[vofs + 1]  & 0xffff;
                    const int indb = bspModel->indexes[vofs + 2] & 0xffff;
                    vec3_t vo, va, vb;
                    vec3_t cross;

                    /* calculate barycentric origin and coordinate axes */
                    VectorCopy(&bspModel->verts[indo * 3], vo);
                    VectorSubtract(&bspModel->verts[inda * 3], vo, va);
                    VectorSubtract(&bspModel->verts[indb * 3], vo, vb);

                    /* calculate area */
                    CrossProduct(va, vb, cross);
                    surfArea += VectorLength(cross);
                }

                if (surfArea < 80.0)
                    continue; /* skip tiny surfaces */

                area += surfArea;
                surf->frame = GRASS_MARK;
            }
        }
    }
    Com_Printf("Total grassy area is %7.0f units (%i cells)\n", area / 2, (int)(area / 2048));

    double areaPerClump = area / MAX_CLUMPS;
    if (areaPerClump < 2048 / (density * density))
        areaPerClump = 2048 / (density * density);

    /* 2nd pass: actually plant the grass */
    double clumpsToPlant = 0.0;
    int planted =  0;

    for (int tile = 0; tile < r_numMapTiles; tile++) {
        /* ignore weaponclip, actorclip and stepon */
        for (int i = 0; i <= LEVEL_LASTVISIBLE; i++) {
            const mBspModel_t* const bspModel = &r_mapTiles[tile]->bsp;
            const mBspHeader_t* const header = &bspModel->submodels[i];

            if (!header->numfaces)
                continue;

            int level;

            for (level = 0; level < PATHFINDING_HEIGHT - 1; level++)
                if (!i || ((1 << level) & i))
                    break;

            for (int j = 0; j < header->numfaces; j++) {
                mBspSurface_t* const surf = &bspModel->surfaces[header->firstface + j];
                const cBspPlane_t* const plane = surf->plane;

                if (surf->frame != GRASS_MARK)
                    continue; /* not suitable for grass or got grass already generated */

                surf->frame--; /* screen from any future stumblings upon it */

                /* walk triangle list and plant grass */
                for (int k = 0; k < surf->numTriangles; k++) {
                    const int vofs = (k + surf->firstTriangle) * 3;
                    const int indo = bspModel->indexes[vofs]  & 0xffff;
                    const int inda = bspModel->indexes[vofs + 1]  & 0xffff;
                    const int indb = bspModel->indexes[vofs + 2] & 0xffff;
                    vec3_t vo, va, vb;
                    vec3_t cross;

                    /* calculate barycentric origin and coordinate axes */
                    VectorCopy(&bspModel->verts[indo * 3], vo);
                    VectorSubtract(&bspModel->verts[inda * 3], vo, va);
                    VectorSubtract(&bspModel->verts[indb * 3], vo, vb);

                    /* calculate area and convert it to clump count */
                    CrossProduct(va, vb, cross);
                    clumpsToPlant += VectorLength(cross) / areaPerClump;

                    while (clumpsToPlant >= 1.0) {
                        /* generate random point within a triangle using barycentic coordinates */
                         float u = frand();
                         float v = frand();

                         /* if barycentric coordinates are outside of triangle, rotate them 180 deg by flipping both coords
                           * explanation: they just got on other half of parallelogram defined by va and vb, which half complements this triangle to said parallelogram
                           */
                         if (u + v > 1.0f) {
                            u = 1.0f - u;
                            v = 1.0f - v;
                         }

                         vec3_t pos;

                         VectorMA(vo, u, va, pos);
                         VectorMA(pos, v, vb, pos);

                         R_AddClump(pos, plane->normal, level);

                         clumpsToPlant -= 1.0;
                         planted++;
                    }
                }
            }
        }
    }

    R_OrganizeClumps();

    for (int i = 0; i < clumpCount; i++)
        R_PlantGrass(clumps[i]);

    if (clumpTriangleCount <= 0) {
        /* no grass geometry generated, so zero triangle counts */
        for (int i = 0; i < PATHFINDING_HEIGHT; i++)
            clumpTrianglesForLevel[i] = 0;
    } else {
        /* generate triangle counts to render the grass in a single OpenGL call */
        int lastClumpCount = 0;
        int triangles = 0;
        for (int i = 0; i < PATHFINDING_HEIGHT; i++) {
            if (clumpsForLevel[i] > lastClumpCount) {
                lastClumpCount = clumpsForLevel[i];
                const Clump& clump = clumps[lastClumpCount - 1];
                triangles = clump.firstTriangle + clump.numTriangles;
            }
            clumpTrianglesForLevel[i] = triangles;
            Com_Printf("%i triangles for level %i (%i clumps)\n", triangles, i + 1, lastClumpCount);
        }
    }

    Com_Printf("Planted %i clumps of grass\n", planted);
}

void R_DrawGrass ()
{
    if (clumpTriangleCount <= 0)
        return;

    R_BindTexture(R_FindImage("models/objects/vegi/plants2/plant_skin3", it_pic)->texnum);

    R_EnableAlphaTest(true);

    R_BindArray(GL_TEXTURE_COORD_ARRAY, GL_FLOAT, gfv_texcoord);
    R_BindArray(GL_VERTEX_ARRAY, GL_FLOAT, gfv_pos);
    glDrawArrays(GL_TRIANGLES, 0, clumpTrianglesForLevel[refdef.worldlevel] * 3);
    R_BindDefaultArray(GL_VERTEX_ARRAY);
    R_BindDefaultArray(GL_TEXTURE_COORD_ARRAY);

    R_EnableAlphaTest(false);

    refdef.batchCount++;
}