Browse Prior Art Database

Efficient Evaluation of X**N for Lighting Calculations

IP.com Disclosure Number: IPCOM000105942D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 8 page(s) / 302K

Publishing Venue

IBM

Related People

Luken, W: AUTHOR [+2]

Abstract

For the most commonly used models of lighting, evaluation of x**n is an important and time-consuming part of the calculations necessary to determine the specular component of the light intensity at a point in space while shading objects (x = hat{R} . hat{V} where hat{R} is the unit vector in the direction of reflection of light and hat{V} is the unit vector in the direction to the viewpoint and n is the specular index of the material).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 19% of the total text.

Efficient Evaluation of X**N for Lighting Calculations

      For the most commonly used models of lighting, evaluation of
x**n is an important and time-consuming part of the calculations
necessary to determine the specular component of the light intensity
at a point in space while shading objects (x = hat{R} . hat{V} where
hat{R} is the unit vector in the direction of reflection of light and
hat{V} is the unit vector in the direction to the viewpoint and n is
the specular index of the material).

      This paper discusses an efficient technique of evaluating x**n
in the above context which is less complicated than the general
problem due to the following restrictions in the domain:

1.  0.0 <= x <= 1.0
2.  1 <= n <= 256
3.  Only 256 different values per color are representable on the
    graphics device using the result of the calculation.  Therefore
    x**n need be evaluated just to sufficient precision to guarantee
    that there would have been no difference in the final result even
    if x**n had been computed with greater precision.

USE OF LOOK-UP TABLES - One common approach used to speed up
evaluation of complex functions such as x**n, cos(x), log x, etc., is
to use precomputed tables which are looked up.  This is a classic
example of a time-space trade-off and the question of the optimal
balance point arises naturally.

      Prior work on "accurate" evaluation of x**n includes factoring
n into a set of primes [1,2]  and multiplying the results.  This
approach relies on accurate evaluation of x**n and requires a lookup
table for storing the decompositions for all the powers.  Other work
on evaluation of x**n includes approximation with polynomials of
lower degree [3]  and Chebyshev polynomials [4].  Though this
technique requires little storage, evaluation of lower degree
polynomials is time-consuming and not suitable in the context of
interactive computer graphics.

      To evaluate x**n at intervals of 0.00001 for all powers between
1 and 256 by using a look-up table it requires 100000 * 256 entries
in the table.  This is a very large price to pay for speed.  In the
context of reducing the memory requirements, without commensurate
loss in speed and considerable increase in complexity, the following
three techniques are discussed in detail.

1.  Domain compaction.

2.  Errors in look-up tables and interpolation.
3.  sqrt(n) Divide and conquer mechanism.

      DOMAIN COMPACTION - In the range 0.0 <= x <= 1.0, f_{n}(x) =
x**n is a monotonically decreasing function of n.  For some x =
x0(n), f_{n}(x) is less than the threshold of the limited precision
necessary in the computation.  Any value less than the threshold can
be replaced by zero.  So, the domain for x is reduced to x0(n) <= x
<= 1.0 from 0.0 <= x <= 1.0.  This means that effectively
f_{n}(x) = 0    if x <= x0(n)
           x**n if x > x0(n)

      Since only 256 levels per each primary color (red, green, an...