Code: Fast/Simple Terrain Smoothing Function

Reposted from the original ETM thread:

KISS smoothing function:
ET::Brush Area::averageFilter(int x, int z, ET::Brush shape, float fIntensity)
{
// When you're doing a loop possibly thousands of times, it's worth setting these
// aside rather than calling a function every iteration.
size_t iWidth = shape.getWidth();
size_t iHeight = shape.getHeight();

// Faster to presize than resize
std::vector<float> vecReturnBuffer(iWidth * iHeight);
std::vector<float> vecHeightBuffer(iWidth * iHeight);
ET::Brush brushReturn = ET::Brush(vecReturnBuffer, iWidth, iHeight);
ET::Brush brushHeights = ET::Brush(vecHeightBuffer, iWidth, iHeight);

m_terrainMgr->getHeights(x, z, brushHeights);

float fSumHeights = 0.0f;
size_t iNumHeights = iWidth * iHeight;

// Find the sum of all the heights within the sample
for (Ogre::uint i = 0; i < iWidth; i++)
{
for(Ogre::uint j = 0; j < iHeight; j++)
{
fSumHeights += brushHeights.at(i, j);
}
}

// Find the average height within the sample
float fAvgHeight = fSumHeights / iNumHeights;

for (Ogre::uint i = 0; i < iWidth; i++)
{
for(Ogre::uint j = 0; j < iHeight; j++)
{
float fHeight = brushHeights.at(i, j);
float fDelta = fHeight - fAvgHeight;
float fShapeMask = shape.at(i, j);

fDelta = (fDelta * fShapeMask * fIntensity);

brushReturn.at(i, j) = fHeight - fDelta;
}
}

return brushReturn;
}

Stupid, fast.

It's simply checking the average height of the sample and applying it, modified by brush intensity and a passed intensity (to allow you to give the user a slider or somesuch to adjust intensity.)

This algorithm behaves similarly to the one in the NWN2 toolset that you mentioned previously and smooths well until brush size reaches around 60ish (debug build), then it struggles. YMMV as far as performance though.

------
Edit: Forgot this bit...

I suggest generating your intensity to pass to the averageFilter similar to the intensity calculations in CABAListic's ETM demo:
float brushIntensity = (m_fFrameTime / 1000) * 2.0 * (m_lMouseDown? 1 : -1);
brushIntensity *= m_fVarIntensity;

// translate our cursor position to vertex indexes
Ogre::Vector3 smoothPos = m_cursor->getPosition();
int x = info->posToVertexX(smoothPos.x);
int z = info->posToVertexZ(smoothPos.z);

m_currentArea->smooth(x, z, m_editBrush, brushIntensity);
Where:
- m_fFrameTime is the time it took to render the last frame in milliseconds
- m_fVarIntensity is the value of that slider provided to the user that I mentioned earlier.
- m_lMouseDown is a bool storing whether the left mouse button is pressed
- m_editBrush is the brush currently being used for editing.
- and where m_currentArea->smooth is the following function:
void Area::smooth(int x, int y, const ET::Brush& brush, float fIntensity)
{
ET::Brush smooth = averageFilter(x, y, brush, fIntensity);
m_terrainMgr->setHeights(x, y, smooth);
}

A few notes:

1. - Letting the RMB make the intensity negative results in a cool "Expansion" effect, where stuff that was far from the average height gets farther, as opposed to the positive "compression" effect where stuff that is far from average height gets closer.
   - Okay, so it was only one note... but if I think of something later, I'll add it here![/list:u]

I originally used this approach in my editor, but there is a flaw in its behaviour you need to be aware of: It only takes values into account which are inside the smoothing region and can therefore produce edges at the borders. Consider a flat plane with a single circular mountain at the center. If you now smooth some region including the mountain via average heights, then the height values in your smoothing region will be adjusted to some average height between the plane's and the mountain's height - this will result in a plateau on your plane.

This may or may not be what you want, for me it wasn't. A more sophisticated approach which I already mentioned in the showcase thread would be box filter. Query the heightmap for a region that is slightly larger than the region you want to update, then adjust each height value by averaging with their direct neighbours. This should keep the edges in touch. Obviously, though, the box filter will require more processing power...

I originally used this approach in my editor, but there is a flaw in its behaviour you need to be aware of: It only takes values into account which are inside the smoothing region and can therefore produce edges at the borders. Consider a flat plane with a single circular mountain at the center. If you now smooth some region including the mountain via average heights, then the height values in your smoothing region will be adjusted to some average height between the plane's and the mountain's height - this will result in a plateau on your plane.

This may or may not be what you want, for me it wasn't. A more sophisticated approach which I already mentioned in the showcase thread would be box filter. Query the heightmap for a region that is slightly larger than the region you want to update, then adjust each height value by averaging with their direct neighbours. This should keep the edges in touch. Obviously, though, the box filter will require more processing power...

Yeah, I started out using the box filter but found it unacceptably slow at large brush sizes.

The trick to getting good(ish) results from the average method is to do it really really slow (which is why I suggest using the constants that I did when calling the method.) This allows the user to "wave" or "brush" the.. uh, brush around the general area they want to smooth to obtain a more organic smoothing effect.

----

Another reason I went with this method is that it allows the user to create a plateau (as you said) by using a higher intensity (or just holding it in the same spot for a while) to place objects like buildings and such upon.

----

In conclusion, the box filter method is a smarter algorithm. This one is stupid fast. I can make my brush 64x64 and smooth a whole mountain range without killing my framerate so badly that it becomes unusable.


So, in conclusion, there are pro's and cons of both, this is the one I decided I liked for my purposes. As always, YMMV.

Of course. Just wanted to mention it so that someone searching for a smoothing algorithm has some ideas of the pros and cons of each method

Here is the box filter algorithm posted by user tdev in the original ETM thread.

enum SmoothSampleType {SST_Small, SST_Large};
ET::Brush boxFilterPatch(int x, int z, int w, int h, enum SmoothSampleType type, ET::Brush intensity);
float buildFactor(ET::Brush heights, int x, int y, float &factor);



float buildFactor (Brush heights, int x, int y, float &factor)
{
if(x >= 0 && x < (int)heights.getWidth() && y >= 0 && y < (int)heights.getHeight())
{
factor += 1.0;
return heights.at(x, y);
}

return 0.0f;
}

Brush boxFilterPatch(int x, int z, int w, int h, enum SmoothSampleType type, Brush intensity)
{
std::vector<float> retBuf;
retBuf.resize(w*h);
std::vector<float> heightsBuf;
heightsBuf.resize(w*h);
Brush ret = Brush(retBuf, w, h);
Brush heights = Brush(heightsBuf, w, h);

mTerrainMgr->getHeights(x, z, heights);
for (uint ix = 0; ix < heights.getWidth(); ix++ )
{
for(uint iy = 0; iy < heights.getHeight(); iy++)
{
int px1 = (int)ix - 1, px2 = (int)ix + 1;
int py1 = (int)iy - 1, py2 = (int)iy + 1;

float height = heights.at(ix, iy);

float final = 0.0f;
float factor = 0.0f;

// Sample grid
// 1 4 7
// 2 5 8
// 3 6 9

if(type == SST_Large) {
final += buildFactor (heights, px1, py1, factor); // 1
final += buildFactor (heights, px1, py2, factor); // 3
final += buildFactor (heights, px2, py1, factor); // 7
final += buildFactor (heights, px2, py2, factor); // 9
}

final += buildFactor (heights, (int)ix, (int)iy, factor); // 5

final += buildFactor (heights, px1, (int)iy, factor); // 2
final += buildFactor (heights, (int)ix, py1, factor); // 4
final += buildFactor (heights, (int)ix, py2, factor); // 6
final += buildFactor (heights, px2, (int)iy, factor); // 8

final /= factor;
float delta = height - final;
float intens = intensity.at(ix, iy);
if(intens > 0.0f) {
delta *= intens;
}

final = height - delta;
ret.at(ix, iy) = final;
}
}

return ret;
}

Note (SotW):
The following line should probably be removed from the above snippet unless there's a good reason for it (like, it causes a div by zero error or something.) I'm not using this algorithm so I'm not sure if it is required.

if(intens > 0.0f) {

And of course the closing brace should be removed as well if you remove the if statement. The code inside the braces should remain.

If left in this if statement results in the "shape" of the brush being ignored and a square being smoothed regardless of brush shape.


how you could use it:
void smooth(Ogre::Vector3 pos, SmoothSampleType type)
{
int x = terrainInfo->posToVertexX(pos.x);
int z = terrainInfo->posToVertexZ(pos.z);
Brush smooth = boxFilterPatch(x, z, 16, 16, type, mEditBrush);
mTerrainMgr->setHeights(x, z, smooth);
}