qssgmeshbvhbuilder.cpp

++ // Copyright (C) 2020 The Qt Company Ltd.

++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only

++ // Qt-Security score:significant reason:default

++

++

++ #include "qssgmeshbvhbuilder_p.h"

++ #include <QtQuick3DUtils/private/qssgassert_p.h>

++

++ QT_BEGIN_NAMESPACE

++

++ static constexpr quint32 QSSG_MAX_TREE_DEPTH = 40;

++ static constexpr quint32 QSSG_MAX_LEAF_TRIANGLES = 10;

++

++ QSSGMeshBVHBuilder::QSSGMeshBVHBuilder(const QSSGMesh::Mesh &mesh)

++     : m_mesh(mesh)

++ {

++     const QSSGMesh::Mesh::VertexBuffer vb = mesh.vertexBuffer();

++     const QSSGMesh::Mesh::IndexBuffer ib = mesh.indexBuffer();

++     m_vertexBufferData = vb.data;

++     m_indexBufferData = ib.data;

++     m_indexBufferComponentType = QSSGRenderComponentType(ib.componentType);

++     if (m_indexBufferComponentType == QSSGRenderComponentType::Int16)

++         m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt16;

++     else if (m_indexBufferComponentType == QSSGRenderComponentType::Int32)

++         m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt32;

++

++     // Get VertexBuffer Information

++     // When using the texture coordinates, UV0 has priority but if the mesh has

++     // UV1 without UV0, UV1 will be used instead of UV0.

++     for (quint32 entryIdx = 0, entryEnd = vb.entries.size(); entryIdx < entryEnd; ++entryIdx) {

++         QSSGRenderVertexBufferEntry entry = vb.entries[entryIdx].toRenderVertexBufferEntry();

++         if (!strcmp(entry.m_name, QSSGMesh::MeshInternal::getPositionAttrName())) {

++             m_hasPositionData = true;

++             m_vertexPosOffset = entry.m_firstItemOffset;

++         } else if (!strcmp(entry.m_name, QSSGMesh::MeshInternal::getUV0AttrName())) {

++             m_hasUVData = true;

++             m_vertexUVOffset = entry.m_firstItemOffset;

++         } else if (!m_hasUVData && !strcmp(entry.m_name, QSSGMesh::MeshInternal::getUV1AttrName())) {

++             m_hasUVData = true;

++             m_vertexUVOffset = entry.m_firstItemOffset;

++         }

++     }

++     m_vertexStride = vb.stride;

++ }

++

++ QSSGMeshBVHBuilder::QSSGMeshBVHBuilder(const QByteArray &vertexBuffer,

++                                        int stride,

++                                        int posOffset,

++                                        bool hasUV,

++                                        int uvOffset,

++                                        bool hasIndexBuffer,

++                                        const QByteArray &indexBuffer,

++                                        QSSGRenderComponentType indexBufferType)

++ {

++     m_vertexBufferData = vertexBuffer;

++     m_vertexStride = stride;

++     m_hasPositionData = true;

++     m_vertexPosOffset = posOffset;

++     m_hasUVData = hasUV;

++     m_vertexUVOffset = uvOffset;

++     m_hasIndexBuffer = hasIndexBuffer;

++     m_indexBufferData = indexBuffer;

++     m_indexBufferComponentType = indexBufferType;

++     if (m_indexBufferComponentType == QSSGRenderComponentType::Int16)

++         m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt16;

++     else if (m_indexBufferComponentType == QSSGRenderComponentType::Int32)

++         m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInt32;

++ }

++

++ std::unique_ptr<QSSGMeshBVH> QSSGMeshBVHBuilder::buildTree()

++ {

++     // This only works with triangles

++     if (m_mesh.isValid() && m_mesh.drawMode() != QSSGMesh::Mesh::DrawMode::Triangles)

++         return nullptr;

++

++     auto meshBvh = std::make_unique<QSSGMeshBVH>();

++     auto &roots = meshBvh->m_roots;

++     auto &triangleBounds = meshBvh->m_triangles;

++

++     // Calculate the bounds for each triangle in whole mesh once

++     quint32 indexCount = 0;

++     if (m_hasIndexBuffer)

++         indexCount = quint32(m_indexBufferData.size() / QSSGBaseTypeHelpers::getSizeOfType(m_indexBufferComponentType));

++     else

++         indexCount = m_vertexBufferData.size() / m_vertexStride;

++     triangleBounds = calculateTriangleBounds(0, indexCount);

++

++     // For each submesh, generate a root bvh node

++     if (m_mesh.isValid()) {

++         const QVector<QSSGMesh::Mesh::Subset> subsets = m_mesh.subsets();

++         roots.reserve(subsets.size());

++         for (quint32 subsetIdx = 0, subsetEnd = subsets.size(); subsetIdx < subsetEnd; ++subsetIdx) {

++             const QSSGMesh::Mesh::Subset &source(subsets[subsetIdx]);

++             QSSGMeshBVHNode::Handle root = meshBvh->newHandle();

++             // Offsets provided by subset are for the index buffer

++             // Convert them to work with the triangle bounds list

++             const quint32 triangleOffset = source.offset / 3;

++             const quint32 triangleCount = source.count / 3;

++             root->boundingData = getBounds(*meshBvh, triangleOffset, triangleCount);

++             // Recursively split the mesh into a tree of smaller bounding volumns

++             root = splitNode(*meshBvh, root, triangleOffset, triangleCount);

++             roots.push_back(root);

++         }

++     } else {

++         // Custom Geometry only has one subset

++         QSSGMeshBVHNode::Handle root = meshBvh->newHandle();

++         root->boundingData = getBounds(*meshBvh, 0, quint32(triangleBounds.size()));

++         root = splitNode(*meshBvh, root, 0, quint32(triangleBounds.size()));

++         roots.push_back(root);

++     }

++

++     return meshBvh;

++ }

++

++

++ template <QSSGRenderComponentType ComponentType>

++ static inline quint32 getIndexBufferValue(quint32 index, const quint32 indexCount, const QByteArray &indexBufferData)

++ {

++     Q_ASSERT(index < indexCount);

++     Q_STATIC_ASSERT(ComponentType == QSSGRenderComponentType::UnsignedInt16 || ComponentType == QSSGRenderComponentType::UnsignedInt32);

++

++     quint32 result = 0;

++     if constexpr (ComponentType == QSSGRenderComponentType::UnsignedInt16) {

++         QSSGDataView<quint16> shortIndex(reinterpret_cast<const quint16 *>(indexBufferData.begin()), indexCount);

++         result = shortIndex[index];

++     } else if (ComponentType == QSSGRenderComponentType::UnsignedInt32) {

++         QSSGDataView<quint32> longIndex(reinterpret_cast<const quint32 *>(indexBufferData.begin()), indexCount);

++         result = longIndex[index];

++     }

++

++     return result;

++ }

++

++ static inline QVector3D getVertexBufferValuePosition(quint32 index, const quint32 vertexStride, const quint32 vertexPosOffset, const QByteArray &vertexBufferData)

++ {

++     const quint32 offset = index * vertexStride + vertexPosOffset;

++     Q_ASSERT(qsizetype(offset) < vertexBufferData.size());

++     const QVector3D *position = reinterpret_cast<const QVector3D *>(vertexBufferData.begin() + offset);

++

++     return *position;

++ }

++

++ static inline QVector2D getVertexBufferValueUV(quint32 index, const quint32 vertexStride, const quint32 vertexUVOffset, const QByteArray &vertexBufferData)

++ {

++     const quint32 offset = index * vertexStride + vertexUVOffset;

++     Q_ASSERT(qsizetype(offset) < vertexBufferData.size());

++     const QVector2D *uv = reinterpret_cast<const QVector2D *>(vertexBufferData.begin() + offset);

++

++     return *uv;

++ }

++

++ template <QSSGRenderComponentType ComponentType, bool hasIndexBuffer, bool hasPositionData, bool hasUVData>

++ static void calculateTriangleBoundsImpl(quint32 indexOffset,

++                                         quint32 indexCount,

++                                         const QByteArray &indexBufferData,

++                                         const QByteArray &vertexBufferData,

++                                         [[maybe_unused]] const quint32 vertexStride,

++                                         [[maybe_unused]] const quint32 vertexUVOffset,

++                                         [[maybe_unused]] const quint32 vertexPosOffset,

++                                         QSSGMeshBVHTriangles &triangleBounds)

++ {

++     const quint32 triangleCount = indexCount / 3;

++     triangleBounds.reserve(triangleCount);

++

++     for (quint32 i = 0; i < triangleCount; ++i) {

++         QSSGMeshBVHTriangle triangle{};

++         if constexpr (hasIndexBuffer || hasPositionData || hasUVData) {

++             // Get the indices for the triangle

++             const quint32 triangleIndex = i * 3 + indexOffset;

++

++             quint32 index1 = triangleIndex + 0;

++             quint32 index2 = triangleIndex + 1;

++             quint32 index3 = triangleIndex + 2;

++

++             if constexpr (hasIndexBuffer) {

++                 index1 = getIndexBufferValue<ComponentType>(index1, indexCount, indexBufferData);

++                 index2 = getIndexBufferValue<ComponentType>(index2, indexCount, indexBufferData);

++                 index3 = getIndexBufferValue<ComponentType>(index3, indexCount, indexBufferData);

++             }

++

++             if constexpr (hasPositionData) {

++                 triangle.vertex1 = getVertexBufferValuePosition(index1, vertexStride, vertexPosOffset, vertexBufferData);

++                 triangle.vertex2 = getVertexBufferValuePosition(index2, vertexStride, vertexPosOffset, vertexBufferData);

++                 triangle.vertex3 = getVertexBufferValuePosition(index3, vertexStride, vertexPosOffset, vertexBufferData);

++             }

++

++             if constexpr (hasUVData) {

++                 triangle.uvCoord1 = getVertexBufferValueUV(index1, vertexStride, vertexUVOffset, vertexBufferData);

++                 triangle.uvCoord2 = getVertexBufferValueUV(index2, vertexStride, vertexUVOffset, vertexBufferData);

++                 triangle.uvCoord3 = getVertexBufferValueUV(index3, vertexStride, vertexUVOffset, vertexBufferData);

++             }

++         }

++

++         triangle.bounds.include(triangle.vertex1);

++         triangle.bounds.include(triangle.vertex2);

++         triangle.bounds.include(triangle.vertex3);

++         triangleBounds.push_back(triangle);

++     }

++ }

++

++ QSSGMeshBVHTriangles QSSGMeshBVHBuilder::calculateTriangleBounds(quint32 indexOffset, quint32 indexCount) const

++ {

++     QSSGMeshBVHTriangles data;

++

++     using CalcTriangleBoundsFn = void (*)(quint32, quint32, const QByteArray &, const QByteArray &, const quint32, const quint32, const quint32, QSSGMeshBVHTriangles &);

++     static const CalcTriangleBoundsFn calcTriangleBounds16Fns[] { &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, false, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, false, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, true, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, false, true, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, false, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, false, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, true, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt16, true, true, true> };

++

++     static const CalcTriangleBoundsFn calcTriangleBounds32Fns[] { &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, false, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, false, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, true, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, false, true, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, false, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, false, true>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, true, false>,

++                                                                   &calculateTriangleBoundsImpl<QSSGRenderComponentType::UnsignedInt32, true, true, true> };

++

++

++     const size_t idx = (size_t(m_hasIndexBuffer) << 2u) | (size_t(m_hasPositionData) << 1u) | (size_t(m_hasUVData));

++

++     if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInt16)

++         calcTriangleBounds16Fns[idx](indexOffset, indexCount, m_indexBufferData, m_vertexBufferData, m_vertexStride, m_vertexUVOffset, m_vertexPosOffset, data);

++     else if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInt32)

++         calcTriangleBounds32Fns[idx](indexOffset, indexCount, m_indexBufferData, m_vertexBufferData, m_vertexStride, m_vertexUVOffset, m_vertexPosOffset, data);

++     return data;

++ }

++

++ QSSGMeshBVHNode::Handle QSSGMeshBVHBuilder::splitNode(QSSGMeshBVH &bvh, QSSGMeshBVHNode::Handle node, quint32 offset, quint32 count, quint32 depth)

++ {

++     // NOTE: The node handle argument is intentionally copied! We can risk the storage reallocating!

++     // Besides, it's a trivial type.

++

++     // Force a leaf node if the there are too few triangles or the tree depth

++     // has exceeded the maximum depth

++     if (count < QSSG_MAX_LEAF_TRIANGLES || depth >= QSSG_MAX_TREE_DEPTH) {

++         node->offset = offset;

++         node->count = count;

++         return node;

++     }

++

++     // Determine where to split the current bounds

++     const QSSGMeshBVHBuilder::Split split = getOptimalSplit(bvh, node->boundingData, offset, count);

++     // Really this shouldn't happen unless there is invalid bounding data, but if that

++     // that does happen make this a leaf node.

++     if (split.axis == QSSGMeshBVHBuilder::Axis::None) {

++         node->offset = offset;

++         node->count = count;

++         return node;

++     }

++

++     // Create the split by sorting the values in m_triangleBounds between

++     // offset - count based on the split axis and position. The returned offset

++     // will determine which values go into the left and right nodes.

++     const quint32 splitOffset = partition(bvh, offset, count, split);

++

++     // Create the leaf nodes

++     if (splitOffset == offset || splitOffset == (offset + count)) {

++         // If the split is at the start or end, this is a leaf node now

++         // because there is no further branches necessary.

++         node->offset = offset;

++         node->count = count;

++     } else {

++         // Create the Left Node

++         node->left = bvh.newHandle();

++         const quint32 leftOffset = offset;

++         const quint32 leftCount = splitOffset - offset;

++         node->left->boundingData = getBounds(bvh, leftOffset, leftCount);

++         node->left = splitNode(bvh, node->left, leftOffset, leftCount, depth + 1);

++

++         // Create the Right Node

++         node->right = bvh.newHandle();

++         const quint32 rightOffset = splitOffset;

++         const quint32 rightCount = count - leftCount;

++         node->right->boundingData = getBounds(bvh, rightOffset, rightCount);

++         node->right = splitNode(bvh, node->right, rightOffset, rightCount, depth + 1);

++     }

++

++     return node;

++ }

++

++ QSSGBounds3 QSSGMeshBVHBuilder::getBounds(const QSSGMeshBVH &bvh, quint32 offset, quint32 count)

++ {

++     QSSGBounds3 totalBounds;

++     const auto &triangleBounds = bvh.triangles();

++

++     for (quint32 i = 0; i < count; ++i) {

++         const QSSGBounds3 &bounds = triangleBounds[i + offset].bounds;

++         totalBounds.include(bounds);

++     }

++     return totalBounds;

++ }

++

++ QSSGMeshBVHBuilder::Split QSSGMeshBVHBuilder::getOptimalSplit(const QSSGMeshBVH &bvh, const QSSGBounds3 &nodeBounds, quint32 offset, quint32 count)

++ {

++     QSSGMeshBVHBuilder::Split split;

++     split.axis = getLongestDimension(nodeBounds);

++     split.pos = 0.f;

++

++     if (split.axis != Axis::None)

++         split.pos = getAverageValue(bvh, offset, count, split.axis);

++

++     return split;

++ }

++

++ QSSGMeshBVHBuilder::Axis QSSGMeshBVHBuilder::getLongestDimension(const QSSGBounds3 &nodeBounds)

++ {

++     QSSGMeshBVHBuilder::Axis axis = Axis::None;

++     float largestDistance = std::numeric_limits<float>::min();

++

++     if (!nodeBounds.isFinite() || nodeBounds.isEmpty())

++         return axis;

++

++     const QVector3D delta = nodeBounds.maximum - nodeBounds.minimum;

++

++     if (delta.x() > largestDistance) {

++         axis = Axis::X;

++         largestDistance = delta.x();

++     }

++     if (delta.y() > largestDistance) {

++         axis = Axis::Y;

++         largestDistance = delta.y();

++     }

++     if (delta.z() > largestDistance)

++         axis = Axis::Z;

++

++     return axis;

++ }

++

++ // Get the average values of triangles for a given axis

++ float QSSGMeshBVHBuilder::getAverageValue(const QSSGMeshBVH &bvh, quint32 offset, quint32 count, QSSGMeshBVHBuilder::Axis axis)

++ {

++     float average = 0;

++

++     Q_ASSERT(axis != Axis::None);

++     Q_ASSERT(count != 0);

++

++     const auto &triangleBounds = bvh.triangles();

++     for (quint32 i = 0; i < count; ++i)

++         average += triangleBounds[i + offset].bounds.center(int(axis));

++

++     return average / count;

++ }

++

++ quint32 QSSGMeshBVHBuilder::partition(QSSGMeshBVH &bvh, quint32 offset, quint32 count, const QSSGMeshBVHBuilder::Split &split)

++ {

++     int left = offset;

++     int right = offset + count - 1;

++     const float pos = split.pos;

++     const int axis = int(split.axis);

++

++     auto &triangleBounds = bvh.m_triangles;

++     while (true) {

++         while (left <= right && triangleBounds[left].bounds.center(axis) < pos)

++             left++;

++

++         while (left <= right && triangleBounds[right].bounds.center(axis) >= pos)

++             right--;

++

++         if (left < right) {

++             // Swap triangleBounds at left and right

++             std::swap(triangleBounds[left], triangleBounds[right]);

++             left++;

++             right--;

++         } else {

++             return left;

++         }

++     }

++     Q_UNREACHABLE();

++ }

++

++ QT_END_NAMESPACE

Revision control