無法實現GJK距離算法

我試圖從頭開始設計我自己的物理引擎，以及矢量/矩陣庫。到目前爲止，一切都很好，直到我試圖在我的庫中實現碰撞檢測。首先使用SAT，對於檢測非常有效，但我也希望找到物體之間的距離。然後我試着實現GJK距離算法，只是爲了看看我能否找到原點和多邊形之間的距離。但它只是不工作，由我實現的算法感知的最小距離是多邊形的頂點之一：無法實現GJK距離算法

我知道我從頭其他圖書館，但我肯定他們正在工作。不管怎麼說，這裏的地方我已經實現了GJK代碼：

#objectL[0] is a hexagon 
    v = objectL[0].nodes[0] 
    W = [] 
    u = 0 
    close_enough = False 
    while not close_enough and v != Vector(0,0): 
     w = objectL[0].support(-v) 
     d = v*w/abs(v) #*:dot product abs:magnitude 
     u = max(u,d) 
     close_enough = abs(v) - u <= 0.0001 
     if not close_enough: 
      W.append(w) 
      while len(W)>2: 
       del W[0] 
      v = Vector(0,0).vectorToLine(*W) #distance from the origin to the simplex 
              #formed by W

而現在的支持方法：

def support(self,axis): 
    maxP = self.nodes[0]*axis #dot product of first vertex with the axis 
    n = self.nodes[0] 
    for node in self.nodes[1:]: 
     p = node*axis 
     if p>maxP: 
      maxP = p 
      n = node 
    return node

這些都是代碼片段，我認爲是錯誤所在，但我找不到它。我從here複製的GJK算法。謝謝！

編輯： Here是我的項目（在pygame中實現）

來源

2016-12-05 Henke

有趣的算法，從來沒有聽說過它，但似乎非常有用！你有沒有看過[this]（http://www.dyn4j.org/2010/04/gjk-distance-closest-points/）鏈接？看起來他們在代碼中實現了距離部分的算法，儘管它不在python中。 – CodeSurgeon

好了，發現的錯誤。哪些不是在實施，而是在我之前提出的功能：支持，返回node而不是n和vectorToLine函數返回一個不正確的向量（負值）。

也爲那些從現在開始閱讀這篇文章裏，並試圖實現這個算法，請注意，我只是改變了while len(W)>2部分：

   while len(W)>2: 
       maxD = 0 
       for w in W: 
        if abs(w)>maxD: 
         maxD = w 
       W.remove(maxD)

從而消除了單純的最遠點/三角形，所以它得到兩個最接近的點（到原點）來繼續算法。

來源

2016-12-06 01:44:26 Henke

無法實現GJK距離算法

回答

相關問題