Perform picking with a Bounding Volume Hierarchy

Change-Id: I49c6b6b91c527784763b5337c77dc9fc8382d9a7
Reviewed-by: Christian Strømme <[email protected]>

11 files changed, 753 insertions, 9 deletions

diff --git a/src/assetimport/assetimport.pro b/src/assetimport/assetimport.pro
index 0e2c16ea..5f15c6b2 100644
--- a/src/assetimport/assetimport.pro
+++ b/src/assetimport/assetimport.pro
@@ -6,9 +6,12 @@ MODULE_PLUGIN_TYPES = assetimporters
 QT += core-private gui qml quick3drender-private quick3dutils-private
 
 SOURCES = \
+    qssgmeshbvhbuilder.cpp \
     qssgmeshutilities.cpp
 
 HEADERS = \
+    qssgmeshbvhbuilder_p.h \
+    qtquick3dassetimportglobal_p.h \
     qssgmeshutilities_p.h
 
 !integrity:!android|android_app:!wasm:!cross_compile {
@@ -18,12 +21,11 @@ SOURCES += \
     qssgqmlutilities.cpp
 
 HEADERS += \
-    qtquick3dassetimportglobal_p.h \
     qssgqmlutilities_p.h \
     qssgassetimporter_p.h \
     qssgassetimporterfactory_p.h \
     qssgassetimporterplugin_p.h \
-    qssgassetimportmanager_p.h \
+    qssgassetimportmanager_p.h
 }
 
 DEFINES += QT_BUILD_QUICK3DASSETIMPORT_LIB
diff --git a/src/assetimport/qssgmeshbvhbuilder.cpp b/src/assetimport/qssgmeshbvhbuilder.cpp
new file mode 100644
index 00000000..05724d57
--- /dev/null
+++ b/src/assetimport/qssgmeshbvhbuilder.cpp
@@ -0,0 +1,306 @@
+/****************************************************************************
+**
+** 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
diff --git a/src/assetimport/qssgmeshbvhbuilder_p.h b/src/assetimport/qssgmeshbvhbuilder_p.h
new file mode 100644
index 00000000..f797ff07
--- /dev/null
+++ b/src/assetimport/qssgmeshbvhbuilder_p.h
@@ -0,0 +1,101 @@
+/****************************************************************************
+**
+** 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$
+**
+****************************************************************************/
+
+#ifndef QSSGMESHBVHBUILDER_H
+#define QSSGMESHBVHBUILDER_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+#include <QtQuick3DAssetImport/private/qtquick3dassetimportglobal_p.h>
+#include <QtQuick3DUtils/private/qssgmeshbvh_p.h>
+#include <QtQuick3DAssetImport/private/qssgmeshutilities_p.h>
+
+QT_BEGIN_NAMESPACE
+
+class Q_QUICK3DASSETIMPORT_EXPORT QSSGMeshBVHBuilder
+{
+public:
+    QSSGMeshBVHBuilder(QSSGMeshUtilities::Mesh *mesh);
+
+    QSSGMeshBVH* buildTree();
+
+private:
+    enum class Axis
+    {
+        None = -1,
+        X = 0,
+        Y = 1,
+        Z = 2
+    };
+    struct Split {
+        Axis axis;
+        float pos;
+    };
+
+    QVector<QSSGMeshBVHTriangle*> calculateTriangleBounds(quint32 indexOffset, quint32 indexCount) const;
+    quint32 getIndexBufferValue(quint32 index) const;
+    QVector3D getVertexBufferValuePosition(quint32 index) const;
+    QVector2D getVertexBufferValueUV0(quint32 index) const;
+
+    QSSGMeshBVHNode *splitNode(QSSGMeshBVHNode *node, quint32 offset, quint32 count, quint32 depth = 0);
+    QSSGBounds3 getBounds(quint32 offset, quint32 count) const;
+    Split getOptimalSplit(const QSSGBounds3 &nodeBounds, quint32 offset, quint32 count) const;
+    static Axis getLongestDimension(const QSSGBounds3 &nodeBounds);
+    float getAverageValue(quint32 offset, quint32 count, Axis axis) const;
+    quint32 partition(quint32 offset, quint32 count, const Split &split);
+
+    QSSGMeshUtilities::Mesh *m_mesh;
+    quint8 *m_baseAddress;
+    QSSGRenderComponentType m_indexBufferComponentType;
+    QSSGByteView m_indexBufferData;
+    QSSGByteView m_vertexBufferData;
+    quint32 m_vertexStride;
+    bool m_hasPositionData = false;
+    quint32 m_vertexPosOffset;
+    bool m_hasUVData = false;
+    quint32 m_vertexUV0Offset;
+
+
+    QVector<QSSGMeshBVHTriangle *> m_triangleBounds;
+    QVector<QSSGMeshBVHNode *> m_roots;
+    quint32 m_maxTreeDepth = 40;
+    quint32 m_maxLeafTriangles = 10;
+};
+
+QT_END_NAMESPACE
+
+#endif // QSSGMESHBVHBUILDER_H
diff --git a/src/runtimerender/qssgrendermesh_p.h b/src/runtimerender/qssgrendermesh_p.h
index fcbe331d..3707478d 100644
--- a/src/runtimerender/qssgrendermesh_p.h
+++ b/src/runtimerender/qssgrendermesh_p.h
@@ -47,6 +47,7 @@
 #include <QtQuick3DRender/private/qssgrenderinputassembler_p.h>
 
 #include <QtQuick3DUtils/private/qssgbounds3_p.h>
+#include <QtQuick3DUtils/private/qssgmeshbvh_p.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -55,9 +56,13 @@ struct QSSGRenderSubsetBase
     quint32 count;
     quint32 offset;
     QSSGBounds3 bounds; // Vertex buffer bounds
+    QSSGMeshBVHNode *bvhRoot = nullptr;
     QSSGRenderSubsetBase() = default;
     QSSGRenderSubsetBase(const QSSGRenderSubsetBase &inOther)
-        : count(inOther.count), offset(inOther.offset), bounds(inOther.bounds)
+        : count(inOther.count)
+        , offset(inOther.offset)
+        , bounds(inOther.bounds)
+        , bvhRoot(inOther.bvhRoot)
     {
     }
 
@@ -66,6 +71,7 @@ struct QSSGRenderSubsetBase
         count = inOther.count;
         offset = inOther.offset;
         bounds = inOther.bounds;
+        bvhRoot = inOther.bvhRoot;
         return *this;
     }
 };
@@ -186,11 +192,17 @@ struct QSSGRenderMesh
     QSSGRenderDrawMode drawMode;
     QSSGRenderWinding winding; // counterclockwise
     quint32 meshId; // Id from the file of this mesh.
+    QSSGMeshBVH *bvh = nullptr;
 
     QSSGRenderMesh(QSSGRenderDrawMode inDrawMode, QSSGRenderWinding inWinding, quint32 inMeshId)
         : drawMode(inDrawMode), winding(inWinding), meshId(inMeshId)
     {
     }
+
+    ~QSSGRenderMesh()
+    {
+        delete bvh;
+    }
 };
 QT_END_NAMESPACE
 
diff --git a/src/runtimerender/qssgrenderray.cpp b/src/runtimerender/qssgrenderray.cpp
index 9aa22f74..50d8106d 100644
--- a/src/runtimerender/qssgrenderray.cpp
+++ b/src/runtimerender/qssgrenderray.cpp
@@ -32,6 +32,8 @@
 
 #include <QtQuick3DUtils/private/qssgplane_p.h>
 #include <QtQuick3DUtils/private/qssgutils_p.h>
+#include <QtQuick3DUtils/private/qssgmeshbvh_p.h>
+#include <QtQuick3DRuntimeRender/private/qssgrendermesh_p.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -55,7 +57,7 @@ QSSGRenderRay::RayData QSSGRenderRay::createRayData(const QMatrix4x4 &globalTran
     QVector3D transformedOrigin = mat44::transform(originTransform, ray.origin);
     float *outOriginTransformPtr(originTransform.data());
     outOriginTransformPtr[12] = outOriginTransformPtr[13] = outOriginTransformPtr[14] = 0.0f;
-    const QVector3D &transformedDirection = mat44::rotate(originTransform, ray.direction);
+    const QVector3D &transformedDirection = mat44::rotate(originTransform, ray.direction).normalized();
     static auto getInverseAndDirOp = [](const QVector3D &dir, QVector3D &invDir, DirectionOp (&dirOp)[3]) {
         for (int i = 0; i != 3; ++i) {
             const float axisDir = dir[i];
@@ -130,6 +132,68 @@ QSSGRenderRay::HitResult QSSGRenderRay::intersectWithAABBv2(const QSSGRenderRay:
     return { tmin, tmax, &bounds };
 }
 
+bool QSSGRenderRay::triangleIntersect(const QSSGRenderRay &ray,
+                                      const QVector3D &v0,
+                                      const QVector3D &v1,
+                                      const QVector3D &v2,
+                                      float &u,
+                                      float &v)
+{
+    // Compute the Triangle's Normal (N)
+    const QVector3D v0v1 = v1 - v0;
+    const QVector3D v0v2 = v2 - v0;
+    const QVector3D normal = QVector3D::crossProduct(v0v1, v0v2);
+    const float denominator = QVector3D::dotProduct(normal, normal);
+
+    // Find the Intersection point (P)
+
+    // Check for the case where the ray and plane are parallel
+    const float Vd = QVector3D::dotProduct(normal, ray.direction);
+    if (std::abs(Vd) < 0.0001f)
+        return false;
+
+    const float d = QVector3D::dotProduct(normal, v0);
+
+    // Check if the triangle is behind the ray start
+    const float t = -(QVector3D::dotProduct(normal, ray.origin) - d) / Vd;
+    if (t < 0)
+        return false;
+
+    // Get the intersetion Point (P) on Triangle Plane
+    const QVector3D P = ray.origin + t * ray.direction;
+
+    // Test if P is inside of the triangle
+    QVector3D C;
+
+    // Edge 0
+    const QVector3D edge0 = v1 - v0;
+    const QVector3D vp0 = P - v0;
+    C = QVector3D::crossProduct(edge0, vp0);
+    if (QVector3D::dotProduct(normal, C) < 0)
+        return false;
+
+    // Edge 1
+    const QVector3D edge1 = v2 - v1;
+    const QVector3D vp1 = P - v1;
+    C = QVector3D::crossProduct(edge1, vp1);
+    u = QVector3D::dotProduct(normal, C);
+    if (u < 0)
+        return false;
+
+    // Edge 2
+    const QVector3D edge2 = v0 - v2;
+    const QVector3D vp2 = P - v2;
+    C = QVector3D::crossProduct(edge2, vp2);
+    v = QVector3D::dotProduct(normal, C);
+    if (v < 0)
+        return false;
+
+    u /= denominator;
+    v /= denominator;
+
+    return true;
+}
+
 QSSGRenderRay::IntersectionResult QSSGRenderRay::intersectWithAABB(const QMatrix4x4 &inGlobalTransform,
                                                                    const QSSGBounds3 &inBounds,
                                                                    const QSSGRenderRay &ray,
@@ -206,6 +270,81 @@ QSSGRenderRay::IntersectionResult QSSGRenderRay::intersectWithAABB(const QMatrix
     return IntersectionResult(rayLengthSquared, relXY, newPosInGlobal);
 }
 
+void QSSGRenderRay::intersectWithBVH(const RayData &data,
+                                     const QSSGMeshBVHNode *bvh,
+                                     const QSSGRenderMesh *mesh,
+                                     QVector<IntersectionResult> &intersections,
+                                     int depth)
+{
+    if (!bvh || !mesh || !mesh->bvh)
+        return;
+
+    // If this is a leaf node, process it's triangles
+    if (bvh->count != 0) {
+        // If there is an intersection on a leaf node, then test against geometry
+        auto results = intersectWithBVHTriangles(data, mesh->bvh->triangles, bvh->offset, bvh->count);
+        if (!results.isEmpty())
+            intersections.append(results);
+        return;
+    }
+
+    auto hit = QSSGRenderRay::intersectWithAABBv2(data, bvh->left->boundingData);
+    if (hit.intersects())
+        intersectWithBVH(data, bvh->left, mesh, intersections, depth + 1);
+
+    hit = QSSGRenderRay::intersectWithAABBv2(data, bvh->right->boundingData);
+    if (hit.intersects())
+        intersectWithBVH(data, bvh->right, mesh, intersections, depth + 1);
+}
+
+
+
+QVector<QSSGRenderRay::IntersectionResult> QSSGRenderRay::intersectWithBVHTriangles(const RayData &data,
+                                                                                    const QVector<QSSGMeshBVHTriangle *> &bvhTriangles,
+                                                                                    int triangleOffset,
+                                                                                    int triangleCount)
+{
+    Q_ASSERT(bvhTriangles.count() >= triangleOffset + triangleCount);
+
+    QVector<QSSGRenderRay::IntersectionResult> results;
+
+    for (int i = triangleOffset; i < triangleCount + triangleOffset; ++i) {
+        const auto &triangle = bvhTriangles[i];
+
+        QSSGRenderRay relativeRay(data.origin, data.direction);
+
+        // Use Barycentric Coordinates to get the intersection values
+        float u = 0.f;
+        float v = 0.f;
+        const bool intersects = triangleIntersect(relativeRay,
+                                                  triangle->vertex1,
+                                                  triangle->vertex2,
+                                                  triangle->vertex3,
+                                                  u,
+                                                  v);
+        if (intersects) {
+            const float w = 1.0f - u - v;
+            const QVector3D localIntersectionPoint = u * triangle->vertex1 +
+                                                     v * triangle->vertex2 +
+                                                     w * triangle->vertex3;
+
+            const QVector2D uvCoordinate = u * triangle->uvCoord1 +
+                                           v * triangle->uvCoord2 +
+                                           w * triangle->uvCoord3;
+            // Get the intersection point in scene coordinates
+            const QVector3D sceneIntersectionPos = mat44::transform(data.globalTransform,
+                                                                    localIntersectionPoint);
+            const QVector3D hitVector = data.ray.origin - sceneIntersectionPos;
+            // Get the magnitude of the hit vector
+            const float rayLengthSquared = vec3::magnitudeSquared(hitVector);
+            results.append(IntersectionResult(rayLengthSquared, uvCoordinate, sceneIntersectionPos));
+        }
+    }
+
+    // Does not intersect with any of the triangles
+    return results;
+}
+
 QSSGOption<QVector2D> QSSGRenderRay::relative(const QMatrix4x4 &inGlobalTransform,
                                                      const QSSGBounds3 &inBounds,
                                                      QSSGRenderBasisPlanes inPlane) const
diff --git a/src/runtimerender/qssgrenderray_p.h b/src/runtimerender/qssgrenderray_p.h
index 0b2dacbb..5528cede 100644
--- a/src/runtimerender/qssgrenderray_p.h
+++ b/src/runtimerender/qssgrenderray_p.h
@@ -51,6 +51,9 @@
 #include <QtGui/QMatrix4x4>
 
 QT_BEGIN_NAMESPACE
+struct QSSGMeshBVHNode;
+struct QSSGRenderMesh;
+struct QSSGMeshBVHTriangle;
 enum class QSSGRenderBasisPlanes
 {
     XY,
@@ -70,6 +73,14 @@ struct Q_AUTOTEST_EXPORT QSSGRenderRay
     // If we are parallel, then no intersection of course.
     static QSSGOption<QVector3D> intersect(const QSSGPlane &inPlane, const QSSGRenderRay &ray);
 
+    // Perform an intersection aslo returning Barycentric Coordinates
+    static bool triangleIntersect(const QSSGRenderRay &ray,
+                                  const QVector3D &v0,
+                                  const QVector3D &v1,
+                                  const QVector3D &v2,
+                                  float &u,
+                                  float &v);
+
     struct IntersectionResult
     {
         bool intersects = false;
@@ -124,6 +135,17 @@ struct Q_AUTOTEST_EXPORT QSSGRenderRay
                                                 const QSSGRenderRay &ray,
                                                 bool inForceIntersect = false);
 
+    static void intersectWithBVH(const RayData &data,
+                                        const QSSGMeshBVHNode *bvh,
+                                        const QSSGRenderMesh *mesh,
+                                        QVector<IntersectionResult> &intersections,
+                                        int depth = 0);
+
+    static QVector<IntersectionResult> intersectWithBVHTriangles(const RayData &data,
+                                                                 const QVector<QSSGMeshBVHTriangle *> &bvhTriangles,
+                                                                 int triangleOffset,
+                                                                 int triangleCount);
+
     QSSGOption<QVector2D> relative(const QMatrix4x4 &inGlobalTransform,
                                         const QSSGBounds3 &inBounds,
                                         QSSGRenderBasisPlanes inPlane) const;
diff --git a/src/runtimerender/rendererimpl/qssgrendererimpl.cpp b/src/runtimerender/rendererimpl/qssgrendererimpl.cpp
index 8aa46167..0c106510 100644
--- a/src/runtimerender/rendererimpl/qssgrendererimpl.cpp
+++ b/src/runtimerender/rendererimpl/qssgrendererimpl.cpp
@@ -883,6 +883,7 @@ void QSSGRendererImpl::intersectRayWithSubsetRenderable(const QSSGRef<QSSGBuffer
         return;
 
     const auto &globalTransform = model.globalTransform;
+    auto rayData = QSSGRenderRay::createRayData(globalTransform, inRay);
     const auto &subMeshes = mesh->subsets;
     QSSGBounds3 modelBounds = QSSGBounds3::empty();
     for (const auto &subMesh : subMeshes)
@@ -891,18 +892,37 @@ void QSSGRendererImpl::intersectRayWithSubsetRenderable(const QSSGRef<QSSGBuffer
     if (modelBounds.isEmpty())
         return;
 
-    QSSGRenderRay::IntersectionResult intersectionResult = QSSGRenderRay::intersectWithAABB(globalTransform, modelBounds, inRay);
+    auto hit = QSSGRenderRay::intersectWithAABBv2(rayData, modelBounds);
 
     // If we don't intersect with the model at all, then there's no need to go furher down!
-    if (!intersectionResult.intersects)
+    if (!hit.intersects())
         return;
 
     // Check each submesh to find the closest intersection point
     float minRayLength = std::numeric_limits<float>::max();
-    // reset intersectionResult
-    intersectionResult = QSSGRenderRay::IntersectionResult();
+    QSSGRenderRay::IntersectionResult intersectionResult;
+    QVector<QSSGRenderRay::IntersectionResult> results;
+
     for (const auto &subMesh : subMeshes) {
-        const auto result = QSSGRenderRay::intersectWithAABB(globalTransform, subMesh.bounds, inRay);
+        QSSGRenderRay::IntersectionResult result;
+        if (subMesh.bvhRoot) {
+            hit = QSSGRenderRay::intersectWithAABBv2(rayData, subMesh.bvhRoot->boundingData);
+            if (hit.intersects()) {
+                results.clear();
+                inRay.intersectWithBVH(rayData, subMesh.bvhRoot, mesh, results);
+                float subMeshMinRayLength = std::numeric_limits<float>::max();
+                for (const auto &subMeshResult : qAsConst(results)) {
+                    if (subMeshResult.rayLengthSquared < subMeshMinRayLength) {
+                        result = subMeshResult;
+                        subMeshMinRayLength = result.rayLengthSquared;
+                    }
+                }
+            }
+        } else {
+            hit = QSSGRenderRay::intersectWithAABBv2(rayData, subMesh.bounds);
+            if (hit.intersects())
+                result = QSSGRenderRay::createIntersectionResult(rayData, hit);
+        }
         if (result.intersects && result.rayLengthSquared < minRayLength) {
             intersectionResult = result;
             minRayLength = intersectionResult.rayLengthSquared;
diff --git a/src/runtimerender/resourcemanager/qssgrenderbuffermanager.cpp b/src/runtimerender/resourcemanager/qssgrenderbuffermanager.cpp
index 9230d8e5..0ad000a8 100644
--- a/src/runtimerender/resourcemanager/qssgrenderbuffermanager.cpp
+++ b/src/runtimerender/resourcemanager/qssgrenderbuffermanager.cpp
@@ -32,6 +32,7 @@
 
 #include <QtQuick3DRuntimeRender/private/qssgrenderprefiltertexture_p.h>
 #include <QtQuick3DRuntimeRender/private/qssgruntimerenderlogging_p.h>
+#include <QtQuick3DAssetImport/private/qssgmeshbvhbuilder_p.h>
 
 #include <QtQuick/QSGTexture>
 
@@ -495,10 +496,15 @@ QSSGRenderMesh *QSSGBufferManager::createRenderMesh(
         ::memcpy(newJoint.localToGlobalBoneSpace, importJoint.m_localToGlobalBoneSpace, 16 * sizeof(float));
     }
 
+    // Build BVH for Mesh
+    QSSGMeshBVHBuilder meshBVHBuilder(result.m_mesh);
+    newMesh->bvh = meshBVHBuilder.buildTree();
+
     for (quint32 subsetIdx = 0, subsetEnd = result.m_mesh->m_subsets.size(); subsetIdx < subsetEnd; ++subsetIdx) {
         QSSGRenderSubset subset;
         const QSSGMeshUtilities::MeshSubset &source(result.m_mesh->m_subsets.index(baseAddress, subsetIdx));
         subset.bounds = source.m_bounds;
+        subset.bvhRoot = newMesh->bvh->roots.at(subsetIdx);
         subset.count = source.m_count;
         subset.offset = source.m_offset;
         subset.joints = newMesh->joints;
diff --git a/src/utils/qssgmeshbvh.cpp b/src/utils/qssgmeshbvh.cpp
new file mode 100644
index 00000000..0a78463d
--- /dev/null
+++ b/src/utils/qssgmeshbvh.cpp
@@ -0,0 +1,40 @@
+/****************************************************************************
+**
+** 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 "qssgmeshbvh_p.h"
+
+QT_BEGIN_NAMESPACE
+
+QSSGMeshBVH::~QSSGMeshBVH()
+{
+    qDeleteAll(triangles);
+    qDeleteAll(roots);
+}
+
+QT_END_NAMESPACE
diff --git a/src/utils/qssgmeshbvh_p.h b/src/utils/qssgmeshbvh_p.h
new file mode 100644
index 00000000..6a18e4fb
--- /dev/null
+++ b/src/utils/qssgmeshbvh_p.h
@@ -0,0 +1,94 @@
+/****************************************************************************
+**
+** 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$
+**
+****************************************************************************/
+
+#ifndef QSSGMESHBVH_H
+#define QSSGMESHBVH_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QtQuick3DUtils/private/qtquick3dutilsglobal_p.h>
+#include <QtQuick3DUtils/private/qssgbounds3_p.h>
+
+#include <QtGui/QVector2D>
+#include <QtCore/QVector>
+
+QT_BEGIN_NAMESPACE
+
+struct Q_QUICK3DUTILS_EXPORT QSSGMeshBVHNode {
+    ~QSSGMeshBVHNode() {
+        delete left;
+        delete right;
+    }
+
+    // Internal
+    QSSGMeshBVHNode *left = nullptr;
+    QSSGMeshBVHNode *right = nullptr;
+    QSSGBounds3 boundingData;
+    //splitAxis
+
+    // Leaf
+    int offset = 0;
+    int count = 0;
+};
+
+struct Q_QUICK3DUTILS_EXPORT QSSGMeshBVHTriangle {
+    QSSGBounds3 bounds;
+    QVector3D vertex1;
+    QVector3D vertex2;
+    QVector3D vertex3;
+    QVector2D uvCoord1;
+    QVector2D uvCoord2;
+    QVector2D uvCoord3;
+};
+
+struct Q_QUICK3DUTILS_EXPORT QSSGMeshBVH
+{
+    QSSGMeshBVH(const QVector<QSSGMeshBVHNode *> &bvhRoots,
+                const QVector<QSSGMeshBVHTriangle *> &bvhTriangles)
+        : roots(bvhRoots)
+        , triangles(bvhTriangles)
+    {}
+    ~QSSGMeshBVH();
+
+    QVector<QSSGMeshBVHNode *> roots;
+    QVector<QSSGMeshBVHTriangle *> triangles;
+};
+
+QT_END_NAMESPACE
+
+#endif // QSSGMESHBVH_H
diff --git a/src/utils/utils.pro b/src/utils/utils.pro
index 3986bdf3..f8434b06 100644
--- a/src/utils/utils.pro
+++ b/src/utils/utils.pro
@@ -7,6 +7,7 @@ DEFINES += QT_BUILD_QUICK3DUTILS_LIB
 
 HEADERS += \
     qssgbounds3_p.h \
+    qssgmeshbvh_p.h \
     qssgutils_p.h \
     qssgdataref_p.h \
     qssgoption_p.h \
@@ -18,6 +19,7 @@ HEADERS += \
 SOURCES += \
     qssgbounds3.cpp \
     qssgdataref.cpp \
+    qssgmeshbvh.cpp \
     qssgperftimer.cpp \
     qssgplane.cpp \
     qssgutils.cpp