qssgshadowmaphelpers.cpp

Go to the documentation of this file.

// Copyright (C) 2024 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
// Qt-Security score:significant reason:default
 
 
#include "qssgshadowmaphelpers_p.h"
 
#include "qssgdebugdrawsystem_p.h"
#include "qssgrenderray_p.h"
 
#include <QVector3D>
#include <QMatrix4x4>
#include <QVector4D>
#include <cmath>
 
QT_BEGIN_NAMESPACE
 
static QMatrix4x4 buildOrthonormalBasis(const QVector3D &normal)
{
    // Assume normal is already normalized
    const QVector3D forward = normal;
 
    // Pick the axis least aligned with forward to use as a reference
    QVector3D ref;
    float absX = std::fabs(forward.x());
    float absY = std::fabs(forward.y());
    float absZ = std::fabs(forward.z());
 
    if (absX <= absY && absX <= absZ)
        ref = QVector3D(1, 0, 0);
    else if (absY <= absZ)
        ref = QVector3D(0, 1, 0);
    else
        ref = QVector3D(0, 0, 1);
 
    const QVector3D right = QVector3D::crossProduct(ref, forward).normalized();
    const QVector3D up = QVector3D::crossProduct(forward, right);
 
    QMatrix4x4 transform(Qt::Uninitialized);
    transform.setRow(0, QVector4D(right, 0.0f));
    transform.setRow(1, QVector4D(up, 0.0f));
    transform.setRow(2, QVector4D(forward, 0.0f));
    transform.setRow(3, QVector4D(0.0f, 0.0f, 0.0f, 1.0f));
    return transform;
}
 
// These indices need to match the order in QSSGBounds3::toQSSGBoxPointsNoEmptyCheck()
static constexpr std::array<std::array<int, 2>, 12> BOX_LINE_INDICES = {
    std::array<int, 2> { 0, 1 }, std::array<int, 2> { 1, 2 }, std::array<int, 2> { 2, 3 }, std::array<int, 2> { 3, 0 },
    std::array<int, 2> { 4, 5 }, std::array<int, 2> { 5, 6 }, std::array<int, 2> { 6, 7 }, std::array<int, 2> { 7, 4 },
    std::array<int, 2> { 0, 4 }, std::array<int, 2> { 1, 5 }, std::array<int, 2> { 2, 6 }, std::array<int, 2> { 3, 7 },
};
 
void ShadowmapHelpers::addDebugBox(const QSSGBoxPoints &box, const QColor &color, QSSGDebugDrawSystem *debugDrawSystem)
{
    if (!debugDrawSystem)
        return;
 
    for (const auto line : BOX_LINE_INDICES)
        debugDrawSystem->drawLine(box[line[0]], box[line[1]], color);
 
    debugDrawSystem->setEnabled(true);
}
 
void ShadowmapHelpers::addDebugFrustum(const QSSGBoxPoints &frustumPoints, const QColor &color, QSSGDebugDrawSystem *debugDrawSystem)
{
    ShadowmapHelpers::addDebugBox(frustumPoints, color, debugDrawSystem);
}
 
void ShadowmapHelpers::addDirectionalLightDebugBox(const QSSGBoxPoints &box, QSSGDebugDrawSystem *debugDrawSystem)
{
    if (!debugDrawSystem)
        return;
 
    constexpr QColor colorBox = QColorConstants::Yellow;
 
    //    .7------6
    //  .' |    .'|
    // 3---+--2'  |
    // |   |  |   |
    // |  .4--+---5
    // |.'    | .'
    // 0------1'
 
    // Find shortest axis line
    float shortestAxisSq = (box[0] - box[1]).lengthSquared();
    shortestAxisSq = std::min(shortestAxisSq, (box[0] - box[4]).lengthSquared());
    shortestAxisSq = std::min(shortestAxisSq, (box[0] - box[3]).lengthSquared());
    const float axisLength = qSqrt(shortestAxisSq) * 0.5f;
 
    auto drawAxisLine = [&](const QVector3D &from, const QVector3D &to, const QColor &axisColor) {
        const QVector3D dir = (to - from).normalized();
        const QVector3D mid = from + dir * axisLength;
        debugDrawSystem->drawLine(from, mid, axisColor);
        debugDrawSystem->drawLine(mid, to, colorBox);
    };
 
    // Draw x,y,z axis in r,g,b color and rest in box color
 
    // Closest to light (front)
    drawAxisLine(box[0], box[1], QColorConstants::Red);
    debugDrawSystem->drawLine(box[1], box[2], colorBox);
    drawAxisLine(box[0], box[3], QColorConstants::Green);
    debugDrawSystem->drawLine(box[2], box[3], colorBox);
 
    // Lines parallel to light direction
    drawAxisLine(box[0], box[4], QColorConstants::Blue);
    debugDrawSystem->drawLine(box[1], box[5], colorBox);
    debugDrawSystem->drawLine(box[2], box[6], colorBox);
    debugDrawSystem->drawLine(box[3], box[7], colorBox);
 
    // Furthest from light (back)
    debugDrawSystem->drawLine(box[4], box[5], colorBox);
    debugDrawSystem->drawLine(box[5], box[6], colorBox);
    debugDrawSystem->drawLine(box[6], box[7], colorBox);
    debugDrawSystem->drawLine(box[7], box[4], colorBox);
 
    debugDrawSystem->setEnabled(true);
}
 
static bool lineLineIntersection(QVector2D a, QVector2D b, QVector2D c, QVector2D d)
{
    // Line AB represented as a1x + b1y = c1
    double a1 = b.y() - a.y();
    double b1 = a.x() - b.x();
    double c1 = a1 * (a.x()) + b1 * (a.y());
 
    // Line CD represented as a2x + b2y = c2
    double a2 = d.y() - c.y();
    double b2 = c.x() - d.x();
    double c2 = a2 * (c.x()) + b2 * (c.y());
 
    double determinant = a1 * b2 - a2 * b1;
 
    if (qFuzzyCompare(determinant, 0)) {
        // The lines are parallel.
        return false;
    }
 
    double x = (b2 * c1 - b1 * c2) / determinant;
    double y = (a1 * c2 - a2 * c1) / determinant;
    const QVector2D min = QVector2D(qMin(a.x(), b.x()), qMin(a.y(), b.y()));
    const QVector2D max = QVector2D(qMax(a.x(), b.x()), qMax(a.y(), b.y()));
    return x > min.x() && x < max.x() && y > min.y() && y < max.y();
}
 
struct Vertex
{
    QVector3D position;
    std::array<int, 3> neighbors = { -1, -1, -1 };
    bool active = true;
    bool borked = false;
 
    void addNeighbor(int neighbor)
    {
        if (neighbor == neighbors[0] || neighbor == neighbors[1] || neighbor == neighbors[2]) {
            borked = true;
            return;
        }
 
        if (neighbors[0] == -1) {
            neighbors[0] = neighbor;
        } else if (neighbors[1] == -1) {
            neighbors[1] = neighbor;
        } else if (neighbors[2] == -1) {
            neighbors[2] = neighbor;
        } else {
            borked = true;
        }
    }
 
    void removeNeighbor(int neighbor)
    {
        if (neighbors[0] == neighbor) {
            neighbors[0] = -1;
        } else if (neighbors[1] == neighbor) {
            neighbors[1] = -1;
        } else if (neighbors[2] == neighbor) {
            neighbors[2] = -1;
        } else {
            borked = true;
        }
    }
 
    bool allNeighbors() const { return neighbors[0] != -1 && neighbors[1] != -1 && neighbors[2] != -1; }
};
 
static QList<QVector3D> sliceBoxByPlanes(const QList<std::array<QVector3D, 2>> &planes,
                                         const QSSGBoxPoints &castingBox,
                                         QSSGDebugDrawSystem *debugDrawSystem,
                                         const QColor &color)
{
 
    QList<Vertex> vertices;
    vertices.reserve(castingBox.size());
    for (const auto &p : castingBox) {
        Vertex point;
        point.position = p;
        vertices.push_back(point);
    }
 
    for (auto line : BOX_LINE_INDICES) {
        vertices[line[0]].addNeighbor(line[1]);
        vertices[line[1]].addNeighbor(line[0]);
    }
 
    QList<QVector2D> planePoints;
    QList<QPair<quint8, quint8>> lines;
    QList<bool> intersecting;
    QList<quint8> newVertexIndices;
    QList<Vertex> verticesPrev;
 
    for (const auto &plane : planes) {
        const QVector3D center = plane[0];
        const QVector3D normal = plane[1];
        newVertexIndices.clear();
        verticesPrev = vertices;
        for (int vertIndexI = 0, vertEnd = vertices.length(); vertIndexI < vertEnd; ++vertIndexI) {
            Vertex vertex = vertices[vertIndexI];
            if (!vertex.active)
                continue;
            // Check if 'p' is lying above or below plane
            // above = inside frustum, below = outside frustum
            if (QVector3D::dotProduct(vertex.position - center, normal) >= 0) {
                continue;
                // 'p' lies outside frustum so project 'p' onto the plane so it lies on the edge of the frustum
            }
 
            // Disable and remove vertex for neighbors
            vertices[vertIndexI].active = false; // disable
            for (int neighborIndex : vertex.neighbors) {
                if (neighborIndex == -1)
                    continue;
                vertices[neighborIndex].removeNeighbor(vertIndexI);
            }
 
            for (int neighborIndex : vertex.neighbors) {
                if (neighborIndex == -1)
                    continue;
 
                const quint32 idx0 = vertIndexI;
                const quint32 idx1 = neighborIndex;
 
                // non-intersecting line, skip
                if (QVector3D::dotProduct(vertices[idx1].position - center, normal) < 0)
                    continue;
 
                QVector3D planePoint = center;
                QVector3D planeNormal = normal;
                QVector3D linePoint = vertices[idx0].position;
                QVector3D lineDirection = vertices[idx0].position - vertices[idx1].position;
                QSSGPlane plane(planePoint, planeNormal);
                QSSGRenderRay ray(linePoint, lineDirection);
 
                if (auto intersect = QSSGRenderRay::intersect(plane, ray); intersect.has_value()) {
                    int addedIdx = vertices.length();
                    Q_ASSERT(addedIdx <= 255);
                    Vertex p;
                    p.position = intersect.value();
                    p.addNeighbor(idx1);
                    vertices[idx1].addNeighbor(addedIdx);
                    vertices.push_back(p);
                    newVertexIndices.push_back(addedIdx);
                }
            }
        }
 
        if (newVertexIndices.isEmpty())
            continue;
 
        // Create rotation matrix from plane
        const QMatrix4x4 transform = buildOrthonormalBasis(normal);
        planePoints.clear();
        planePoints.reserve(newVertexIndices.length());
        for (auto &p0 : newVertexIndices) {
            QVector3D p = transform.map(vertices[p0].position);
            planePoints.push_back(QVector2D(p.x(), p.y()));
        }
 
        // Create all possible lines from point
        // num lines = (num_points/2)^2
        lines.clear();
        lines.reserve((planePoints.length() * planePoints.length()) / 4);
        for (int i = 0, length = planePoints.length(); i < length; ++i) {
            for (int j = i + 1; j < length; ++j) {
                lines.push_back({ i, j });
            }
        }
 
        // O((num_lines/2)^2)
        intersecting.clear();
        intersecting.resize(lines.length(), false);
        for (int i = 0, length = lines.length(); i < length; ++i) {
            QPair<quint8, quint8> lineI = lines[i];
            QVector2D a = planePoints[lineI.first];
            QVector2D b = planePoints[lineI.second];
            for (int j = i + 1; j < length; ++j) {
                QPair<quint8, quint8> lineJ = lines[j];
 
                // Skip connected lines
                if (lineJ.first == lineI.first || lineJ.first == lineI.second || lineJ.second == lineI.first
                    || lineJ.second == lineI.second)
                    continue;
 
                QVector2D c = planePoints[lineJ.first];
                QVector2D d = planePoints[lineJ.second];
                if (lineLineIntersection(a, b, c, d)) {
                    intersecting[i] = true;
                    intersecting[j] = true;
                }
            }
        }
 
        for (int i = 0, length = lines.length(); i < length; ++i) {
            if (intersecting[i]) {
                continue;
            }
 
            QPair<quint8, quint8> lineI = lines[i];
            int a = newVertexIndices[lineI.first];
            int b = newVertexIndices[lineI.second];
            vertices[a].addNeighbor(b);
            vertices[b].addNeighbor(a);
        }
 
        // Sanity check and revert if any point is borked
        for (const Vertex &point : std::as_const(vertices)) {
            if (point.active && (point.borked || !point.allNeighbors())) {
                vertices = verticesPrev;
                break;
            }
        }
    }
 
    QList<QVector3D> result;
    result.reserve(vertices.length());
    for (const Vertex &vertex : std::as_const(vertices)) {
        if (vertex.active)
            result.push_back(vertex.position);
    }
 
    if (debugDrawSystem) {
        debugDrawSystem->setEnabled(true);
        for (int i = 0; i < vertices.length(); i++) {
            Vertex point = vertices[i];
            if (!point.active)
                continue;
 
            QVector3D position = vertices[i].position;
            debugDrawSystem->drawLine(position, vertices[point.neighbors[0]].position, color);
            debugDrawSystem->drawLine(position, vertices[point.neighbors[1]].position, color);
            debugDrawSystem->drawLine(position, vertices[point.neighbors[2]].position, color);
        }
    }
 
    return result;
}
 
QList<QVector3D> ShadowmapHelpers::intersectBoxByFrustum(const std::array<QVector3D, 8> &frustumPoints,
                                                         const QSSGBoxPoints &box,
                                                         QSSGDebugDrawSystem *debugDrawSystem,
                                                         const QColor &color)
{
    static std::array<std::array<int, 4>, 6> faceIndices = {
        std::array<int, 4> { 0, 1, 2, 3 }, std::array<int, 4> { 0, 3, 7, 4 }, std::array<int, 4> { 3, 2, 6, 7 },
        std::array<int, 4> { 7, 6, 5, 4 }, std::array<int, 4> { 4, 5, 1, 0 }, std::array<int, 4> { 2, 1, 5, 6 },
    };
 
    QList<std::array<QVector3D, 2>> faces;
    faces.resize(faceIndices.size());
    for (int i = 0; i < int(faceIndices.size()); ++i) {
        std::array<int, 4> face = faceIndices[i];
        QVector3D center = frustumPoints[face[0]]; // Since the plane is infinite we can take any point
        QVector3D b = frustumPoints[face[1]] - frustumPoints[face[0]];
        QVector3D a = frustumPoints[face[2]] - frustumPoints[face[0]];
        QVector3D n = QVector3D::crossProduct(a, b).normalized();
        faces[i] = { center, n };
    }
 
    return sliceBoxByPlanes(faces, box, debugDrawSystem, color);
}
 
QList<QVector3D> ShadowmapHelpers::intersectBoxByBox(const QSSGBounds3 &boxBounds, const QSSGBoxPoints &box)
{
    const float minX = boxBounds.minimum.x();
    const float minY = boxBounds.minimum.y();
    const float minZ = boxBounds.minimum.z();
    const float maxX = boxBounds.maximum.x();
    const float maxY = boxBounds.maximum.y();
    const float maxZ = boxBounds.maximum.z();
 
    QSSGBoxPoints points;
    points[0] = QVector3D(minX, minY, minZ);
    points[1] = QVector3D(maxX, minY, minZ);
    points[2] = QVector3D(maxX, maxY, minZ);
    points[3] = QVector3D(minX, maxY, minZ);
    points[4] = QVector3D(minX, minY, maxZ);
    points[5] = QVector3D(maxX, minY, maxZ);
    points[6] = QVector3D(maxX, maxY, maxZ);
    points[7] = QVector3D(minX, maxY, maxZ);
 
    // constexpr std::array<int, 4> NEAR = { 0, 1, 2, 3 };
    // constexpr std::array<int, 4> FAR = { 7, 6, 5, 4 };
    static constexpr std::array<int, 4> LEFT = { 0, 3, 7, 4 };
    static constexpr std::array<int, 4> TOP = { 3, 2, 6, 7 };
    static constexpr std::array<int, 4> BOTTOM = { 4, 5, 1, 0 };
    static constexpr std::array<int, 4> RIGHT = { 2, 1, 5, 6 };
    static constexpr std::array<std::array<int, 4>, 4> faceIndices = { LEFT, TOP, BOTTOM, RIGHT };
 
    QList<std::array<QVector3D, 2>> faces;
    faces.resize(faceIndices.size());
    for (int i = 0; i < int(faceIndices.size()); ++i) {
        std::array<int, 4> face = faceIndices[i];
        QVector3D center = points[face[0]]; // Since the plane is infinite we can take any point
        QVector3D b = points[face[1]] - points[face[0]];
        QVector3D a = points[face[2]] - points[face[0]];
        QVector3D n = -QVector3D::crossProduct(a, b).normalized();
        faces[i] = { center, n };
    }
 
    return sliceBoxByPlanes(faces, box, nullptr, QColorConstants::Black);
}
 
QT_END_NAMESPACE