Time/Space Tradeoffs for Polygon Mesh Rendering

Reuven Bar-Yehuda, Craig Gotsman

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

We investigate architectural schemes, generalizing that of existing graphics engines, supporting fast rendering of triangle meshes. A mesh defined on n vertices is rendered by sending vertices down a graphics pipeline, after which they are pushed on a stack to be popped when no longer needed. Only individual triangles 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 during the rendering process. 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(√n) is sufficient to render any triangle mesh defined on n vertices, such that each vertex is sent only once through the graphics pipeline (time cost = n). We provide an algorithm that generates an appropriate "rendering sequence" of commands for any given mesh. Moreover, we show that no algorithm can do better, that is, Ω(√n) is a lower bound. Some re-vertex meshes may be rendered using a stack whose size is significantly less than O(√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 theoretically possible to render a triangle mesh in minimum time with a stack of size S, our algorithm generates a minimum-time rendering sequence requiring a stack of size no larger than 2S log3/2n. If only a stack of size k is available, we provide an algorithm generating a rendering sequence requiring a stack of size no larger than k, such that at most n(1 + c/k) vertices must be sent through the pipeline, for some constant c.

Original languageEnglish (US)
Pages (from-to)141-152
Number of pages12
JournalACM Transactions on Graphics
Volume15
Issue number2
DOIs
StatePublished - Apr 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Algorithms
  • G.2.2 [Discrete Mathematics]: Graph Theory - graph algorithms
  • Graphics pipeline
  • I.3.1 [Computer Graphics]: Hardware Architecture - graphics processors; raster display devices
  • Polygons
  • Rendering

Fingerprint Dive into the research topics of 'Time/Space Tradeoffs for Polygon Mesh Rendering'. Together they form a unique fingerprint.

Cite this