Учитывая сферический сегмент (его радиус, направление и угол), как мне проще всего вычислить его выровненную по оси ограничивающую рамку?
Обратите внимание, что меня интересует произвольно ориентированный сегмент, при этом прямоугольник должен быть выровнен по оси. Плотно ориентированный ограничивающий прямоугольник вычислить несложно.
Задачу можно упростить до ограничивающего прямоугольника сферической крышки, но я не смог найти и для этого алгоритма.
Для простоты предположим, что мы перемещаем и масштабируем систему координат так, что центр находится в (0, ..., 0), а радиус равен 1. Пусть u будет конечной точкой сегмента (так что ‖ u ‖² = 1) и пусть угол в радианах равен θ. Синий сектор - это все точки v такие, что ‖ v ‖² ≤ 1 и u · v ≥ ‖ < strong> u ‖ ‖ v ‖ cos θ = ‖ v ‖ cos θ. Чтобы найти выровненную по оси ограничивающую рамку в измерениях d, нам нужно найти 2 d вектора v, которые минимизируют / максимизируют каждую отдельную координату, т. е. задан вектор e, такой что либо + e, либо - e принадлежит осевому базису (например, e = (0, −1, 0, ..., 0)) мы хотим максимизировать e · v с учетом ограничений на v .
maximize e·v
subject to
‖v‖² ≤ 1
u·v ≥ ‖v‖ cos θ
Сначала заметим, что без ограничения общности v ‖ = 0 или ‖ v ‖ = 1, так как цель линейна, а другие точки лежат на выпуклой комбинации эти. Остановимся на последнем случае.
maximize e·v
subject to
‖v‖² = 1
u·v ≥ cos θ
Во-вторых, существует оптимальное решение, которое находится в пространстве, ограниченном e и u. При любом оптимальном решении мы можем взять ортогональную проекцию в это пространство, не увеличивая ее норму или не изменяя скалярное произведение с помощью e или u, поэтому проекция также возможна и оптимальна. .
Поэтому мы перепишем задачу в терминах коэффициентов α и β, положив v = α e + β u.
maximize e·(αe + βu)
subject to
‖αe + βu‖² = 1
u·(αe + βu) ≥ cos θ
Давайте расширим продукты и воспользуемся тем фактом, что ‖ e ‖² = ‖ u ‖² = 1.
maximize α + β(e·u)
subject to
α² + 2αβ(e·u) + β² = 1
α(e·u) + β ≥ cos θ
Теперь у нас есть анализ случая. Игнорируя линейное ограничение, цель не больше 1, следовательно, решение α = 1 и β = 0 (т.е. v = e) является оптимальным. Это решение возможно, только если e · u ≥ cos θ.
Если это решение невозможно, линейное ограничение должно быть жестким: α (e · u) + β = cos θ или β = cos θ - α ( e · u). Затем мы можем выполнить замену, решить полученное квадратное уравнение и выбрать решение, которое имеет более высокий балл (если они оба не имеют отрицательных результатов, и в этом случае оценка равна 0).
Следуя ответу Дэвида, я реализовал этот алгоритм, который, похоже, работает нормально:
Box ComputeSphericalSegmentBoundingBox( const Vec3& u, const float angle )
{
const float cosAngle = cosf( angle ); // cos θ
const auto solveAxis = [&] ( const Vec3& e )
{
const float eu = Vec3::Dot( e, u ); // e·u
if ( eu >= cosAngle )
{
return 1.0f;
}
// solve for a² + 2a(cosθ - a(e·u))(e·u) + (cosθ - a(e·u))² = 1
const float det = ( cosAngle * cosAngle - 1.0f ) / ( eu * eu - 1.0f );
if ( det >= 0.0f )
{
const float a = sqrtf( det );
// maximize x = a + b(e·u)
const float x0 = ( cosAngle - a * eu ) * eu + a;
const float x1 = ( cosAngle + a * eu ) * eu - a;
return Clamp( max( x0, x1 ), 0.0f, 1.0f );
}
return 0.0f;
};
Vec3 boxMin
{
min(0.0f, -solveAxis( Vec3(-1,0,0) ) ),
min(0.0f, -solveAxis( Vec3(0,-1,0) ) ),
min(0.0f, -solveAxis( Vec3(0,0,-1) ) )
};
Vec3 boxMax
{
max(0.0f, solveAxis( Vec3(1,0,0) ) ),
max(0.0f, solveAxis( Vec3(0,1,0) ) ),
max(0.0f, solveAxis( Vec3(0,0,1) ) )
};
return { boxMin, boxMax };
}
