Revision control
Copy as Markdown
// 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