DiagSplit: Parallel, Crack-Free, Adaptive Tessellation for Micropolygon Rendering

As hoped, we just kicked another micropolygon-related paper out the door. We've been working on a parallel algorithm for generating micropolygons via adaptive tessellation for the past year and the result of this study is an algorithm that we've called DiagSplit.

DiagSplit is an implementation of Split-Dice with two interesting modifications. First, instead of what many consider to be the "traditional Reyes" dicer that generates tensor-product UV grids of quadrilateral micropolygons, DiagSplit's dicing step is the D3D11 Tessellation stage. Thus, it produces slightly irregular meshes as output. Second, to get everything to work without creating cracks, the splitting process must sometimes split subpatches along non-isoparametric directions. In other words, the algorithm sometimes makes diagonal splits in parametric space (hence the name DiagSplit).

DiagSplit is intended for tight integration with the real-time graphics pipeline. In the short term, an implementation might do all the splitting on the CPU or within a compute shader, then ship diceable subpatches (not final triangles) over to the graphics pipeline for all the heavily lifting of dicing and surface evaluation. We've really designed DiagSplit for even tighter integration with future graphics pipelines and can imagine the entire adaptive splitting process being implemented in the pipeline itself with only a few extensions to D3D11. For those interested in an early read, the final draft of the paper, which will appear in SIGGRAPH Asia 2009, has been placed online here.

Paper Abstract:

We present DiagSplit, a parallel algorithm for adaptively tessellating displaced parametric surfaces into high-quality, crack-free micropolygon meshes. DiagSplit modifies the split-dice tessellation algorithm to allow splits along non-isoparametric directions in the surface's parametric domain, and uses a dicing scheme that supports unique tessellation factors for each subpatch edge. Edge tessellation factors are computed using only information local to subpatch edges. These modifications allow all subpatches generated by DiagSplit to be processed independently without introducing T-junctions or mesh cracks and without incurring the tessellation overhead of binary dicing. We demonstrate that DiagSplit produces output that is better (in terms of image quality and number of micropolygons produced) than existing parallel tessellation schemes, and as good as highly adaptive split-dice implementations that are less amenable to parallelization.