Scan-converting the Sphere: Circle In-Out Test

Perspective Scaling of the Radius
Kenny Hoff 6/17/97

Method 1: Cube-root of the Determinant

Given the sphere's center and radius in world coordinates, and the current composite transformation matrix that includes both modeling and viewing transformations, we must project then center and perspectively scale the radius. Normally, a sphere would project to an ellipse and would require major and minor axis radii (not really, but it is a better approx than a circle; it is actually a "warped" ellipse), but in our approximation the sphere is projected into a circle and we need only find the "proper" scaling of the sphere radius to find a radius of the circle in pixel or screen space.

On PixelPlanes 4 and 5, the radius scaling factor used was the cube-root of the determinant of the 3x3 matrix formed from the transformed principle axes as follows:

principle axes are treated as points, transformed by the composite matrix, and then homogenized (perspective div by w)
resulting points form columns of the 3x3 matrix to represent the transformed axes and hopefully a reasonable approximation to the deformation of the space

The resulting scaling factor will scale the world radius to form a radius in NDC space; another scaling based on the viewport transformation will be required to find a "pixel" radius (unless, of course the viewport transformation is part of the composite matrix).

The intuition for this scaling factor is based on the change in volume of a unit cube after transformation. We can define a unit cube with three orthonormal vectors. The volume of the parallelpiped formed from these vectors after transformation will be the scaling factor cubed. For a cube, the cube-root of the volume equals the length of a side. The approximation to the new "side length" is the cube-root of the volume of the cube after transformation. The ratio of the new side length to the old is the scaling factor that takes the world radius into screen radius (NDC coordinates).

The composite transformation matrix contains the transformed axes of this parallelpiped in the upper 3x3. The unit cube and its determinant is represented as follows:

  -- X axis -- 0
  -- Y axis -- 0
  -- Z axis -- 0
   0   0   0   1

  1.000000 0.000000 0.000000 0.000000
  0.000000 1.000000 0.000000 0.000000
  0.000000 0.000000 1.000000 0.000000
  0.000000 0.000000 0.000000 1.000000

  Upper 3x3 Determinant = 1.000000 = volume of unit cube
  Side length = CubeRoot(1.000000) = 1

If we scale the matrix so that the cube is a 2x2x2, we will see the reflected change in the determinant and the computed side length:

  2.000000 0.000000 0.000000 0.000000
  0.000000 2.000000 0.000000 0.000000
  0.000000 0.000000 2.000000 0.000000
  0.000000 0.000000 0.000000 1.000000

  Upper 3x3 Determinant = 8.000000 = volume of tranformed cube
  Side length = CubeRoot(8.000000) = 2

Method 2: Transformation of Boundary Points

The basic idea here is much simpler than the previous method. We simply take sample points on the boundary of the sphere and transform them along with the center. We can approximate the radius by the max distance between the center and the other boundary sample points. Sample points must be chosen so as to minimize the error from any viewing direction. As a minimum, we can choose three points chosen along the three principal axes emanating from the sphere's center.

Method 3: Finding Boundary Points on the Silhouette

As opposed to the previous method where we take sample points on the sphere in world coordinates irrespective of the viewer's position in hopes of finding samples near the projected boundary, we find samples on the silhouette in eye space. In eye space, we know that the eye is at the origin looking down the -Z axis (assuming OpenGL conventions). We can select sample points on the sphere boundary that are perpendicular to the viewing direction and then apply the remaining projection transformations to find the radius in NDC and/or screen space. We do have to have the radius in eye space, but this should be a simple calculation with the assumptions we make below.

This method has the potential to be the simplest of them all; however it requires some key assumptions. Basically, the composite matrix is formed from the multiplication of the Projection matrix with the ModelView matrix (ModelView being applied first, so Comp=Proj*Model for premult/col vectors). This method will be quite "accurate" if we can assume the following:

the perspective projection is contained in the Projection matrix (as it should be, but OpenGL makes no such restriction)
the ModelView matrix contains all necessary transformations to take a point in model space to eye space (eye at origin looking down -Z axis)
only uniform scaling is present in the ModelView matrix; so only rotations, translations, and uniform scaling is present in ModelView

This method proceeds as follows:

Transform the center and any point on the boundary of the sphere into eye space by transforming by the ModelView matrix.
The radius in eye space is computed as the distance between the two transformed points.
Find sample points on the silhouette EyeRadius distance from the eye-space center along a direction perpendicular to the viewing direction. A single sample point should suffice in either the viewer's up or horizon directions EyeSamplePt = EyeCenter + (0,1,0)*EyeRadius.
Now the EyeSamplePt and the EyeCenter can be transformed by the Projection matrix; a perspective divide will obtain NDC coordinates and another viewport transformation will obtain pixel coordinates. The distance between the points in either space will be the radius of the projected sphere in that space.