Archive for December 2009

Exact numeric integration

This post describes a simple way to integrate a function over an interval and get an exact answer. The question came out of another one, which is how to optimally render a continuous-space image onto a discrete array of pixels.

For anti-aliasing, I’ll make two simplying assumptions (to be revisited):

  • Each pixel is a square area. (With apologies to Alvy Ray Smith.)
  • Since I can choose only one color per pixel, I want exactly the average of the continuous image over pixel’s subregion of 2D space.

The average of a function over a region (here a continuous image over a 2D interval) is equal to the integral of the function across the region divided by the size (area for 2D) of the region. Since our regions are simple squares, the average and the integral can each be defined easily in terms of the other (dividing or multiplying by the size).

To simplify the problem further, I’ll consider one-dimensional integration, i.e., integrating a function of R over a 1D interval. My solution below involves the least upper bound operator I’ve written about (and its specialization unamb).

Continue reading ‘Exact numeric integration’ »