2013-04-10 82 views
2

重點在於查找時間(交點開始時),儘管位置也很重要。邊界框(不是軸對齊)具有位置,旋轉,速度和角速度(旋轉速率)。沒有加速度,這應該真的簡化了事情......如果有必要的話,我也可以刪除角速度分量。無論是連續函數還是迭代函數都可以工作,但除非迭代函數主動向解(或缺少)求解,否則它可能會太慢。查找時間和兩個移動的旋轉邊界框的交點位置

我看着the SAT,但它似乎並沒有建立起來,以找到運動物體的實際碰撞時間。它似乎只適用於不移動的快照,並且設計用於處理比矩形更復雜的對象,所以它實際上似乎不適合這個問題。

我已經考慮過可能畫出每個8點的軌跡,然後以某種方式有一個功能,如果一個點是在或不在其他形狀,並獲得發生的時間範圍,但我很漂亮失去了如何去做這件事。一個很好的特點是它完全隨時間運行,並忽略了離散「步驟」的想法,但它也讓我覺得這是一種低效率的方法。

不用擔心廣泛的階段(確定是否值得看看這兩個邊界框是否可能重疊),我已經解決了這個問題。

回答

2

找到一個精確的碰撞時間本質上是一個非線性的根發現問題。這意味着您最終需要一種迭代方法來確定最終碰撞時間 - 但設計碰撞求解器時的巧妙之處在於避免在實際上不需要時解決根問題......

SAT是一個定理,而不是算法:它可以用來指導碰撞求解器的設計,但它本身不是一個。簡而言之,它表示,如果您可以證明存在分離軸,則這些對象沒有發生碰撞。相反,如果你能證明沒有這樣的軸,那麼當前的對象重疊。正如你指出的那樣,你可以直接或多或少地使用這個原則來設計一個二進制的「是/否」查詢,以確定給定位置上的兩個對象是否重疊。

與碰撞求解器的區別在於問題是動態的,或動力學的:對象位置是時間的函數。解決此問題的一種方法是從有效的「是/否」碰撞測試開始,將所有不平等視爲時間的函數,並使用根查找方法在此基礎上查找實際碰撞時間。

已發表的學術文獻中有多種現有方法。我推薦一些圖書館研究:最好的選擇可能取決於你的應用程序的細節。

0

首先,而不是兩個矩形的思維與速度(x1, y1)(x2, y2)分別移動,可以解決這些問題的一個(其速度設置爲(0, 0)),並認爲另一個與速度(x2 - x1, y2 - y1)移動。

這樣,情況看起來像一個矩形是不可移動的,另一個矩形是經過的,可能會碰到第一個矩形。

  • 假設你沒有任何角速度

enter image description here

不難看出,可以然後相交4個軌跡的第二矩形的(它們是從不同的角落開始射線在(x2 - x1, y2 - y1)方向上的邊界框的邊界),第一個矩形的四邊靜止。然後,您也必須執行相同的操作 - 找到第一個矩形的相反方向 - (-(x2 - x1), -(y2 - y1))與第二個矩形的4個邊的交點。選擇你找到的所有交點之間的最小距離(可能有0-8個),你就完成了。

不要忘了考慮很多特殊情況 - 當兩個矩形的邊是平行的,當有一個在所有等

注意沒有交集,這一切都是在O(1)時間內完成,但計算是相當複雜 - 光線和線段的32個交點。

  • 如果你真的希望你的矩形與一些的速度旋轉,我會建議考慮什麼@comingstorm說:這不過是找到一種非線性方程的根,的問題,即使在這種情況下,如果你的矩形的角速度是有限的,你可以將任務分成一系列的子任務,但我想這只是解決非線性問題的可能方法之一。