1
\$\begingroup\$

My engine is based on Cells and Portals. From the Current Cell, I traverse the portals recursively. While doing so, I cache the clipping rect. When rendering the cells, I use the cached clipping rect and set the Scissor rect.

This works reasonably fast already (2-4ms on a five year old CPU for around 400 cells without any "already visited" mechanisms)

Here is my current recursive function:

struct cell_visibility_query {
    cell_id from;
    cell_id to;
    float4 viewport;
    unsigned short count;
};


bool check_portal(const room_visibility_portal& portal, const float3 view_position, const float4 viewport, float4& clipport,
                  const matrix& view_projection) {
    const auto n = get_portal_normal(portal.direction);
    const auto view_angle = dot(view_position - float3(portal.corners[0]), n);
    if(view_angle <= 0) {
        return false;
    }

    unsigned char z_clip = 0;
    float4 portal_vertices[4];
    for(auto i = 0u; i < 4; i++) {
        auto& p = portal_vertices[i];
        p = view_projection * float4(float3(portal.corners[i]), 1.0f);
        if(p.w > 0.0f) {
            p.xy *= float2(1.0f / p.w);
            clipport.x = glm::min(clipport.x, p.x);
            clipport.y = glm::min(clipport.y, p.y);
            clipport.z = glm::max(clipport.z, p.x);
            clipport.w = glm::max(clipport.w, p.y);
        }else {
            z_clip++;
        }
    }
    if(z_clip == 4) {
        return false;
    }
    if(z_clip > 0) {
        for(auto i = 0u; i < 4; i++) {
            const auto& a = portal_vertices[i];
            const auto& b = portal_vertices[(i + 1) % 4];

            if((a.w > 0.0f) ^ (b.w > 0.0f)) {
                if(a.x < 0.0f && b.x < 0.0f) {
                    clipport.x = -1.0f;
                }
                else if(a.x > 0.0f && b.x > 0.0f) {
                    clipport.z = 1.0f;
                }
                else {
                    clipport.x = -1.0f;
                    clipport.z = 1.0f;
                }

                if(a.y < 0.0f && b.y < 0.0f) {
                    clipport.y = -1.0f;
                }
                else if(a.y > 0.0f && b.y > 0.0f) {
                    clipport.w = 1.0f;
                }
                else {
                    clipport.y = -1.0f;
                    clipport.w = 1.0f;
                }

            }
        }
    }

    if(clipport.x > viewport.z || clipport.y > viewport.w || clipport.z < viewport.x || clipport.w < viewport.y) {
        return false;
    }

    clipport.x = glm::max(clipport.x, viewport.x);
    clipport.y = glm::max(clipport.y, viewport.y);
    clipport.z = glm::min(clipport.z, viewport.z);
    clipport.w = glm::min(clipport.w, viewport.w);

    return true;
}

void get_visible_cells(const std::span<cell_info> cell_data, std::insert_iterator<std::vector<cell_render_node>>& inserter,
                       const cell_visibility_query& query, const float3& view_direction, const matrix& view_projection) {
    auto& cell = cell_data[query.to];
    *(inserter++) = {.cell_index = query.to, .portal = query.viewport};
    for(auto& p: cell.visibility_portals) {
        if(query.from == p.cell) {
            continue;
        }
        float4 clipport{INFINITY, INFINITY, -INFINITY, -INFINITY};
        if(!check_portal(p, view_direction,query.viewport,clipport,view_projection)) {
            continue;
        }
        get_visible_cells(cell_data, inserter, cell_visibility_query{.from = query.to, .to = p.cell, .viewport = clipport, .count = (unsigned short)(query.count + 1)},view_direction, view_projection);
    }
}

However, because it is recursive, I traverse cells multiple times a lot; The required memory explodes (for 400 visible cells, tests showed I collect around 10000 cell_render_nodes). I would like to reduce this memory requirement.

About my engine:

Each Cell is cuboidal (i.e. 3D).
Portals are axis aligned.
Each portal is unique, i.e. it can only lead to one cell (the adjacent cell has a different portal).

Do you have any advice?

\$\endgroup\$

0

You must log in to answer this question.

Browse other questions tagged .