A Greedy, Non-Recursive Algorithm for Minimum-Time Rendering of Triangle Meshes

Abstract We propose a new algorithm for solving the so-called minimum-time rendering (MTR) problem in computer graphics. Bar-Yehuda and Gotsman [ACM Transaction on Graphics, vol.15, no.2 (1996) p. 141-52] formulated the problem of MTR as a precise model to analyze fundamentally how efficient one can render polygon meshes. They showed also that their divide-and-conquer based method can always produce a minumum-time rendering sequence using a cache size bounded by O( √ n), and that this growth rate cannot be improved in a worst case sense. We illustrate that one can in general reduce the underlying hidden constant by a factor of 2 by using a non-recursive algorithm. The new MTR algorithm presented in this paper handles meshes of arbitrary topology, is non-recursive and greedy in nature, is very simple to implement, and runs in O(n log n) time when aided by a heap data-structure. We emphasize the benefit of avoiding a divide-and-conquer strategy through an analysis on a family of structured meshes; and present also computational results on a set of unstructured meshes encountered in computer graphics which illustrate a similar benefit as predicted by the theoretical analysis. Based on our MTR algorithm, we derive also a new algorithm for rendering arbitrarily large meshes when a controllable cache of a certain fixed size is given. We compare our method with two current state-of-the-art methods based on FIFO cache. Our result gives encouragement that algorithms based on a controllable cache (like ours) can give better average cache miss ratios when compared to algorithms based on the more standard FIFO cache model