我必须实现一个算法来分解体素中的三维体积。该算法通过识别切割平面的每一侧上的哪些顶点以及第二步中哪条边穿过切割平面来开始。何时从无序列表切换到排序列表？ [优化]
这个过程可以通过使用排序列表的好处来优化。识别分割点是O log（n）。但我必须维护一个这样的排序列表，每个轴和顶点和边缘。由于这是要被GPU使用的，所以我对内存管理（即CUDA）也有一些限制。侵入性列表M /树和C是强加的。
有了完整的“体素化”，我预计最终会有4000点和12000个边缘。幸运的是，这可以通过使用更智能的策略来摆脱已处理的体素并对剩余体积进行排序以使其数量保持最小，从而进行优化。在这种情况下，我希望有少于100点和300个边缘。这使得这个过程更加复杂，但最终可能会更有效率。
因此，问题是帮助我确定标准，以确定何时使用排序数据结构的好处值得努力和复杂性开销与简单的入侵链接列表相比较。
问题总是归结为哪个操作员最常见，访问或添加。 如果您有一个无序列表，添加到它无需时间，访问特定项目需要额外的时间。 如果您有一个排序列表，添加它需要更多时间，但访问更快。
大多数应用程序花费大部分时间访问数据，而不是增加数据，这意味着创建排序列表时的（运行）时间开销通常会平衡或覆盖访问列表中保存的时间。 如果你的数据中有很多流失（它听起来并不像这样），那么维护一个排序列表并不一定是可取的，因为你会不断地使用这个清单作为可观的CPU成本。
数据结构的复杂性只有在不能以有用的方式对进行排序时才有意义。如果他们可以进行排序，那么你就必须通过
访问次数启发式去：确定变化
的号码，如果排序是一个好主意。
chmike，这听起来像是你想要做的第一个简单的方法，看看它的行为。一旦你至少进入大容量（你似乎没有），任何类型的GPU体素化方法对于系统细节都非常脆弱。在你的鞋子里，我绝对需要首先直接实现，如果没有其他原因要检查...
考虑到所有的答案后，我发现用于避免重复计算的后面的方法由于在数据结构中进行维护和导航的工作而效率会降低。除此之外，最初的方法可以直接与几个小的内核例程并行化，因此更适合于GPU实现。
检查我的初始方法我还发现了显着的优化机会，让音量减少方法远远落后。
因为我必须选择一个答案，所以我选择了devinb是因为他回答了这个问题，但是Simon的评论由Tobias Warre评论支持，对我来说同样重要。
感谢大家帮我解决这个问题。 堆栈溢出是一项令人印象深刻的服务。
这是一个非常好的主意，有一个简单的，也许很慢的版本，这是正确的，可以对其进行测试。然后你可以开发一个更复杂的版本，运行速度更快，并且可以根据天真的版本检查正确性。 然后，制作排序后的链接列表并不那么复杂，它主要是关于如何插入元素，但是，以与排序顺序不同的顺序检索它们仍然会产生缓慢的结果，同样会插入新元素。 – 2009-04-21 15:07:49
我已经可以验证体素化的好处了。现在我想优化流程，并使用与首先使用的策略不同的策略。在第一种方法中，我实例化了体素并用体积表面切割了它们的面。这是最简单的实现，并且很平行。但是我最终重新计算了相同的交点和其他值。通过体积体积进行优化可以避免它，但会带来开销。 – chmike 2009-04-21 15:54:16