I'm writing a Binary Space Partitioning (BSP) tree for the purpose of optimizing finding the nearest point on the surface of a 3d triangle mesh with respect to another point. I'm currently following a method similar to the one described here to build the tree and then using Barycentric coordinates to locate the nearest points on the surface of the triangles.
I'm having an issue on how to resolve when a triangle is split by the splitting plane (i.e. all three points in the triangle are not on the same side of the splitting plane). One solution presented in the previous link would be to attach these conflicting triangles to the root node, but I'm not sure how this would impact tree traversal. When traversing through the tree and eventually getting to a leaf node containing a set of triangles that are nearest to your query point, which you would have to check each to see which is nearest, would you be also required to check against all triangles in parent nodes?
A different method I thought of would be to just include the conflicting triangles in both the positive and negative children of a node that is split (positive children being above the plane, negative below). This way, they could still be excluded in further iterations of the splitting plane, but it seems a bit redundant.
A final alternative is to instead use vertices to build my tree and once having found the nearest vertex to the query point reference nearby triangles. This would make building the tree much simpler, but because the nearest point is not necessarily a part of the nearest triangle, you are required to retrieve multiple nearest points and query against multiple nearest triangles to ensure you have the correct nearest one.
Each of these methods seems a bit inelegant so I'm hoping there's a simpler solution out there.
