source: ps/trunk/source/renderer/SilhouetteRenderer.cpp@ 25266

/* Copyright (C) 2021 Wildfire Games.
 * This file is part of 0 A.D.
 *
 * 0 A.D. 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.
 *
 * 0 A.D. 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 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "precompiled.h"

#include "SilhouetteRenderer.h"

#include "graphics/Camera.h"
#include "graphics/HFTracer.h"
#include "graphics/Model.h"
#include "graphics/Patch.h"
#include "graphics/ShaderManager.h"
#include "maths/MathUtil.h"
#include "ps/Profile.h"
#include "renderer/Renderer.h"
#include "renderer/Scene.h"

#include <cfloat>

extern int g_xres, g_yres;

// For debugging
static const bool g_DisablePreciseIntersections = false;

SilhouetteRenderer::SilhouetteRenderer()
{
    m_DebugEnabled = false;
}

void SilhouetteRenderer::AddOccluder(CPatch* patch)
{
    m_SubmittedPatchOccluders.push_back(patch);
}

void SilhouetteRenderer::AddOccluder(CModel* model)
{
    m_SubmittedModelOccluders.push_back(model);
}

void SilhouetteRenderer::AddCaster(CModel* model)
{
    m_SubmittedModelCasters.push_back(model);
}

/*
 * Silhouettes are the solid-colored versions of units that are rendered when
 * standing behind a building or terrain, so the player won't lose them.
 *
 * The rendering is done in CRenderer::RenderSilhouettes, by rendering the
 * units (silhouette casters) and buildings/terrain (silhouette occluders)
 * in an extra pass using depth and stencil buffers. It's very inefficient to
 * render those objects when they're not actually going to contribute to a
 * silhouette.
 *
 * This class is responsible for finding the subset of casters/occluders
 * that might contribute to a silhouette and will need to be rendered.
 *
 * The algorithm is largely based on sweep-and-prune for detecting intersection
 * along a single axis:
 *
 * First we compute the 2D screen-space bounding box of every occluder, and
 * their minimum distance from the camera. We also compute the screen-space
 * position of each caster (approximating them as points, which is not perfect
 * but almost always good enough).
 *
 * We split each occluder's screen-space bounds into a left ('in') edge and
 * right ('out') edge. We put those edges plus the caster points into a list,
 * and sort by x coordinate.
 *
 * Then we walk through the list, maintaining an active set of occluders.
 * An 'in' edge will add an occluder to the set, an 'out' edge will remove it.
 * When we reach a caster point, the active set contains all the occluders that
 * intersect it in x. We do a quick test of y and depth coordinates against
 * each occluder in the set. If they pass that test, we do a more precise ray
 * vs bounding box test (for model occluders) or ray vs patch (for terrain
 * occluders) to see if we really need to render that caster and occluder.
 *
 * Performance relies on the active set being quite small. Given the game's
 * typical occluder sizes and camera angles, this works out okay.
 *
 * We have to do precise ray/patch intersection tests for terrain, because
 * if we just used the patch's bounding box, pretty much every unit would
 * be seen as intersecting the patch it's standing on.
 *
 * We store screen-space coordinates as 14-bit integers (0..16383) because
 * that lets us pack and sort the edge/point list efficiently.
 */

static const u16 g_MaxCoord = 1 << 14;
static const u16 g_HalfMaxCoord = g_MaxCoord / 2;

struct Occluder
{
    CRenderableObject* renderable;
    bool isPatch;
    u16 x0, y0, x1, y1;
    float z;
    bool rendered;
};

struct Caster
{
    CModel* model;
    u16 x, y;
    float z;
    bool rendered;
};

enum { EDGE_IN, EDGE_OUT, POINT };

// Entry is essentially:
//   struct Entry {
//     u16 id; // index into occluders array
//     u16 type : 2;
//     u16 x : 14;
//  };
// where x is in the most significant bits, so that sorting as a uint32_t
// is the same as sorting by x. To avoid worrying about endianness and the
// compiler's ability to handle bitfields efficiently, we use uint32_t instead
// of the actual struct.

typedef uint32_t Entry;

static Entry EntryCreate(int type, u16 id, u16 x) { return (x << 18) | (type << 16) | id; }
static int EntryGetId(Entry e) { return e & 0xffff; }
static int EntryGetType(Entry e) { return (e >> 16) & 3; }

struct ActiveList
{
    std::vector<u16> m_Ids;

    void Add(u16 id)
    {
        m_Ids.push_back(id);
    }

    void Remove(u16 id)
    {
        ssize_t sz = m_Ids.size();
        for (ssize_t i = sz-1; i >= 0; --i)
        {
            if (m_Ids[i] == id)
            {
                m_Ids[i] = m_Ids[sz-1];
                m_Ids.pop_back();
                return;
            }
        }
        debug_warn(L"Failed to find id");
    }
};

static void ComputeScreenBounds(Occluder& occluder, const CBoundingBoxAligned& bounds, CMatrix3D& proj)
{
    u16 x0 = std::numeric_limits<u16>::max();
    u16 y0 = std::numeric_limits<u16>::max();
    u16 x1 = std::numeric_limits<u16>::min();
    u16 y1 = std::numeric_limits<u16>::min();
    float z0 = std::numeric_limits<float>::max();
    for (size_t ix = 0; ix <= 1; ++ix)
    {
        for (size_t iy = 0; iy <= 1; ++iy)
        {
            for (size_t iz = 0; iz <= 1; ++iz)
            {
                CVector4D svec = proj.Transform(CVector4D(bounds[ix].X, bounds[iy].Y, bounds[iz].Z, 1.0f));
                x0 = std::min(x0,  static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.X / svec.W)));
                y0 = std::min(y0,  static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.Y / svec.W)));
                x1 = std::max(x1,  static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.X / svec.W)));
                y1 = std::max(y1,  static_cast<u16>(g_HalfMaxCoord + static_cast<u16>(g_HalfMaxCoord * svec.Y / svec.W)));
                z0 = std::min(z0, svec.Z / svec.W);
            }
        }
    }
    // TODO: there must be a quicker way to do this than to test every vertex,
    // given the symmetry of the bounding box

    occluder.x0 = Clamp(x0, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    occluder.y0 = Clamp(y0, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    occluder.x1 = Clamp(x1, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    occluder.y1 = Clamp(y1, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    occluder.z = z0;
}

static void ComputeScreenPos(Caster& caster, const CVector3D& pos, CMatrix3D& proj)
{
    CVector4D svec = proj.Transform(CVector4D(pos.X, pos.Y, pos.Z, 1.0f));
    u16 x = g_HalfMaxCoord + static_cast<int>(g_HalfMaxCoord * svec.X / svec.W);
    u16 y = g_HalfMaxCoord + static_cast<int>(g_HalfMaxCoord * svec.Y / svec.W);
    caster.x = Clamp(x, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    caster.y = Clamp(y, std::numeric_limits<u16>::min(), g_MaxCoord - 1);
    caster.z = svec.Z / svec.W;
}

void SilhouetteRenderer::ComputeSubmissions(const CCamera& camera)
{
    PROFILE3("compute silhouettes");

    m_DebugBounds.clear();
    m_DebugRects.clear();
    m_DebugSpheres.clear();

    m_VisiblePatchOccluders.clear();
    m_VisibleModelOccluders.clear();
    m_VisibleModelCasters.clear();

    std::vector<Occluder> occluders;
    std::vector<Caster> casters;
    std::vector<Entry> entries;

    occluders.reserve(m_SubmittedModelOccluders.size() + m_SubmittedPatchOccluders.size());
    casters.reserve(m_SubmittedModelCasters.size());
    entries.reserve((m_SubmittedModelOccluders.size() + m_SubmittedPatchOccluders.size()) * 2 + m_SubmittedModelCasters.size());

    CMatrix3D proj = camera.GetViewProjection();

    // Bump the positions of unit casters upwards a bit, so they're not always
    // detected as intersecting the terrain they're standing on
    CVector3D posOffset(0.0f, 0.1f, 0.0f);

#if 0
    // For debugging ray-patch intersections - casts a ton of rays and draws
    // a sphere where they intersect
    for (int y = 0; y < g_yres; y += 8)
    {
        for (int x = 0; x < g_xres; x += 8)
        {
            SOverlaySphere sphere;
            sphere.m_Color = CColor(1, 0, 0, 1);
            sphere.m_Radius = 0.25f;
            sphere.m_Center = camera.GetWorldCoordinates(x, y, false);

            CVector3D origin, dir;
            camera.BuildCameraRay(x, y, origin, dir);

            for (size_t i = 0; i < m_SubmittedPatchOccluders.size(); ++i)
            {
                CPatch* occluder = m_SubmittedPatchOccluders[i];
                if (CHFTracer::PatchRayIntersect(occluder, origin, dir, &sphere.m_Center))
                    sphere.m_Color = CColor(0, 0, 1, 1);
            }
            m_DebugSpheres.push_back(sphere);
        }
    }
#endif

    {
        PROFILE("compute bounds");

        for (size_t i = 0; i < m_SubmittedModelOccluders.size(); ++i)
        {
            CModel* occluder = m_SubmittedModelOccluders[i];

            Occluder d;
            d.renderable = occluder;
            d.isPatch = false;
            d.rendered = false;
            ComputeScreenBounds(d, occluder->GetWorldBounds(), proj);

            // Skip zero-sized occluders, so we don't need to worry about EDGE_OUT
            // getting sorted before EDGE_IN
            if (d.x0 == d.x1 || d.y0 == d.y1)
                continue;

            u16 id = static_cast<u16>(occluders.size());
            occluders.push_back(d);

            entries.push_back(EntryCreate(EDGE_IN, id, d.x0));
            entries.push_back(EntryCreate(EDGE_OUT, id, d.x1));
        }

        for (size_t i = 0; i < m_SubmittedPatchOccluders.size(); ++i)
        {
            CPatch* occluder = m_SubmittedPatchOccluders[i];

            Occluder d;
            d.renderable = occluder;
            d.isPatch = true;
            d.rendered = false;
            ComputeScreenBounds(d, occluder->GetWorldBounds(), proj);

            // Skip zero-sized occluders
            if (d.x0 == d.x1 || d.y0 == d.y1)
                continue;

            u16 id = static_cast<u16>(occluders.size());
            occluders.push_back(d);

            entries.push_back(EntryCreate(EDGE_IN, id, d.x0));
            entries.push_back(EntryCreate(EDGE_OUT, id, d.x1));
        }

        for (size_t i = 0; i < m_SubmittedModelCasters.size(); ++i)
        {
            CModel* model = m_SubmittedModelCasters[i];
            CVector3D pos = model->GetTransform().GetTranslation() + posOffset;

            Caster d;
            d.model = model;
            d.rendered = false;
            ComputeScreenPos(d, pos, proj);

            u16 id = static_cast<u16>(casters.size());
            casters.push_back(d);

            entries.push_back(EntryCreate(POINT, id, d.x));
        }
    }

    // Make sure the u16 id didn't overflow
    ENSURE(occluders.size() < 65536 && casters.size() < 65536);

    {
        PROFILE("sorting");
        std::sort(entries.begin(), entries.end());
    }

    {
        PROFILE("sweeping");

        ActiveList active;
        CVector3D cameraPos = camera.GetOrientation().GetTranslation();

        for (size_t i = 0; i < entries.size(); ++i)
        {
            Entry e = entries[i];
            int type = EntryGetType(e);
            u16 id = EntryGetId(e);
            if (type == EDGE_IN)
                active.Add(id);
            else if (type == EDGE_OUT)
                active.Remove(id);
            else
            {
                Caster& caster = casters[id];
                for (size_t j = 0; j < active.m_Ids.size(); ++j)
                {
                    Occluder& occluder = occluders[active.m_Ids[j]];

                    if (caster.y < occluder.y0 || caster.y > occluder.y1)
                        continue;

                    if (caster.z < occluder.z)
                        continue;

                    // No point checking further if both are already being rendered
                    if (caster.rendered && occluder.rendered)
                        continue;

                    if (!g_DisablePreciseIntersections)
                    {
                        CVector3D pos = caster.model->GetTransform().GetTranslation() + posOffset;
                        if (occluder.isPatch)
                        {
                            CPatch* patch = static_cast<CPatch*>(occluder.renderable);
                            if (!CHFTracer::PatchRayIntersect(patch, pos, cameraPos - pos, NULL))
                                continue;
                        }
                        else
                        {
                            float tmin, tmax;
                            if (!occluder.renderable->GetWorldBounds().RayIntersect(pos, cameraPos - pos, tmin, tmax))
                                continue;
                        }
                    }

                    caster.rendered = true;
                    occluder.rendered = true;
                }
            }
        }
    }

    if (m_DebugEnabled)
    {
        for (size_t i = 0; i < occluders.size(); ++i)
        {
            DebugRect r;
            r.color = occluders[i].rendered ? CColor(1.0f, 1.0f, 0.0f, 1.0f) : CColor(0.2f, 0.2f, 0.0f, 1.0f);
            r.x0 = occluders[i].x0;
            r.y0 = occluders[i].y0;
            r.x1 = occluders[i].x1;
            r.y1 = occluders[i].y1;
            m_DebugRects.push_back(r);

            DebugBounds b;
            b.color = r.color;
            b.bounds = occluders[i].renderable->GetWorldBounds();
            m_DebugBounds.push_back(b);
        }
    }

    for (size_t i = 0; i < occluders.size(); ++i)
    {
        if (occluders[i].rendered)
        {
            if (occluders[i].isPatch)
                m_VisiblePatchOccluders.push_back(static_cast<CPatch*>(occluders[i].renderable));
            else
                m_VisibleModelOccluders.push_back(static_cast<CModel*>(occluders[i].renderable));
        }
    }

    for (size_t i = 0; i < casters.size(); ++i)
        if (casters[i].rendered)
            m_VisibleModelCasters.push_back(casters[i].model);
}

void SilhouetteRenderer::RenderSubmitOverlays(SceneCollector& collector)
{
    for (size_t i = 0; i < m_DebugSpheres.size(); i++)
        collector.Submit(&m_DebugSpheres[i]);
}

void SilhouetteRenderer::RenderSubmitOccluders(SceneCollector& collector)
{
    for (size_t i = 0; i < m_VisiblePatchOccluders.size(); ++i)
        collector.Submit(m_VisiblePatchOccluders[i]);

    for (size_t i = 0; i < m_VisibleModelOccluders.size(); ++i)
        collector.SubmitNonRecursive(m_VisibleModelOccluders[i]);
}

void SilhouetteRenderer::RenderSubmitCasters(SceneCollector& collector)
{
    for (size_t i = 0; i < m_VisibleModelCasters.size(); ++i)
        collector.SubmitNonRecursive(m_VisibleModelCasters[i]);
}

void SilhouetteRenderer::RenderDebugOverlays(const CCamera& camera)
{
    CShaderTechniquePtr shaderTech = g_Renderer.GetShaderManager().LoadEffect(str_gui_solid);
    shaderTech->BeginPass();
    CShaderProgramPtr shader = shaderTech->GetShader();

    glDepthMask(0);
    glDisable(GL_CULL_FACE);

    shader->Uniform(str_transform, camera.GetViewProjection());

    for (size_t i = 0; i < m_DebugBounds.size(); ++i)
    {
        shader->Uniform(str_color, m_DebugBounds[i].color);
        m_DebugBounds[i].bounds.RenderOutline(shader);
    }

    CMatrix3D m;
    m.SetIdentity();
    m.Scale(1.0f, -1.f, 1.0f);
    m.Translate(0.0f, (float)g_yres, -1000.0f);

    CMatrix3D proj;
    proj.SetOrtho(0.f, g_MaxCoord, 0.f, g_MaxCoord, -1.f, 1000.f);
    m = proj * m;

    shader->Uniform(str_transform, proj);

    for (size_t i = 0; i < m_DebugRects.size(); ++i)
    {
        const DebugRect& r = m_DebugRects[i];
        shader->Uniform(str_color, r.color);
        u16 verts[] = {
            r.x0, r.y0,
            r.x1, r.y0,
            r.x1, r.y1,
            r.x0, r.y1,
            r.x0, r.y0,
        };
        shader->VertexPointer(2, GL_SHORT, 0, verts);
        glDrawArrays(GL_LINE_STRIP, 0, 5);
    }

    shaderTech->EndPass();

    glEnable(GL_CULL_FACE);
    glDepthMask(1);
}

void SilhouetteRenderer::EndFrame()
{
    m_SubmittedPatchOccluders.clear();
    m_SubmittedModelOccluders.clear();
    m_SubmittedModelCasters.clear();
}