Memory access patterns of occlusion-compatible 3D image warping
William R. Mark, Gary J. Bishop · 1997
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. CR Categories and Subject Descriptors: I.3.3 [Computer Graphics ]: Picture/Image Generation -- Display Algorithms; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism -- Visible line/surface algorithms; I.3.1 [Computer Graphics]: Hardware Archit...