球冠体的边界框（圆锥-球体相交）

Question

如何以最简单的方式计算球段（其半径、方向和角度）的轴对齐边界框？请注意，我感兴趣的是任意定向的部分，而框必须是轴对齐的。紧密定向的边界框易于计算。

问题可以简化为球冠的边界框，但我也找不到算法。

- Witek902

---

不清楚您需要圆锥的哪个部分，是整个包括顶部球形部分的部分，只是那个部分还是只有实际的圆锥部分？ - Makogan

@Makogan 我对整个蓝色形状感兴趣，包括球冠，而不仅仅是锥体，后者是一个简单得多的问题。 - Witek902

@Witek902 看看Cone to box collision吧，虽然它并没有回答你的问题，但如果你要在三维空间中构建基于球冠锥体的东西，这可能会对你有所帮助... - Spektre

Answer 1

为了简便，假设我们将坐标系平移和缩放，以使中心点为 (0, ..., 0)，半径为1。设u为线段的终点（因此 ‖u‖² = 1），角度为θ。蓝色扇形包含所有满足 ‖v‖² ≤ 1 且 u·v ≥ ‖u‖ ‖v‖ cos θ = ‖v‖ cos θ 的点v。要在d维中找到轴对齐的边界框，我们需要找到2d个向量v，分别最小化/最大化每个坐标，即给定一个向量e，使得+e 或 -e属于轴基（例如，e = (0, −1, 0, ..., 0)），我们希望在v的限制条件下，最大化e·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）。

- David Eisenstat

---

感谢您的快速回复和深入分析！我在另一个答案中发布了基于您解决方案的算法源代码。希望它是正确的。 - Witek902

Answer 2

参考 David 的回答，我实现了这个算法，它似乎运行良好：

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

- Witek902