Scan-converting the Sphere: Circle In-Out Test

Depth-Evaluation using Paraboloid Approximation
Kenny Hoff 6/17/97

Since we are assuming that the silhouette of the projected sphere is a circle, we will also assume that the depth values are approximated by the front half of a sphere centered about the pixel point (a,b,c) with a radius of r pixels (pixel point (a,b,c) is the perspective depth-transformed sphere center). We can then evaluate the z-value for a particular (x,y) pixel point as follows:

  (x-a)² + (y-b)² + (z-c)² = r²         // original sphere equation
  (z-c)² = r² - (x-a)² - (y-b)²         // solving for z
  z - c = SQRT( r² - (x-a)² - (y-b)² )
  z = c + SQRT( r² - (x-a)² - (y-b)² )

Again in order to be efficient, we would like to make as much use as possible of the linear expression evaluator and any previously computed values. Clearly we will have a difficult time linearing this equation, so instead we will approximate the depth values by a paraboloid with the following properties:

maximum point is at point (a,b,c+r); maximum Z values
extends to infinity in the -Z direction
whose intersection with the plane Z=c exactly matches the circle. So, it must intersect the following points (a+r,b,c), (a-r,b,c), (a,b+r,c), (a,b-r,c).

Rather than finding the equation for the paraboloid directly, we can simplify the problem by finding the equations for the parabolas of two perpendicular slices of the paraboloid: one in the XZ-plane and one in the YZ-plane, with both slices going through the center (a,b,c). The maximum Z-point of the parabolas will coincide with the maximum Z-point of the paraboloid. So we have two parabolic equations to find, of the following form: Ax²+Bx+C=z; we have three points for each parabola to pass through, so we can generate a system of three equations to solve for the three unknown coefficients:

Parabola 1: XZ-plane passing through points (a+r,c), (a-r,c), (a,c+r)

  f(x) = [ x² x 1 ] [ A B C ]^T = z

  [ (a+r)²  (a+r)  1 ] [ A ]   [  c  ]
  [ (a-r)²  (a-r)  1 ] [ B ] = [  c  ]
  [     a²    a    1 ] [ C ] = [ c+r ]

Parabola 2: YZ-plane passing through points (b+r,c), (b-r,c), (b,c+r)

  f(y) = [ y² y 1 ] [ A B C ]^T = z

  [ (b+r)²  (b+r)  1 ] [ A ]   [  c  ]
  [ (b-r)²  (b-r)  1 ] [ B ] = [  c  ]
  [     b²    b    1 ] [ C ] = [ c+r ]

If we solve for this system, we obtain the values for A,B,C and the resulting paraboloid equation is written follows:

  A=-1/r
  B=0
  C=c+r
  f(x) = -(x-a)²/r + (c+r)
  f(y) = -(y-b)²/r + (c+r)
  f(x,y) = f(x) + (f(y)-(c+r))
         = c + ( (r² - (x-a)² - (y-b)²) / r )

NOTE: the above equations can be greatly simplified by assuming a center of (a,b,c)=(0,0,0) and then finding f(x,y) in the following form:

  f(x,y) = z = -(x² + y²)/r + r

and then converting to the form centered about (a,b,c):

  z-c = -((x-a)² + (y-b)²)/r + r

Working through the algebra will result in the same f(x,y) as done previously.