1

我有一个基于分离轴定理（SAT）的凸二维多边形与凸二维多边形碰撞测试。

我的问题是：是否有可能在不以某种形式纠正 MTV 方向的情况下实现这个算法？（通过注意缠绕顺序，朝外的法线或我可能弄错的其他细节）。

SAT 产生一个最小平移向量。我发现很难让 MTV 的方向正确，因为它大约有一半时间指向错误的方向（如果将多边形 A 和 B 传递给碰撞检测功能，则 MTV 应该始终用于 A）。它只有在添加检查两个投影之间重叠方向的代码后才开始正常工作，而不仅仅是两个投影重叠。

pub struct Projection {
    min: f64,
    max: f64,
}

impl Projection {
   // omitted some other functions not relevant to the question

   /// Calculates the direction of overlap between two projections.
   /// In case of no overlap, None is returned
   pub fn overlap(&self, other: &Self) -> Option<f64> {
        let sum = (self.max - self.min) + (other.max - other.min);    
        let extent = self.max.max(other.max) - self.min.min(other.min);
        if (sum - extent).is_sign_negative() {
            None
        }
        else if self.max - other.min < other.max - self.min {
            Some(self.max - other.min)
        } else { 
            Some(self.min - other.max)
        }
    }
}

但是我感觉我可能错过了一个重要的细节，因为我读过的关于 SAT 的各种文章和评论都提到了面向外的多边形法线，而 MTV 方向的话题却很少受到关注（好像它很简单，而对我来说这是最难的部分）。

我的 SAT 实现的核心是这个函数，它被调用了两次。第二次调用该函数时参数的顺序颠倒了，这会影响 MTV 方向，但我很清楚这一点。

fn find_mtv(a: &Convex, b: &Convex) -> Option<MtvComponents> {   
    let mut comps = MtvComponents::new();
    for axis in a.iter_normals().map(Vector::normalize) {
        let proj_a = Projection::new(a.iter_vertices(), axis);
        let proj_b = Projection::new(b.iter_vertices(), axis);
        if let Some(overlap) = proj_a.overlap(&proj_b) {
            comps.store_min(overlap, axis);
        } else {
            return None
        }
    }
    Some(comps)
}
4

0 回答 0