Minimum bounding sphere of a Frustum

sepul · 2011-06-30T07:24:26

I'm trying to find minimum bounding sphere for a frustum and haven't succeeded so far. the method I use is very simple, assuming frustum is symmetric , the center of the sphere should be on the line between two centers of frustum planes (shown in the image) so we have : 1) Dot(P - A, P - A) = Dot(P - B, P - B) 2) P = S + t*N by putting P into the equation (1), I could solve t and find sphere center but I can't get corrent results and two distances are never the same after solving it can someone tell we where I'm doing wrong ? or how can I compute the minimum sphere of the frustum ? here is the code : // 0~3 points of 'frustPts' = nearPlane // 4~7 points of 'frustPts' = farPlane void CSM::CalcMinSphere( const math::Vector3f frustPts[8], math::Sphere* sphere ) { math::Vector3f S = (frustPts[0] + frustPts[2]) * 0.5f; // center pt - near plane math::Vector3f S2 = (frustPts[4] + frustPts[6]) * 0.5f; // far pt - near plane math::Vector3f N = S2 - S; math::Vec3Normalize(N, &N); math::Vector3f A = frustPts[0]; math::Vector3f B = frustPts[4]; fl32 d = 2.0f*(math::Vec3Dot(N, A) - math::Vec3Dot(N, B)); fl32 t = ( math::Vec3Dot(A, A) - math::Vec3Dot(B, B) - 2.0f*S.x*(A.x+B.x) - 2.0f*S.y*(A.y+B.y) - 2.0f*S.z*(A.z+B.z) ) / d; math::Vector3f center = S + N*t; fl32 radius = math::Vec3Length( B - center ); fl32 d1 = Vec3Dot( center - A, center - A ); fl32 d2 = Vec3Dot( center - B, center - B ); _ASSERT( Fl32Equal(d1, d2) ); // asset failure !!! ( + we have invalid bounding sphere) sphere->Set(center.x, center.y, center.z, radius); }

Math and Physics Programming

Started by sepul June 23, 2011 03:42 PM

14 comments, last by sepul 12 years, 9 months ago

HappyCoder

5,076

June 26, 2011 03:39 AM

I think I have it figured out.

First of all A and B need to be in the camera space, meaning that the line that goes out the center of the camera (the line formed by S + N * t) will fall directly on the z axis. This means that the X and Y of this line will always be 0 or.

Px = 0
Py = 0

This leaves us with only one variable to solve for or Pz.

We know that the distance between P and A is the same as P and B so

Ax^2 + Ay^2 + (Az - Pz)^2 = Bx^2 + By^2 + (Bz - Pz)^2

at this point we just solve for Pz.

Pz = ((Bx^2 + By^2 + Bz^2) - (Ax^2 + Ay^2 + Az^2)) / (2(Bz - Az))

The only thing left to do is the transform P into world space and calculate the radius of the circle by finding the distance between P and A or P and B.

If I didn't explain clearly enough let me know and I can give some detail.

My current game project Platform RPG

Dave Eberly

1,182

June 26, 2011 05:43 PM

Let E be the eyepoint. Let the view direction be D, the up direction be U, and the right direction be R. D, U, and R are unit length and mutually perpendicular. The frustum values are dmin (near), dmax (far), rmax (right), -rmax (left), umax (up), and -umax (down). The sphere center is C = E + s*D for some s. A vertex of the near plane is P0 = E + dmin*D + umax*U + rmax*R. A vertex of the far plane is P1 = E + dmax*D + (dmax*umax/dmin)*U + (dmax*rmax/dmin)*R. The squared distances from P0 to C and P1 to C must be equal, so (s-dmin)^2 + rmax^2 + umax^2 = (s - dmax)^2 + (dmax*rmax/dmin)^2 + (dmax*umax/dmin)^2. This leads to s = ((dmin + dmax)/2)*(1 + (rmax/dmin)^2 + (umax/dmin)^2).

This is actually the circumscribed sphere, which I believe is the minimum-volume sphere as long as center C is inside the frustum, which means as long as s <= dmax. When s > dmax, the minimum-volume sphere is the one whose center is E+dmax*D. The radius is distance from C to a vertex on the far plane. In the case s < dmax, the radius is the distance from C to any of the 8 vertices, but you can just substitute the value of s in either of the squared distances I mentioned and then take the square root.

sepul

257

Author

June 28, 2011 06:54 PM

@Mussi: I solved them using Maple, you should give it a try, nice app

@Owl: I have tried checking miniball algorithm out, Dave Eberly also has an implementation in his website, which is very complicated and as long as frustum has 8 verts and is symmetric I don't think I need to implement that.

@Dave, @HappyCoder
thanks guys, as long as I got HappyCoder's method more clearly, I'll try to implement that first and check the results

another method I'm currently using is that, I use barycentric minimum bounding spheres method (described here) for two tetrahedrons inside of the frustum. if indices 0~3 is vertices of the frustum's near plane, and 4~7 for far plane, I calculate one sphere for 0-2-5-7, and one for 1-3-4-6 (opposite tetrahedrons) , and merge two spheres. I think get acceptable results from this, but it's still pretty big especially for frustums with high aspect ratio (fov is high and (far-near) is small), although I don't think I can get small bounding spheres for those, because of the nature of the shape.

dark-hammer engine - http://www.hmrengine.com

Postie

1,559

June 28, 2011 11:40 PM

Did the circumcircle idea I suggested not work out?

[size="2"]Currently working on an open world survival RPG - For info check out my Development blog:[size="2"] ByteWrangler

Dave Eberly

1,182

June 29, 2011 05:06 AM





//----------------------------------------------------------------------------

void ComputeMinimumVolumeSphereOfFrustum (const float eye[3],

    const float direction[3], const float dmin, const float dmax,

    const float rmax, const float umax, float center[3], float& radius)

{

    float invDMin = 1.0f/dmin;

    float u = umax*invDMin;

    float r = rmax*invDMin;

    float u2pr2 = u*u + r*r;

    float s = 0.5f*(dmin + dmax)*(1.0f + u2pr2);

    if (s >= dmax)

    {

        s = dmax;

        radius = dmax*sqrt(u2pr2);

    }

    else

    {

        float diff = 1.0f - s/dmax;

        radius = dmax*sqrt(diff*diff + u2pr2);

    }

    for (int i = 0; i < 3; ++i)

    {

        center = eye + s*direction;

    }

}

//----------------------------------------------------------------------------

template <int n, typename Real>

void ComputeMiniballFrustum (const Real eye[n], const Real direction[n],

    const Real min0, const Real max[n], Real center[n], Real& radius)

{

    Real invMin0 = ((Real)1)/min0;

    float ratio[n], sqrLength = (Real)0;

    for (int i = 1; i < n; ++i)

    {

        ratio = max*invMin0;

        sqrLength += ratio*ratio;

    }

    Real s = ((Real)0.5)*(min0 + max[0])*((Real)1 + sqrLength);

    if (s >= max[0])

    {

        s = max[0];

        radius = max[0]*sqrt(sqrLength);

    }

    else

    {

        Real diff = (Real)1 - s/max[0];

        radius = max[0]*sqrt(diff*diff + sqrLength);

    }

    for (int i = 0; i < n; ++i)

    {

        center = eye + s*direction;

    }

}

//----------------------------------------------------------------------------

int main ()

{

    float eye[3] = { 0.0f, 0.0f, 0.0f };

    float direction[3] = { 0.0f, 0.0f, 1.0f };

    float dmin = 10.0f, dmax = 1000.0f, rmax = 2.0f, umax = 1.0f;

    float center0[3], radius0;

    ComputeMinimumVolumeSphereOfFrustum(eye, direction, dmin,

        dmax, rmax, umax, center0, radius0);



    float min0 = dmin, max[3] = { dmax, rmax, umax };

    float center1[3], radius1;

    ComputeMiniballFrustum<3,float>(eye, direction, min0, max, center1,

        radius1);

    return 0;

}

//----------------------------------------------------------------------------

sepul

257

Author

June 30, 2011 07:24 AM

Methods described by HappyCoder and David Eberly as well as the method I described in my previous post (slower), worked and gave identical results
thanks

@Postie: no I couldn't get that to work, I used barycentric coordinates to calculate circum circle of three points, and chose different set of points, but none of them gave minimum sphere of the frustum

dark-hammer engine - http://www.hmrengine.com

sepul

257

Author

June 30, 2011 07:34 AM