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
85static bool lineLineIntersection(QVector2D a, QVector2D b, QVector2D c, QVector2D d)
86{
87 // Line AB represented as a1x + b1y = c1
88 double a1 = b.y() - a.y();
89 double b1 = a.x() - b.x();
90 double c1 = a1 * (a.x()) + b1 * (a.y());
91
92 // Line CD represented as a2x + b2y = c2
93 double a2 = d.y() - c.y();
94 double b2 = c.x() - d.x();
95 double c2 = a2 * (c.x()) + b2 * (c.y());
96
97 double determinant = a1 * b2 - a2 * b1;
98
99 if (qFuzzyCompare(p1: determinant, p2: 0)) {
100 // The lines are parallel.
101 return false;
102 }
103
104 double x = (b2 * c1 - b1 * c2) / determinant;
105 double y = (a1 * c2 - a2 * c1) / determinant;
106 const QVector2D min = QVector2D(qMin(a: a.x(), b: b.x()), qMin(a: a.y(), b: b.y()));
107 const QVector2D max = QVector2D(qMax(a: a.x(), b: b.x()), qMax(a: a.y(), b: b.y()));
108 return x > min.x() && x < max.x() && y > min.y() && y < max.y();
109}
110
111struct Vertex
112{
113 QVector3D position;
114 std::array<int, 3> neighbors = { -1, -1, -1 };
115 bool active = true;
116 bool borked = false;
117
118 void addNeighbor(int neighbor)
119 {
120 if (neighbor == neighbors[0] || neighbor == neighbors[1] || neighbor == neighbors[2]) {
121 borked = true;
122 return;
123 }
124
125 if (neighbors[0] == -1) {
126 neighbors[0] = neighbor;
127 } else if (neighbors[1] == -1) {
128 neighbors[1] = neighbor;
129 } else if (neighbors[2] == -1) {
130 neighbors[2] = neighbor;
131 } else {
132 borked = true;
133 }
134 }
135
136 void removeNeighbor(int neighbor)
137 {
138 if (neighbors[0] == neighbor) {
139 neighbors[0] = -1;
140 } else if (neighbors[1] == neighbor) {
141 neighbors[1] = -1;
142 } else if (neighbors[2] == neighbor) {
143 neighbors[2] = -1;
144 } else {
145 borked = true;
146 }
147 }
148
149 bool allNeighbors() const { return neighbors[0] != -1 && neighbors[1] != -1 && neighbors[2] != -1; }
150};
151
152static QList<QVector3D> sliceBoxByPlanes(const QList<std::array<QVector3D, 2>> &planes,
153 const QSSGBoxPoints &castingBox,
154 QSSGDebugDrawSystem *debugDrawSystem,
155 const QColor &color)
156{
157
158 QList<Vertex> vertices;
159 vertices.reserve(asize: castingBox.size());
160 for (const auto &p : castingBox) {
161 Vertex point;
162 point.position = p;
163 vertices.push_back(t: point);
164 }
165
166 for (auto line : BOX_LINE_INDICES) {
167 vertices[line[0]].addNeighbor(neighbor: line[1]);
168 vertices[line[1]].addNeighbor(neighbor: line[0]);
169 }
170
171 QList<QVector2D> planePoints;
172 QList<QPair<quint8, quint8>> lines;
173 QList<bool> intersecting;
174 QList<quint8> newVertexIndices;
175 QList<Vertex> verticesPrev;
176
177 for (const auto &plane : planes) {
178 const QVector3D center = plane[0];
179 const QVector3D normal = plane[1];
180 newVertexIndices.clear();
181 verticesPrev = vertices;
182 for (int vertIndexI = 0, vertEnd = vertices.length(); vertIndexI < vertEnd; ++vertIndexI) {
183 Vertex vertex = vertices[vertIndexI];
184 if (!vertex.active)
185 continue;
186 // Check if 'p' is lying above or below plane
187 // above = inside frustum, below = outside frustum
188 if (QVector3D::dotProduct(v1: vertex.position - center, v2: normal) >= 0) {
189 continue;
190 // 'p' lies outside frustum so project 'p' onto the plane so it lies on the edge of the frustum
191 }
192
193 // Disable and remove vertex for neighbors
194 vertices[vertIndexI].active = false; // disable
195 for (int neighborIndex : vertex.neighbors) {
196 if (neighborIndex == -1)
197 continue;
198 vertices[neighborIndex].removeNeighbor(neighbor: vertIndexI);
199 }
200
201 for (int neighborIndex : vertex.neighbors) {
202 if (neighborIndex == -1)
203 continue;
204
205 const quint32 idx0 = vertIndexI;
206 const quint32 idx1 = neighborIndex;
207
208 // non-intersecting line, skip
209 if (QVector3D::dotProduct(v1: vertices[idx1].position - center, v2: normal) < 0)
210 continue;
211
212 QVector3D planePoint = center;
213 QVector3D planeNormal = normal;
214 QVector3D linePoint = vertices[idx0].position;
215 QVector3D lineDirection = vertices[idx0].position - vertices[idx1].position;
216 QSSGPlane plane(planePoint, planeNormal);
217 QSSGRenderRay ray(linePoint, lineDirection);
218
219 if (auto intersect = QSSGRenderRay::intersect(inPlane: plane, ray); intersect.has_value()) {
220 int addedIdx = vertices.length();
221 Q_ASSERT(addedIdx <= 255);
222 Vertex p;
223 p.position = intersect.value();
224 p.addNeighbor(neighbor: idx1);
225 vertices[idx1].addNeighbor(neighbor: addedIdx);
226 vertices.push_back(t: p);
227 newVertexIndices.push_back(t: addedIdx);
228 }
229 }
230 }
231
232 if (newVertexIndices.isEmpty())
233 continue;
234
235 // Create rotation matrix from plane
236 QMatrix4x4 transform;
237 // we let z (forward) = normal of the plane, the other vectors are
238 // unimportant.
239 const QVector3D forward = normal;
240 const QVector3D right = QVector3D(-forward.y(), forward.x(), 0);
241 const QVector3D up = QVector3D::crossProduct(v1: forward, v2: right);
242 transform.setRow(index: 0, value: QVector4D(right, 0.0f));
243 transform.setRow(index: 1, value: QVector4D(up, 0.0f));
244 transform.setRow(index: 2, value: QVector4D(forward, 0.0f));
245 transform.setRow(index: 3, value: QVector4D(0.0f, 0.0f, 0.0f, 1.0f));
246
247 planePoints.clear();
248 planePoints.reserve(asize: newVertexIndices.length());
249 for (auto &p0 : newVertexIndices) {
250 QVector3D p = transform.map(point: vertices[p0].position);
251 planePoints.push_back(t: QVector2D(p.x(), p.y()));
252 }
253
254 // Create all possible lines from point
255 // num lines = (num_points/2)^2
256 lines.clear();
257 lines.reserve(asize: (planePoints.length() * planePoints.length()) / 4);
258 for (int i = 0, length = planePoints.length(); i < length; ++i) {
259 for (int j = i + 1; j < length; ++j) {
260 lines.push_back(t: { i, j });
261 }
262 }
263
264 // O((num_lines/2)^2)
265 intersecting.clear();
266 intersecting.resize(size: lines.length(), c: false);
267 for (int i = 0, length = lines.length(); i < length; ++i) {
268 QPair<quint8, quint8> lineI = lines[i];
269 QVector2D a = planePoints[lineI.first];
270 QVector2D b = planePoints[lineI.second];
271 for (int j = i + 1; j < length; ++j) {
272 QPair<quint8, quint8> lineJ = lines[j];
273
274 // Skip connected lines
275 if (lineJ.first == lineI.first || lineJ.first == lineI.second || lineJ.second == lineI.first
276 || lineJ.second == lineI.second)
277 continue;
278
279 QVector2D c = planePoints[lineJ.first];
280 QVector2D d = planePoints[lineJ.second];
281 if (lineLineIntersection(a, b, c, d)) {
282 intersecting[i] = true;
283 intersecting[j] = true;
284 }
285 }
286 }
287
288 for (int i = 0, length = lines.length(); i < length; ++i) {
289 if (intersecting[i]) {
290 continue;
291 }
292
293 QPair<quint8, quint8> lineI = lines[i];
294 int a = newVertexIndices[lineI.first];
295 int b = newVertexIndices[lineI.second];
296 vertices[a].addNeighbor(neighbor: b);
297 vertices[b].addNeighbor(neighbor: a);
298 }
299
300 // Sanity check and revert if any point is borked
301 for (const Vertex &point : vertices) {
302 if (point.active && (point.borked || !point.allNeighbors())) {
303 vertices = verticesPrev;
304 break;
305 }
306 }
307 }
308
309 QList<QVector3D> result;
310 result.reserve(asize: vertices.length());
311 for (const Vertex &vertex : vertices) {
312 if (vertex.active)
313 result.push_back(t: vertex.position);
314 }
315
316 if (debugDrawSystem) {
317 debugDrawSystem->setEnabled(true);
318 for (int i = 0; i < vertices.length(); i++) {
319 Vertex point = vertices[i];
320 if (!point.active)
321 continue;
322
323 QVector3D position = vertices[i].position;
324 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[0]].position, color);
325 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[1]].position, color);
326 debugDrawSystem->drawLine(startPoint: position, endPoint: vertices[point.neighbors[2]].position, color);
327 }
328 }
329
330 return result;
331}
332
333QList<QVector3D> ShadowmapHelpers::intersectBoxByFrustum(const std::array<QVector3D, 8> &frustumPoints,
334 const QSSGBoxPoints &box,
335 QSSGDebugDrawSystem *debugDrawSystem,
336 const QColor &color)
337{
338 static std::array<std::array<int, 4>, 6> faceIndices = {
339 std::array<int, 4> { 0, 1, 2, 3 }, std::array<int, 4> { 0, 3, 7, 4 }, std::array<int, 4> { 3, 2, 6, 7 },
340 std::array<int, 4> { 7, 6, 5, 4 }, std::array<int, 4> { 4, 5, 1, 0 }, std::array<int, 4> { 2, 1, 5, 6 },
341 };
342
343 QList<std::array<QVector3D, 2>> faces;
344 faces.resize(size: faceIndices.size());
345 for (int i = 0; i < int(faceIndices.size()); ++i) {
346 std::array<int, 4> face = faceIndices[i];
347 QVector3D center = frustumPoints[face[0]]; // Since the plane is infinite we can take any point
348 QVector3D b = frustumPoints[face[1]] - frustumPoints[face[0]];
349 QVector3D a = frustumPoints[face[2]] - frustumPoints[face[0]];
350 QVector3D n = QVector3D::crossProduct(v1: a, v2: b).normalized();
351 faces[i] = { center, n };
352 }
353
354 return sliceBoxByPlanes(planes: faces, castingBox: box, debugDrawSystem, color);
355}
356
357QList<QVector3D> ShadowmapHelpers::intersectBoxByBox(const QSSGBounds3 &boxBounds, const QSSGBoxPoints &box)
358{
359 const float minX = boxBounds.minimum.x();
360 const float minY = boxBounds.minimum.y();
361 const float minZ = boxBounds.minimum.z();
362 const float maxX = boxBounds.maximum.x();
363 const float maxY = boxBounds.maximum.y();
364 const float maxZ = boxBounds.maximum.z();
365
366 QSSGBoxPoints points;
367 points[0] = QVector3D(minX, minY, minZ);
368 points[1] = QVector3D(maxX, minY, minZ);
369 points[2] = QVector3D(maxX, maxY, minZ);
370 points[3] = QVector3D(minX, maxY, minZ);
371 points[4] = QVector3D(minX, minY, maxZ);
372 points[5] = QVector3D(maxX, minY, maxZ);
373 points[6] = QVector3D(maxX, maxY, maxZ);
374 points[7] = QVector3D(minX, maxY, maxZ);
375
376 // constexpr std::array<int, 4> NEAR = { 0, 1, 2, 3 };
377 // constexpr std::array<int, 4> FAR = { 7, 6, 5, 4 };
378 static constexpr std::array<int, 4> LEFT = { 0, 3, 7, 4 };
379 static constexpr std::array<int, 4> TOP = { 3, 2, 6, 7 };
380 static constexpr std::array<int, 4> BOTTOM = { 4, 5, 1, 0 };
381 static constexpr std::array<int, 4> RIGHT = { 2, 1, 5, 6 };
382 static constexpr std::array<std::array<int, 4>, 4> faceIndices = { LEFT, TOP, BOTTOM, RIGHT };
383
384 QList<std::array<QVector3D, 2>> faces;
385 faces.resize(size: faceIndices.size());
386 for (int i = 0; i < int(faceIndices.size()); ++i) {
387 std::array<int, 4> face = faceIndices[i];
388 QVector3D center = points[face[0]]; // Since the plane is infinite we can take any point
389 QVector3D b = points[face[1]] - points[face[0]];
390 QVector3D a = points[face[2]] - points[face[0]];
391 QVector3D n = -QVector3D::crossProduct(v1: a, v2: b).normalized();
392 faces[i] = { center, n };
393 }
394
395 return sliceBoxByPlanes(planes: faces, castingBox: box, debugDrawSystem: nullptr, color: QColorConstants::Black);
396}
397
398QT_END_NAMESPACE
399

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