One of the standard weapons in any graphics programmer’s arsenal is a procedure for mesh triangle order optimization. \u00a0Although most meshes are intended to produce output that is independent of the ordering of their triangles, the order of triangles within a mesh can have a big impact on performance. \u00a0This gives us great leeway in picking our triangle order and also a great incentive for doing so wisely.<\/p>\n
With today’s hardware and game content, a reasonable consideration when picking triangle order is overdraw. \u00a0Games tend to be limited by fragment processing and early-z rejection is the primary way of keeping that cost to a minimum. \u00a0The same meshes that are intended to be triangle order independent are usually also intended to be mesh order independent. \u00a0Consequently most games minimize overdraw by sorting meshes relative to the camera position and rendering them in nearest-to-farthest order. \u00a0This maximizes early-z rejection from intermesh occlusion, but it doesn’t address the possibility of intra-mesh occlusion. \u00a0Any concave mesh may, after all, have self-occluding elements that could benefit from a nearest-to-farthest ordering. \u00a0Since it isn’t feasible to sort the triangles within a mesh based on camera position every frame, the most common overdraw minimizing mesh optimization is ordering triangles offline based on a camera-independent probability of being occluded. \u00a0If you take a torus, for example, it is pretty clear that the probability of the inner wall of the torus being occluded from a random camera angle is much higher than the probability of the outer wall being occluded. \u00a0An overdraw-conscious triangle order for a torus would therefore render triangles on the outer wall of the torus before the triangles on the inner wall. \u00a0Since computing this camera-independent probability of occlusion can be quite expensive and since there are other performance advantages to rendering adjacent triangles together, a good approach to overdraw ordering is to first decompose the mesh into convex clusters of adjacent triangles and then compute the occlusion probability per cluster. \u00a0This approach is detailed in\u00a0“Triangle Order Optimization for Graphics Hardware Computation Culling<\/a>” which was presented at SIGGRAPH in 2006 and is implemented in AMD’s\u00a0Tootle<\/a>\u00a0mesh optimization library.<\/p>\n Although I said that overdraw is a reasonable consideration in picking a triangle order, I get the impression that overdraw optimization is still pretty uncommon in games. \u00a0There is good cause for skepticism about the value of overdraw optimization, since it has yet to be demonstrated conclusively that it works. \u00a0Hardware implementations of early-z cull vary widely and aren’t well documented, so it is difficult to construct an a priori argument in favor of overdraw optimization. \u00a0One obvious concern is that hardware pipelines are getting deeper, and there is no guarantee that depth output from one triangle will even be available to the z-cull unit in time to affect other triangles in the same mesh. \u00a0Rather than deal with these issues, many game developers choose instead to render an explicit z prepass. \u00a0A z prepass ensures zero overdraw in fragment processing but adds significant additional CPU setup and GPU vertex processing cost.<\/p>\n There is still plenty of room for improvement in techniques for overdraw optimization of triangle order, but what this field really needs is a comprehensive evaluation of the advantages of overdraw optimization. \u00a0Until someone can show that real-world games can reap real-world benefits, there isn’t going to be much interest in overdraw minimizing triangle orders.<\/p>\n A second possible consideration in picking a triangle order, and by far the most common one, is making good use of the post-transform vertex cache. \u00a0Whether you’re sorting whole meshes at once or subsets from your overdraw optimization pass, there is usually plenty of room for minimizing vertex processing work. \u00a0The concept is pretty simple; indexed triangle meshes allow the same vertex to be used in multiple triangles. \u00a0Most graphics hardware provide a small cache of recently processed vertices so that when the same index is used more than once the “transformed” vertex can be pulled from the cache rather than being processed again. \u00a0The effectiveness of the post-transform cache is measured by counting how many vertices must be transformed on average per triangle. \u00a0This number is known as the “average cache miss ratio” or ACMR. \u00a0For a mesh with no vertex reuse the ACMR is obviously 3.0. \u00a0Most meshes however exhibit a lot of vertex reuse and for large meshes an ACMR under 1.0 is not uncommon. \u00a0The ACMR for a mesh is dependent on the number of entries in the post-transform cache and, for meshes with more vertices than cache entries, it is dependent on the order in which the vertices are used. \u00a0Luckily for hardware designers, it turns out that there are pretty steeply diminishing returns in ACMR for increasing cache sizes, assuming an optimal vertex order. \u00a0As long as software developers do their jobs and provide meshes with optimized triangle orders, the hardware can achieve near-optimal ACMR values with a modest-sized cache. \u00a0Consequently, the graphics chips I work with typically have between 10 and 24 entries in the post-transform cache.<\/p>\n Post-transform cache optimization has been well researched and many consider it to be a solved problem. \u00a0The top optimization algorithms generally yield ACMRs within a few percent of one another and within a few percent of optimal across a wide range of cache sizes. \u00a0Even algorithms that are cache size aware are generally tolerant of varying cache sizes and continue to provide competitive results. \u00a0This is probably because at their hearts most of the modern algorithms are the same. \u00a0To achieve good runtime performance they are greedy algorithms that employ a heuristic to select vertices that will maximize hits in a simulated cache. \u00a0These days it doesn’t make much sense to implement your own solution for post-transform cache optimization. \u00a0There are too many good libraries available for free and too small a gap between them and the theoretical ideal.<\/p>\n I recently had the opportunity to compare some of the front-runners in this field. \u00a0I took four competing algorithms for post-transform cache optimization and ran them on the mesh libraries for two games. \u00a0The complete test bed was over 19 million triangles in 25 thousand meshes, and it included plenty of the sort of low-poly, flat-shaded rocks and table legs that cache optimizers hate. \u00a0I timed the results and computed ACMR values for a range of cache sizes. \u00a0The algorithms I compared were Direct3D’s D3DXOptimizeFaces function which I believe is based on Hugues Hoppe’s work<\/a>, my own implementation\u00a0of Tom Forsyth’s “Linear-Speed Vertex Cache Optimization<\/a>” algorithm, AMD’s implementation of the “Tipsy<\/a>” algorithm in Tootle, and a third-party implementation of Gang Lin and Thomas P.-Y. Yu’s K-Cache<\/a> algorithm. \u00a0Since Forsyth’s algorithm takes as a parameter the size of the simulated cache and Tipsy takes as a parameter the size of the targeted cache, I tested each algorithm multiple times with appropriate values. \u00a0Here are the results:<\/p>\n ACMR at various cache sizes\r\n Time (secs) 10 14 18 24 32\r\n-----------------------------------------------------------------------------\r\nNone 0.00 1.613 1.554 1.507 1.458 1.416\r\nForsyth-32 131.27 1.235 1.216 1.208 1.203 1.200\r\nForsyth-64 139.18 1.240 1.215 1.206 1.200 1.196\r\nD3DX 20.05 1.276 1.227 1.220 1.214 1.210\r\nTootle-14 7.87 1.281 1.232 1.224 1.216 1.209\r\nTootle-16 7.55 1.288 1.235 1.220 1.213 1.207\r\nTootle-32 7.50 1.302 1.260 1.236 1.214 1.198\r\nK-Cache 413.36 1.256 1.232 1.219 1.208 1.204<\/pre>\n