我正在尝试构建一个表示最初由 CSG（构造实体几何）树描述的体积的八叉树。
我最初的计划是从一个包含整个对象的大立方体开始，然后对八个子立方体中的每一个进行测试，哪些是完全在外部的，哪些是完全在对象内部的，哪些是内部的和外部的。然后这些“中间”立方体将被递归细分。
我的问题可能很愚蠢，但我无法设计一种方法来找到立方体和 CSG 对象的交集，以便能够如上所述对立方体进行分类。
我的 CSG 结构是由诸如立方体、球体和圆柱体（未来可能还有环面）之类的基元构建的，具有并集、交集和减法的布尔运算。
除了 CSG 的显式树结构之外，从它的表示来看，我还有一种距离函数d(x,y,z)，它可以告诉我该点(x,y,z)是在对象外部 (>0) 还是在对象内部 (<0)。
如何找到一个立方体是否与 CSG 结构所描述的对象相交？
听起来有点像您正在尝试重新发明稀疏体素八叉树。
我的想法是以您希望考虑的最佳立方体分辨率采样（无论如何您都必须有一个分辨率截止）。
在 Z 阶曲线（也称为 Morton 阶）上的点上对距离函数进行采样，并在每次距离函数更改符号时记下坐标。请注意，基于 Z 阶曲线的特性，为此所需的存储空间应相对于表面积而不是体积渐近缩放。
这种结构在功能上等同于离散八叉树（因此您可以想象按原样使用它），因为 Morton 排序等同于八叉树的深度优先遍历。
但重点是，使用这种结构，您可以使用立方角的 Mortonized 坐标的二分搜索来有效地测试八叉树与立方体的交点。请注意，在执行此操作时，可以使用 2 个坐标来描述八叉树对齐的立方体。对于 Morton 阶，我们将有一个“下”和一个“上”立体角，并且当且仅当有任何符号变化时，立方体在采样分辨率下是“有趣的”（不是完全空的或满的）间隔(lower,upper]。只要您选择的原始采样分辨率足够精细，以至于单个 CSG 基元不能完全适合您的最小网格线，您就不会错过任何功能。
明确地找到与立方体边界的交点稍微复杂一些，但相当可行。根据我的记忆，您必须考虑立方体边界处发生的符号变化，并考虑表面边界与立方体边界重合的特殊情况（也可能发生在完全完整的立方体上）。我将把它作为练习留给读者，因为我有一段时间没有计算出数学了。我只是想尝试帮助你更进一步。