12
\$\begingroup\$

How do you find the largest sphere that you can draw in perspective?

Viewed from the top, it'd be this:

enter image description here

Added: on the frustum on the right, I've marked four points I think we know something about. We can unproject all eight corners of the frusum, and the centres of the near and far ends. So we know point 1, 3 and 4. We also know that point 2 is the same distance from 3 as 4 is from 3. So then we can compute the nearest point on the line 1 to 4 to point 2 in order to get the centre? But the actual math and code escapes me.

I want to draw models (which are approximately spherical and which I have a miniball bounding sphere for) as large as possible.

Update: I've tried to implement the incircle-on-two-planes approach as suggested by bobobobo and Nathan Reed :

function getFrustumsInsphere(viewport,invMvpMatrix) {
    var midX = viewport[0]+viewport[2]/2,
        midY = viewport[1]+viewport[3]/2,
        centre = unproject(midX,midY,null,null,viewport,invMvpMatrix),
        incircle = function(a,b) {
            var c = ray_ray_closest_point_3(a,b);
            a = a[1]; // far clip plane
            b = b[1]; // far clip plane
            c = c[1]; // camera
            var A = vec3_length(vec3_sub(b,c)),
                B = vec3_length(vec3_sub(a,c)),
                C = vec3_length(vec3_sub(a,b)),
                P = 1/(A+B+C),
                x = ((A*a[0])+(B*a[1])+(C*a[2]))*P,
                y = ((A*b[0])+(B*b[1])+(C*b[2]))*P,
                z = ((A*c[0])+(B*c[1])+(C*c[2]))*P;
            c = [x,y,z]; // now the centre of the incircle
            c.push(vec3_length(vec3_sub(centre[1],c))); // add its radius
            return c;
        },
        left = unproject(viewport[0],midY,null,null,viewport,invMvpMatrix),
        right = unproject(viewport[2],midY,null,null,viewport,invMvpMatrix),
        horiz = incircle(left,right),
        top = unproject(midX,viewport[1],null,null,viewport,invMvpMatrix),
        bottom = unproject(midX,viewport[3],null,null,viewport,invMvpMatrix),
        vert = incircle(top,bottom);
    return horiz[3]<vert[3]? horiz: vert;
}

I admit I'm winging it; I'm trying to adapt 2D code by extending it into 3 dimensions. It doesn't compute the insphere correctly; the centre-point of the sphere seems to be on the line between the camera and the top-left each time, and its too big (or too close). Is there any obvious mistakes in my code? Does the approach, if fixed, work?

\$\endgroup\$
  • \$\begingroup\$ Do the sphere have to be entirely on the hither side of the far-plane as in the image? \$\endgroup\$ – Mikael Högström Aug 1 '13 at 14:44
  • \$\begingroup\$ @MikaelHögström I imagine they would have be, in order to be as big as possible? \$\endgroup\$ – Will Aug 1 '13 at 14:48
  • \$\begingroup\$ Hmm I guess it depends on your purpose... If you draw a sphere with one half beyond the far-plane then that would be bigger but maybe that goes against your purpose? \$\endgroup\$ – Mikael Högström Aug 1 '13 at 14:58
  • \$\begingroup\$ @MikaelHögström aha I understand your question; yes I want the whole model drawn, no far plane clipping through it. \$\endgroup\$ – Will Aug 1 '13 at 14:59
12
\$\begingroup\$

I shall assume that your frustum is symmetrical, since your drawing seems to suggest so. There are three constraints (two if your frustum is 2D):

A. the sphere cannot be larger than the distance between the near and far planes

If D is the near-far distance, the first constraint is simply:

R ≤ D / 2

B. the sphere cannot grow wider than the side planes

Now for the other constraint, let’s say α is the half-angle of the frustum and L is the half-width of the far plane, as shown in this drawing:

frustum

The first formula is given by trigonometry in the triangle. The second comes from the sum of a triangle’s angles. Which gives us the second constraint:

R ≤ L tan((π - 2α) / 4)

If your frustum is 3D, you'll have a third constraint with new L and α values.

Final result

The R value you are looking for is the min of the three bounds.

How to get the parameters

If you can unproject the frustum in view or world space, you can compute L, D and α in the following way, where the P points are from the near plane, and the Q points are from the far plane:

formula2

Arrows mean vectors, “.” is the dot product, and || indicates the length of a vector. Replace Q2 with Q3 and P2 with P3 to get L and α in the vertical dimension.

\$\endgroup\$
  • \$\begingroup\$ How, from the frustum (computed by unprojecting the viewport points to get near and far), do you determine the field of view? And in 3D there's only two choices not three, right? My attempts to put your algorithm into code always give me very big R. \$\endgroup\$ – Will Aug 1 '13 at 21:45
  • \$\begingroup\$ @Will I added a second drawing with formulas that will hopefully help. \$\endgroup\$ – sam hocevar Aug 2 '13 at 10:04
1
\$\begingroup\$

I'm attempting to do something similar, and in my case, speed is more crucial than accuracy as long as the sphere does not exist outside any of the frustum's bounds.

If you calculate the shortest distance between linesegs (or faces in 3d), the shortest distance found could be used as the diameter of an incircle/insphere which lies fully inside the frustum. The origin of the incircle/insphere could simply the average of all vertices (sum & divide). It would be quite fast and also work for all types of convex polyhedra.

The only drawback is that the circle or sphere won't necessarily be the largest incircle or insphere possible. For a frustum with a lot of volume and one very short edge, the circle/sphere would share much less of the frustums space than possible.

Another Idea

If you want the insphere of a 3D view-frustum and you have the perspective matrix used to construct this frustum, then you could simply use that matrix on the insphere of a unit cube, and that should be a perfect insphere for the frustum. (The diameter of the insphere of a cube is the length of one of the cube's edges, the center is the middle of the cube which is the average of the cube's vertices)

\$\endgroup\$
1
\$\begingroup\$

The Biggest Sphere possible should touch the far-plane (using the terms for view-frustrums here) right in the center. It would also touch the top/bottom or the left/right planes, depending on which FoV-angle is smaller. I have to say that i don´t have an actual mathematical proof for those assumptions, but they should be right. Maybe someone has an idea on how to proof this.

A Sphere can be defined by it´s center point and a radius. Cx and Cy is the same as the center of the farplane.

Cz and the radius can be obtained by solving an equation system based on the assumptions listed above.

T is one of the either bottom/top plane or left/right plane (see above) with t1,t2 and t3 as normalized normal vector and t4 as distance from origin. f is the center of the farplane.

t1*cx + t2*cy + t3*cz - t4 = r

-fz + cz = r

t1*cx + t2*cy + t3*cz - t4 = -fz + cz

t1*cx + t2*cy + fz - t2 = +cz - t3*cz

t1*cx + t2*cy - fz - t2 = cz * (1 - t3)

cz = (t1*cx + t2*cy - fz - t2) / (1 - t3)

r is then calculated by inserting cz into this: -fz + cz = r

You can obtain all planes from the Projection Matrix youre using. (Not ViewProjection in this case)

afterwards you have to move the sphere to the right space: C' = inverse(View) * C

\$\endgroup\$
2
\$\begingroup\$

In 2D: consider the frustum as a triangle (2D)

enter image description here

You then want to find the incircle of the triangle.

As a 3D problem, you need to find the insphere of a square based pyramid.

If I had the formula I would print it here, but alas, I do not know the formula.

\$\endgroup\$
  • 2
    \$\begingroup\$ It probably suffices to find the incircle of either the vertical or horizontal frustum in 2D, whichever has the smaller FOV, at least for "standard" frusta (not sheared or anything). \$\endgroup\$ – Nathan Reed Aug 1 '13 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.