I spent about two hours finding and fixing a nasty bug in my ROAM terrain tessellator. The symptom was the RIB generator complaining about negative polygon vertex indices. This was very strange because the ROAM system should never produce invalid geometry. The problem only occurred when the bucket-sorting stage was enabled. This is an optional post-processing step that runs after terrain generation; it breaks the monolithic terrain mesh into a number of smaller spatially-coherent meshes, making it easier for PRMan to “digest.” The sorter creates new vertex and index arrays for each output mesh, including only the polygons and vertices referenced by each mesh. In order to maintain the same sharing of indices with the big input mesh, the sorter uses a temporary array to track the new index it gives to each vertex that is pulled from the input mesh. The temporary array is looked up by index, so it must be large enough to contain the greatest-valued index as a valid element. This is where I found the bug. The sorter chooses the size of the array to be the same as the size of the index array on the input mesh. This makes a hidden assumption that the input mesh is not sparse, i.e., it does not contain any index values greater than the size of the index array itself. This assumption no longer holds because I recently added an optimization to the ROAM tessellator that culls polygons outside the camera frustum. It deletes the polygons but leaves their vertices in the vertex array. The resulting meshes are “sparse,” so this was fouling up the bucket sorter. The fix was simply to size the temporary index mapping array as big as the greatest index value seen in the input mesh.