I Math per il rilevamento di collisioni 2D tra un OBB e un cerchio

Question

Sto creando un gioco 2D e voglio testare la collisione tra un OBB (Oriented Bounding Box) e un Circle. Non sono sicuro della matematica e del codice per farlo. Sto creando il gioco in C++ e opengl.

Answer 1

Poiché entrambe le forme sono convesse, è possibile utilizzare Separating Axis Theorem. Ecco a tutorial su come implementare un algoritmo per farlo.

In sostanza, si tenta di trovare se è possibile mettere una linea da qualche parte tra le due forme e se non si riesce a trovarne una, allora si sa che si scontrano.

Riferimenti e risposta generale presi da this question.

Answer 2

Ecco cosa farei, in pseudocodice:

function does_line_go_through_circle (original_line, circle_centerpoint, radius): 
    original_slope = get_slope_of_line (original_line) 
    perpendicular_slope = 1/original_slope 
    perpendicular_line = create_line_with_slope_through_point (perpendicular_slope, circle_centerpoint) 
    intersect_point = intersection_of_infinite_lines (perpendicular_line, original_line) 
    if point_is_on_line (intersect_point, original_line): 
     finite_line_along_radius = create_finite_line_between_points (circle_centerpoint, intersect_point) 
     if length_of_line (finite_line_along_radius) < length_of_line (radius): 
      return true 
     end 
    end 
    return false 
end 

function does_box_intersect_with_circle (bounding_box, circle): 
    for each side in bounding_box: 
     if does_line_go_through_circle (side, circle.center, circle.radius): 
      return true 
     end 
    end 
    return false 
end 

tenere a mente, io sono un po 'arrugginito su questa roba, potrei sbagliarmi.

In ogni caso, dovrebbe essere banale implementarlo in C++.

Answer 3

Divideremo il rettangolo in 4 linee finite. Possiamo costruire l'equazione linea ax + by + c = 0 collega i punti (x1, y1) e (x2, y2) come segue:

mx - y + c = 0 

dove m = (y2-y1)/(x2-x1)

Shortest (perpendicolare) distanza dalla linea ax + by + c = 0 ad un punto (xc, yc) è dato dall'espressione:

d = (a*xc + b*yc + c)/sqrt(a*a + b*b) 

o d = (m*xc - yc + c)/sqrt(m*m + 1) secondo la suddetta equazione

Per le linee infinite, è possibile verificare se 'd' è inferiore al raggio del cerchio. Ma per le linee finite, dovresti anche assicurarti che il punto di contatto sia all'interno della linea.

Ora m = tan (angolo). Si può avere

cos = 1/sqrt(m*m + 1); sin = m/sqrt(m*m + 1) 

Quindi è possibile calcolare il punto di contatto come

xp = xc + d*cos; yp = yc + d*sin 

E per verificare se (xp, yp) si trova tra i punti di collegamento di linea, si può fare un semplice controllo da

if(x1 < xp < x2 && y1 < yp < y2) 
    return true 

a seconda di quale è maggiore tra x1 x2 e y1 y2.

È possibile ripetere lo stesso algoritmo per tutte e quattro le linee di un rettangolo passando i punti.

Per favore correggimi se sbaglio da qualche parte.