Можно ли упростить эту реализацию теоремы о разделительной оси?

У меня есть рабочий тест столкновения выпуклого 2-го многоугольника против выпуклого 2-го многоугольника, основанный на теореме о разделении осей (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)
}

0 ответов

Другие вопросы по тегам