1// Copyright (C) 2008-2012 NVIDIA Corporation.
2// Copyright (C) 2019 The Qt Company Ltd.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
4
5#include "qssgrenderray_p.h"
6
7#include <QtQuick3DUtils/private/qssgplane_p.h>
8#include <QtQuick3DUtils/private/qssgutils_p.h>
9#include <QtQuick3DUtils/private/qssgmeshbvh_p.h>
10#include <QtQuick3DRuntimeRender/private/qssgrendermesh_p.h>
11
12#include <optional>
13
14QT_BEGIN_NAMESPACE
15
16// http://www.siggraph.org/education/materials/HyperGraph/raytrace/rayplane_intersection.htm
17
18std::optional<QVector3D> QSSGRenderRay::intersect(const QSSGPlane &inPlane, const QSSGRenderRay &ray)
19{
20 float Vd = QVector3D::dotProduct(v1: inPlane.n, v2: ray.direction);
21 if (std::abs(x: Vd) < .0001f)
22 return std::nullopt;
23 float V0 = -1.0f * (QVector3D::dotProduct(v1: inPlane.n, v2: ray.origin) + inPlane.d);
24 float t = V0 / Vd;
25 return ray.origin + (ray.direction * t);
26}
27
28QSSGRenderRay::RayData QSSGRenderRay::createRayData(const QMatrix4x4 &globalTransform,
29 const QSSGRenderRay &ray)
30{
31 using DirectionOp = RayData::DirectionOp;
32 QMatrix4x4 originTransform = globalTransform.inverted();
33 QVector3D transformedOrigin = QSSGUtils::mat44::transform(m: originTransform, v: ray.origin);
34 float *outOriginTransformPtr(originTransform.data());
35 outOriginTransformPtr[12] = outOriginTransformPtr[13] = outOriginTransformPtr[14] = 0.0f;
36 const QVector3D &transformedDirection = QSSGUtils::mat44::rotate(m: originTransform, v: ray.direction).normalized();
37 static auto getInverseAndDirOp = [](const QVector3D &dir, QVector3D &invDir, DirectionOp (&dirOp)[3]) {
38 for (int i = 0; i != 3; ++i) {
39 const float axisDir = dir[i];
40 dirOp[i] = qFuzzyIsNull(f: axisDir) ? DirectionOp::Zero : ((axisDir < -std::numeric_limits<float>::epsilon())
41 ? DirectionOp::Swap
42 : DirectionOp::Normal);
43 invDir[i] = qFuzzyIsNull(f: axisDir) ? 0.0f : (1.0f / axisDir);
44 }
45 };
46 DirectionOp dirOp[3];
47 QVector3D transformedDirectionInvers;
48 getInverseAndDirOp(transformedDirection, transformedDirectionInvers, dirOp);
49 return RayData{ .globalTransform: globalTransform, .ray: ray, .origin: transformedOrigin, .directionInvers: transformedDirectionInvers,
50 .direction: transformedDirection, .dirOp: { dirOp[0], dirOp[1], dirOp[2] } };
51}
52
53QSSGRenderRay::IntersectionResult QSSGRenderRay::createIntersectionResult(const QSSGRenderRay::RayData &data,
54 const HitResult &hit)
55{
56 Q_ASSERT(hit.intersects());
57 Q_ASSERT(hit.bounds != nullptr);
58 const QSSGBounds3 &bounds = *hit.bounds;
59 // Local postion
60 const QVector3D &scaledDir = data.direction * hit.min;
61 const QVector3D &localPosition = scaledDir + data.origin;
62 // ray length squared
63 const QVector3D &globalPosition = QSSGUtils::mat44::transform(m: data.globalTransform, v: localPosition);
64 const QVector3D &cameraToLocal = data.ray.origin - globalPosition;
65 const float rayLenSquared = QSSGUtils::vec3::magnitudeSquared(v: cameraToLocal);
66 // UV coordinates
67 const auto &boundsMin = bounds.minimum;
68 const auto &boundsMax = bounds.maximum;
69 const float xRange = boundsMax.x() - boundsMin.x();
70 const float yRange = boundsMax.y() - boundsMin.y();
71 const QVector2D uvCoords{((localPosition[0] - boundsMin.x()) / xRange), ((localPosition[1] - boundsMin.y()) / yRange)};
72
73 // Since we just intersected with a bounding box, there is no face normal
74 return IntersectionResult(rayLenSquared, uvCoords, globalPosition, localPosition, QVector3D());
75}
76
77QSSGRenderRay::HitResult QSSGRenderRay::intersectWithAABBv2(const QSSGRenderRay::RayData &data,
78 const QSSGBounds3 &bounds)
79{
80 // Intersect the origin with the AABB described by bounds.
81
82 // Scan each axis separately. This code basically finds the distance
83 // from the origin to the near and far bbox planes for a given
84 // axis. It then divides this distance by the direction for that axis to
85 // get a range of t [near,far] that the ray intersects assuming the ray is
86 // described via origin + t*(direction). Running through all three axis means
87 // that you need to min/max those ranges together to find a global min/max
88 // that the pick could possibly be in.
89 float tmax = std::numeric_limits<float>::max();
90 float tmin = std::numeric_limits<float>::min();
91 float origin;
92 const QVector3D *const barray[] { &bounds.minimum, &bounds.maximum };
93
94 for (int axis = 0; axis != 3; ++axis) {
95 origin = data.origin[axis];
96 const bool zeroDir = (data.dirOp[axis] == RayData::DirectionOp::Zero);
97 if (zeroDir && (origin < bounds.minimum[axis] || origin > bounds.maximum[axis])) {
98 // Pickray is roughly parallel to the plane of the slab
99 // so, if the origin is not in the range, we have no intersection
100 return { .min: -1.0f, .max: -1.0f, .bounds: nullptr };
101 }
102 if (!zeroDir) {
103 // Shrink the intersections to find the closest hit
104 tmax = std::min(a: ((*barray[1-quint8(data.dirOp[axis])])[axis] - origin) * data.directionInvers[axis], b: tmax);
105 tmin = std::max(a: ((*barray[quint8(data.dirOp[axis])])[axis] - origin) * data.directionInvers[axis], b: tmin);
106 }
107 }
108
109 return { .min: tmin, .max: tmax, .bounds: &bounds };
110}
111
112// Möller-Trumbore ray-triangle intersection
113// https://www.graphics.cornell.edu/pubs/1997/MT97.pdf
114// https://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/raytri/
115bool QSSGRenderRay::triangleIntersect(const QSSGRenderRay &ray,
116 const QVector3D &v0,
117 const QVector3D &v1,
118 const QVector3D &v2,
119 float &u,
120 float &v,
121 QVector3D &normal)
122{
123 const float epsilon = std::numeric_limits<float>::epsilon();
124
125 // Compute the Triangle's Edges
126 const QVector3D edge1 = v1 - v0;
127 const QVector3D edge2 = v2 - v0;
128
129 // Compute the vector P as the cross product of the ray direction and edge2
130 const QVector3D P = QVector3D::crossProduct(v1: ray.direction, v2: edge2);
131
132 // Compute the determinant
133 const float determinant = QVector3D::dotProduct(v1: edge1, v2: P);
134
135 QVector3D Q;
136
137 // If determinant is near zero, the ray lies in the plane of the triangle
138 if (determinant > epsilon) {
139 // Compute the vector T from the ray origin to the first vertex of the triangle
140 const QVector3D T = ray.origin - v0;
141
142 // Calculate coordinate u and test bounds
143 u = QVector3D::dotProduct(v1: T, v2: P);
144 if (u < 0.0f || u > determinant)
145 return false;
146
147 // Compute the vector Q as the cross product of vector T and edge1
148 Q = QVector3D::crossProduct(v1: T, v2: edge1);
149
150 // Calculate coordinate v and test bounds
151 v = QVector3D::dotProduct(v1: ray.direction, v2: Q);
152 if (v < 0.0f || ((u + v) > determinant))
153 return false;
154 } /*else if (determinant < -epsilon) { // This would be if we cared about backfaces
155 // Compute the vector T from the ray origin to the first vertex of the triangle
156 const QVector3D T = ray.origin - v0;
157
158 // Calculate coordinate u and test bounds
159 u = QVector3D::dotProduct(T, P);
160 if (u > 0.0f || u < determinant)
161 return false;
162
163 // Compute the vector Q as the cross product of vector T and edge1
164 Q = QVector3D::crossProduct(T, edge1);
165
166 // Calculate coordinate v and test bounds
167 v = QVector3D::dotProduct(ray.direction, Q);
168 if (v > 0.0f || ((u + v) < determinant))
169 return false;
170 } */else {
171 // Ray is parallel to the plane of the triangle
172 return false;
173 }
174
175 const float invDeterminant = 1.0f / determinant;
176
177 // Calculate the value of t, the parameter of the intersection point along the ray
178 const float t = QVector3D::dotProduct(v1: edge2, v2: Q) * invDeterminant;
179
180 if (t > epsilon) {
181 normal = QVector3D::crossProduct(v1: edge1, v2: edge2).normalized();
182 u *= invDeterminant;
183 v *= invDeterminant;
184 return true;
185 }
186
187 return false;
188}
189
190
191void QSSGRenderRay::intersectWithBVH(const RayData &data,
192 const QSSGMeshBVHNode *bvh,
193 const QSSGRenderMesh *mesh,
194 QVector<IntersectionResult> &intersections,
195 int depth)
196{
197 if (!bvh || !mesh || !mesh->bvh)
198 return;
199
200 // If this is a leaf node, process it's triangles
201 if (bvh->count != 0) {
202 // If there is an intersection on a leaf node, then test against geometry
203 auto results = intersectWithBVHTriangles(data, bvhTriangles: mesh->bvh->triangles(), triangleOffset: bvh->offset, triangleCount: bvh->count);
204 if (!results.isEmpty())
205 intersections.append(l: results);
206 return;
207 }
208
209 auto hit = QSSGRenderRay::intersectWithAABBv2(data, bounds: bvh->left->boundingData);
210 if (hit.intersects())
211 intersectWithBVH(data, bvh: static_cast<const QSSGMeshBVHNode *>(bvh->left), mesh, intersections, depth: depth + 1);
212
213 hit = QSSGRenderRay::intersectWithAABBv2(data, bounds: bvh->right->boundingData);
214 if (hit.intersects())
215 intersectWithBVH(data, bvh: static_cast<const QSSGMeshBVHNode *>(bvh->right), mesh, intersections, depth: depth + 1);
216}
217
218
219
220QVector<QSSGRenderRay::IntersectionResult> QSSGRenderRay::intersectWithBVHTriangles(const RayData &data,
221 const QSSGMeshBVHTriangles &bvhTriangles,
222 int triangleOffset,
223 int triangleCount)
224{
225 Q_ASSERT(bvhTriangles.size() >= size_t(triangleOffset + triangleCount));
226
227 QVector<QSSGRenderRay::IntersectionResult> results;
228
229 for (int i = triangleOffset; i < triangleCount + triangleOffset; ++i) {
230 const auto &triangle = bvhTriangles[i];
231
232 QSSGRenderRay relativeRay(data.origin, data.direction);
233
234 // Use Barycentric Coordinates to get the intersection values
235 float u = 0.f;
236 float v = 0.f;
237 QVector3D normal;
238 const bool intersects = triangleIntersect(ray: relativeRay,
239 v0: triangle.vertex1,
240 v1: triangle.vertex2,
241 v2: triangle.vertex3,
242 u,
243 v,
244 normal);
245 if (intersects) {
246 const float w = 1.0f - u - v;
247 const QVector3D localIntersectionPoint = w * triangle.vertex1 +
248 u * triangle.vertex2 +
249 v * triangle.vertex3;
250
251 const QVector2D uvCoordinate = w * triangle.uvCoord1 +
252 u * triangle.uvCoord2 +
253 v * triangle.uvCoord3;
254 // Get the intersection point in scene coordinates
255 const QVector3D sceneIntersectionPos = QSSGUtils::mat44::transform(m: data.globalTransform,
256 v: localIntersectionPoint);
257 const QVector3D hitVector = data.ray.origin - sceneIntersectionPos;
258 // Get the magnitude of the hit vector
259 const float rayLengthSquared = QSSGUtils::vec3::magnitudeSquared(v: hitVector);
260 results.append(t: IntersectionResult(rayLengthSquared,
261 uvCoordinate,
262 sceneIntersectionPos,
263 localIntersectionPoint,
264 normal));
265 }
266 }
267
268 // Does not intersect with any of the triangles
269 return results;
270}
271
272std::optional<QVector2D> QSSGRenderRay::relative(const QMatrix4x4 &inGlobalTransform,
273 const QSSGBounds3 &inBounds,
274 QSSGRenderBasisPlanes inPlane) const
275{
276 QMatrix4x4 theOriginTransform = inGlobalTransform.inverted();
277
278 QVector3D theTransformedOrigin = QSSGUtils::mat44::transform(m: theOriginTransform, v: origin);
279 float *outOriginTransformPtr(theOriginTransform.data());
280 outOriginTransformPtr[12] = outOriginTransformPtr[13] = outOriginTransformPtr[14] = 0.0f;
281 QVector3D theTransformedDirection = QSSGUtils::mat44::rotate(m: theOriginTransform, v: direction);
282
283 // The XY plane is going to be a plane with either positive or negative Z direction that runs
284 // through
285 QVector3D theDirection(0, 0, 1);
286 QVector3D theRight(1, 0, 0);
287 QVector3D theUp(0, 1, 0);
288 switch (inPlane) {
289 case QSSGRenderBasisPlanes::XY:
290 break;
291 case QSSGRenderBasisPlanes::XZ:
292 theDirection = QVector3D(0, 1, 0);
293 theUp = QVector3D(0, 0, 1);
294 break;
295 case QSSGRenderBasisPlanes::YZ:
296 theDirection = QVector3D(1, 0, 0);
297 theRight = QVector3D(0, 0, 1);
298 break;
299 }
300 QSSGPlane thePlane(theDirection,
301 QVector3D::dotProduct(v1: theDirection, v2: theTransformedDirection) > 0.0f
302 ? QVector3D::dotProduct(v1: theDirection, v2: inBounds.maximum)
303 : QVector3D::dotProduct(v1: theDirection, v2: inBounds.minimum));
304
305 const QSSGRenderRay relativeRay(theTransformedOrigin, theTransformedDirection);
306 std::optional<QVector3D> localIsect = QSSGRenderRay::intersect(inPlane: thePlane, ray: relativeRay);
307 if (localIsect.has_value()) {
308 float xRange = QVector3D::dotProduct(v1: theRight, v2: inBounds.maximum) - QVector3D::dotProduct(v1: theRight, v2: inBounds.minimum);
309 float yRange = QVector3D::dotProduct(v1: theUp, v2: inBounds.maximum) - QVector3D::dotProduct(v1: theUp, v2: inBounds.minimum);
310 float xOrigin = xRange / 2.0f + QVector3D::dotProduct(v1: theRight, v2: inBounds.minimum);
311 float yOrigin = yRange / 2.0f + QVector3D::dotProduct(v1: theUp, v2: inBounds.minimum);
312 return QVector2D((QVector3D::dotProduct(v1: theRight, v2: *localIsect) - xOrigin) / xRange,
313 (QVector3D::dotProduct(v1: theUp, v2: *localIsect) - yOrigin) / yRange);
314 }
315 return std::nullopt;
316}
317
318QT_END_NAMESPACE
319

source code of qtquick3d/src/runtimerender/qssgrenderray.cpp