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

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