我已经阅读了维基百科上关于k-d树的描述，维基百科指出k-d树保存点。我有一个三角形网格，并需要一些结构来有效地计算与圆柱体的交点和点查询的距离。据我所知，如果我通过平面分割我的网格 - 许多三角形可能会相交于该平面。那么我该怎么做呢？将三角形的拷贝放入左右子框中，还是分割交错的三角形？
1个回答
2
您需要将相交的三角形拆分。查看任何使用KD树的开源光线追踪算法，以了解如何执行此操作，或在Google学术中搜索学术论文。
请查看表面积启发式算法以选择好的拆分平面，在光线追踪中通常使用，但它可能适用于您的情况。
- jkflying
2
我已经实现了带三角形的3D kd-tree。如果分割平面与三角形相交，则将其放入两个子节点中。我使用SAH和min-max binning来选择分割平面-这是我在构建速度和树质量之间的一个很好的折衷方案。在你的回答之后，我开始思考分割三角形的想法。在你看来，分割三角形和不分割三角形对于最近邻搜索和范围查询有什么优缺点？ - hardliner
抱歉耽搁了。我将它们分开的原因是，这样您就可以使用带有边界框的标准KD-Tree来加速NN查找。如果您不拆分三角形，则边界框会变得很大，从而降低NN搜索的效率。 - jkflying
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接