我試圖構建一個八叉樹，它代表最初由CSG（構造實體幾何）樹描述的體積。找到立方體和CSG對象之間的八叉樹細分的交集
我最初的計劃是從一個包含整個對象的大立方體開始，然後爲八個子立方體中的每一個測試哪些完全在外面，哪些完全位於對象內部，哪些都在內部和外面。然後這些「中間」小方塊將被遞歸細分。
我的問題可能很愚蠢，但我無法設計出一種方法來查找CSG對象的立方體和 的交集，以便能夠像上面那樣對立方體進行分類。
我的CSG結構是從諸如立方體，球體和圓柱體（以及未來的toruses）等基元構建而成的，具有聯合，交叉和減法的布爾操作。
旁CSG的明確的樹形結構，從它的表示我也有一種距離函數d(x,y,z)那會告訴我如果點(x,y,z)是外部（> 0）或內側（< 0）的對象。
如何找到立方體是否與CSG結構描述的對象相交？
聽起來有點像你試圖重新發明稀疏體素八叉樹。
我的想法是以您希望考慮的最好的立方體分辨率取樣（無論如何您都必須有解決方案截止點）。
在位於Z-階曲線（也稱爲莫頓階）上的點上採樣距離函數，並記錄每次距離函數改變符號時的座標。請注意，基於Z階曲線的屬性，所需的存儲空間應該相對於表面積漸近地縮放，而不是按體積縮放。
這個結構在功能上等同於一個離散的八叉樹（因此你可以想象它是按原樣使用的），因爲Morton排序相當於八叉樹的深度優先遍歷。
但重點是，使用此結構，您可以使用二維搜索立方體角的Mortonized座標來高效地測試八叉樹立體交叉點。注意這樣做時，可以使用2個座標來描述八叉樹對齊的立方體。對於Morton階，我們將有一個「較低」和「較高」的立方體角，當且僅當有任何符號變化時，抽樣分辨率（不完全爲空或滿）的立方體纔是「有趣的」區間(lower,upper]。只要您選擇您的原始採樣分辨率足夠好，以使單個CSG基元不能完全適合您的最小網格線，您將不會錯過任何功能。
明確地發現與立方體邊界的交點有一點涉及，但相當可行。在我的記憶中，您必須考慮在立方體邊界處發生的符號變化，並考慮表面邊界與立方體邊界重合的特殊情況（這也可能發生在完全立方體上）。我將把它作爲讀者的練習，因爲我一段時間都沒有計算出數學。我只是想盡力幫助你更前進。