網格網格交叉點

我正在尋找一個庫或描述如何確定一個三角形網格與另一個相交的紙張。網格網格交叉點

有趣的是，我來了空。如果有一些方法可以在CGAL中完成，它就會避開我。

看起來似乎應該是可能的，因爲三角形相交是可能的，因爲每個網格包含有限數量的三角形。但是我認爲一定有更好的辦法來做到這一點，而不是明顯的O（n * m）方法，其中一個網格有n個三角形，另一個網格有m個三角形。

2011-11-01 Doug McClean

的「明顯」的做法會給假陰性，如果網格的一個完全是另一內。 – cmannett85

我感興趣的網格之間的碰撞作爲零厚度表面。我看到如果我感興趣的解釋爲多面體的網格之間的碰撞會如何發生。 –

[另請參閱三角形 - 三角形]（http://www.realtimerendering.com/intersections.html） – bobobobo

我覺得您搜索的詞是覆蓋。例如，這裏是一個網頁Surface Mesh Overlay。該網站有一個簡短的參考書目，全部由相同的作者。這是另一篇論文：「Overlay mesh construction using interleaved spanning trees，」 INFOCOM 2004：IEEE計算機與通信學會第23屆年度聯合會議。另請參閱GIS SE問題「Performing Overlay of Two Triangulated Irregular Networks (TIN)」。

來源

2011-11-02 01:09:59

本書Real-Time Collision Detection對實現這樣的算法有一些很好的建議。基本方法是使用空間分區或邊界體積來減少需要執行的三邊相交測試的數量。

有一些很好的學術軟件包可以解決這個問題，包括Proximity Query Package和GAMMA research group at University of North Carolina的其他工作，SWIFT，I-COLLIDE和RAPID都是衆所周知的。檢查這些庫上的許可證是否可以接受。

開放動態引擎（ODE）是一個物理引擎，它包含大量相交原語的優化實現。您可以查看他們的wiki上的三角形 - 三角形相交測試的文檔。

雖然它不是你尋找什麼，我認爲，這也可能與CGAL - Tree of Triangles, for Intersection and Distance Queries

來源

2011-11-02 04:54:01

偉大的書籍推薦 – Fattie

我們通常做使用CGAL的方法是用CGAL::box_intersection_d。

您可以通過將此example與此one混合。

來源

2011-11-02 07:19:18 sloriot

考試4和5對初學者非常有用。但是，如何創建AABB的樹形結構以加速整個過程尚不清楚。此外，這些例子對於自相交情況更爲明顯。在兩個單獨的網格的情況下，它不是很清楚（我猜想把所有的三角形/方塊扔在一個矢量中並不是最優的）。以上任何建議？ –

您需要爲每個網格使用一個矢量並使用[CGAL :: box_intersection_d（）]（http://doc.cgal.org/latest/Box_intersection_d/group__PkgBoxIntersectionD__box__intersection__d.html）。 – sloriot

要添加到其他答案，還有技術涉及三維Minkowski和凸多面體 - 凹多面體可以分解爲凸部分。檢出this。

來源

2011-11-02 07:27:03 cmannett85

在libigl，我們結束CGAL的CGAL::box_intersection_d到相交頂點V網狀並面對F與頂點U另一個網和麪向G，存儲對相交面作爲行中IF：

igl::intersect_other(V,F,U,G,false,IF);

這將忽略自交。爲了完整起見，我會提到，我們也支持自相交在一個單獨的功能：

igl::self_intersect(V,F,...,IF);

來源

2014-04-26 02:17:43

網格網格交叉點

回答

相關問題