我必须实现一种算法来分解体素中的 3D 体积。该算法首先确定哪些顶点位于切割计划的每一侧,然后在第二步中哪条边穿过切割计划。
这个过程可以通过使用排序列表的好处来优化。识别分裂点是O log(n)。但是我必须为每个轴维护一个这样的排序列表,这个列表用于顶点和边。由于这是为了供 GPU 使用而实现的,所以我对内存管理(即 CUDA)也有一些限制。强加了侵入性列表 M/树和 C。
通过完整的“体素化”,我希望最终得到约 4000 个点和 12000 个边缘。幸运的是,这可以通过使用更智能的策略来优化,以摆脱处理过的体素并订购剩余体积切割以将其数量保持在最低限度。在这种情况下,我希望有少于 100 个点和 300 个边。这使得流程管理起来更加复杂,但最终可能会变得更加高效。
因此,问题是帮助我确定标准,以确定与简单的侵入式链接列表相比,使用排序数据结构的好处何时值得付出努力和复杂性开销。