4.7.2 Line Tracing

Interval arithmetic may form the basis for rendering algorithms other than those given here. Sophisticated methods are certainly possible. Care should be taken to preserve the strength of the underlying interval arithmetic, so that algorithm guarantees may be given.

In [66], an implicit curve approximation algorithm is given; it is argued, therein, that the given algorithm is more reliable than those based on sampling. This is clear, although the algorithm given assumes the following:

• G is a continuous, 1D manifold;
  • G has no isolated singularities,
  • G has no regions of dimension greater than one,
  • each disjoint curve segment of G is either closed,
    or has endpoints at the graphing boundary,
• G has no segments aligned with either axis.

The output of the algorithm is a collection of line segments, which approximate G.

Using a linear interval arithmetic in place of a constant interval arithmetic allows a similar algorithm to be constructed, which returns a collection of polygons which include G. With domain and continuity tracking in conjunction with automated derivative analysis, some of the assumptions may be lifted, as they may be verified as the algorithm proceeds.

Many algorithms which use interval arithmetic, do so peripherally, and would benefit from a re-engineering which allows the concepts of interval arithmetic to permeate the entire algorithm. A chief benefit of such re-engineering is that a clear, strong guarantee of program output may be given. With the curve approximation algorithm, one may output the polygons as a collection of (circular) lists, with the guarantee that the curve segment passes from polygon to polygon, in the order given. Strong guarantees may be given for the original algorithm, but they are intricate and somewhat unsatisifying. Strong guarantees may even be given for algorithms based on floating-point, but such guarantees are considerably more intricate, and consequently even less satisfying.

An adoption of linear interval arithmetic in place of constant interval arithmetic increases the efficiency of a method, and may be enacted using a minimal expenditure of effort. Portions which performed derivative analysis may be removed, as such analysis is done automatically, within the linear interval arithmetic library. The desired results may be obtained from the linear interval arithmetic library. A generalized interval arithmetic library may use demotions to shield an application from the interval arithmetic being used.

Jeff Tupper

March 1996