An Improved Adjacency Data Structure for Fast Triangle Stripping
An Improved Adjacency Data Structure for Fast Triangle Stripping
复制标题
一种改进的快速三角形剥离邻接数据结构
DOI：
10.1080/2151237x.2005.10129196
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Alexa
中科院分区：
文献类型：
--
作者：
Patrick Reuter;J. Behr;M. Alexa
为了加快多边形网格的绘制速度，三角形条带通常用于通过利用相邻三角形共享一条边的事实来减少发送到图形子系统的顶点的数量。本文提出了一种改进的邻接数据结构，用于快速三角形剥离算法。有三个主要贡献：第一，数据结构可以从任何索引的面集快速和鲁棒地创建;第二，其缓存友好的布局是专门设计的，以有效地回答常见的剥离查询，如邻居查找和最小度三角形查找，在恒定的时间;第三，剥离算法就地操作，因为条带是通过简单地重新链接指针创建的。剥离算法的实现与其他实现相比显示出显著的加速。我们的实现作为OpenSG的一部分公开提供。
To speed up the rendering of polygonal meshes, triangle strips are commonly used to reduce the number of vertices sent to the graphics subsystem by exploiting the fact that adjacent triangles share an edge. In this paper, we present an improved adjacency data structure for fast triangle stripping algorithms. There are three major contributions: first, the data structure can be created quickly and robustly from any indexed face set; second, its cache-friendly layout is specifically designed to efficiently answer common stripping queries, such as neighbor finding and least-degree triangle finding, in constant time; and third, the stripping algorithm operates in-place, since strips are created by simply relinking pointers. An implementation of a stripping algorithm shows a significant speed-up compared to other implementations. Our implementation is publicly available as part of OpenSG.