用于查找 3D 中最近三角形的数据结构
Data structure for finding nearest triangle in 3D
我有一组三角形，我想在 space 中找到离任意点最近的三角形。
强力方法对我来说太慢了，所以我正在研究可以帮助加速搜索的各种数据结构。
我的问题是，我研究过的结构（rtree、kdtree）使用边界框来缩小搜索范围，但在很多情况下，最近的边界框不一定对应于最近的三角形。
这是一个这样的例子：
注意蓝点如何最接近大边界框，但更接近绿色小三角形。这让我觉得依赖边界框的数据结构会导致不正确的搜索结果......除非我遗漏了一些明显的东西？
总的来说，我正在寻找一种轻量级的 C++ 解决方案（因此没有 CGAL 或其他强大的包），或者只是指向我应该研究的正确算法的一点。
谢谢！
您可以使用边界框方法来缩小搜索范围。您只需执行以下操作：
- 找到最近的边界框（假设它是您示例中的大边界框）
- 令 r 为点与最近边界框之间的距离，b 为边界框的大小。找出所有距离该点小于 (r+b) 的边界框。
- 使用蛮力在剩余的边界框中找到最近的三角形。
我认为你可以使用 Binary Space Partitioning 来更有效地处理像你描述的那样的尴尬情况。
本质上你会有类似于 k-d 树的东西，你可以沿着任意平面（通常基于场景中的现有边缘之一）而不是轴对齐的分割。
缺点是构建树的速度可能会比较慢。
我有一组三角形，我想在 space 中找到离任意点最近的三角形。
强力方法对我来说太慢了，所以我正在研究可以帮助加速搜索的各种数据结构。
我的问题是，我研究过的结构（rtree、kdtree）使用边界框来缩小搜索范围，但在很多情况下，最近的边界框不一定对应于最近的三角形。
这是一个这样的例子：
注意蓝点如何最接近大边界框，但更接近绿色小三角形。这让我觉得依赖边界框的数据结构会导致不正确的搜索结果......除非我遗漏了一些明显的东西？
总的来说，我正在寻找一种轻量级的 C++ 解决方案（因此没有 CGAL 或其他强大的包），或者只是指向我应该研究的正确算法的一点。
谢谢！
您可以使用边界框方法来缩小搜索范围。您只需执行以下操作：
- 找到最近的边界框（假设它是您示例中的大边界框）
- 令 r 为点与最近边界框之间的距离，b 为边界框的大小。找出所有距离该点小于 (r+b) 的边界框。
- 使用蛮力在剩余的边界框中找到最近的三角形。
我认为你可以使用 Binary Space Partitioning 来更有效地处理像你描述的那样的尴尬情况。
本质上你会有类似于 k-d 树的东西，你可以沿着任意平面（通常基于场景中的现有边缘之一）而不是轴对齐的分割。
缺点是构建树的速度可能会比较慢。