Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

15.9 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file    OcclusionView.hpp
 * @brief   What this view already has something solid in front of.
 *
 * @details The other half of the cull, beside Frustum: one says what is outside
 *          the view, this says what is inside it and hidden. Both are asked
 *          through one predicate (RenderCollectContext::visible) so a renderable
 *          cannot be judged by one of them and not the other.
 *
 *          A DEPTH GRID, not a query: the collect may not touch the device
 *          (RenderFrame's first invariant), and a GPU occlusion query answers a
 *          frame late through a readback the WebGL2 path would stall on. Solid
 *          boxes an author declared are rasterised onto a small grid here, and
 *          every bound is tested against it before it becomes a draw.
 *
 *          Conservative in one direction ON PURPOSE. Claiming too little costs
 *          draws that were already being paid; claiming too much makes objects
 *          vanish in front of the player, which no counter shows and no gate
 *          catches. Everything below rounds towards drawing: only texels a face
 *          covers WHOLE take a depth, that depth is the face's farthest point
 *          over the texel, and a box that reaches behind the eye is dropped
 *          rather than approximated.
 */
#pragma once

#include "../../core/Types.hpp"

#include <glm/glm.hpp>
#include <glm/gtc/quaternion.hpp>

#include <algorithm>
#include <array>
#include <cmath>
#include <limits>

namespace esengine {

/**
 * @brief The depths this view is blocked at, and the test a bound asks it.
 *
 * @details `begin`, an `addBox` per declared occluder, `finish`, then `hidden`
 *          until the next `begin`. The stored view-projection serves both halves:
 *          a tester holding its own copy is how a raster and a test come to
 *          disagree about where something is.
 */
class OcclusionView {
public:
    /** @brief Grid resolution of the coarsest useful answer. A texel is ~1.5% of
     *         the screen, which is what an occluder must exceed to hide anything;
     *         finer costs the rasterisation, which is the only cost here. */
    static constexpr u32 kSize = 64;
    /** @brief 64, 32, 16, 8, 4, 2, 1 — down to one texel, so an object covering
     *         the whole screen still takes a bounded number of reads. */
    static constexpr u32 kLevels = 7;

    /** @brief Texels a side a bound is tested over: sixteen reads, whatever its
     *         size on screen. */
    static constexpr u32 kTestSpan = 4;

    /** @brief Depth of a texel nothing covers: no bound is ever farther. */
    static constexpr f32 kOpen = std::numeric_limits<f32>::infinity();

    /** @brief Smallest clip w a corner may have. Anything at or behind the eye
     *         plane makes the projection meaningless, and the cases that reach
     *         it — the eye inside the box, the box across the near plane — are
     *         exactly the ones a conservative answer must refuse. */
    static constexpr f32 kMinW = 1e-4f;

    /** @brief Opens a view looking through @p viewProjection. Nothing is blocked
     *         until a box is taken, which is what a scene declaring no occluder
     *         (every 2D one) pays: one comparison per renderable. */
    void begin(const glm::mat4& viewProjection) {
        view_projection_ = viewProjection;
        boxes_ = 0;
    }

    /**
     * @brief Takes one solid box — @p half world half-extents about @p centre,
     *        turned by @p rotation — as something sight does not pass through.
     *
     * @return Whether it was taken. A refusal is not an error: a box reaching
     *         behind the eye plane is dropped whole rather than clipped, because
     *         everything this class may get wrong must be got wrong towards
     *         drawing.
     */
    bool addBox(const glm::vec3& centre, const glm::quat& rotation, const glm::vec3& half) {
        glm::vec3 corners[8];
        if (!projectBox(centre, rotation, half, corners)) return false;

        // Grid coordinates, where a texel is one unit and its centre a half — the
        // edge bias and the depth slope below are both read in texels, and two
        // spaces would put the rounding in one of them only.
        glm::vec2 lo(static_cast<f32>(kSize)), hi(0.0f);
        for (const glm::vec3& c : corners) {
            lo = glm::min(lo, glm::vec2(c));
            hi = glm::max(hi, glm::vec2(c));
        }
        // The texels the silhouette TOUCHES, both ends floored: a rectangle that
        // rounded one end up would hand the coverage test a texel the box never
        // reaches, and the test and the scan must agree on which texels exist.
        const i32 x0 = std::max(0, static_cast<i32>(std::floor(lo.x)));
        const i32 y0 = std::max(0, static_cast<i32>(std::floor(lo.y)));
        const i32 x1 = std::min(static_cast<i32>(kSize) - 1, static_cast<i32>(std::floor(hi.x)));
        const i32 y1 = std::min(static_cast<i32>(kSize) - 1, static_cast<i32>(std::floor(hi.y)));
        // Off screen entirely: what is outside the view hides nothing inside it,
        // and the frustum has already answered for anything out there.
        if (x1 < x0 || y1 < y0) return false;

        Face faces[6];
        u32 faceCount = 0;
        for (const auto& quad : kFaces) {
            Face face;
            if (buildFace(corners, quad, face)) faces[faceCount++] = face;
        }
        // Every face edge-on at once means a box with no thickness on screen.
        if (faceCount == 0) return false;

        if (boxes_ == 0) base_.fill(kOpen);
        ++boxes_;

        for (i32 y = y0; y <= y1; ++y) {
            for (i32 x = x0; x <= x1; ++x) {
                const glm::vec2 p(static_cast<f32>(x) + 0.5f, static_cast<f32>(y) + 0.5f);
                f32 blocked = kOpen;
                for (u32 f = 0; f < faceCount; ++f) {
                    const Face& face = faces[f];
                    if (!face.covers(p)) continue;
                    // The face's FARTHEST depth over the whole texel, not its depth
                    // at the centre: the claim a texel makes is about every point in
                    // it, and half a texel of slope is what separates the two.
                    blocked = std::min(blocked, face.maxDepthOver(p));
                }
                if (blocked < kOpen) {
                    f32& cell = base_[static_cast<usize>(y) * kSize + static_cast<usize>(x)];
                    // Nearest wins: whatever is in front blocks most, and which box
                    // it came from cannot change the answer — so the order the
                    // registry hands them over in cannot either.
                    cell = std::min(cell, blocked);
                }
            }
        }
        return true;
    }

    /** @brief Closes the view: reduces the grid by MAXIMUM into a pyramid, so a
     *         bound of any size on screen costs four reads rather than its area.
     *         A coarse texel answers for a whole region, and taking the farthest
     *         of them is what keeps a region that is only partly blocked drawn. */
    void finish() {
        if (boxes_ == 0) return;
        for (u32 level = 1; level < kLevels; ++level) {
            const u32 size = kSize >> level;
            const u32 src = kSize >> (level - 1);
            f32* out = levelData(level);
            const f32* in = levelData(level - 1);
            for (u32 y = 0; y < size; ++y) {
                for (u32 x = 0; x < size; ++x) {
                    const f32 a = in[(2 * y) * src + 2 * x];
                    const f32 b = in[(2 * y) * src + 2 * x + 1];
                    const f32 c = in[(2 * y + 1) * src + 2 * x];
                    const f32 d = in[(2 * y + 1) * src + 2 * x + 1];
                    out[y * size + x] = std::max(std::max(a, b), std::max(c, d));
                }
            }
        }
    }

    /** @brief Whether nothing of a box bounded by @p centre / @p half can be seen,
     *         because every texel it covers is blocked nearer than its nearest point. */
    bool hidden(const glm::vec3& centre, const glm::vec3& half) const {
        if (boxes_ == 0) return false;

        glm::vec3 corners[8];
        if (!projectBox(centre, glm::quat(1.0f, 0.0f, 0.0f, 0.0f), half, corners)) return false;

        glm::vec2 lo(static_cast<f32>(kSize)), hi(0.0f);
        f32 nearest = kOpen;
        for (const glm::vec3& c : corners) {
            lo = glm::min(lo, glm::vec2(c));
            hi = glm::max(hi, glm::vec2(c));
            nearest = std::min(nearest, c.z);
        }

        // Clamped to the grid, because what falls outside it is off screen and needs
        // no occluder to be unseen. An empty rectangle after the clamp is entirely
        // off screen, which is the frustum's answer to give, not this one's.
        const i32 x0 = std::max(0, static_cast<i32>(std::floor(lo.x)));
        const i32 y0 = std::max(0, static_cast<i32>(std::floor(lo.y)));
        const i32 x1 = std::min(static_cast<i32>(kSize) - 1, static_cast<i32>(std::floor(hi.x)));
        const i32 y1 = std::min(static_cast<i32>(kSize) - 1, static_cast<i32>(std::floor(hi.y)));
        if (x1 < x0 || y1 < y0) return false;

        // FOUR texels a side, not two: a level's texels align to the grid and not to
        // this rectangle, so at two the overhang is the object's own width again —
        // measured, six of nine cubes squarely behind a wall went uncalled.
        u32 level = 0;
        while (level + 1 < kLevels
               && ((x1 >> level) - (x0 >> level) >= static_cast<i32>(kTestSpan)
                   || (y1 >> level) - (y0 >> level) >= static_cast<i32>(kTestSpan))) {
            ++level;
        }
        const u32 size = kSize >> level;
        const f32* cells = levelData(level);
        f32 farthest = -kOpen;
        for (i32 y = y0 >> level; y <= (y1 >> level); ++y) {
            for (i32 x = x0 >> level; x <= (x1 >> level); ++x) {
                farthest = std::max(farthest, cells[static_cast<usize>(y) * size
                                                    + static_cast<usize>(x)]);
            }
        }
        // Strictly nearer, so a bound resting exactly on the blocking depth is drawn:
        // equality here is a surface touching the occluder, which is visible.
        return farthest < nearest;
    }

    /** @brief Whether this view blocks nothing, so every bound is visible to it. */
    bool empty() const { return boxes_ == 0; }

    /** @brief How many declared boxes this view took. */
    u32 boxes() const { return boxes_; }

private:
    /** @brief One planar face of a box, in grid space: where it lies and how deep. */
    struct Face {
        /** Edge functions as (a, b, c) with a*x + b*y + c >= bias inside. */
        glm::vec3 edges[4];
        /** How far each edge function may fall across half a texel either way. */
        f32 bias[4];
        /** Depth as an affine function of grid position — which is what a PLANE's
         *  depth is in screen space, and why no perspective divide happens here. */
        f32 zx = 0.0f, zy = 0.0f, z0 = 0.0f;

        bool covers(const glm::vec2& p) const {
            for (u32 i = 0; i < 4; ++i) {
                if (edges[i].x * p.x + edges[i].y * p.y + edges[i].z < bias[i]) return false;
            }
            return true;
        }

        f32 maxDepthOver(const glm::vec2& p) const {
            return zx * p.x + zy * p.y + z0 + 0.5f * (std::fabs(zx) + std::fabs(zy));
        }
    };

    /** @brief The six faces as corner indices, each a ring around the quad. Winding
     *         is not read: which side faces the eye is decided per face from the
     *         projection, so a box turned inside out cannot flip the answer. */
    static constexpr u32 kFaces[6][4] = {
        {0, 1, 3, 2}, {4, 6, 7, 5}, {0, 4, 5, 1}, {2, 3, 7, 6}, {0, 2, 6, 4}, {1, 5, 7, 3},
    };

    /**
     * @brief Projects a box's eight corners into grid space with depth.
     *
     * @return False when any corner is at or behind the eye plane. Rejecting the
     *         whole box is what keeps the arithmetic honest: a projection is only
     *         monotone in depth where w stays positive, and the eye INSIDE an
     *         occluder is this same case — a box whose every ray would be called
     *         blocked.
     */
    bool projectBox(const glm::vec3& centre, const glm::quat& rotation, const glm::vec3& half,
                    glm::vec3 (&out)[8]) const {
        const glm::mat3 basis = glm::mat3_cast(rotation);
        for (u32 i = 0; i < 8; ++i) {
            const glm::vec3 local((i & 1u) ? half.x : -half.x,
                                  (i & 2u) ? half.y : -half.y,
                                  (i & 4u) ? half.z : -half.z);
            const glm::vec4 clip = view_projection_ * glm::vec4(centre + basis * local, 1.0f);
            if (clip.w <= kMinW) return false;
            const glm::vec3 ndc = glm::vec3(clip) / clip.w;
            // Behind the near plane in the convention every camera projection here
            // is built in (near = -1). A depth-zero-to-one projection simply never
            // trips it, which costs culling and never correctness.
            if (ndc.z < -1.0f) return false;
            out[i] = {(ndc.x + 1.0f) * 0.5f * static_cast<f32>(kSize),
                      (ndc.y + 1.0f) * 0.5f * static_cast<f32>(kSize), ndc.z};
        }
        return true;
    }

    /** @brief Builds the face @p quad names, or false if it projected to a sliver —
     *         a face seen edge-on covers nothing and has no depth to give. */
    static bool buildFace(const glm::vec3 (&corners)[8], const u32 (&quad)[4], Face& out) {
        const glm::vec3 v[4] = {corners[quad[0]], corners[quad[1]],
                                corners[quad[2]], corners[quad[3]]};
        // Signed area decides the orientation, so the inside test below is the same
        // expression for a face pointing at the eye and one pointing away.
        f32 area = 0.0f;
        for (u32 i = 0; i < 4; ++i) {
            const glm::vec3& a = v[i];
            const glm::vec3& b = v[(i + 1) % 4];
            area += a.x * b.y - b.x * a.y;
        }
        if (std::fabs(area) < 1e-3f) return false;
        const f32 sign = area > 0.0f ? 1.0f : -1.0f;

        for (u32 i = 0; i < 4; ++i) {
            const glm::vec3& a = v[i];
            const glm::vec3& b = v[(i + 1) % 4];
            const f32 ex = -(b.y - a.y) * sign;
            const f32 ey = (b.x - a.x) * sign;
            out.edges[i] = {ex, ey, -(ex * a.x + ey * a.y)};
            // Half a texel each way: the test is then "covers this texel WHOLE",
            // which is the difference between an occluder that may hide something
            // and one that only touches the pixels at its own silhouette.
            out.bias[i] = 0.5f * (std::fabs(ex) + std::fabs(ey));
        }

        const glm::vec2 d1(v[1].x - v[0].x, v[1].y - v[0].y);
        const glm::vec2 d2(v[2].x - v[0].x, v[2].y - v[0].y);
        const f32 det = d1.x * d2.y - d1.y * d2.x;
        if (std::fabs(det) < 1e-6f) return false;
        const f32 dz1 = v[1].z - v[0].z;
        const f32 dz2 = v[2].z - v[0].z;
        out.zx = (dz1 * d2.y - dz2 * d1.y) / det;
        out.zy = (d1.x * dz2 - d2.x * dz1) / det;
        out.z0 = v[0].z - out.zx * v[0].x - out.zy * v[0].y;
        return true;
    }

    /** @brief One pyramid in one array: level 0 is the grid, each next a quarter. */
    static constexpr usize kCells = (kSize * kSize * 4) / 3 + 1;

    f32* levelData(u32 level) { return base_.data() + offsetOf(level); }
    const f32* levelData(u32 level) const { return base_.data() + offsetOf(level); }

    static constexpr usize offsetOf(u32 level) {
        usize offset = 0;
        for (u32 i = 0; i < level; ++i) offset += static_cast<usize>(kSize >> i) * (kSize >> i);
        return offset;
    }

    glm::mat4 view_projection_{1.0f};
    std::array<f32, kCells> base_{};
    u32 boxes_ = 0;
};

}  // namespace esengine