Technical Report CIS9515

Authors: R. Bar-Yehuda and C. Gotsman
Abstract: We investigate architectural schemes, generalizing that of existing graphics engines, supporting fast rendering of polygon meshes. A mesh defined on $n$ vertices is rendered by sending vertices down a graphics pipeline, after which some are stored in a stack, to be removed when no longer needed. Only individual polygons whose vertices are present in the stack may be rendered. The storage cost of the mesh rendering is the size of the stack required to store mesh vertices. This may be significantly less than $n$. The time cost of the mesh rendering is the number of vertices sent down the graphics pipeline. If a large enough stack is available, it suffices to send each vertex once. If only a small stack is available, some vertices may have to be sent more than once, so a time/space tradeoff exists. With our architecture, a stack of size $O(\sqrt{n})$ is sufficient to render any polygon mesh defined on $n$ vertices, such that each vertex is sent only once through the graphics pipeline (time cost = $n$). We provide an algorithm which generates an appropriate ``rendering sequence'' of commands for any given mesh. Moreover, we show that no algorithm can do better, i.e., $\Omega(\sqrt{n})$ is a lower bound. Some $n$-vertex meshes may be rendered using a stack whose size is significantly less than $O(\sqrt{N})$. An algorithm generating a minimum-time rendering sequence requiring the minimum stack size is an open question. We provide an approximation: If it is possible to render a polygon mesh in minimum time with attack of size $S$, we provide an algorithm which generates a minimum-time rendering sequence requiring a stack of size $ \leq 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 $\leq k$, such that at most $n(1+c/k)$ vertices must be sent through the pipeline, for some constant $c$.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion