Complexity of the MIP map algorithm for perspective texture warping

The MPEG4-based visual presentation is a scene presentation, which is composed of multiple visual objects. The MPEG-4 standard allows viewers to interactively change their viewing positions relative to a scene. Therefore, an MPEG4-compliant graphical rendering device should be able to transform a decoded video object in 3D space according to viewer's viewing position. This type of texture transformation is known as perspective texture warping. In order to assure high quality images during perspective texture warping, the warping algorithm needs to be incorporated with anti-aliasing functions. One of the popular anti-aliasing methods is known as the MIP mapping, which stands for `multum in parvo', a Latin phrase meaning `many things in a small place.' The advantage of the MIP mapping method is that the number of operations and memory accesses is constant. Compared to other anti-aliasing methods, the MIP mapping method requires fewer memory accesses. We studied the complexity of the MIP mapping method and estimated the number of basic arithmetic operations needed in order to implement the algorithm in hardware. We believe that the result of the complexity analysis can provide useful information in terms of algorithm selection for hardware implementation as well as actual hardware design.