我正在制作一个物理引擎，我正在使用GJK算法。现在我已经根据这篇博客文章写了它，下面是我的代码：
class CollManager:
@staticmethod
def supportPoint(a, b, direction):
return a.supportPoint(direction) -
b.supportPoint(-direction)
@staticmethod
def nextSimplex(args):
length = len(args[0])
if length == 2:
return CollManager.lineSimplex(args)
if length == 3:
return CollManager.triSimplex(args)
if length == 4:
return CollManager.tetraSimplex(args)
return False
@staticmethod
def lineSimplex(args):
a, b = args[0]
ab = b - a
ao = -a
if ab.dot(ao) > 0:
args[1] = ab.cross(ao).cross(ab)
else:
args[0] = [a]
args[1] = ao
@staticmethod
def triSimplex(args):
a, b, c = args[0]
ab = b - a
ac = c - a
ao = -a
abc = ab.cross(ac)
if abc.cross(ac).dot(ao) > 0:
if ac.dot(ao) > 0:
args[0] = [a, c]
args[1] = ac.cross(ao).cross(ac)
else:
args[0] = [a, b]
return CollManager.lineSimplex(args)
elif ab.cross(abc).dot(ao) > 0:
args[0] = [a, b]
return CollManager.lineSimplex(args)
else:
if abc.dot(ao) > 0:
args[1] = abc
else:
args[0] = [a, c, b]
args[1] = -abc
return False
@staticmethod
def tetraSimplex(args):
a, b, c, d = args[0]
ab = b - a
ac = c - a
ad = d - a
ao = -a
abc = ab.cross(ac)
acd = ac.cross(ad)
adb = ad.cross(ab)
if abc.dot(ao) > 0:
args[0] = [a, b, c]
return CollManager.triSimplex(args)
if acd.dot(ao) > 0:
args[0] = [a, c, d]
return CollManager.triSimplex(args)
if adb.dot(ao) > 0:
args[0] = [a, d, b]
return CollManager.triSimplex(args)
return True
@staticmethod
def gjk(a, b):
ab = a.pos - b.pos
c = Vector3(ab.z, ab.z, -ab.x - ab.y)
if c == Vector3.zero():
c = Vector3(-ab.y - ab.z, ab.x, ab.x)
support = CollManager.supportPoint(a, b, ab.cross(c))
points = [support]
direction = -support
while True:
support = CollManager.supportPoint(a, b, direction)
if support.dot(direction) <= 0:
return None
points.insert(0, support)
args = [points, direction]
if CollManager.nextSimplex(args):
return args[0]
points, direction = args
我已经检查了支撑点函数是否按预期工作，因为我已经计算出了它背后的数学。我所做的是创建了两个立方体，边长都为2，位置分别为(0，0，0(和(1，0，O(。计算的第一个方向是Vector3(0, 1, 0)，因此单纯形上的第一个点是Vector3(1, -2, 0)。从另一个方向看，第二点正好相反，Vector3(-1, 2, 0)。这就产生了一个问题，因为创建的下一个方向使用了两者的叉积，即Vector3(0, 0, 0)。显然，没有矢量与此方向相同，因此线路if support.dot(direction) <= 0:发生故障。
但是，当x为-1、0或1时，会发生这种情况，但在-2和2时不会发生这种情况。
如何确保在单纯形上找到的第二个点与第一个点不完全相反，从而使支票提前返回？
最小可复制示例(使用完全相同的代码(：
# main.py
from vector3 import Vector3
import math
class BoxCollider:
def __init__(self, position, side_length):
self.pos = position
self.side_length = side_length
def supportPoint(self, direction):
maxDistance = -math.inf
min, max = self.pos - self.side_length // 2, self.pos + self.side_length // 2
for x in (min.x, max.x):
for y in (min.y, max.y):
for z in (min.z, max.z):
distance = Vector3(x, y, z).dot(direction)
if distance > maxDistance:
maxDistance = distance
maxVertex = Vector3(x, y, z)
return maxVertex
def supportPoint(a, b, direction):
return a.supportPoint(direction) -
b.supportPoint(-direction)
def nextSimplex(args):
length = len(args[0])
if length == 2:
return lineSimplex(args)
if length == 3:
return triSimplex(args)
if length == 4:
return tetraSimplex(args)
return False
def lineSimplex(args):
a, b = args[0]
ab = b - a
ao = -a
if ab.dot(ao) > 0:
args[1] = ab.cross(ao).cross(ab)
else:
args[0] = [a]
args[1] = ao
def triSimplex(args):
a, b, c = args[0]
ab = b - a
ac = c - a
ao = -a
abc = ab.cross(ac)
if abc.cross(ac).dot(ao) > 0:
if ac.dot(ao) > 0:
args[0] = [a, c]
args[1] = ac.cross(ao).cross(ac)
else:
args[0] = [a, b]
return lineSimplex(args)
elif ab.cross(abc).dot(ao) > 0:
args[0] = [a, b]
return lineSimplex(args)
else:
if abc.dot(ao) > 0:
args[1] = abc
else:
args[0] = [a, c, b]
args[1] = -abc
return False
def tetraSimplex(args):
a, b, c, d = args[0]
ab = b - a
ac = c - a
ad = d - a
ao = -a
abc = ab.cross(ac)
acd = ac.cross(ad)
adb = ad.cross(ab)
if abc.dot(ao) > 0:
args[0] = [a, b, c]
return triSimplex(args)
if acd.dot(ao) > 0:
args[0] = [a, c, d]
return triSimplex(args)
if adb.dot(ao) > 0:
args[0] = [a, d, b]
return triSimplex(args)
return True
def gjk(a, b):
ab = a.pos - b.pos
c = Vector3(ab.z, ab.z, -ab.x - ab.y)
if c == Vector3.zero():
c = Vector3(-ab.y - ab.z, ab.x, ab.x)
support = supportPoint(a, b, ab.cross(c))
points = [support]
direction = -support
while True:
support = supportPoint(a, b, direction)
if support.dot(direction) <= 0:
return None
points.insert(0, support)
args = [points, direction]
if nextSimplex(args):
return args[0]
points, direction = args
a = BoxCollider(Vector3(0, 0, 0), 2)
b = BoxCollider(Vector3(1, 0, 0), 2)
print(gjk(a, b))
我的vector3.py文件太长了，这里有一个同样有效的文件：https://github.com/pyunity/pyunity/blob/07fed7871ace0c1b1b3cf8051d08d6677fe18209/pyunity/vector3.py
修复方法是将ab.cross(ao).cross(ab)更改为仅ab / 2，因为这会给出从AB中点到原点的向量，并且比两个叉积便宜得多。