|
This document is not complete, I am still slowly adding to it when I have free time... I developed this algorithm a long time ago and never used it for anything, so I don't actually have any detailed documentation on it yet. Right now this is more a brain dump than a "paper". So read at your own risk. Eye Candy some old video capture screenshot1 - Low resolution to demonstrate a large delta in LOD quality over distance and terrain roughness. Overview The Flip-Flop level of detail algorithm for heightfield terrain is a byproduct of my work on Fatal Traction. While ultimately I used a pre-computed RTIN (right triangle irregular network) due to time constraints, I had also come up with a few ideas for generating the optimized view dependent mesh. Flip-Flip is probably one of the most useful variations... Advantages: - It requires no additional per-vertex memory, so its quite cheap memory wise. - It never does any per-vertex, per-index or per-triangle computation on the CPU so its easily faster than most non-chunked algorithms. - It doesn't need "skirting" (extra polygons added to hide the fact there are holes in the geometry). Which means better visual quality than most chunked algorithms at lower resolutions. - It outputs chunks of Right Triangles that fit perfectly with its neighbors. - The actual LOD logic is entirely integer based! - Uses an iterative approach. So it can take advantage of coherence between frames. - It can compute a LOD level from start to finish very fast. Fast enough that it probably doesn't matter that it takes advantage of coherence. Disadvantages: - Detail changes are not per-triangle but per-cell, meaning that if you want a small region to be very high precision, you tend to waste more triangles than you would with something like ROAM. - Geomorphing is slightly more difficult to implement. Data Constraints - The heightfield is broken up into square chunks. So the only limit on the input data is that it must fit "(heightfieldSize-1) == (chunkSize-1) * numChunks" for a given axis. - Rectangular terrains are fine. - Chunks do have to be power of two +1... For example, in my tests I settled on 65x65 for the chunk size. - Chunks must be square. The Algorithm For reasons of simplicity, I will be describing the algorithm without any major optimizations... there are several easy wins on both memory and performance, but with that said, out of the box this is pretty memory efficient and optimal. Code provided here isn't meant to compile, consider it pseudo code with C++ like syntax. Flip-Flop is a chunk based algorithm but with a twist. Rather than pre-computing a large set of meshes for each chunk and then just picking different versions of the mesh based on distance, we pre-computer a fixed number of index buffers that can be shared amongst all chunks. The idea being that we "choose wisely" which index buffer to use with each chunk based on which one the neighboring chunks use with the goal of rendering a seamless mesh with no T-junctions or gaps with resolution variations based on both roughness and distance to the viewer. In order to understand the rest of this paper you need to know a few definitions: - Chunk : a square selection of the heightfield. Each Chunk is equal to one draw call. A chunk contains its own vertex buffer which it does not share with any other chunk, and pointer to an index buffer, which it shares with the rest of the chunks. The current value of this index buffer point is what defines the tessellation and number of triangles rendered at any given time. - Cell : this is what we call the 4 LOD levels that make up a Chunk. A Chunk has 4 levels so that we can basically adjust the resolution of the mesh slightly form one side of the Chunk to the other... this concept allows for a seamless final mesh. One of the key bits is mapping the LOD levels from cells to chunks... this is actually fairly simple and it doesn't particularly matter how you do it as long as you are consistent and avoid any "collisions" (that is to say, no two unique input sets to this function can yield the same output). The function I used looks something like this:
uint32 calcChunkLOD(uint32 north, uint32 east, uint32 south, uint32 west)
{
uint32 n = north;
uint32 e = m_numLods * east;
uint32 s = m_numLods * m_numLods * south;
uint32 w = m_numLods * m_numLods * m_numLods * m_numLods * west;
return n+e+s+w;
}
In this function 'm_numLods' is the number of possible LOD levels that a cell can have. The 'north'/'east'/'south'/'west' values are the cell LOD levels for the given chunk. So now you probably are wondering, what does a cell LOD level represent? A cell's LOD value basically represents its inverse geometric mip level... for instance, a cell LOD of 0 basically means that cell will be 1 triangle while LOD 1 will be 2 triangles and so forth. The number of triangles needed for a given cell LOD == 1 << cellLODLevel;  Figure 1: Diagram showing only the tessellation of the East cell LOD levels 0 through 2. In Figure 1 there are a few things that you should take notice of... First, when we split the triangles of a cell, we split such that we add a vertex in the middle of the hypotenuse. Second, Each Odd level adds a new vertex along the External edges (edges that border cells of neighboring chunks). Third, each Even level (except level 0) adds a new vertex along the Internal edges (edges that border cells within the same chunk). Given these observations, there are a few rules we can now force on our cell levels in order to guarantee a hole-free terrain. First, for all cell pairs (cells that border each other), their LOD levels must be equal or have a difference of 1. Second, for Internal cell pairs, the cell with the lowest LOD must be Even. Third, for External cell pairs, the cell with the lowest LOD must be Odd. Now, lets write some functions for testing cell pair validity...
bool isValidInternalPair(uint32 a, uint32 b)
{
bool valid = false
if(a == b) // are these LODs the same?
{
valid = true;
}
else if(a^b == 1 && (min(a,b) & 1) == 0) // are these LODs only different by 1 and the lowest LOD is Even?
{
valid = true;
}
return valid;
}
bool isValidExternalPair(uint32 a, uint32 b)
{
bool valid = false
if(a == b) // are these LODs the same?
{
valid = true;
}
else if(a^b == 1 && (min(a,b) & 1) == 1) // are these LODs only different by 1 and the lowest LOD is Odd?
{
valid = true;
}
return valid;
}
bool isValidChunk(uint32 north, uint32 east, uint32 south, uint32 west)
{
bool valid = false;
if(isValidInternalPair(north, east) && isValidInternalPair(east, south) &&
isValidInternalPair(south, west) && isValidInternalPair(west, north))
{
valid = true;
}
return valid;
}
We now know how to build the indices for a cell, but how do we build the index buffer for a chunk at a given LOD? This is actually quite simple and is only needed to be done at load time. Basically, we just concatenate the indices for each cell into the index buffer of the chunk... it should look something like this:
for(uint32 north=0; north<m_numLods; north++)
for(uint32 east =0; east <m_numLods; north++)
for(uint32 south=0; south<m_numLods; north++)
for(uint32 west =0; west <m_numLods; north++)
{
if(isValidChunk(north, east, south, west)) // check to see if these cells can be validly combined.
{
uint32 chunkLOD = calcChunkLOD(m_numLods, north, east, south, west);
IndexBuffer *indices = new IndexBuffer;
// TODO: build the index lists of each cell here and just append them to the 'indices' IndexBuffer...
chunkIndexBufferArray[chunkLOD] = indices;
}
}
So, we now know what a cell looks like for a given level, and we know how to map between 4 cell LODs into a single chunk LOD, and we know that a given chunk LOD's index buffer is just the concatenation of indices of the 4 cell LODs that map to it. So, the question that is left, how do we decide what cell LODs to use across our terrain such that there is variation in detail without holes forming in the terrain? There is a lot of flexibility as in this area, but the general concept is, you pick your desired LOD for each cell (based on that cell's roughness, distance to the camera, and anything else you might care about in your game), and then run some sort of simplified filter over all your chunks to make sure all the cells are valid. In my tests, I would query a quad-tree for visible chunks and then set each visible chunk's cell's LOD based on distance to camera, and a pre-computed roughness value (basically, how bumpy the heightfield is in that cell) then ran the following filter on my chunks.
// check validity of thisCell to thatCell... if thisCell is less than the minimum LOD of thatCell's pair
// we return the minimum allowed LOD.
uint32 incrementInternalCell(uint32 &thisCell, uint32 thatCell)
{
uint32 flip = 0;
if(!isValidInternalPair(thisCell, thatCell))
{
uint32 minlod = thatCell & ~1;
if(thisCell i< minlod)
{
thisCell = minlod;
flip = 1;
}
}
return flip;
}
// check validity of thisCell to thatCell... if thisCell is less than the minimum LOD of thatCell's pair
// we return the minimum allowed LOD.
uint32 incrementExternalCell(uint32 &thisCell, uint32 thatCell)
{
uint32 flip = 0;
if(!isValidInternalPair(thisCell, thatCell))
{
uint32 minlod = !thatCell || thatCell & 1 ? thatCell : thatCell-1;
if(thisCell i< minlod)
{
thisCell = minlod;
flip = 1;
}
}
return flip;
}
// this is basically a brute force version of the filter, but it gets the point across.
void updateLOD(void)
{
while(1) // we iterate until the terrain is hole-free.
{
uint32 numFlips = 0;
for(uint32 i=0; i<m_chunks.size; i++)
{
Chunk chunk = m_chunks[i];
// flip
numFlips += incrementInternalCell(chunk.north, chunk.east);
numFlips += incrementInternalCell(chunk.north, chunk.west);
numFlips += incrementInternalCell(chunk.east, chunk.south);
numFlips += incrementInternalCell(chunk.east, chunk.north);
numFlips += incrementInternalCell(chunk.south, chunk.west);
numFlips += incrementInternalCell(chunk.south, chunk.east);
numFlips += incrementInternalCell(chunk.west, chunk.north);
numFlips += incrementInternalCell(chunk.west, chunk.south);
uint32 row = GET_ROW(m_numChunkCols, i);
uint32 col = GET_COL(m_numChunkCols, i);
if(row>0) numFlips += incrementExternalCell(chunk.north, m_chunks[GET_INDEX(m_numChunkCols, col, row-1)].south);
if(col<m_numChunkCols-1) numFlips += incrementExternalCell(chunk.east, m_chunks[GET_INDEX(m_numChunkCols, col+1, row)].west);
if(row<m_numChunkRows-1) numFlips += incrementExternalCell(chunk.south, m_chunks[GET_INDEX(m_numChunkCols, col, row+1)].north);
if(col>0) numFlips += incrementExternalCell(chunk.west, m_chunks[GET_INDEX(m_numChunkCols, col-1, row)].east);
}
if(numFlips == 0) break;
}
}
As you can see in the filter above, its actually a fairly brute force filter that will continuously adjust cell values over and over until the terrain is hole free. Now, in reality, in my tests it usually only takes 2 or 3 iterations to complete so it's not too insane. One of the keys here is that we always increase LOD values (you could adjust it to always decrease depending on if you favor quality or performance), but by making sure we always move the LOD values in one direction, we drasticly reduce the number of iterations it takes to complete. While double buffering the cell LODs would allow for a single iteration filter, I found that the performance hit by this brute force approach wasn't significant. |