TIME SPACE TRADEOFFS FOR POLYGON MESH RENDERING/

We investigate architectural schemes, generalizing that of existing gr aphics engines, supporting fast rendering of triangle meshes. A mesh d efined on n vertices is rendered by sending vertices down a graphics p ipeline, after which they are pushed on a stack to be popped when no l onger needed. Only individual triangles whose vertices are present in the stack may be rendered. The storage cost of the mesh rendering is t he size of the stack required to store mesh vertices during the render ing process. This may be significantly less than n. The time cost of t he mesh rendering is the number of vertices sent down the graphics pip eline. If a large enough stack is available, it suffices to send each vertex once. If only a small stack is available, some vertices may hav e to be sent more than once, so a time/space tradeoff exists. With our architecture, a stack of size O(root n) is sufficient to fender any t riangle mesh defined on n vertices, such that each vertex is sent only once through the graphics pipeline (time cost = n). We provide an alg orithm that generates an appropriate ''rendering sequence'' of command s for any given mesh. Moreover, we show that no algorithm can do bette r, that is, Omega(root n) is a lower bound. Some n-vertex meshes may b e rendered using a stack whose size is significantly less than O(root n). An algorithm generating a minimum-time rendering sequence requirin g the minimum stack size is an open question. We provide an approximat ion: if it is theoretically possible to render a triangle mesh in mini mum time with a stack of size S, our algorithm generates a minimum-tim e rendering sequence requiring a stack of size no larger than 2S log(3 /2)n. If only a stack of size k is available, we provide an algorithm generating a rendering sequence requiring a stack of size no larger th an k, such that at most n(1 + c/k) vertices must be sent through the p ipeline, for some constant c.