QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
qgsorientedbox3d.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsorientedbox3d.cpp
3 --------------------
4 begin : July 2023
5 copyright : (C) 2023 by Nyall Dawson
6 email : nyall dot dawson at gmail dot com
7 ******************************************************************
8 ***************************************************************************/
9
10/***************************************************************************
11 * *
12 * This program is free software; you can redistribute it and/or modify *
13 * it under the terms of the GNU General Public License as published by *
14 * the Free Software Foundation; either version 2 of the License, or *
15 * (at your option) any later version. *
16 * *
17 ***************************************************************************/
18
19#include "qgsorientedbox3d.h"
20#include "qgsbox3d.h"
22#include "qgsmatrix4x4.h"
23#include "qgsvector3d.h"
24
26
27QgsOrientedBox3D::QgsOrientedBox3D( const QList<double> &center, const QList<double> &halfAxes )
28{
29 if ( center.size() == 3 )
30 {
31 mCenter[0] = center.at( 0 );
32 mCenter[1] = center.at( 1 );
33 mCenter[2] = center.at( 2 );
34 }
35 if ( halfAxes.size() == 9 )
36 {
37 for ( int i = 0; i < 9; ++i )
38 {
39 mHalfAxes[i] = halfAxes.at( i );
40 }
41 }
42}
43
44QgsOrientedBox3D::QgsOrientedBox3D( const QgsVector3D &center, const QList<QgsVector3D> &halfAxes )
45{
46 mCenter[0] = center.x();
47 mCenter[1] = center.y();
48 mCenter[2] = center.z();
49 if ( halfAxes.size() == 3 )
50 {
51 for ( int i = 0; i < 3; ++i )
52 {
53 mHalfAxes[static_cast< int >( i * 3 )] = halfAxes.at( i ).x();
54 mHalfAxes[static_cast< int >( i * 3 + 1 )] = halfAxes.at( i ).y();
55 mHalfAxes[static_cast< int >( i * 3 + 2 )] = halfAxes.at( i ).z();
56 }
57 }
58}
59
61{
62 return QgsOrientedBox3D( box.center(), QList< QgsVector3D >
63 {
64 QgsVector3D( box.width() * 0.5, 0, 0 ),
65 QgsVector3D( 0, box.height() * 0.5, 0 ),
66 QgsVector3D( 0, 0, box.depth() * 0.5 )
67 } );
68}
69
71{
72 return std::isnan( mCenter[0] ) || std::isnan( mCenter[1] ) || std::isnan( mCenter[2] );
73}
74
75QList< double > QgsOrientedBox3D::halfAxesList() const
76{
77 QList< double > res;
78 res.reserve( 9 );
79 for ( int i = 0; i < 9; ++i )
80 {
81 res.append( mHalfAxes[i] );
82 }
83 return res;
84}
85
87{
88 const double extent[3]
89 {
90 std::fabs( mHalfAxes[0] ) + std::fabs( mHalfAxes[3] ) + std::fabs( mHalfAxes[6] ),
91 std::fabs( mHalfAxes[1] ) + std::fabs( mHalfAxes[4] ) + std::fabs( mHalfAxes[7] ),
92 std::fabs( mHalfAxes[2] ) + std::fabs( mHalfAxes[5] ) + std::fabs( mHalfAxes[8] ),
93 };
94
95 const double minX = mCenter[0] - extent[0];
96 const double maxX = mCenter[0] + extent[0];
97 const double minY = mCenter[1] - extent[1];
98 const double maxY = mCenter[1] + extent[1];
99 const double minZ = mCenter[2] - extent[2];
100 const double maxZ = mCenter[2] + extent[2];
101
102 return QgsBox3D( minX, minY, minZ, maxX, maxY, maxZ );
103}
104
105QVector<QgsVector3D> QgsOrientedBox3D::corners() const
106{
107 const QgsVector3D center( mCenter[0], mCenter[1], mCenter[2] );
108 const QgsVector3D a1( mHalfAxes[0], mHalfAxes[1], mHalfAxes[2] ), a0( -mHalfAxes[0], -mHalfAxes[1], -mHalfAxes[2] );
109 const QgsVector3D b1( mHalfAxes[3], mHalfAxes[4], mHalfAxes[5] ), b0( -mHalfAxes[3], -mHalfAxes[4], -mHalfAxes[5] );
110 const QgsVector3D c1( mHalfAxes[6], mHalfAxes[7], mHalfAxes[8] ), c0( -mHalfAxes[6], -mHalfAxes[7], -mHalfAxes[8] );
111
112 QVector<QgsVector3D> cor( 8 );
113 QgsVector3D *corData = cor.data();
114 for ( int i = 0; i < 8; ++i, ++corData )
115 {
116 const QgsVector3D aa = ( i % 2 == 0 ? a1 : a0 );
117 const QgsVector3D bb = ( ( i / 2 ) % 2 == 0 ? b1 : b0 );
118 const QgsVector3D cc = ( i / 4 == 0 ? c1 : c0 );
119 const QgsVector3D q = aa + bb + cc;
120 *corData = center + q;
121 }
122 return cor;
123}
124
126{
127 QgsVector3D axis1( mHalfAxes[0], mHalfAxes[1], mHalfAxes[2] );
128 QgsVector3D axis2( mHalfAxes[3], mHalfAxes[4], mHalfAxes[5] );
129 QgsVector3D axis3( mHalfAxes[6], mHalfAxes[7], mHalfAxes[8] );
130 return QgsVector3D( 2 * axis1.length(), 2 * axis2.length(), 2 * axis3.length() );
131}
132
134{
135 // reproject corners to destination CRS
136 QVector<QgsVector3D> c = corners();
137 Q_ASSERT( c.count() == 8 );
138 for ( int i = 0; i < 8; ++i )
139 {
140 c[i] = ct.transform( c[i] );
141 }
142
143 // find AABB for the 8 transformed points
144 QgsVector3D v0 = c[0], v1 = c[0];
145 for ( const QgsVector3D &v : std::as_const( c ) )
146 {
147 if ( v.x() < v0.x() ) v0.setX( v.x() );
148 if ( v.y() < v0.y() ) v0.setY( v.y() );
149 if ( v.z() < v0.z() ) v0.setZ( v.z() );
150 if ( v.x() > v1.x() ) v1.setX( v.x() );
151 if ( v.y() > v1.y() ) v1.setY( v.y() );
152 if ( v.z() > v1.z() ) v1.setZ( v.z() );
153 }
154 return QgsBox3D( v0.x(), v0.y(), v0.z(), v1.x(), v1.y(), v1.z() );
155}
156
158{
159 const double *ptr = transform.constData();
160 const QgsMatrix4x4 mm( ptr[0], ptr[4], ptr[8], 0,
161 ptr[1], ptr[5], ptr[9], 0,
162 ptr[2], ptr[6], ptr[10], 0,
163 0, 0, 0, 1 );
164
165 const QgsVector3D trCenter = transform.map( QgsVector3D( mCenter[0], mCenter[1], mCenter[2] ) );
166
167 const QgsVector3D col1 = mm.map( QgsVector3D( mHalfAxes[0], mHalfAxes[1], mHalfAxes[2] ) );
168 const QgsVector3D col2 = mm.map( QgsVector3D( mHalfAxes[3], mHalfAxes[4], mHalfAxes[5] ) );
169 const QgsVector3D col3 = mm.map( QgsVector3D( mHalfAxes[6], mHalfAxes[7], mHalfAxes[8] ) );
170
171 return QgsOrientedBox3D( QList<double>() << trCenter.x() << trCenter.y() << trCenter.z(),
172 QList<double>() << col1.x() << col1.y() << col1.z()
173 << col2.x() << col2.y() << col2.z()
174 << col3.x() << col3.y() << col3.z() );
175}
176
178{
179 // use the Separating Axis Theorem (SAT) for OBB (Oriented Bounding Box) collision detection.
180 // based off section 5 in OBBTree: A Hierarchical Structure for Rapid Interference Detection (1996)
181
182 const QgsVector3D thisCenter = center();
183 const QgsVector3D thisHalfAxis[3]
184 {
185 { mHalfAxes[0], mHalfAxes[1], mHalfAxes[2] },
186 { mHalfAxes[3], mHalfAxes[4], mHalfAxes[5] },
187 { mHalfAxes[6], mHalfAxes[7], mHalfAxes[8] }
188 };
189 const QgsVector3D otherCenter = other.center();
190 const QgsVector3D otherHalfAxis[3]
191 {
192 { other.mHalfAxes[0], other.mHalfAxes[1], other.mHalfAxes[2] },
193 { other.mHalfAxes[3], other.mHalfAxes[4], other.mHalfAxes[5] },
194 { other.mHalfAxes[6], other.mHalfAxes[7], other.mHalfAxes[8] }
195 };
196
197 for ( int a = 0; a < 3; ++a )
198 {
199 const QgsVector3D *aAxis = thisHalfAxis + a;
200 for ( int b = 0; b < 3; ++b )
201 {
202 const QgsVector3D *bAxis = otherHalfAxis + b;
203 QgsVector3D lAxis = QgsVector3D::crossProduct( *aAxis, *bAxis );
204 if ( lAxis.isNull() )
205 continue;
206
207 lAxis.normalize();
208
209 const double tl = std::abs( QgsVector3D::dotProduct( lAxis, otherCenter ) - QgsVector3D::dotProduct( lAxis, thisCenter ) );
210 const double ra = std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[2] ) );
211 const double rb = std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[2] ) );
212 const double penetration = ( ra + rb ) - tl;
213 if ( penetration <= 0 )
214 return false;
215 }
216 }
217
218 for ( int a = 0; a < 3; ++a )
219 {
220 QgsVector3D lAxis = *( thisHalfAxis + a );
221 lAxis.normalize();
222
223 const double tl = std::abs( QgsVector3D::dotProduct( lAxis, otherCenter ) - QgsVector3D::dotProduct( lAxis, thisCenter ) );
224 const double ra = std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[2] ) );
225 const double rb = std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[2] ) );
226 const double penetration = ( ra + rb ) - tl;
227 if ( penetration <= 0 )
228 return false;
229 }
230
231 for ( int b = 0; b < 3; ++b )
232 {
233 QgsVector3D lAxis = *( otherHalfAxis + b );
234 lAxis.normalize();
235
236 const double tl = std::abs( QgsVector3D::dotProduct( lAxis, otherCenter ) - QgsVector3D::dotProduct( lAxis, thisCenter ) );
237 const double ra = std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, thisHalfAxis[2] ) );
238 const double rb = std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[0] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[1] ) ) + std::abs( QgsVector3D::dotProduct( lAxis, otherHalfAxis[2] ) );
239 const double penetration = ( ra + rb ) - tl;
240 if ( penetration <= 0 )
241 return false;
242 }
243
244 return true;
245}
A 3-dimensional box composed of x, y, z coordinates.
Definition qgsbox3d.h:43
QgsVector3D center() const
Returns the center of the box as a vector.
Definition qgsbox3d.cpp:106
Class for doing transforms between two map coordinate systems.
QgsPointXY transform(const QgsPointXY &point, Qgis::TransformDirection direction=Qgis::TransformDirection::Forward) const
Transform the point from the source CRS to the destination CRS.
A simple 4x4 matrix implementation useful for transformation in 3D space.
QgsVector3D map(const QgsVector3D &vector) const
Matrix-vector multiplication (vector is converted to homogeneous coordinates [X,Y,...
const double * constData() const
Returns pointer to the matrix data (stored in column-major order)
Represents a oriented (rotated) box in 3 dimensions.
const double * halfAxes() const
Returns the half axes matrix;.
QgsBox3D extent() const
Returns the overall bounding box of the object.
bool isNull() const
Returns true if the box is a null box.
QgsOrientedBox3D()
Constructor for a null oriented box.
bool intersects(const QgsOrientedBox3D &other) const
Returns true if the box intersects the other box.
QVector< QgsVector3D > corners() const
Returns an array of all corners as 3D vectors.
static QgsOrientedBox3D fromBox3D(const QgsBox3D &box)
Constructs an oriented box from an axis-aligned bounding box.
QList< double > halfAxesList() const
Returns the half axes matrix;.
QgsBox3D reprojectedExtent(const QgsCoordinateTransform &ct) const
Reprojects corners of this box using the given coordinate transform and returns axis-aligned box cont...
QgsVector3D center() const
Returns the vector to the center of the box.
QgsVector3D size() const
Returns size of sides of the box.
QgsOrientedBox3D transformed(const QgsMatrix4x4 &transform) const
Returns box transformed by a 4x4 matrix.
Class for storage of 3D vectors similar to QVector3D, with the difference that it uses double precisi...
Definition qgsvector3d.h:31
double y() const
Returns Y coordinate.
Definition qgsvector3d.h:50
double z() const
Returns Z coordinate.
Definition qgsvector3d.h:52
void setZ(double z)
Sets Z coordinate.
Definition qgsvector3d.h:70
bool isNull() const
Returns true if all three coordinates are zero.
Definition qgsvector3d.h:45
static double dotProduct(const QgsVector3D &v1, const QgsVector3D &v2)
Returns the dot product of two vectors.
double x() const
Returns X coordinate.
Definition qgsvector3d.h:48
void setX(double x)
Sets X coordinate.
Definition qgsvector3d.h:58
void normalize()
Normalizes the current vector in place.
static QgsVector3D crossProduct(const QgsVector3D &v1, const QgsVector3D &v2)
Returns the cross product of two vectors.
void setY(double y)
Sets Y coordinate.
Definition qgsvector3d.h:64
double length() const
Returns the length of the vector.
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