Тест пересечения сферы AABB
У меня есть сфера, и я хочу знать, находятся ли мои выровненные по оси ограничивающие рамки (AABB) полностью, частично или вообще не находятся внутри сферы. Я нашел много алгоритмов, но они дают только частичные или внешние результаты. Есть указатели?
Решение
И тест пересечения, приводящий к true для хотя бы частичного пересечения и false нет пересечения подробно Вот.
Теперь вы хотите проверить, находится ли AABB полностью внутри сферы. Вы можете легко сделать это, проверив, все ли ваши точки находятся внутри сферы. Этот тест можно упростить, чтобы проверить, являются ли два противоположные вершины ААББ находятся внутри сферы. Сравнение квадрата расстояния с квадратом радиуса сферы делает этот тест очень быстрым.
Вы можете легко объединить оба теста:
- Проверьте, полностью ли содержится AABB. Если нет, проверьте, частично ли он содержится или нет.
- Или наоборот: проверьте, содержится ли AABB хотя бы частично. Если это так, проверьте, полностью ли он содержится.
В зависимости от того, как часто происходит каждый случай, один или другой может быть лучше — профилируйте свой код, если вы чувствуете потребность в скорости.
Другие решения
Вы, вероятно, уже нашли самый популярный алгоритм, чтобы определить, пересекается ли AABB с твердый сфера или нет Джим Арво, в «Графика Gems»:
dmin = 0;
for( i = 0; i < 3; i++ ) {
if( C[i] < Bmin[i] ) dmin += SQR( C[i] - Bmin[i] ); else
if( C[i] > Bmax[i] ) dmin += SQR( C[i] - Bmax[i] );
}
if( dmin <= r2 ) return TRUE;
куда Bmin хранит минимумы AABB для каждой оси, Bmax хранит максимумы AABB для каждой оси, C — координата центра сферы и r2 это квадрат радиуса. Это решение было, например, также показано в этом вопросе: Тест пересечения кубической сферы?
Как вы уже обнаружили, этот алгоритм также возвращает TRUE если AABB находится полностью внутри сферы, но вы хотите обнаружить эту ситуацию как особый случай. Один из способов сделать это — изменить то, что делает вышеуказанный алгоритм. Алгоритм работает, по существу, находя точку AABB, которая ближайший к центру сферы и суммируя квадратичные дельты координат между этой точкой и центром сферы. Если эта сумма меньше квадрата радиуса сферы, то (после теоремы Пифагора) точка AABB лежит внутри сферы. В результате AABB частично или полностью содержится внутри сферы.
Теперь предположим, что вы уже выполнили эту проверку и хотите выяснить, является ли AABB только частично или полностью содержится. Для этого давайте запустим аналогичную проверку, но не с точкой AABB, ближайшей к центру круга, а с точкой, наиболее удаленной от нее. Если расстояние этой точки от центра сферы меньше радиуса сферы, то AABB полностью содержится внутри сферы.
Как ни странно, часто цитируемый алгоритм Джима Арво уже содержит алгоритм, который делает именно это. Оригинальный код содержит проверки для «полых» или «сплошных» сфер и AABB. К сожалению, оригинальный код на http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c больше недоступен, но в интернет-архиве все еще есть: http://web.archive.org/web/20100323053111/http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c Вас в основном интересуют случаи с полой сферой. Я не знаю, хотите ли вы, чтобы ваше поле AABB было пустым или нет (разница в том, возвращает ли ваш чек значение true, когда сфера внутри поле), поэтому я буду вставлять оба случая здесь:
switch( mode )
{
case 0: /* Hollow Box and Hollow Sphere */
dmin = 0;
dmax = 0;
face = FALSE;
for( i = 0; i < n; i++ ) {
a = SQR( C[i] - Bmin[i] );
b = SQR( C[i] - Bmax[i] );
dmax += MAX( a, b );
if( C[i] < Bmin[i] ) {
face = TRUE;
dmin += a;
}
else if( C[i] > Bmax[i] ) {
face = TRUE;
dmin += b;
}
else if( MIN( a, b ) <= r2 ) face = TRUE;
}
if( face && ( dmin <= r2 ) && ( r2 <= dmax ) ) return TRUE;
break;
case 2: /* Solid Box and Hollow Sphere */
dmax = 0;
dmin = 0;
for( i = 0; i < n; i++ ) {
a = SQR( C[i] - Bmin[i] );
b = SQR( C[i] - Bmax[i] );
dmax += MAX( a, b );
if( C[i] < Bmin[i] ) dmin += a; else
if( C[i] > Bmax[i] ) dmin += b;
}
if( dmin <= r2 && r2 <= dmax ) return TRUE;
break;
Чтобы решить ваш начальный вопрос, вы бы изменили условие возврата. Если dmin меньше чем r2 но dmax больше, чем r2 тогда ваш AABB лежит на поверхности сферы (частичное пересечение). Если dmin а также dmax меньше чем r2 тогда ваш AABB полностью лежит внутри вашей сферы.
Попробуйте этот алгоритм: сфера сталкивается с AABB, если сфера лежит (или частично лежит) на inside side всех самолетов ААББ. Inside side плоскости означает полупространство, направленное к центру AABB.
Таким образом, вы должны проверить наличие пересечений между сферами и плоскостями, выровненными по осям, для каждой из 6 плоскостей AABB (xmin / xmax, ymin / ymax, zmin / zmax). Это сравнение довольно просто, если вы выдавливаете плоскость по радиусу сферы и проверяете sphere center point против extruded plane,
П.С. Я не пробовал это на практике. Этот алгоритм основан на аналогичном методе определения точки внутри треугольника (https://stackoverflow.com/a/2049593/326017)