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.

  • 1
    \$\begingroup\$ Standard solutions are to either include them in the parent nodes (all queries must look at them) or store them in each partition they are in. It is not clear why the latter solution is inelegant: the spatial data structure (octree, kd-tree, bsp tree, etc.) must store all geometry that is nearby an area in order to answer nearest point queries, even if this means duplicated geometry (use indices to avoid storing it multiple times). \$\endgroup\$
    – user41442
    Mar 25, 2015 at 2:45
  • \$\begingroup\$ I suppose when I think about it further it's really not, I guess I wanted to just make sure there wasn't anything established that was more refined. Thanks for the answer! \$\endgroup\$
    – Erik
    Mar 25, 2015 at 5:16
  • \$\begingroup\$ The conflict for me is between the cost of being seen by many (in the parent node) and the bookkeeping of identifying that you've considered the leaf already when overlapping many leaf nodes. Both have pros and cons. \$\endgroup\$
    – Steven
    Mar 27, 2015 at 6:54
  • \$\begingroup\$ What did you end up settling with and how did it work out? \$\endgroup\$
    – Korijn
    Sep 13, 2016 at 16:57
  • \$\begingroup\$ I ended up adding triangles that were split by a partition plane to both left and right partitions. You can see the implementation here in the BSPTree's Split(...) method. Bear in mind that my actual partitioning algorithm is far from optimal! I never added an answer, as I still don't know if there's a specific optimal way of doing this. \$\endgroup\$
    – Erik
    Sep 15, 2016 at 20:54


You must log in to answer this question.

Browse other questions tagged .