qt-everywhere-src-5.15.1/qtquick3d/src/assetimport/qssgmeshbvhbuilder.cpp - orbit - Git at Google

 /****************************************************************************
 **
 ** 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
	/****************************************************************************
	**
	** 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