Bounding box of spherical sector (cone-sphere intersection)

Question

Given a spherical segment (its radius, direction and angle), how do I compute its axis-aligned bounding box in a easiest way?

Note that I'm interested in arbitrarily oriented segment, while the box must be axis-aligned. Tight oriented bounding box is trivial to compute.

The problem can be simplified to a bounding box of a spherical cap, but I couldn't find algorithm for that either.

it's not clear which section of the cone you want, is it the entiretiy including the spherical section at the top, just that section or just the actual cone? — Makogan, Nov 04 '20 at 20:49
@Makogan I'm interested in the whole blue shape, including the spherical cap, not just the cone, which is much simpler problem. — Witek902, Nov 05 '20 at 21:21
@Witek902 see [Cone to box collision](https://stackoverflow.com/a/62257945/2521214) it does not answer your question but it might be interesting for you to read (in case you will build stuff on top of spherical cap cones in 3D ...) — Spektre, Nov 06 '20 at 08:43

score 3 · Accepted Answer · answered Nov 05 '20 at 01:37

For simplicity, assume that we translate and scale the coordinate system so that the center is at (0, ..., 0) and the radius is 1. Let u be the endpoint of the segment (so that ‖u‖² = 1) and let the angle in radians be θ. The blue sector is all points v such that ‖v‖² ≤ 1 and u·v ≥ ‖u‖ ‖v‖ cos θ = ‖v‖ cos θ. To find the axis-aligned bounding box in d dimensions, we need to find the 2d vectors v that minimize/maximize each individual coordinate, i.e., given a vector e such that either +e or −e belongs to the axial basis (e.g., e = (0, −1, 0, ..., 0)) we want to maximize e·v subject to the restrictions on v.

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

We observe first that without loss of generality, ‖v‖ = 0 or ‖v‖ = 1, since the objective is linear and the other points lie on a convex combination of these. Let's focus on the latter case.

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

Second, there exists an optimal solution that lies in the space spanned by e and u. Given any optimal solution, we can take the orthogonal projection into that space without increasing its norm or changing the dot product with e or u, so the projection is feasible and optimal too.

Therefore we rewrite the problem in terms of coefficients α and β by letting v = αe + βu.

maximize e·(αe + βu)
subject to
‖αe + βu‖² = 1
u·(αe + βu) ≥ cos θ

Let's expand the products and use the fact that ‖e‖² = ‖u‖² = 1.

maximize α + β(e·u)
subject to
α² + 2αβ(e·u) + β² = 1
α(e·u) + β ≥ cos θ

Now we have a case analysis. Ignoring the linear constraint, the objective is at most 1, hence the solution α = 1 and β = 0 (i.e., v = e) is optimal. This solution is feasible only if e·u ≥ cos θ.

If this solution is not feasible, the linear constraint must be tight: α(e·u) + β = cos θ, or β = cos θ − α(e·u). Then we can substitute, solve the resulting quadratic equation, and take the solution that scores better (unless they both score negative, in which case the bound is 0).

Thanks for fast reply and in-depth analysis! In a separate answer I posted the source code for algorithm based on your solution. Hopefully it's correct. — Witek902, Nov 05 '20 at 23:32

Witek902 · Answer 2 · 2020-11-06T01:58:00.687

Following David's answer, I implemented this algorithm which seems to work fine:

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)

2 Answers2