Ok, I suspect your familiar with the first part, the optimal tesselation of the terrain into smaller and smaller tris while the screen error is above a certain metric defined by the distance from camera and your viewradius settings. If not, here is the 100% accurate review of how ROAM works, and how this implementation functions:
http://www.gamasutra.com/view/feature/3 ... etail_.php
This isnt the first stripping method we used. The first was pushing each tri as a separate primitive. Slow, clunky, excessive cpu overhead.
The second one stripped the tris based on neighbouring relationships, doing quasi random walks on the triangles. Canned due to avg only 16 tris per strip.
This third one uses a wholly different approach, illustrated by the following paint masterpiece:
Each patch of terrain (128*128 hmap pixels) is split into 2 base triangles, one for top left, one for bottom right. The image above only contains top left, but the process is identical for bottom right.
All triangles created during tesselation are right angle tris, and there are no T junctions.
So I make a linked list, with the first element containing the bottom left coords of the base tri, and the second (and last) element contains the top right. Then I pass the link to first element to the recursive stripper. The recurse stripper then inserts the coords of the apex of the triangle after the link passed into the linked list. Then if the triangle is not a leaf node, then it passes the first link to the left child, and the apex link to the right child.
After the recursion finishes, I read out the corresponding vertexes from the list into an array, and store the array as only the array needs to be pushed when when the cam isnt changed. This is also the part that seems to introduce the flickering bug. If I read out the list, and push the read, it doesnt flicker, If i just push the read array, it flickers.
This solution results in 2n+2 vertexes for the n tris in a single strip.
The ugly hack part of the solution is the following:
This algo does not do proper winding of triangles, so approx 50% of tris end up facing the other side. So I do a glDisable(GL_CULL_FACE) before the rendering, and enable it back after map render is complete.
The reason I still chose this method, is that it generates only 2 strips per patch, and is linear time.
For me, it results in correct stripping:
But your GPU seems to discard or cull tris differently, since i can see from your screenies that you have tris that arent right angled tris.
My screenshot of the wiremap when turning backface culling on is this:
All of my tris are right angled tris.
Here is the code for stripping a half triangle of a patch:
Code: Select all
void Patch::RecursRender2(TriTreeNode *tri, int leftX, int leftY, int rightX,
int rightY, int apexX, int apexY, int n, int insertafterthis, bool dir)
{
lstrip[lend].x=apexX;
lstrip[lend].y=apexY;
lstrip[lend].next=lstrip[insertafterthis].next;;
lstrip[insertafterthis].next=lend;
lend++;
if (tri->LeftChild) // All non-leaf nodes have both children, so just check for one
{
int centerX = (leftX + rightX) >> 1; // Compute X coordinate of center of Hypotenuse
int centerY = (leftY + rightY) >> 1; // Compute Y coord...
int tmp=lstrip[insertafterthis].next;
if(rightX==lstrip[insertafterthis].x&&rightY==lstrip[insertafterthis].y){
RecursRender2(tri->RightChild, rightX, rightY, apexX, apexY, centerX,centerY, n,insertafterthis,dir);
RecursRender2(tri->LeftChild, apexX, apexY, leftX, leftY, centerX, centerY, n,tmp,dir);
}else if(apexX==lstrip[lstrip[insertafterthis].next].x&&apexY==lstrip[lstrip[insertafterthis].next].y){
RecursRender2(tri->RightChild, rightX, rightY, apexX, apexY, centerX,centerY, n,tmp,dir);
RecursRender2(tri->LeftChild, apexX, apexY, leftX, leftY, centerX, centerY, n,insertafterthis,dir);
}
}
}
EDIT: Fixed the flickering! Please pull from git again! (caused by a badly passed pointer) May have also caused the bad stripping seen by Kloot.