QGIS API Documentation 3.41.0-Master (8825f861dd5)
qgsraycastingutils.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsraycastingutils_h.cpp
3 --------------------------------------
4 Date : June 2018
5 Copyright : (C) 2018 by Martin Dobias
6 Email : wonder dot sk at gmail dot com
7 ***************************************************************************
8 * *
9 * This program is free software; you can redistribute it and/or modify *
10 * it under the terms of the GNU General Public License as published by *
11 * the Free Software Foundation; either version 2 of the License, or *
12 * (at your option) any later version. *
13 * *
14 ***************************************************************************/
15
17
18#include "qgis.h"
19#include "qgsaabb.h"
20#include "qgslogger.h"
21
22#include <Qt3DRender/QCamera>
23#include <Qt3DRender/QGeometryRenderer>
24
25#if QT_VERSION < QT_VERSION_CHECK( 6, 0, 0 )
26#include <Qt3DRender/QAttribute>
27#include <Qt3DRender/QBuffer>
28#include <Qt3DRender/QGeometry>
29typedef Qt3DRender::QAttribute Qt3DQAttribute;
30typedef Qt3DRender::QBuffer Qt3DQBuffer;
31typedef Qt3DRender::QGeometry Qt3DQGeometry;
32#else
33#include <Qt3DCore/QAttribute>
34#include <Qt3DCore/QBuffer>
35#include <Qt3DCore/QGeometry>
36typedef Qt3DCore::QAttribute Qt3DQAttribute;
37typedef Qt3DCore::QBuffer Qt3DQBuffer;
38typedef Qt3DCore::QGeometry Qt3DQGeometry;
39#endif
40
42
43
44namespace QgsRayCastingUtils
45{
46
47 // copied from qt3d/src/render/raycasting/qray3d_p.h + qray3d.cpp
48 // by KDAB, licensed under the terms of LGPL
49
50
51 Ray3D::Ray3D()
52 : m_direction( 0.0f, 0.0f, 1.0f )
53 {
54 }
55
56 Ray3D::Ray3D( QVector3D origin, QVector3D direction, float distance )
57 : m_origin( origin )
58 , m_direction( direction )
59 , m_distance( distance )
60 {}
61
62 QVector3D Ray3D::origin() const
63 {
64 return m_origin;
65 }
66
67 void Ray3D::setOrigin( QVector3D value )
68 {
69 m_origin = value;
70 }
71
72 QVector3D Ray3D::direction() const
73 {
74 return m_direction;
75 }
76
77 void Ray3D::setDirection( QVector3D value )
78 {
79 if ( value.isNull() )
80 return;
81
82 m_direction = value;
83 }
84
85 float Ray3D::distance() const
86 {
87 return m_distance;
88 }
89
90 void Ray3D::setDistance( float distance )
91 {
92 m_distance = distance;
93 }
94
95 QVector3D Ray3D::point( float t ) const
96 {
97 return m_origin + t * m_direction;
98 }
99
100 Ray3D &Ray3D::transform( const QMatrix4x4 &matrix )
101 {
102 m_origin = matrix * m_origin;
103 m_direction = matrix.mapVector( m_direction );
104
105 return *this;
106 }
107
108 Ray3D Ray3D::transformed( const QMatrix4x4 &matrix ) const
109 {
110 return Ray3D( matrix * m_origin, matrix.mapVector( m_direction ) );
111 }
112
113 bool Ray3D::operator==( const Ray3D &other ) const
114 {
115 return m_origin == other.origin() && m_direction == other.direction();
116 }
117
118 bool Ray3D::operator!=( const Ray3D &other ) const
119 {
120 return !( *this == other );
121 }
122
123 bool Ray3D::contains( QVector3D point ) const
124 {
125 const QVector3D ppVec( point - m_origin );
126 if ( ppVec.isNull() ) // point coincides with origin
127 return true;
128 const float dot = QVector3D::dotProduct( ppVec, m_direction );
129 if ( qFuzzyIsNull( dot ) )
130 return false;
131 return qFuzzyCompare( dot * dot, ppVec.lengthSquared() * m_direction.lengthSquared() );
132 }
133
134 bool Ray3D::contains( const Ray3D &ray ) const
135 {
136 const float dot = QVector3D::dotProduct( m_direction, ray.direction() );
137 if ( !qFuzzyCompare( dot * dot, m_direction.lengthSquared() * ray.direction().lengthSquared() ) )
138 return false;
139 return contains( ray.origin() );
140 }
141
142 float Ray3D::projectedDistance( QVector3D point ) const
143 {
144 Q_ASSERT( !m_direction.isNull() );
145
146 return QVector3D::dotProduct( point - m_origin, m_direction ) / m_direction.lengthSquared();
147 }
148
149 QVector3D Ray3D::project( QVector3D vector ) const
150 {
151 const QVector3D norm = m_direction.normalized();
152 return QVector3D::dotProduct( vector, norm ) * norm;
153 }
154
155
156 float Ray3D::distance( QVector3D point ) const
157 {
158 const float t = projectedDistance( point );
159 return ( point - ( m_origin + t * m_direction ) ).length();
160 }
161
162 QDebug operator<<( QDebug dbg, const Ray3D &ray )
163 {
164 const QDebugStateSaver saver( dbg );
165 dbg.nospace() << "QRay3D(origin("
166 << ray.origin().x() << ", " << ray.origin().y() << ", "
167 << ray.origin().z() << ") - direction("
168 << ray.direction().x() << ", " << ray.direction().y() << ", "
169 << ray.direction().z() << "))";
170 return dbg;
171 }
172
173} // namespace QgsRayCastingUtils
174
175
177
178
179struct box
180{
181 box( const QgsAABB &b )
182 {
183 min[0] = b.xMin;
184 min[1] = b.yMin;
185 min[2] = b.zMin;
186 max[0] = b.xMax;
187 max[1] = b.yMax;
188 max[2] = b.zMax;
189 }
190 double min[3];
191 double max[3];
192};
193
194struct ray
195{
196 ray( double xO, double yO, double zO, double xD, double yD, double zD )
197 {
198 origin[0] = xO;
199 origin[1] = yO;
200 origin[2] = zO;
201 dir[0] = xD;
202 dir[1] = yD;
203 dir[2] = zD;
204 dir_inv[0] = 1 / dir[0];
205 dir_inv[1] = 1 / dir[1];
206 dir_inv[2] = 1 / dir[2];
207 }
208 ray( const QgsRayCastingUtils::Ray3D &r )
209 {
210 // ignoring length...
211 origin[0] = r.origin().x();
212 origin[1] = r.origin().y();
213 origin[2] = r.origin().z();
214 dir[0] = r.direction().x();
215 dir[1] = r.direction().y();
216 dir[2] = r.direction().z();
217 dir_inv[0] = 1 / dir[0];
218 dir_inv[1] = 1 / dir[1];
219 dir_inv[2] = 1 / dir[2];
220 }
221 double origin[3];
222 double dir[3];
223 double dir_inv[3];
224};
225
226// https://tavianator.com/fast-branchless-raybounding-box-intersections/
227// https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/
228
229bool intersection( const box &b, const ray &r )
230{
231 double t1 = ( b.min[0] - r.origin[0] ) * r.dir_inv[0];
232 double t2 = ( b.max[0] - r.origin[0] ) * r.dir_inv[0];
233
234 double tmin = std::min( t1, t2 );
235 double tmax = std::max( t1, t2 );
236
237 for ( int i = 1; i < 3; ++i )
238 {
239 t1 = ( b.min[i] - r.origin[i] ) * r.dir_inv[i];
240 t2 = ( b.max[i] - r.origin[i] ) * r.dir_inv[i];
241
242 tmin = std::max( tmin, std::min( std::min( t1, t2 ), tmax ) );
243 tmax = std::min( tmax, std::max( std::max( t1, t2 ), tmin ) );
244 }
245
246 return tmax > std::max( tmin, 0.0 );
247}
248
249
250namespace QgsRayCastingUtils
251{
252
253 bool rayBoxIntersection( const Ray3D &r, const QgsAABB &aabb )
254 {
255 box b( aabb );
256
257 // intersection() does not like yMin==yMax (excludes borders)
258 if ( b.min[0] == b.max[0] )
259 b.max[0] += 0.1;
260 if ( b.min[1] == b.max[1] )
261 b.max[1] += 0.1;
262 if ( b.min[2] == b.max[2] )
263 b.max[2] += 0.1;
264
265 return intersection( b, ray( r ) );
266 }
267
268 // copied from intersectsSegmentTriangle() from qt3d/src/render/backend/triangleboundingvolume.cpp
269 // by KDAB, licensed under the terms of LGPL
270 bool rayTriangleIntersection( const Ray3D &ray, QVector3D a, QVector3D b, QVector3D c, QVector3D &uvw, float &t )
271 {
272 // Note: a, b, c in clockwise order
273 // RealTime Collision Detection page 192
274
275 const QVector3D ab = b - a;
276 const QVector3D ac = c - a;
277 const QVector3D qp = ( ray.origin() - ray.point( ray.distance() ) );
278
279 const QVector3D n = QVector3D::crossProduct( ab, ac );
280 const float d = QVector3D::dotProduct( qp, n );
281
282 if ( d <= 0.0f || std::isnan( d ) )
283 return false;
284
285 const QVector3D ap = ray.origin() - a;
286 t = QVector3D::dotProduct( ap, n );
287
288 if ( t < 0.0f || t > d )
289 return false;
290
291 const QVector3D e = QVector3D::crossProduct( qp, ap );
292 uvw.setY( QVector3D::dotProduct( ac, e ) );
293
294 if ( uvw.y() < 0.0f || uvw.y() > d )
295 return false;
296
297 uvw.setZ( -QVector3D::dotProduct( ab, e ) );
298
299 if ( uvw.z() < 0.0f || uvw.y() + uvw.z() > d )
300 return false;
301
302 const float ood = 1.0f / d;
303 t *= ood;
304 uvw.setY( uvw.y() * ood );
305 uvw.setZ( uvw.z() * ood );
306 uvw.setX( 1.0f - uvw.y() - uvw.z() );
307
308 return true;
309 }
310
311 bool rayMeshIntersection( Qt3DRender::QGeometryRenderer *geometryRenderer, const QgsRayCastingUtils::Ray3D &r, const QMatrix4x4 &worldTransform, QVector3D &intPt, int &triangleIndex )
312 {
313 if ( geometryRenderer->primitiveType() != Qt3DRender::QGeometryRenderer::Triangles )
314 {
315 QgsDebugError( QString( "Unsupported primitive type for intersection: " ).arg( geometryRenderer->primitiveType() ) );
316 return false;
317 }
318 if ( geometryRenderer->instanceCount() != 1 || geometryRenderer->indexOffset() != 0 || geometryRenderer->indexBufferByteOffset() != 0 || geometryRenderer->firstVertex() != 0 || geometryRenderer->firstInstance() != 0 )
319 {
320 QgsDebugError( QString( "Unsupported geometry renderer for intersection." ) );
321 return false;
322 }
323
324 Qt3DQGeometry *geometry = geometryRenderer->geometry();
325
326 Qt3DQAttribute *positionAttr = nullptr;
327 Qt3DQAttribute *indexAttr = nullptr;
328 for ( Qt3DQAttribute *attr : geometry->attributes() )
329 {
330 if ( attr->name() == Qt3DQAttribute::defaultPositionAttributeName() )
331 {
332 positionAttr = attr;
333 }
334 else if ( attr->attributeType() == Qt3DQAttribute::IndexAttribute )
335 {
336 indexAttr = attr;
337 }
338 }
339
340 if ( !positionAttr )
341 {
342 QgsDebugError( "Could not find position attribute!" );
343 return false;
344 }
345
346 if ( positionAttr->vertexBaseType() != Qt3DQAttribute::Float || positionAttr->vertexSize() != 3 )
347 {
348 QgsDebugError( QString( "Unsupported position attribute: base type %1, vertex size %2" ).arg( positionAttr->vertexBaseType() ).arg( positionAttr->vertexSize() ) );
349 return false;
350 }
351
352 const QByteArray vertexBuf = positionAttr->buffer()->data();
353 const char *vertexPtr = vertexBuf.constData();
354 vertexPtr += positionAttr->byteOffset();
355 int vertexByteStride = positionAttr->byteStride() == 0 ? 3 * sizeof( float ) : positionAttr->byteStride();
356
357 const uchar *indexPtrUChar = nullptr;
358 const ushort *indexPtrUShort = nullptr;
359 const uint *indexPtrUInt = nullptr;
360 if ( indexAttr )
361 {
362 if ( indexAttr->byteStride() != 0 || indexAttr->vertexSize() != 1 )
363 {
364 QgsDebugError( QString( "Unsupported index attribute: stride %1, vertex size %2" ).arg( indexAttr->byteStride() ).arg( indexAttr->vertexSize() ) );
365 return false;
366 }
367
368 const QByteArray indexBuf = indexAttr->buffer()->data();
369 if ( indexAttr->vertexBaseType() == Qt3DQAttribute::UnsignedByte )
370 {
371 indexPtrUChar = reinterpret_cast<const uchar *>( indexBuf.constData() + indexAttr->byteOffset() );
372 }
373 else if ( indexAttr->vertexBaseType() == Qt3DQAttribute::UnsignedShort )
374 {
375 indexPtrUShort = reinterpret_cast<const ushort *>( indexBuf.constData() + indexAttr->byteOffset() );
376 }
377 else if ( indexAttr->vertexBaseType() == Qt3DQAttribute::UnsignedInt )
378 {
379 indexPtrUInt = reinterpret_cast<const uint *>( indexBuf.constData() + indexAttr->byteOffset() );
380 }
381 else
382 {
383 QgsDebugError( QString( "Unsupported index attribute: base type %1" ).arg( indexAttr->vertexBaseType() ) );
384 return false;
385 }
386 }
387
388 int vertexCount = geometryRenderer->vertexCount();
389 if ( vertexCount == 0 && indexAttr )
390 {
391 vertexCount = indexAttr->count();
392 }
393 if ( vertexCount == 0 )
394 {
395 vertexCount = positionAttr->count();
396 }
397
398 QVector3D intersectionPt, minIntersectionPt;
399 float minDistance = -1;
400
401 for ( int i = 0; i < vertexCount; i += 3 )
402 {
403 int v0index = 0, v1index = 0, v2index = 0;
404 if ( !indexAttr )
405 {
406 v0index = i;
407 v1index = i + 1;
408 v2index = i + 2;
409 }
410 else if ( indexPtrUShort )
411 {
412 v0index = indexPtrUShort[i];
413 v1index = indexPtrUShort[i + 1];
414 v2index = indexPtrUShort[i + 2];
415 }
416 else if ( indexPtrUChar )
417 {
418 v0index = indexPtrUChar[i];
419 v1index = indexPtrUChar[i + 1];
420 v2index = indexPtrUChar[i + 2];
421 }
422 else if ( indexPtrUInt )
423 {
424 v0index = indexPtrUInt[i];
425 v1index = indexPtrUInt[i + 1];
426 v2index = indexPtrUInt[i + 2];
427 }
428 else
429 Q_ASSERT( false );
430
431 const float *v0ptr = reinterpret_cast<const float *>( vertexPtr + v0index * vertexByteStride );
432 const float *v1ptr = reinterpret_cast<const float *>( vertexPtr + v1index * vertexByteStride );
433 const float *v2ptr = reinterpret_cast<const float *>( vertexPtr + v2index * vertexByteStride );
434
435 const QVector3D a( v0ptr[0], v0ptr[1], v0ptr[2] );
436 const QVector3D b( v1ptr[0], v1ptr[1], v1ptr[2] );
437 const QVector3D c( v2ptr[0], v2ptr[1], v2ptr[2] );
438
439 // Currently the worldTransform only has vertical offset, so this could be optimized by applying the transform
440 // to the ray and the resulting intersecting point instead of all triangles
441 // Need to check for potential performance gains.
442 const QVector3D tA = worldTransform * a;
443 const QVector3D tB = worldTransform * b;
444 const QVector3D tC = worldTransform * c;
445
446 QVector3D uvw;
447 float t = 0;
448
449 // We're testing both triangle orientations here and ignoring the culling mode.
450 // We should probably respect the culling mode used for the entity and perform a
451 // single test using the properly oriented triangle.
452 if ( QgsRayCastingUtils::rayTriangleIntersection( r, tA, tB, tC, uvw, t ) || QgsRayCastingUtils::rayTriangleIntersection( r, tA, tC, tB, uvw, t ) )
453 {
454 intersectionPt = r.point( t * r.distance() );
455 const float distance = r.projectedDistance( intersectionPt );
456
457 // we only want the first intersection of the ray with the mesh (closest to the ray origin)
458 if ( minDistance == -1 || distance < minDistance )
459 {
460 triangleIndex = static_cast<int>( i / 3 );
461 minDistance = distance;
462 minIntersectionPt = intersectionPt;
463 }
464 }
465 }
466
467 if ( minDistance != -1 )
468 {
469 intPt = minIntersectionPt;
470 return true;
471 }
472 else
473 return false;
474 }
475} // namespace QgsRayCastingUtils
476
477
float yMax
Definition qgsaabb.h:90
float xMax
Definition qgsaabb.h:89
float xMin
Definition qgsaabb.h:86
float zMax
Definition qgsaabb.h:91
float yMin
Definition qgsaabb.h:87
float zMin
Definition qgsaabb.h:88
As part of the API refactoring and improvements which landed in the Processing API was substantially reworked from the x version This was done in order to allow much of the underlying Processing framework to be ported into c
Qt3DCore::QAttribute Qt3DQAttribute
Qt3DCore::QGeometry Qt3DQGeometry
QDataStream & operator<<(QDataStream &out, const QgsFeature &feature)
Writes the feature to stream out. QGIS version compatibility is not guaranteed.
#define QgsDebugError(str)
Definition qgslogger.h:38
Qt3DCore::QAttribute Qt3DQAttribute
Qt3DCore::QBuffer Qt3DQBuffer
Qt3DCore::QGeometry Qt3DQGeometry