1// Copyright (C) 2024 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
3
4#include "qssgshadowmaphelpers_p.h"
5
6#include "qssgdebugdrawsystem_p.h"
7#include "qssgrenderray_p.h"
8
9QT_BEGIN_NAMESPACE
10
11// These indices need to match the order in QSSGBounds3::toQSSGBoxPointsNoEmptyCheck()
12static constexpr std::array<std::array<int, 2>, 12> BOX_LINE_INDICES = {
13 std::array<int, 2> { 0, 1 }, std::array<int, 2> { 1, 2 }, std::array<int, 2> { 2, 3 }, std::array<int, 2> { 3, 0 },
14 std::array<int, 2> { 4, 5 }, std::array<int, 2> { 5, 6 }, std::array<int, 2> { 6, 7 }, std::array<int, 2> { 7, 4 },
15 std::array<int, 2> { 0, 4 }, std::array<int, 2> { 1, 5 }, std::array<int, 2> { 2, 6 }, std::array<int, 2> { 3, 7 },
16};
17
18void ShadowmapHelpers::addDebugBox(const QSSGBoxPoints &box, const QColor &color, QSSGDebugDrawSystem *debugDrawSystem)
19{
20 if (!debugDrawSystem)
21 return;
22
23 for (const auto line : BOX_LINE_INDICES)
24 debugDrawSystem->drawLine(startPoint: box[line[0]], endPoint: box[line[1]], color);
25
26 debugDrawSystem->setEnabled(true);
27}
28
29void ShadowmapHelpers::addDebugFrustum(const QSSGBoxPoints &frustumPoints, const QColor &color, QSSGDebugDrawSystem *debugDrawSystem)
30{
31 ShadowmapHelpers::addDebugBox(box: frustumPoints, color, debugDrawSystem);
32}
33
34void ShadowmapHelpers::addDirectionalLightDebugBox(const QSSGBoxPoints &box, QSSGDebugDrawSystem *debugDrawSystem)
35{
36 if (!debugDrawSystem)
37 return;
38
39 constexpr QColor colorBox = QColorConstants::Yellow;
40
41 // .7------6
42 // .' | .'|
43 // 3---+--2' |
44 // | | | |
45 // | .4--+---5
46 // |.' | .'
47 // 0------1'
48
49 // Find shortest axis line
50 float shortestAxisSq = (box[0] - box[1]).lengthSquared();
51 shortestAxisSq = std::min(a: shortestAxisSq, b: (box[0] - box[4]).lengthSquared());
52 shortestAxisSq = std::min(a: shortestAxisSq, b: (box[0] - box[3]).lengthSquared());
53 const float axisLength = qSqrt(v: shortestAxisSq) * 0.5f;
54
55 auto drawAxisLine = [&](const QVector3D &from, const QVector3D &to, const QColor &axisColor) {
56 const QVector3D dir = (to - from).normalized();
57 const QVector3D mid = from + dir * axisLength;
58 debugDrawSystem->drawLine(startPoint: from, endPoint: mid, color: axisColor);
59 debugDrawSystem->drawLine(startPoint: mid, endPoint: to, color: colorBox);
60 };
61
62 // Draw x,y,z axis in r,g,b color and rest in box color
63
64 // Closest to light (front)
65 drawAxisLine(box[0], box[1], QColorConstants::Red);
66 debugDrawSystem->drawLine(startPoint: box[1], endPoint: box[2], color: colorBox);
67 drawAxisLine(box[0], box[3], QColorConstants::Green);
68 debugDrawSystem->drawLine(startPoint: box[2], endPoint: box[3], color: colorBox);
69
70 // Lines parallel to light direction
71 drawAxisLine(box[0], box[4], QColorConstants::Blue);
72 debugDrawSystem->drawLine(startPoint: box[1], endPoint: box[5], color: colorBox);
73 debugDrawSystem->drawLine(startPoint: box[2], endPoint: box[6], color: colorBox);
74 debugDrawSystem->drawLine(startPoint: box[3], endPoint: box[7], color: colorBox);
75
76 // Furthest from light (back)
77 debugDrawSystem->drawLine(startPoint: box[4], endPoint: box[5], color: colorBox);
78 debugDrawSystem->drawLine(startPoint: box[5], endPoint: box[6], color: colorBox);
79 debugDrawSystem->drawLine(startPoint: box[6], endPoint: box[7], color: colorBox);
80 debugDrawSystem->drawLine(startPoint: box[7], endPoint: box[4], color: colorBox);
81
82 debugDrawSystem->setEnabled(true);
83}
84
85void ShadowmapHelpers::addPointLightDebugBox(const QVector3D &lightPos, const float shadowMapFar, QSSGDebugDrawSystem *debugDrawSystem)
86{
87 if (!debugDrawSystem)
88 return;
89
90 QSSGBounds3 bounds;
91 bounds.include(v: lightPos - QVector3D(shadowMapFar, shadowMapFar, shadowMapFar));
92 bounds.include(v: lightPos + QVector3D(shadowMapFar, shadowMapFar, shadowMapFar));
93 addDebugBox(box: bounds.toQSSGBoxPoints(), color: QColorConstants::Yellow, debugDrawSystem);
94}
95
96static bool lineLineIntersection(QVector2D a, QVector2D b, QVector2D c, QVector2D d)
97{
98 // Line AB represented as a1x + b1y = c1
99 double a1 = b.y() - a.y();
100 double b1 = a.x() - b.x();
101 double c1 = a1 * (a.x()) + b1 * (a.y());
102
103 // Line CD represented as a2x + b2y = c2
104 double a2 = d.y() - c.y();
105 double b2 = c.x() - d.x();
106 double c2 = a2 * (c.x()) + b2 * (c.y());
107
108 double determinant = a1 * b2 - a2 * b1;
109
110 if (qFuzzyCompare(p1: determinant, p2: 0)) {
111 // The lines are parallel.
112 return false;
113 }
114
115 double x = (b2 * c1 - b1 * c2) / determinant;
116 double y = (a1 * c2 - a2 * c1) / determinant;
117 const QVector2D min = QVector2D(qMin(a: a.x(), b: b.x()), qMin(a: a.y(), b: b.y()));
118 const QVector2D max = QVector2D(qMax(a: a.x(), b: b.x()), qMax(a: a.y(), b: b.y()));
119 return x > min.x() && x < max.x() && y > min.y() && y < max.y();
120}
121
122struct Vertex
123{
124 QVector3D position;
125 std::array<int, 3> neighbors = { -1, -1, -1 };
126 bool active = true;
127 bool borked = false;
128
129 void addNeighbor(int neighbor)
130 {
131 if (neighbor == neighbors[0] || neighbor == neighbors[1] || neighbor == neighbors[2]) {
132 borked = true;
133 return;
134 }
135
136 if (neighbors[0] == -1) {
137 neighbors[0] = neighbor;
138 } else if (neighbors[1] == -1) {
139 neighbors[1] = neighbor;
140 } else if (neighbors[2] == -1) {
141 neighbors[2] = neighbor;
142 } else {
143 borked = true;
144 }
145 }
146
147 void removeNeighbor(int neighbor)
148 {
149 if (neighbors[0] == neighbor) {
150 neighbors[0] = -1;
151 } else if (neighbors[1] == neighbor) {
152 neighbors[1] = -1;
153 } else if (neighbors[2] == neighbor) {
154 neighbors[2] = -1;
155 } else {
156 borked = true;
157 }
158 }
159
160 bool allNeighbors() const { return neighbors[0] != -1 && neighbors[1] != -1 && neighbors[2] != -1; }
161};
162
163static QList<QVector3D> sliceBoxByPlanes(const QList<std::array<QVector3D, 2>> &planes,
164 const QSSGBoxPoints &castingBox,
165 QSSGDebugDrawSystem *debugDrawSystem,
166 const QColor &color)
167{
168
169 QList<Vertex> vertices;
170 vertices.reserve(asize: castingBox.size());
171 for (const auto &p : castingBox) {
172 Vertex point;
173 point.position = p;
174 vertices.push_back(t: point);
175 }
176
177 for (auto line : BOX_LINE_INDICES) {
178 vertices[line[0]].addNeighbor(neighbor: line[1]);
179 vertices[line[1]].addNeighbor(neighbor: line[0]);
180 }
181
182 QList<QVector2D> planePoints;
183 QList<QPair<quint8, quint8>> lines;
184 QList<bool> intersecting;
185 QList<quint8> newVertexIndices;
186 QList<Vertex> verticesPrev;
187
188 for (const auto &plane : planes) {
189 const QVector3D center = plane[0];
190 const QVector3D normal = plane[1];
191 newVertexIndices.clear();
192 verticesPrev = vertices;
193 for (int vertIndexI = 0, vertEnd = vertices.length(); vertIndexI < vertEnd; ++vertIndexI) {
194 Vertex vertex = vertices[vertIndexI];
195 if (!vertex.active)
196 continue;
197 // Check if 'p' is lying above or below plane
198 // above = inside frustum, below = outside frustum
199 if (QVector3D::dotProduct(v1: vertex.position - center, v2: normal) >= 0) {
200 continue;
201 // 'p' lies outside frustum so project 'p' onto the plane so it lies on the edge of the frustum
202 }
203
204 // Disable and remove vertex for neighbors
205 vertices[vertIndexI].active = false; // disable
206 for (int neighborIndex : vertex.neighbors) {
207 if (neighborIndex == -1)
208 continue;
209 vertices[neighborIndex].removeNeighbor(neighbor: vertIndexI);
210 }
211
212 for (int neighborIndex : vertex.neighbors) {
213 if (neighborIndex == -1)
214 continue;
215
216 const quint32 idx0 = vertIndexI;
217 const quint32 idx1 = neighborIndex;
218
219 // non-intersecting line, skip
220 if (QVector3D::dotProduct(v1: vertices[idx1].position - center, v2: normal) < 0)
221 continue;
222
223 QVector3D planePoint = center;
224 QVector3D planeNormal = normal;
225 QVector3D linePoint = vertices[idx0].position;
226 QVector3D lineDirection = vertices[idx0].position - vertices[idx1].position;
227 QSSGPlane plane(planePoint, planeNormal);
228 QSSGRenderRay ray(linePoint, lineDirection);
229
230 if (auto intersect = QSSGRenderRay::intersect(inPlane: plane, ray); intersect.has_value()) {
231 int addedIdx = vertices.length();
232 Q_ASSERT(addedIdx <= 255);
233 Vertex p;
234 p.position = intersect.value();
235 p.addNeighbor(neighbor: idx1);
236 vertices[idx1].addNeighbor(neighbor: addedIdx);
237 vertices.push_back(t: p);
238 newVertexIndices.push_back(t: addedIdx);
239 }
240 }
241 }
242
243 if (newVertexIndices.isEmpty())
244 continue;
245
246 // Create rotation matrix from plane
247 QMatrix4x4 transform;
248 // we let z (forward) = normal of the plane, the other vectors are
249 // unimportant.
250 const QVector3D forward = normal;
251 const QVector3D right = QVector3D(-forward.y(), forward.x(), 0);
252 const QVector3D up = QVector3D::crossProduct(v1: forward, v2: right);
253 transform.setRow(index: 0, value: QVector4D(right, 0.0f));
254 transform.setRow(index: 1, value: QVector4D(up, 0.0f));
255 transform.setRow(index: 2, value: QVector4D(forward, 0.0f));
256 transform.setRow(index: 3, value: QVector4D(0.0f, 0.0f, 0.0f, 1.0f));
257
258 planePoints.clear();
259 planePoints.reserve(asize: newVertexIndices.length());
260 for (auto &p0 : newVertexIndices) {
261 QVector3D p = transform.map(point: vertices[p0].position);
262 planePoints.push_back(t: QVector2D(p.x(), p.y()));
263 }
264
265 // Create all possible lines from point
266 // num lines = (num_points/2)^2
267 lines.clear();
268 lines.reserve(asize: (planePoints.length() * planePoints.length()) / 4);
269 for (int i = 0, length = planePoints.length(); i < length; ++i) {
270 for (int j = i + 1; j < length; ++j) {
271 lines.push_back(t: { i, j });
272 }
273 }
274
275 // O((num_lines/2)^2)
276 intersecting.clear();
277 intersecting.resize(size: lines.length(), c: false);
278 for (int i = 0, length = lines.length(); i < length; ++i) {
279 QPair<quint8, quint8> lineI = lines[i];
280 QVector2D a = planePoints[lineI.first];
281 QVector2D b = planePoints[lineI.second];
282 for (int j = i + 1; j < length; ++j) {
283 QPair<quint8, quint8> lineJ = lines[j];
284
285 // Skip connected lines
286 if (lineJ.first == lineI.first || lineJ.first == lineI.second || lineJ.second == lineI.first
287 || lineJ.second == lineI.second)
288 continue;
289
290 QVector2D c = planePoints[lineJ.first];
291 QVector2D d = planePoints[lineJ.second];
292 if (lineLineIntersection(a, b, c, d)) {
293 intersecting[i] = true;
294 intersecting[j] = true;
295 }
296 }
297 }
298
299 for (int i = 0, length = lines.length(); i < length; ++i) {
300 if (intersecting[i]) {
301 continue;
302 }
303
304 QPair<quint8, quint8> lineI = lines[i];
305 int a = newVertexIndices[lineI.first];
306 int b = newVertexIndices[lineI.second];
307 vertices[a].addNeighbor(neighbor: b);
308 vertices[b].addNeighbor(neighbor: a);
309 }
310
311 // Sanity check and revert if any point is borked
312 for (const Vertex &point : vertices) {
313 if (point.active && (point.borked || !point.allNeighbors())) {
314 vertices = verticesPrev;
315 break;
316 }
317 }
318 }
319
320 QList<QVector3D> result;
321 result.reserve(asize: vertices.length());
322 for (const Vertex &vertex : vertices) {
323 if (vertex.active)
324 result.push_back(t: vertex.position);
325 }
326
327 if (debugDrawSystem) {
328 debugDrawSystem->setEnabled(true);
329 for (int i = 0; i < vertices.length(); i++) {
330 Vertex point = vertices[i];
331 if (!point.active)
332 continue;
333
334 QVector3D position = vertices[i].position;
335 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[0]].position, color);
336 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[1]].position, color);
337 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[2]].position, color);
338 }
339 }
340
341 return result;
342}
343
344QList<QVector3D> ShadowmapHelpers::intersectBoxByFrustum(const std::array<QVector3D, 8> &frustumPoints,
345 const QSSGBoxPoints &box,
346 QSSGDebugDrawSystem *debugDrawSystem,
347 const QColor &color)
348{
349 static std::array<std::array<int, 4>, 6> faceIndices = {
350 std::array<int, 4> { 0, 1, 2, 3 }, std::array<int, 4> { 0, 3, 7, 4 }, std::array<int, 4> { 3, 2, 6, 7 },
351 std::array<int, 4> { 7, 6, 5, 4 }, std::array<int, 4> { 4, 5, 1, 0 }, std::array<int, 4> { 2, 1, 5, 6 },
352 };
353
354 QList<std::array<QVector3D, 2>> faces;
355 faces.resize(size: faceIndices.size());
356 for (int i = 0; i < int(faceIndices.size()); ++i) {
357 std::array<int, 4> face = faceIndices[i];
358 QVector3D center = frustumPoints[face[0]]; // Since the plane is infinite we can take any point
359 QVector3D b = frustumPoints[face[1]] - frustumPoints[face[0]];
360 QVector3D a = frustumPoints[face[2]] - frustumPoints[face[0]];
361 QVector3D n = QVector3D::crossProduct(v1: a, v2: b).normalized();
362 faces[i] = { center, n };
363 }
364
365 return sliceBoxByPlanes(planes: faces, castingBox: box, debugDrawSystem, color);
366}
367
368QList<QVector3D> ShadowmapHelpers::intersectBoxByBox(const QSSGBounds3 &boxBounds, const QSSGBoxPoints &box)
369{
370 const float minX = boxBounds.minimum.x();
371 const float minY = boxBounds.minimum.y();
372 const float minZ = boxBounds.minimum.z();
373 const float maxX = boxBounds.maximum.x();
374 const float maxY = boxBounds.maximum.y();
375 const float maxZ = boxBounds.maximum.z();
376
377 QSSGBoxPoints points;
378 points[0] = QVector3D(minX, minY, minZ);
379 points[1] = QVector3D(maxX, minY, minZ);
380 points[2] = QVector3D(maxX, maxY, minZ);
381 points[3] = QVector3D(minX, maxY, minZ);
382 points[4] = QVector3D(minX, minY, maxZ);
383 points[5] = QVector3D(maxX, minY, maxZ);
384 points[6] = QVector3D(maxX, maxY, maxZ);
385 points[7] = QVector3D(minX, maxY, maxZ);
386
387 // constexpr std::array<int, 4> NEAR = { 0, 1, 2, 3 };
388 // constexpr std::array<int, 4> FAR = { 7, 6, 5, 4 };
389 static constexpr std::array<int, 4> LEFT = { 0, 3, 7, 4 };
390 static constexpr std::array<int, 4> TOP = { 3, 2, 6, 7 };
391 static constexpr std::array<int, 4> BOTTOM = { 4, 5, 1, 0 };
392 static constexpr std::array<int, 4> RIGHT = { 2, 1, 5, 6 };
393 static constexpr std::array<std::array<int, 4>, 4> faceIndices = { LEFT, TOP, BOTTOM, RIGHT };
394
395 QList<std::array<QVector3D, 2>> faces;
396 faces.resize(size: faceIndices.size());
397 for (int i = 0; i < int(faceIndices.size()); ++i) {
398 std::array<int, 4> face = faceIndices[i];
399 QVector3D center = points[face[0]]; // Since the plane is infinite we can take any point
400 QVector3D b = points[face[1]] - points[face[0]];
401 QVector3D a = points[face[2]] - points[face[0]];
402 QVector3D n = -QVector3D::crossProduct(v1: a, v2: b).normalized();
403 faces[i] = { center, n };
404 }
405
406 return sliceBoxByPlanes(planes: faces, castingBox: box, debugDrawSystem: nullptr, color: QColorConstants::Black);
407}
408
409QT_END_NAMESPACE
410

source code of qtquick3d/src/runtimerender/rendererimpl/qssgshadowmaphelpers.cpp