Как определить, перекрываются ли два прямоугольника (под углом)

Я хочу определить, перекрываются ли два прямоугольника (не пересекаются). Я знаю, как это сделать для прямоугольников, выровненных по оси, но в этом случае у меня есть один прямоугольник, который не всегда выровнен по оси (иначе говоря, повернут в центре). В этом сообщении показано, как для вычисления двух пересекающихся прямоугольников, но он не классифицирует один прямоугольник внутри другого, как показано на этом рисунке потому что они перекрываются, а не пересекаются.

В моем случае один из прямоугольников выровнен по оси (черный прямоугольник), а другой вращается (красный прямоугольник), что может упростить задачу.

Думаю, мне понадобится несколько дел, чтобы определить, пересекаются ли они. Первый простой случай - проверить, не находится ли какая-либо из красных вершин внутри черного ящика. Затем я могу проверить, пересекаются ли какие-либо из красных / черных краев. Я не уверен, как я могу охватить случай, показанный выше, и есть ли более простой способ сделать это.

Дополнительные сведения: это для моего графического программного клиппера (в данном случае нельзя использовать аппаратное отсечение), где черный ящик - это мое окно / область просмотра, красный ящик - это «спрайт», а все, что находится за черным ящиком, обрезано / не- рендеринг Я использую ортоганальную / 2D проекцию. В конце у меня будет две функции: одна для определения того, находится ли спрайт за пределами окна / области просмотра (что я задаю в этом вопросе), а позже я создам функцию для обрезки спрайта внутри окна / область просмотра с использованием алгоритма Сазерленда – Ходжмана.

РЕДАКТИРОВАТЬ:

В этом сообщении, как правило, описывается, как выполнять SAT, но это не так. вдаваться в подробности. Как создать нормали? "Углы" - это координаты экрана или расстояние от центра фигуры? Я пробовал адаптировать их код для своих целей, но не могу понять, как выполнить тест SAT со списком вершин (экран x и y) для каждой формы / прямоугольника.


clip shapes overlap graphics angle
person Protofall    schedule 10.11.2019    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Обычно это называется тестом на пересечение AABB-OBB. (выровненная по оси ограничительная рамка и ориентированная ограничительная рамка). Если одна ограничивающая рамка полностью находится внутри другой, это все равно считается «пересечением».

Чтобы решить эту проблему, используйте теорему о разделяющей оси. Если AABB и OBB не перекрываются, то они должны иметь по крайней мере одну разделяющую ось, параллельную одной из их сторон.

Для теста пересечения OBB-OBB вы проецируете две формы на 8 разных линий (по одной для каждого края каждого прямоугольника) и выполняете простой одномерный тест на перекрытие для каждой проекции.

Для AABB-OBB это в основном то же самое, но сокращается до 4 проекций, поскольку четыре пары ребер всегда параллельны.

Взгляните на следующее объяснение OBB-OBB:

https://gamedev.stackexchange.com/questions/25397/obb-vs-obb-collision-detection

person prideout    schedule 12.11.2019
comment
Я прочитал рекомендуемый ответ. Я смутно понимаю, что происходит, но недостаточно, чтобы правильно это понять. И в коде есть несколько дыр с небольшими пояснениями (Что такое HUGE? Max int или что-то в этом роде?). Я посмотрю на другие объяснения SAT, но спасибо, что указали мне правильный ответ :) - person Protofall; 16.11.2019
comment
У меня большая часть работы работает, но я не могу следовать их логике проецирования двух форм на линии. Я понимаю, что линия нормальная, но как они проецируют на нее вершины, не имеет смысла. Они производят одно скалярное произведение на вершину, а затем сортируют его в список? Я много гуглил эту часть, и единственный другой ответ, который я смог найти, был намного сложнее. Вы знаете, что там происходит? - person Protofall; 17.11.2019

arrow_upward
0
arrow_downward

Прежде всего я хотел бы поблагодарить пользователя prideout за то, что он указал мне в правильном направлении. Его заметки, особенно необходимые только для 4 нормалей, помогли мне оптимизировать мой код. Как ни странно, код в предоставленной ссылке, похоже, не работает раздавленные вершины фигур перекрывались). Я нашел этот полезный пример на C ++, который указал мне правильное направление, и теперь мой код отлично работает .

Вот моя функция обнаружения перекрытия AABB-OBB + функция SAT (используемый язык - обработка, основанная на Java).

// True if overlap, False if they don't
boolean seperating_axis_theorem(float[] x1, float[] y1, float[] x2, float[] y2, float[] normal){
  float[] range = new float[4];  //minAlong1, maxAlong1, minAlong2, maxAlong2
  range[0] = Float.MAX_VALUE;
  range[1] = -Float.MAX_VALUE;
  range[2] = Float.MAX_VALUE;
  range[3] = -Float.MAX_VALUE;
  
  // Dot is projecting the points onto the seperating axis and then we get the max and min
  float dotVal;
  for(int i = 0; i < 4; i++){
    dotVal = dot(x1[i], y1[i], normal[0], normal[1]);
    if(dotVal < range[0]){range[0] = dotVal;}
    if(dotVal > range[1]){range[1] = dotVal;}
    
    dotVal = dot(x2[i], y2[i], normal[0], normal[1]);
    if(dotVal < range[2]){range[2] = dotVal;}
    if(dotVal > range[3]){range[3] = dotVal;}
  }
  
  if(range[1] < range[2] || range[0] > range[3]){
    return false;
  }
  
  return true;
}

// True if two shapes overlap, False otherwise
Boolean AABB_OBB_Overlap(float[] OBB_X, float[] OBB_Y, float[] AABB_X, float[] AABB_Y){
  
  // Checking the camera's normals, simplified since we know its axis aligned so no unit vector calculations needed
  float[] range = get_range(OBB_X);  // Returns min and max of array
  if(range[1] < AABB_X[0] || range[0] > AABB_X[1]){
    return false;
  }
  range = get_range(OBB_Y);
  if(range[1] < AABB_Y[0] || range[0] > AABB_Y[2]){
    return false;
  }
  
  // Checking the sprite's normals
  float[] normal1 = unit_vector(OBB_X[1] - OBB_X[0], OBB_Y[1] - OBB_Y[0]);  // Top side
  float[] normal2 = unit_vector(OBB_X[2] - OBB_X[0], OBB_Y[2] - OBB_Y[0]);  // Left side
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal1)){
    return false;
  }
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal2)){
    return false;
  }
  
  // They overlap
  return true;
}
person Protofall    schedule 18.10.2020