A Breadth-First Approach To Efficient Mesh Traversal

Mitra, Tulika; Chiueh, Tzi-cker

A Breadth-First Approach To Efficient Mesh Traversal

Files

031-037.pdf (952.32 KB)

Date

1998

Authors

Mitra, Tulika
Chiueh, Tzi-cker

Publisher

The Eurographics Association

Abstract

Complex 3D polygonal models are typically represented as triangular meshes, especially when they are generated procedurally, or created from volumetric data sets through surface extraction. Existing 3D rendering hardware, on the other hand, processes one triangle at a time. Therefore triangle meshes need to be converted to individual triangles when they are fed to the graphics pipeline. The design goal of such conversion algorithms is to minimize the number of vertices that are sent redundantly to the rendering pipeline. This paper proposes a breadth-first approach to traverse triangle meshes that reduces vertex redundancy to very close to the theoretical minimum. With the proposed scheme, no triangle vertices need to be specified multiple times, barring exceptional cases. In addition, owing to a prefetching technique, the on-chip storage requirement for effective mesh traversal remains small and largely constant regardless of the mesh size. Our experimental results show that assuming a 64-vertex buffer, the redundant transformation overhead associated with the proposed approach is between 1.00% and 7.33%, for a set of 8 triangle meshes whose size ranges from 2,992 to 40,000 triangles.

        @inproceedings{:10.2312/EGGH/EGGH98/031-037
,
booktitle = {SIGGRAPH/Eurographics Workshop on Graphics Hardware
},
editor = {S. N. Spencer
},
title = {{A Breadth-First Approach To Efficient Mesh Traversal
}},
author = {Mitra, Tulika and 
Chiueh, Tzi-cker
},
year = {1998
},
publisher = {The Eurographics Association
},
ISSN = {1727-3471
},
ISBN = {0-89791-097-X
},
DOI = {/10.2312/EGGH/EGGH98/031-037
}
}