1/****************************************************************************
2**
3** Copyright (C) 2014 Klaralvdalens Datakonsult AB (KDAB).
4** Copyright (C) 2016 The Qt Company Ltd and/or its subsidiary(-ies).
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the Qt3D module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#include "calcboundingvolumejob_p.h"
42
43#include <Qt3DRender/private/nodemanagers_p.h>
44#include <Qt3DRender/private/entity_p.h>
45#include <Qt3DRender/private/renderlogging_p.h>
46#include <Qt3DRender/private/managers_p.h>
47#include <Qt3DRender/private/geometryrenderer_p.h>
48#include <Qt3DRender/private/geometry_p.h>
49#include <Qt3DRender/private/buffermanager_p.h>
50#include <Qt3DRender/private/attribute_p.h>
51#include <Qt3DRender/private/buffer_p.h>
52#include <Qt3DRender/private/sphere_p.h>
53#include <Qt3DRender/private/buffervisitor_p.h>
54#include <Qt3DRender/private/entityvisitor_p.h>
55#include <Qt3DCore/private/qaspectmanager_p.h>
56
57#include <QtCore/qmath.h>
58#if QT_CONFIG(concurrent)
59#include <QtConcurrent/QtConcurrent>
60#endif
61#include <Qt3DRender/private/job_common_p.h>
62
63QT_BEGIN_NAMESPACE
64
65namespace Qt3DRender {
66namespace Render {
67
68namespace {
69
70class BoundingVolumeCalculator
71{
72public:
73 BoundingVolumeCalculator(NodeManagers *manager) : m_manager(manager) { }
74
75 const Sphere& result() { return m_volume; }
76 const QVector3D min() const { return m_min; }
77 const QVector3D max() const { return m_max; }
78
79 bool apply(Qt3DRender::Render::Attribute *positionAttribute,
80 Qt3DRender::Render::Attribute *indexAttribute,
81 int drawVertexCount,
82 bool primitiveRestartEnabled,
83 int primitiveRestartIndex)
84 {
85 FindExtremePoints findExtremePoints(m_manager);
86 if (!findExtremePoints.apply(attribute: positionAttribute, indexAttribute, drawVertexCount,
87 primitiveRestartEnabled, primitiveRestartIndex))
88 return false;
89
90 m_min = QVector3D(findExtremePoints.xMin, findExtremePoints.yMin, findExtremePoints.zMin);
91 m_max = QVector3D(findExtremePoints.xMax, findExtremePoints.yMax, findExtremePoints.zMax);
92
93 FindMaxDistantPoint maxDistantPointY(m_manager);
94 maxDistantPointY.setReferencePoint = true;
95 if (!maxDistantPointY.apply(attribute: positionAttribute, indexAttribute, drawVertexCount,
96 primitiveRestartEnabled, primitiveRestartIndex))
97 return false;
98 if (maxDistantPointY.hasNoPoints)
99 return false;
100
101 //const Vector3D x = maxDistantPointY.referencePt;
102 const Vector3D y = maxDistantPointY.maxDistPt;
103
104 FindMaxDistantPoint maxDistantPointZ(m_manager);
105 maxDistantPointZ.setReferencePoint = false;
106 maxDistantPointZ.referencePt = y;
107 if (!maxDistantPointZ.apply(attribute: positionAttribute, indexAttribute, drawVertexCount,
108 primitiveRestartEnabled, primitiveRestartIndex)) {
109 return false;
110 }
111 const Vector3D z = maxDistantPointZ.maxDistPt;
112
113 const Vector3D center = (y + z) * 0.5f;
114
115 FindMaxDistantPoint maxDistantPointCenter(m_manager);
116 maxDistantPointCenter.setReferencePoint = false;
117 maxDistantPointCenter.referencePt = center;
118 if (!maxDistantPointCenter.apply(attribute: positionAttribute, indexAttribute, drawVertexCount,
119 primitiveRestartEnabled, primitiveRestartIndex)) {
120 return false;
121 }
122
123 const float radius = (center - maxDistantPointCenter.maxDistPt).length();
124
125 m_volume = Qt3DRender::Render::Sphere(center, radius);
126
127 if (m_volume.isNull())
128 return false;
129
130 return true;
131 }
132
133private:
134 Sphere m_volume;
135 NodeManagers *m_manager;
136 QVector3D m_min;
137 QVector3D m_max;
138
139 class FindExtremePoints : public Buffer3fVisitor
140 {
141 public:
142 FindExtremePoints(NodeManagers *manager)
143 : Buffer3fVisitor(manager)
144 , xMin(0.0f), xMax(0.0f), yMin(0.0f), yMax(0.0f), zMin(0.0f), zMax(0.0f)
145 { }
146
147 float xMin, xMax, yMin, yMax, zMin, zMax;
148 Vector3D xMinPt, xMaxPt, yMinPt, yMaxPt, zMinPt, zMaxPt;
149
150 void visit(uint ndx, float x, float y, float z) override
151 {
152 if (ndx) {
153 if (x < xMin) {
154 xMin = x;
155 xMinPt = Vector3D(x, y, z);
156 }
157 if (x > xMax) {
158 xMax = x;
159 xMaxPt = Vector3D(x, y, z);
160 }
161 if (y < yMin) {
162 yMin = y;
163 yMinPt = Vector3D(x, y, z);
164 }
165 if (y > yMax) {
166 yMax = y;
167 yMaxPt = Vector3D(x, y, z);
168 }
169 if (z < zMin) {
170 zMin = z;
171 zMinPt = Vector3D(x, y, z);
172 }
173 if (z > zMax) {
174 zMax = z;
175 zMaxPt = Vector3D(x, y, z);
176 }
177 } else {
178 xMin = xMax = x;
179 yMin = yMax = y;
180 zMin = zMax = z;
181 xMinPt = xMaxPt = yMinPt = yMaxPt = zMinPt = zMaxPt = Vector3D(x, y, z);
182 }
183 }
184 };
185
186 class FindMaxDistantPoint : public Buffer3fVisitor
187 {
188 public:
189 FindMaxDistantPoint(NodeManagers *manager)
190 : Buffer3fVisitor(manager)
191 { }
192
193 float maxLengthSquared = 0.0f;
194 Vector3D maxDistPt;
195 Vector3D referencePt;
196 bool setReferencePoint = false;
197 bool hasNoPoints = true;
198
199 void visit(uint ndx, float x, float y, float z) override
200 {
201 Q_UNUSED(ndx);
202 const Vector3D p = Vector3D(x, y, z);
203
204 if (hasNoPoints && setReferencePoint) {
205 maxLengthSquared = 0.0f;
206 referencePt = p;
207 }
208 const float lengthSquared = (p - referencePt).lengthSquared();
209 if ( lengthSquared >= maxLengthSquared ) {
210 maxDistPt = p;
211 maxLengthSquared = lengthSquared;
212 }
213 hasNoPoints = false;
214 }
215 };
216};
217
218struct BoundingVolumeComputeData {
219 Entity *entity = nullptr;
220 Geometry *geometry = nullptr;
221 Attribute *positionAttribute = nullptr;
222 Attribute *indexAttribute = nullptr;
223 bool primitiveRestartEnabled = false;
224 int primitiveRestartIndex = -1;
225 int vertexCount = 0;
226
227 bool valid() const { return entity != nullptr; }
228};
229
230BoundingVolumeComputeData findBoundingVolumeComputeData(NodeManagers *manager, Entity *node)
231{
232 GeometryRenderer *gRenderer = node->renderComponent<GeometryRenderer>();
233 GeometryManager *geometryManager = manager->geometryManager();
234 if (!gRenderer || gRenderer->primitiveType() == QGeometryRenderer::Patches)
235 return {};
236
237 Geometry *geom = geometryManager->lookupResource(id: gRenderer->geometryId());
238 if (!geom)
239 return {};
240
241 int drawVertexCount = gRenderer->vertexCount(); // may be 0, gets changed below if so
242
243 Qt3DRender::Render::Attribute *positionAttribute = manager->lookupResource<Attribute, AttributeManager>(id: geom->boundingPositionAttribute());
244 bool hasBoundingVolumePositionAttribute = positionAttribute != nullptr;
245
246 // Use the default position attribute if attribute is null
247 if (!hasBoundingVolumePositionAttribute) {
248 const auto attrIds = geom->attributes();
249 for (const Qt3DCore::QNodeId &attrId : attrIds) {
250 positionAttribute = manager->lookupResource<Attribute, AttributeManager>(id: attrId);
251 if (positionAttribute &&
252 positionAttribute->name() == QAttribute::defaultPositionAttributeName())
253 break;
254 }
255 }
256
257 if (!positionAttribute
258 || positionAttribute->attributeType() != QAttribute::VertexAttribute
259 || positionAttribute->vertexBaseType() != QAttribute::Float
260 || positionAttribute->vertexSize() < 3) {
261 qWarning(msg: "findBoundingVolumeComputeData: Position attribute not suited for bounding volume computation");
262 return {};
263 }
264
265 Buffer *buf = manager->lookupResource<Buffer, BufferManager>(id: positionAttribute->bufferId());
266 // No point in continuing if the positionAttribute doesn't have a suitable buffer
267 if (!buf) {
268 qWarning(msg: "findBoundingVolumeComputeData: Position attribute not referencing a valid buffer");
269 return {};
270 }
271
272 // Check if there is an index attribute.
273 Qt3DRender::Render::Attribute *indexAttribute = nullptr;
274 Buffer *indexBuf = nullptr;
275
276 if (!hasBoundingVolumePositionAttribute) {
277 const QVector<Qt3DCore::QNodeId> attributes = geom->attributes();
278
279 for (Qt3DCore::QNodeId attrNodeId : attributes) {
280 Qt3DRender::Render::Attribute *attr = manager->lookupResource<Attribute, AttributeManager>(id: attrNodeId);
281 if (attr && attr->attributeType() == QAttribute::IndexAttribute) {
282 indexBuf = manager->lookupResource<Buffer, BufferManager>(id: attr->bufferId());
283 if (indexBuf) {
284 indexAttribute = attr;
285
286 if (!drawVertexCount)
287 drawVertexCount = indexAttribute->count();
288
289 const QAttribute::VertexBaseType validIndexTypes[] = {
290 QAttribute::UnsignedShort,
291 QAttribute::UnsignedInt,
292 QAttribute::UnsignedByte
293 };
294
295 if (std::find(first: std::begin(arr: validIndexTypes),
296 last: std::end(arr: validIndexTypes),
297 val: indexAttribute->vertexBaseType()) == std::end(arr: validIndexTypes)) {
298 qWarning() << "findBoundingVolumeComputeData: Unsupported index attribute type" << indexAttribute->name() << indexAttribute->vertexBaseType();
299 return {};
300 }
301
302 break;
303 }
304 }
305 }
306 }
307
308 if (hasBoundingVolumePositionAttribute || (!indexAttribute && !drawVertexCount))
309 drawVertexCount = positionAttribute->count();
310
311 // Buf will be set to not dirty once it's loaded
312 // in a job executed after this one
313 // We need to recompute the bounding volume
314 // If anything in the GeometryRenderer has changed
315 if (buf->isDirty()
316 || node->isBoundingVolumeDirty()
317 || positionAttribute->isDirty()
318 || geom->isDirty()
319 || gRenderer->isDirty()
320 || (indexAttribute && indexAttribute->isDirty())
321 || (indexBuf && indexBuf->isDirty())) {
322 BoundingVolumeComputeData res;
323 res.entity = node;
324 res.geometry = geom;
325 res.positionAttribute = positionAttribute;
326 res.indexAttribute = indexAttribute;
327 res.primitiveRestartEnabled = gRenderer->primitiveRestartEnabled();
328 res.primitiveRestartIndex = gRenderer->restartIndexValue();
329 res.vertexCount = drawVertexCount;
330 return res;
331 }
332
333 return {};
334}
335
336QVector<Geometry *> calculateLocalBoundingVolume(NodeManagers *manager, const BoundingVolumeComputeData &data)
337{
338 // The Bounding volume will only be computed if the position Buffer
339 // isDirty
340
341 QVector<Geometry *> updatedGeometries;
342
343 BoundingVolumeCalculator reader(manager);
344 if (reader.apply(positionAttribute: data.positionAttribute, indexAttribute: data.indexAttribute, drawVertexCount: data.vertexCount,
345 primitiveRestartEnabled: data.primitiveRestartEnabled, primitiveRestartIndex: data.primitiveRestartIndex)) {
346 data.entity->localBoundingVolume()->setCenter(reader.result().center());
347 data.entity->localBoundingVolume()->setRadius(reader.result().radius());
348 data.entity->unsetBoundingVolumeDirty();
349
350 // Record min/max vertex in Geometry
351 data.geometry->updateExtent(min: reader.min(), max: reader.max());
352 // Mark geometry as requiring a call to update its frontend
353 updatedGeometries.push_back(t: data.geometry);
354 }
355
356 return updatedGeometries;
357}
358
359struct UpdateBoundFunctor
360{
361 NodeManagers *manager;
362
363 // This define is required to work with QtConcurrent
364 typedef QVector<Geometry *> result_type;
365 QVector<Geometry *> operator ()(const BoundingVolumeComputeData &data)
366 {
367 return calculateLocalBoundingVolume(manager, data);
368 }
369};
370
371struct ReduceUpdateBoundFunctor
372{
373 void operator ()(QVector<Geometry *> &result, const QVector<Geometry *> &values)
374 {
375 result += values;
376 }
377};
378
379class DirtyEntityAccumulator : public EntityVisitor
380{
381public:
382 DirtyEntityAccumulator(NodeManagers *manager)
383 : EntityVisitor(manager)
384 {
385 }
386
387 EntityVisitor::Operation visit(Entity *entity) override
388 {
389 if (!entity->isTreeEnabled())
390 return Prune;
391 auto data = findBoundingVolumeComputeData(manager: m_manager, node: entity);
392 if (data.valid())
393 m_entities.push_back(x: data);
394 return Continue;
395 }
396
397 std::vector<BoundingVolumeComputeData> m_entities;
398};
399
400} // anonymous
401
402CalculateBoundingVolumeJob::CalculateBoundingVolumeJob()
403 : m_manager(nullptr)
404 , m_node(nullptr)
405{
406 SET_JOB_RUN_STAT_TYPE(this, JobTypes::CalcBoundingVolume, 0)
407}
408
409void CalculateBoundingVolumeJob::run()
410{
411 DirtyEntityAccumulator accumulator(m_manager);
412 accumulator.apply(root: m_node);
413
414 std::vector<BoundingVolumeComputeData> entities = std::move(accumulator.m_entities);
415
416 QVector<Geometry *> updatedGeometries;
417 updatedGeometries.reserve(asize: entities.size());
418
419#if QT_CONFIG(concurrent)
420 if (entities.size() > 1) {
421 UpdateBoundFunctor functor;
422 functor.manager = m_manager;
423 ReduceUpdateBoundFunctor reduceFunctor;
424 updatedGeometries += QtConcurrent::blockingMappedReduced<decltype(updatedGeometries)>(sequence: entities, map: functor, reduce: reduceFunctor);
425 } else
426#endif
427 {
428 for (const auto &data: entities)
429 updatedGeometries += calculateLocalBoundingVolume(manager: m_manager, data);
430 }
431
432 // Send extent updates to frontend
433 for (Geometry *geometry : updatedGeometries)
434 geometry->notifyExtentChanged();
435}
436
437void CalculateBoundingVolumeJob::setRoot(Entity *node)
438{
439 m_node = node;
440}
441
442void CalculateBoundingVolumeJob::setManagers(NodeManagers *manager)
443{
444 m_manager = manager;
445}
446
447} // namespace Render
448} // namespace Qt3DRender
449
450QT_END_NAMESPACE
451
452

source code of qt3d/src/render/jobs/calcboundingvolumejob.cpp