Oleg Fryazinov, Alexander Pasko and Peter Comninos, “Fast Reliable Interrogation of Procedurally Defined Implicit Surfaces Using Extended Revised Affine Arithmetic”, Computers & Graphics, Volume 34, Issue 6, pages 708–718, December 2010 PDF (preprint)

Abstract: Techniques based on Interval and Affine Arithmetic and their modifications are shown to provide reliable function range evaluation for the purposes of surface interrogation. In this paper we present a technique for the reliable interrogation of implicit surfaces using a modification of Affine Arithmetic called Revised Affine Arithmetic. We extend the range of functions presented in Revised Affine Arithmetic by introducing affine operations for arbitrary functions such as set-theoretic operations with R-functions, blending and conditional operators. The obtained affine forms of arbitrary functions provide faster and tighter function range evaluation. Several case studies for operations using affine forms are presented. The proposed techniques for surface interrogation are tested using ray-surface intersection for ray-tracing and spatial cell enumeration for polygonization. These applications with our extensions provide fast and reliable rendering of a wide range of arbitrary procedurally defined implicit surfaces (including polynomial surfaces, constructive solids, pseudo-random objects, procedurally defined microstructures, and others). We compare the function range evaluation technique based on Extended Revised Affine Arithmetic with other reliable techniques based on Interval and Affine Arithmetic to show that our technique provides the fastest and tightest function range evaluation for fast and reliable interrogation of procedurally defined implicit surfaces.