Can I simplify this implementation of the separating axis theorem?

727 views Asked by At

I have a working convex 2d polygon vs convex 2d polygon collision test based on the separating axes theorem (SAT).

My question is: Is it possibly to implement this algorithm without correcting the direction of the MTV in some form? (by paying attention to winding order, outward facing normals or other details that I might have gotten wrong).

The SAT produces a minimum translation vector. I found it difficult to get the direction of the MTV right, as it was pointing in the wrong direction about half of the time (if polygon A and B are passed to the collision detection function, the MTV should always be for A). It started working correctly only after adding code that checks for the direction of overlap between two projections, not merely if two projections overlap.

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)
        }
    }
}

However I have the feeling that I may have missed an important detail because various articles and comments on SAT that I've read mention outward facing polygon normals, and the topic of the MTV direction is given relatively little attention (as if it was trivially easy, while for me it was the hardest part).

The core of my SAT implementation is this function, which is called twice. The second time the function is called with order of arguments reversed, which affects MTV direction but I'm well aware of this.

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

There are 0 answers