如何查找3D對象是否適合其他3D對象（容器）？

給定兩個3d對象，我怎麼才能找到一個是否適合第二個（並找到對象在容器中的位置）。如何查找3D對象是否適合其他3D對象（容器）？

該對象應該被翻譯和旋轉以適應容器 - 但不能修改。

其他併發症：

同樣的情況 - 但尋找最適合的解決方案，即使它不是一個正確的匹配（最小化不適合於容器中的物體的體積）
支持彈性目標 - 找到最適合的，而在對象

這是一個相當普遍的問題最小化「變形」 - 我不期望一個完整的解決方案。任何指向相關論文\文章\圖書館\工具的指針將是有用的

來源

2013-01-12 Ophir Yoktan

天真的解決方案：檢查所有可能的交點對面。 –

我還不夠清楚 - 第一個物體應該移動\旋轉以適應容器 –

啊。那麼這很複雜！ –

這是一個可能不太理想的方法。

您可以嘗試修復1形狀的位置（在3D空間中）。將其他形狀放置在該形狀的頂部。然後創建鏈接，將形狀中的一個點連接到另一個形狀中的一個點。然後模擬鏈接拉緊時發生的情況。導致未固定的點旋轉並平移，直到穩定。

如果擬合足夠鬆散，則只能使用3個鏈接（3D的最小數量的鏈接）並嘗試每種可能的組合。然而，爲了更緊密的配合，你需要更多的鏈接，可能足以將它們放置在形狀最少的點上。這意味着你需要一些方法來確定如何放置鏈接，這不是微不足道的。

來源

2013-01-13 00:07:18 Nuclearman

你假設我知道對象中的哪個點應該靠近容器中的特定點 –

這就是爲什麼它不太理想，因爲確定並不容易，所以爲什麼你需要嘗試每個有限的組合。我描述的兩種方法（第二種使用小點的所有點）需要O（N^3）組合加上所有模擬所需的任何組合，並且會發現合適的是「鬆散」（想象裏面的方塊的八角形）或「緊」（想象一個稍大的正方形內的方形），但可能無法處理之間的事情。雖然，我認爲我可能低估了緊配合算法，因爲它本身可能就足夠了。 – Nuclearman

然後，如果你有100,000+點，O（N^3）或O（N^2）（裸露的最小緊配合），可能不實際。在這種情況下，希望有人知道更好的方法。 – Nuclearman

這似乎是一個相當難的問題。可能的方法是採取一些啓發式的方式來建議變革，而檢查是否是好的方法。如果變換隻將對象略微移出內部（例如在一個部分），而不是略微調整變換並測試它。如果對象是「很多」（例如，在兩側相同/所有軸上），則會比創建新的啓發式猜測。

只是啓發式的一般想法。對具有相同像素大小的對象進行光柵化。它可以是對象體積的八叉樹。在像素之間建立連接圖。檢查圖之間的子圖同構。如果有一個比該位置更適合測試的子圖。

此方法還支持90deg旋轉（s）。

即使在圖表上也可以完成一些測試。如果一個子圖的所有體積鄰居都處於較大的圖形中，則該對象處於較大的圖形中。

一般而言，這是「精煉」的邊界框方法。

來源

2013-01-13 13:21:04 Ante

另一種解決方案是在兩個物體上投影相同數量的點並在點集上進行最小二乘擬合。點集可能不會被排序爲相同，因此在最小二乘擬合與點的重新排序之間進行迭代，以使兩個對象上的點接近相同的順序。這個方程式的發展有很多代數，但概念上並不複雜。

來源

2014-02-03 19:24:50 JimR

考慮目標對象中的一個多邊形（三角形）。對於這個多邊形，在其他幾何體（源）中找到等效多邊形，即。邊的長度，邊之間的角度，面積都應該是相同的。如果只有一個匹配，則找到剛性變換矩陣，即改變頂點的方式：X' = M*X。由於X'和X對匹配多邊形上的所有點都是已知的，所以這應該可以用線性代數來實現。

如果要在多邊形的頂點之間進行一對一映射，以相同順序遍歷多邊形的邊，並創建一個查找表，將每個頂點映射到另一個頂點。如果你有一個你的3d對象的half edge data structure，這將很大程度上簡化這個過程。

如果您發現多個匹配的多邊形，請從兩個點遍歷源多邊形，並使其相鄰多邊形與目標多邊形保持匹配。繼續，直到其中一箇中斷，之後您可以執行與單匹配版本相同的步驟。

有更嚴重的解決方案，其中列出here，但我認爲上述方法也可以。

來源

2014-02-03 23:08:25

如何查找3D對象是否適合其他3D對象（容器）？

回答

相關問題