| /**************************************************************************** |
| ** |
| ** Copyright (C) 2020 The Qt Company Ltd. |
| ** Contact: https://www.qt.io/licensing/ |
| ** |
| ** This file is part of Qt Quick 3D. |
| ** |
| ** $QT_BEGIN_LICENSE:GPL$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see https://www.qt.io/terms-conditions. For further |
| ** information use the contact form at https://www.qt.io/contact-us. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 3 or (at your option) any later version |
| ** approved by the KDE Free Qt Foundation. The licenses are as published by |
| ** the Free Software Foundation and appearing in the file LICENSE.GPL3 |
| ** included in the packaging of this file. Please review the following |
| ** information to ensure the GNU General Public License requirements will |
| ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #include "qssgmeshbvhbuilder_p.h" |
| |
| QT_BEGIN_NAMESPACE |
| |
| QSSGMeshBVHBuilder::QSSGMeshBVHBuilder(QSSGMeshUtilities::Mesh *mesh) |
| : m_mesh(mesh) |
| { |
| m_baseAddress = reinterpret_cast<quint8 *>(m_mesh); |
| m_vertexBufferData = QSSGByteView(m_mesh->m_vertexBuffer.m_data.begin(m_baseAddress), |
| m_mesh->m_vertexBuffer.m_data.size()); |
| m_indexBufferData = QSSGByteView(m_mesh->m_indexBuffer.m_data.begin(m_baseAddress), |
| m_mesh->m_indexBuffer.m_data.size()); |
| m_indexBufferComponentType = m_mesh->m_indexBuffer.m_componentType; |
| if (m_indexBufferComponentType == QSSGRenderComponentType::Integer16) |
| m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInteger16; |
| else if (m_indexBufferComponentType == QSSGRenderComponentType::Integer32) |
| m_indexBufferComponentType = QSSGRenderComponentType::UnsignedInteger32; |
| |
| // Get VertexBuffer Information |
| const auto &entries = m_mesh->m_vertexBuffer.m_entries; |
| for (quint32 entryIdx = 0, entryEnd = entries.size(); entryIdx < entryEnd; ++entryIdx) { |
| QSSGRenderVertexBufferEntry entry = entries.index(m_baseAddress, entryIdx).toVertexBufferEntry(m_baseAddress); |
| if (!strcmp(entry.m_name, QSSGMeshUtilities::Mesh::getPositionAttrName())) { |
| m_hasPositionData = true; |
| m_vertexPosOffset = entry.m_firstItemOffset; |
| } else if (!strcmp(entry.m_name, QSSGMeshUtilities::Mesh::getUVAttrName())) { |
| m_hasUVData = true; |
| m_vertexUV0Offset = entry.m_firstItemOffset; |
| } |
| } |
| m_vertexStride = m_mesh->m_vertexBuffer.m_stride; |
| |
| } |
| |
| QSSGMeshBVH* QSSGMeshBVHBuilder::buildTree() |
| { |
| m_roots.clear(); |
| |
| // This only works with triangles |
| if (m_mesh->m_drawMode != QSSGRenderDrawMode::Triangles) |
| return nullptr; |
| |
| // Calculate the bounds for each triangle in whole mesh once |
| const quint32 indexCount = m_indexBufferData.size() / getSizeOfType(m_indexBufferComponentType); |
| m_triangleBounds = calculateTriangleBounds(0, indexCount); |
| |
| // For each submesh, generate a root bvh node |
| for (quint32 subsetIdx = 0, subsetEnd = m_mesh->m_subsets.size(); subsetIdx < subsetEnd; ++subsetIdx) { |
| const QSSGMeshUtilities::MeshSubset &source(m_mesh->m_subsets.index(m_baseAddress, subsetIdx)); |
| QSSGMeshBVHNode *root = new QSSGMeshBVHNode(); |
| // Offsets provided by subset are for the index buffer |
| // Convert them to work with the triangle bounds list |
| const quint32 triangleOffset = source.m_offset / 3; |
| const quint32 triangleCount = source.m_count / 3; |
| root->boundingData = getBounds(triangleOffset, triangleCount); |
| // Recursively split the mesh into a tree of smaller bounding volumns |
| root = splitNode(root, triangleOffset, triangleCount); |
| m_roots.append(root); |
| } |
| |
| return new QSSGMeshBVH(m_roots, m_triangleBounds); |
| } |
| |
| QVector<QSSGMeshBVHTriangle *> QSSGMeshBVHBuilder::calculateTriangleBounds(quint32 indexOffset, quint32 indexCount) const |
| { |
| QVector<QSSGMeshBVHTriangle *> triangleBounds; |
| const quint32 triangleCount = indexCount / 3; |
| |
| for (quint32 i = 0; i < triangleCount; ++i) { |
| // Get the indices for the triangle |
| const quint32 triangleIndex = i * 3 + indexOffset; |
| |
| const quint32 index1 = getIndexBufferValue(triangleIndex + 0); |
| const quint32 index2 = getIndexBufferValue(triangleIndex + 1); |
| const quint32 index3 = getIndexBufferValue(triangleIndex + 2); |
| |
| QSSGMeshBVHTriangle *triangle = new QSSGMeshBVHTriangle(); |
| |
| triangle->vertex1 = getVertexBufferValuePosition(index1); |
| triangle->vertex2 = getVertexBufferValuePosition(index2); |
| triangle->vertex3 = getVertexBufferValuePosition(index3); |
| triangle->uvCoord1 = getVertexBufferValueUV0(index1); |
| triangle->uvCoord2 = getVertexBufferValueUV0(index2); |
| triangle->uvCoord3 = getVertexBufferValueUV0(index3); |
| |
| triangle->bounds = QSSGBounds3::empty(); |
| triangle->bounds.include(triangle->vertex1); |
| triangle->bounds.include(triangle->vertex2); |
| triangle->bounds.include(triangle->vertex3); |
| triangleBounds.append(triangle); |
| } |
| return triangleBounds; |
| } |
| |
| quint32 QSSGMeshBVHBuilder::getIndexBufferValue(quint32 index) const |
| { |
| quint32 result = 0; |
| const quint32 indexCount = m_indexBufferData.size() / getSizeOfType(m_indexBufferComponentType); |
| Q_ASSERT(index < indexCount); |
| |
| if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInteger16) { |
| QSSGDataView<quint16> shortIndex(reinterpret_cast<const quint16 *>(m_indexBufferData.begin()), indexCount); |
| result = shortIndex[index]; |
| } else if (m_indexBufferComponentType == QSSGRenderComponentType::UnsignedInteger32) { |
| QSSGDataView<quint32> longIndex(reinterpret_cast<const quint32 *>(m_indexBufferData.begin()), indexCount); |
| result = longIndex[index]; |
| } else { |
| // If you get here something terrible happend |
| Q_ASSERT(false); |
| } |
| return result; |
| } |
| |
| QVector3D QSSGMeshBVHBuilder::getVertexBufferValuePosition(quint32 index) const |
| { |
| if (!m_hasPositionData) |
| return QVector3D(); |
| |
| const quint32 offset = index * m_vertexStride + m_vertexPosOffset; |
| const QVector3D *position = reinterpret_cast<const QVector3D *>(m_vertexBufferData.begin() + offset); |
| |
| return *position; |
| } |
| |
| QVector2D QSSGMeshBVHBuilder::getVertexBufferValueUV0(quint32 index) const |
| { |
| if (!m_hasUVData) |
| return QVector2D(); |
| |
| const quint32 offset = index * m_vertexStride + m_vertexUV0Offset; |
| const QVector2D *uv0 = reinterpret_cast<const QVector2D *>(m_vertexBufferData.begin() + offset); |
| |
| return *uv0; |
| } |
| |
| QSSGMeshBVHNode *QSSGMeshBVHBuilder::splitNode(QSSGMeshBVHNode *node, quint32 offset, quint32 count, quint32 depth) |
| { |
| // Force a leaf node if the there are too few triangles or the tree depth |
| // has exceeded the maximum depth |
| if (count < m_maxLeafTriangles || depth >= m_maxTreeDepth) { |
| node->offset = offset; |
| node->count = count; |
| return node; |
| } |
| |
| // Determine where to split the current bounds |
| const QSSGMeshBVHBuilder::Split split = getOptimalSplit(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(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 = new QSSGMeshBVHNode(); |
| const quint32 leftOffset = offset; |
| const quint32 leftCount = splitOffset - offset; |
| node->left->boundingData = getBounds(leftOffset, leftCount); |
| node->left = splitNode(node->left, leftOffset, leftCount, depth + 1); |
| |
| // Create the Right Node |
| node->right = new QSSGMeshBVHNode(); |
| const quint32 rightOffset = splitOffset; |
| const quint32 rightCount = count - leftCount; |
| node->right->boundingData = getBounds(rightOffset, rightCount); |
| node->right = splitNode(node->right, rightOffset, rightCount, depth + 1); |
| } |
| |
| return node; |
| } |
| |
| QSSGBounds3 QSSGMeshBVHBuilder::getBounds(quint32 offset, quint32 count) const |
| { |
| QSSGBounds3 totalBounds = QSSGBounds3::empty(); |
| |
| for (quint32 i = 0; i < count; ++i) { |
| QSSGBounds3 bounds = m_triangleBounds[i + offset]->bounds; |
| totalBounds.include(bounds); |
| } |
| return totalBounds; |
| } |
| |
| QSSGMeshBVHBuilder::Split QSSGMeshBVHBuilder::getOptimalSplit(const QSSGBounds3 &nodeBounds, quint32 offset, quint32 count) const |
| { |
| QSSGMeshBVHBuilder::Split split; |
| split.axis = getLongestDimension(nodeBounds); |
| split.pos = 0.f; |
| |
| if (split.axis != Axis::None) |
| split.pos = getAverageValue(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; |
| largestDistance = delta.z(); |
| } |
| return axis; |
| } |
| |
| // Get the average values of triangles for a given axis |
| float QSSGMeshBVHBuilder::getAverageValue(quint32 offset, quint32 count, QSSGMeshBVHBuilder::Axis axis) const |
| { |
| float average = 0; |
| |
| Q_ASSERT(axis != Axis::None); |
| Q_ASSERT(count != 0); |
| |
| for (quint32 i = 0; i < count; ++i) |
| average += m_triangleBounds[i + offset]->bounds.center(int(axis)); |
| |
| return average / count; |
| } |
| |
| quint32 QSSGMeshBVHBuilder::partition(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); |
| |
| while (true) { |
| while (left <= right && m_triangleBounds[left]->bounds.center()[axis] < pos) |
| left++; |
| |
| while (left <= right && m_triangleBounds[right]->bounds.center()[axis] >= pos) |
| right--; |
| |
| if (left < right) { |
| // Swap triangleBounds at left and right |
| auto temp = m_triangleBounds[left]; |
| m_triangleBounds[left] = m_triangleBounds[right]; |
| m_triangleBounds[right] = temp; |
| |
| left++; |
| right--; |
| } else { |
| return left; |
| } |
| } |
| Q_UNREACHABLE(); |
| } |
| |
| QT_END_NAMESPACE |