球扇形边界框（锥球相交）

Question

给定一个球形段（它的半径、方向和角度），我如何以最简单的方式计算它的轴对齐边界框？

请注意，我对任意方向的片段感兴趣，而框必须与轴对齐。紧密定向的边界框计算起来很简单。

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

Answer 1

为简单起见，假设我们平移和缩放坐标系，使中心位于 (0, ..., 0)，半径为 1。令 u是线段的端点（因此 ‖u‖² = 1）并设弧度角为 θ。蓝色扇区是所有点 v 使得‖v‖² ≤ 1 且 u·v ≥ ‖u‖ ‖v‖ cos θ = ‖v‖ 余弦θ。要在 d 维度中找到 axis-aligned 边界框，我们需要找到 2d 个向量 v minimize/maximize 每个单独的坐标，即给定一个向量 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，因为 objective 是线性的，其他点位于这些点的凸组合上。让我们关注后一种情况。

maximize e·v
subject to
‖v‖² = 1
u·v ≥ cos θ

其次，e和u所跨越的space存在最优解。给定任何最优解，我们可以在不增加范数或用 e 或 u[=66= 改变点积的情况下将正交投影放入 space ], 所以投影也是可行和最优的。

因此我们根据系数 α 和 β 重写问题，让 v = αe + β你.

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 θ

现在我们进行案例分析。忽略线性约束，objective 最多为 1，因此解 α = 1 和 β = 0（即 v = e) 是最优的。只有当 e·u ≥ cos θ.
时，此解才可行
如果此解不可行，则线性约束必须紧：α(e·u) + β = cos θ , 或 β = cos θ − α(e·u)。然后我们可以代入，求解得到的二次方程，并取得分更好的解（除非他们都得分为负，在这种情况下界限为 0）。

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

球扇形边界框（锥球相交）

Bounding box of spherical sector (cone-sphere intersection)

algorithm

geometry

intersection

bounding-box