Memory Access Patterns of Occlusion-Compatible 3D Image Warping

William R. Mark, Gary Bishop.

Proceedings of SIGGRAPH/Eurographics Workshop on Graphics Hardware (Los Angeles, California, Aug. 3-4, 1997), pp. 35-44.


McMillan and Bishop's 3D image warp can be efficiently implemented by exploiting the coherency of its memory accesses. We analyze this coherency, and present algorithms that take advantage of it. These algorithms traverse the reference image in an occlusion-compatible order, which is an order that can resolve visibility using a painter's algorithm. Required cache sizes are calculated for several one-pass 3D warp algorithms, and we develop a two-pass algorithm which requires a smaller cache size than any of the practical one-pass algorithms. We also show that reference image traversal orders that are occlusion-compatible for continuous images are not always occlusion-compatible when applied to the discrete images used in practice.

Full Paper (Adobe PDF, 0.4 MB).
Full Paper (postscript, 1.2 MB).