1// Copyright (C) 2020 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only
3
4#include "qssgmeshbvhbuilder_p.h"
5#include <QtQuick3DUtils/private/qssgassert_p.h>
6
7QT_BEGIN_NAMESPACE
8
9static constexpr quint32 QSSG_MAX_TREE_DEPTH = 40;
10static constexpr quint32 QSSG_MAX_LEAF_TRIANGLES = 10;
11
12QSSGMeshBVHBuilder::QSSGMeshBVHBuilder(const QSSGMesh::Mesh &mesh)
13 : m_mesh(mesh)
14{
15 const QSSGMesh::Mesh::VertexBuffer vb = mesh.vertexBuffer();
16 const QSSGMesh::Mesh::IndexBuffer ib = mesh.indexBuffer();
17 m_vertexBufferData = vb.data;
18 m_indexBufferData = ib.data;
19 m_indexBufferComponentType = QSSGRenderComponentType(ib.componentType);
20 if (m_indexBufferComponentType == QSSGRenderComponentType::Int16)
21 m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt16;
22 else if (m_indexBufferComponentType == QSSGRenderComponentType::Int32)
23 m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt32;
24
25 // Get VertexBuffer Information
26 // When using the texture coordinates, UV0 has priority but if the mesh has
27 // UV1 without UV0, UV1 will be used instead of UV0.
28 for (quint32 entryIdx = 0, entryEnd = vb.entries.size(); entryIdx < entryEnd; ++entryIdx) {
29 QSSGRenderVertexBufferEntry entry = vb.entries[entryIdx].toRenderVertexBufferEntry();
30 if (!strcmp(s1: entry.m_name, s2: QSSGMesh::MeshInternal::getPositionAttrName())) {
31 m_hasPositionData = true;
32 m_vertexPosOffset = entry.m_firstItemOffset;
33 } else if (!strcmp(s1: entry.m_name, s2: QSSGMesh::MeshInternal::getUV0AttrName())) {
34 m_hasUVData = true;
35 m_vertexUVOffset = entry.m_firstItemOffset;
36 } else if (!m_hasUVData && !strcmp(s1: entry.m_name, s2: QSSGMesh::MeshInternal::getUV1AttrName())) {
37 m_hasUVData = true;
38 m_vertexUVOffset = entry.m_firstItemOffset;
39 }
40 }
41 m_vertexStride = vb.stride;
42}
43
44QSSGMeshBVHBuilder::QSSGMeshBVHBuilder(const QByteArray &vertexBuffer,
45 int stride,
46 int posOffset,
47 bool hasUV,
48 int uvOffset,
49 bool hasIndexBuffer,
50 const QByteArray &indexBuffer,
51 QSSGRenderComponentType indexBufferType)
52{
53 m_vertexBufferData = vertexBuffer;
54 m_vertexStride = stride;
55 m_hasPositionData = true;
56 m_vertexPosOffset = posOffset;
57 m_hasUVData = hasUV;
58 m_vertexUVOffset = uvOffset;
59 m_hasIndexBuffer = hasIndexBuffer;
60 m_indexBufferData = indexBuffer;
61 m_indexBufferComponentType = indexBufferType;
62 if (m_indexBufferComponentType == QSSGRenderComponentType::Int16)
63 m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt16;
64 else if (m_indexBufferComponentType == QSSGRenderComponentType::Int32)
65 m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt32;
66}
67
68std::unique_ptr<QSSGMeshBVH> QSSGMeshBVHBuilder::buildTree()
69{
70 // This only works with triangles
71 if (m_mesh.isValid() && m_mesh.drawMode() != QSSGMesh::Mesh::DrawMode::Triangles)
72 return nullptr;
73
74 auto meshBvh = std::make_unique<QSSGMeshBVH>();
75 auto &roots = meshBvh->m_roots;
76 auto &triangleBounds = meshBvh->m_triangles;
77
78 // Calculate the bounds for each triangle in whole mesh once
79 quint32 indexCount = 0;
80 if (m_hasIndexBuffer)
81 indexCount = quint32(m_indexBufferData.size() / QSSGBaseTypeHelpers::getSizeOfType(type: m_indexBufferComponentType));
82 else
83 indexCount = m_vertexBufferData.size() / m_vertexStride;
84 triangleBounds = calculateTriangleBounds(indexOffset: 0, indexCount);
85
86 // For each submesh, generate a root bvh node
87 if (m_mesh.isValid()) {
88 const QVector<QSSGMesh::Mesh::Subset> subsets = m_mesh.subsets();
89 roots.reserve(n: subsets.size());
90 for (quint32 subsetIdx = 0, subsetEnd = subsets.size(); subsetIdx < subsetEnd; ++subsetIdx) {
91 const QSSGMesh::Mesh::Subset &source(subsets[subsetIdx]);
92 QSSGMeshBVHNode::Handle root = meshBvh->newHandle();
93 // Offsets provided by subset are for the index buffer
94 // Convert them to work with the triangle bounds list
95 const quint32 triangleOffset = source.offset / 3;
96 const quint32 triangleCount = source.count / 3;
97 root->boundingData = getBounds(bvh: *meshBvh, offset: triangleOffset, count: triangleCount);
98 // Recursively split the mesh into a tree of smaller bounding volumns
99 root = splitNode(bvh&: *meshBvh, node: root, offset: triangleOffset, count: triangleCount);
100 roots.push_back(x: root);
101 }
102 } else {
103 // Custom Geometry only has one subset
104 QSSGMeshBVHNode::Handle root = meshBvh->newHandle();
105 root->boundingData = getBounds(bvh: *meshBvh, offset: 0, count: quint32(triangleBounds.size()));
106 root = splitNode(bvh&: *meshBvh, node: root, offset: 0, count: quint32(triangleBounds.size()));
107 roots.push_back(x: root);
108 }
109
110 return meshBvh;
111}
112
113
114template <QSSGRenderComponentType ComponentType>
115static inline quint32 getIndexBufferValue(quint32 index, const quint32 indexCount, const QByteArray &indexBufferData)
116{
117 Q_ASSERT(index < indexCount);
118 Q_STATIC_ASSERT(ComponentType == QSSGRenderComponentType::UnsignedInt16 || ComponentType == QSSGRenderComponentType::UnsignedInt32);
119
120 quint32 result = 0;
121 if constexpr (ComponentType == QSSGRenderComponentType::UnsignedInt16) {
122 QSSGDataView<quint16> shortIndex(reinterpret_cast<const quint16 *>(indexBufferData.begin()), indexCount);
123 result = shortIndex[index];
124 } else if (ComponentType == QSSGRenderComponentType::UnsignedInt32) {
125 QSSGDataView<quint32> longIndex(reinterpret_cast<const quint32 *>(indexBufferData.begin()), indexCount);
126 result = longIndex[index];
127 }
128
129 return result;
130}
131
132static inline QVector3D getVertexBufferValuePosition(quint32 index, const quint32 vertexStride, const quint32 vertexPosOffset, const QByteArray &vertexBufferData)
133{
134 const quint32 offset = index * vertexStride + vertexPosOffset;
135 const QVector3D *position = reinterpret_cast<const QVector3D *>(vertexBufferData.begin() + offset);
136
137 return *position;
138}
139
140static inline QVector2D getVertexBufferValueUV(quint32 index, const quint32 vertexStride, const quint32 vertexUVOffset, const QByteArray &vertexBufferData)
141{
142 const quint32 offset = index * vertexStride + vertexUVOffset;
143 const QVector2D *uv = reinterpret_cast<const QVector2D *>(vertexBufferData.begin() + offset);
144
145 return *uv;
146}
147
148template <QSSGRenderComponentType ComponentType, bool hasIndexBuffer, bool hasPositionData, bool hasUVData>
149static void calculateTriangleBoundsImpl(quint32 indexOffset,
150 quint32 indexCount,
151 const QByteArray &indexBufferData,
152 const QByteArray &vertexBufferData,
153 [[maybe_unused]] const quint32 vertexStride,
154 [[maybe_unused]] const quint32 vertexUVOffset,
155 [[maybe_unused]] const quint32 vertexPosOffset,
156 QSSGMeshBVHTriangles &triangleBounds)
157{
158 const quint32 triangleCount = indexCount / 3;
159 triangleBounds.reserve(n: triangleCount);
160
161 for (quint32 i = 0; i < triangleCount; ++i) {
162 QSSGMeshBVHTriangle triangle{};
163 if constexpr (hasIndexBuffer || hasPositionData || hasUVData) {
164 // Get the indices for the triangle
165 const quint32 triangleIndex = i * 3 + indexOffset;
166
167 quint32 index1 = triangleIndex + 0;
168 quint32 index2 = triangleIndex + 1;
169 quint32 index3 = triangleIndex + 2;
170
171 if constexpr (hasIndexBuffer) {
172 index1 = getIndexBufferValue<ComponentType>(index1, indexCount, indexBufferData);
173 index2 = getIndexBufferValue<ComponentType>(index2, indexCount, indexBufferData);
174 index3 = getIndexBufferValue<ComponentType>(index3, indexCount, indexBufferData);
175 }
176
177 if constexpr (hasPositionData) {
178 triangle.vertex1 = getVertexBufferValuePosition(index: index1, vertexStride, vertexPosOffset, vertexBufferData);
179 triangle.vertex2 = getVertexBufferValuePosition(index: index2, vertexStride, vertexPosOffset, vertexBufferData);
180 triangle.vertex3 = getVertexBufferValuePosition(index: index3, vertexStride, vertexPosOffset, vertexBufferData);
181 }
182
183 if constexpr (hasUVData) {
184 triangle.uvCoord1 = getVertexBufferValueUV(index: index1, vertexStride, vertexUVOffset, vertexBufferData);
185 triangle.uvCoord2 = getVertexBufferValueUV(index: index2, vertexStride, vertexUVOffset, vertexBufferData);
186 triangle.uvCoord3 = getVertexBufferValueUV(index: index3, vertexStride, vertexUVOffset, vertexBufferData);
187 }
188 }
189
190 triangle.bounds.include(v: triangle.vertex1);
191 triangle.bounds.include(v: triangle.vertex2);
192 triangle.bounds.include(v: triangle.vertex3);
193 triangleBounds.push_back(x: triangle);
194 }
195}
196
197QSSGMeshBVHTriangles QSSGMeshBVHBuilder::calculateTriangleBounds(quint32 indexOffset, quint32 indexCount) const
198{
199 QSSGMeshBVHTriangles data;
200
201 using CalcTriangleBoundsFn = void (*)(quint32, quint32, const QByteArray &, const QByteArray &, const quint32, const quint32, const quint32, QSSGMeshBVHTriangles &);
202 static const CalcTriangleBoundsFn calcTriangleBounds16Fns[] { &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, false, false>,
203 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, false, true>,
204 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, true, false>,
205 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, true, true>,
206 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, false, false>,
207 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, false, true>,
208 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, true, false>,
209 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, true, true> };
210
211 static const CalcTriangleBoundsFn calcTriangleBounds32Fns[] { &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, false, false>,
212 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, false, true>,
213 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, true, false>,
214 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, true, true>,
215 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, false, false>,
216 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, false, true>,
217 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, true, false>,
218 &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, true, true> };
219
220
221 const size_t idx = (size_t(m_hasIndexBuffer) << 2u) | (size_t(m_hasPositionData) << 1u) | (size_t(m_hasUVData));
222
223 if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInt16)
224 calcTriangleBounds16Fns[idx](indexOffset, indexCount, m_indexBufferData, m_vertexBufferData, m_vertexStride, m_vertexUVOffset, m_vertexPosOffset, data);
225 else if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInt32)
226 calcTriangleBounds32Fns[idx](indexOffset, indexCount, m_indexBufferData, m_vertexBufferData, m_vertexStride, m_vertexUVOffset, m_vertexPosOffset, data);
227 return data;
228}
229
230QSSGMeshBVHNode::Handle QSSGMeshBVHBuilder::splitNode(QSSGMeshBVH &bvh, QSSGMeshBVHNode::Handle node, quint32 offset, quint32 count, quint32 depth)
231{
232 // NOTE: The node handle argument is intentionally copied! We can risk the storage reallocating!
233 // Besides, it's a trivial type.
234
235 // Force a leaf node if the there are too few triangles or the tree depth
236 // has exceeded the maximum depth
237 if (count < QSSG_MAX_LEAF_TRIANGLES || depth >= QSSG_MAX_TREE_DEPTH) {
238 node->offset = offset;
239 node->count = count;
240 return node;
241 }
242
243 // Determine where to split the current bounds
244 const QSSGMeshBVHBuilder::Split split = getOptimalSplit(bvh, nodeBounds: node->boundingData, offset, count);
245 // Really this shouldn't happen unless there is invalid bounding data, but if that
246 // that does happen make this a leaf node.
247 if (split.axis == QSSGMeshBVHBuilder::Axis::None) {
248 node->offset = offset;
249 node->count = count;
250 return node;
251 }
252
253 // Create the split by sorting the values in m_triangleBounds between
254 // offset - count based on the split axis and position. The returned offset
255 // will determine which values go into the left and right nodes.
256 const quint32 splitOffset = partition(bvh, offset, count, split);
257
258 // Create the leaf nodes
259 if (splitOffset == offset || splitOffset == (offset + count)) {
260 // If the split is at the start or end, this is a leaf node now
261 // because there is no further branches necessary.
262 node->offset = offset;
263 node->count = count;
264 } else {
265 // Create the Left Node
266 node->left = bvh.newHandle();
267 const quint32 leftOffset = offset;
268 const quint32 leftCount = splitOffset - offset;
269 node->left->boundingData = getBounds(bvh, offset: leftOffset, count: leftCount);
270 node->left = splitNode(bvh, node: node->left, offset: leftOffset, count: leftCount, depth: depth + 1);
271
272 // Create the Right Node
273 node->right = bvh.newHandle();
274 const quint32 rightOffset = splitOffset;
275 const quint32 rightCount = count - leftCount;
276 node->right->boundingData = getBounds(bvh, offset: rightOffset, count: rightCount);
277 node->right = splitNode(bvh, node: node->right, offset: rightOffset, count: rightCount, depth: depth + 1);
278 }
279
280 return node;
281}
282
283QSSGBounds3 QSSGMeshBVHBuilder::getBounds(const QSSGMeshBVH &bvh, quint32 offset, quint32 count)
284{
285 QSSGBounds3 totalBounds;
286 const auto &triangleBounds = bvh.triangles();
287
288 for (quint32 i = 0; i < count; ++i) {
289 const QSSGBounds3 &bounds = triangleBounds[i + offset].bounds;
290 totalBounds.include(b: bounds);
291 }
292 return totalBounds;
293}
294
295QSSGMeshBVHBuilder::Split QSSGMeshBVHBuilder::getOptimalSplit(const QSSGMeshBVH &bvh, const QSSGBounds3 &nodeBounds, quint32 offset, quint32 count)
296{
297 QSSGMeshBVHBuilder::Split split;
298 split.axis = getLongestDimension(nodeBounds);
299 split.pos = 0.f;
300
301 if (split.axis != Axis::None)
302 split.pos = getAverageValue(bvh, offset, count, axis: split.axis);
303
304 return split;
305}
306
307QSSGMeshBVHBuilder::Axis QSSGMeshBVHBuilder::getLongestDimension(const QSSGBounds3 &nodeBounds)
308{
309 QSSGMeshBVHBuilder::Axis axis = Axis::None;
310 float largestDistance = std::numeric_limits<float>::min();
311
312 if (!nodeBounds.isFinite() || nodeBounds.isEmpty())
313 return axis;
314
315 const QVector3D delta = nodeBounds.maximum - nodeBounds.minimum;
316
317 if (delta.x() > largestDistance) {
318 axis = Axis::X;
319 largestDistance = delta.x();
320 }
321 if (delta.y() > largestDistance) {
322 axis = Axis::Y;
323 largestDistance = delta.y();
324 }
325 if (delta.z() > largestDistance)
326 axis = Axis::Z;
327
328 return axis;
329}
330
331// Get the average values of triangles for a given axis
332float QSSGMeshBVHBuilder::getAverageValue(const QSSGMeshBVH &bvh, quint32 offset, quint32 count, QSSGMeshBVHBuilder::Axis axis)
333{
334 float average = 0;
335
336 Q_ASSERT(axis != Axis::None);
337 Q_ASSERT(count != 0);
338
339 const auto &triangleBounds = bvh.triangles();
340 for (quint32 i = 0; i < count; ++i)
341 average += triangleBounds[i + offset].bounds.center(axis: int(axis));
342
343 return average / count;
344}
345
346quint32 QSSGMeshBVHBuilder::partition(QSSGMeshBVH &bvh, quint32 offset, quint32 count, const QSSGMeshBVHBuilder::Split &split)
347{
348 int left = offset;
349 int right = offset + count - 1;
350 const float pos = split.pos;
351 const int axis = int(split.axis);
352
353 auto &triangleBounds = bvh.m_triangles;
354 while (true) {
355 while (left <= right && triangleBounds[left].bounds.center(axis) < pos)
356 left++;
357
358 while (left <= right && triangleBounds[right].bounds.center(axis) >= pos)
359 right--;
360
361 if (left < right) {
362 // Swap triangleBounds at left and right
363 std::swap(a&: triangleBounds[left], b&: triangleBounds[right]);
364 left++;
365 right--;
366 } else {
367 return left;
368 }
369 }
370 Q_UNREACHABLE();
371}
372
373QT_END_NAMESPACE
374

source code of qtquick3d/src/utils/qssgmeshbvhbuilder.cpp