Re: [Algorithms] Terrain Normals

[Peter D. <pd...@mm...>]

> Also, could you briefly explain the reasoning of the normal-generating
> algorithm you suggested as follows?  A high-level, general idea is fine.
:-)

Brief explanation:

The surface partial derivatives are approximated with central differences;
the normal is computed by normalizing the cross product of the tangential
vectors.

More elaborate explanation:

Assume that the height field represents a regularly sampled smooth surface y
= F(x, z). To compute the tangential vectors to this surface we need to
approximate the partial derivatives dF/dx and dF/dz. I have chosen to use
central differences

dF/dx ~= ( F(x+a) - F(x-a) ) / (2 a)

instead of the more widely used forward differences

dF/dx ~= ( F(x+a) - F(x) ) / a

because the central difference is exact for degree 2 polynomials
(ax^2+bx+c), while the forward/backward version is exact for linear
functions (ax+b), and heightfields (including bumpmaps) are much better
approximated by the former.

So, we compute

nx = height(x-1, z) - height(x+1, z)
nz = height(x, z-1) - height(x, z+1)

(note that the signs are reversed)

and

dF/dx ~= - nx / 2a
dF/dz ~= - nz / 2a

where a is the distance in world units between two adjacent vertices of the
grid, i.e. the grid spacing.

The tangential vectors are

vx = (1, - nx / 2a, 0)
vz = (0, - nz / 2a, 1)

and their cross product is

v = (nx / 2a, 1, nz / 2a).

The only thing left is to normalize v. Note that to avoid the two divisions
we may compute v' = 2av = (nx, 2a, nz) instead, because it's going to be
normalized anyway.

Hope this helps.

--
Peter Dimov
Multi Media Ltd.

(code left for reference)

> > void VertexNormal(
> >     Vector3& normal,
> >     long col,
> >     long row,
> >     float gridSpacing)
> > {
> >     float nx, nz, denom;
> >
> >     if (col > 0 && col < m_fieldSize - 1)
> >     {
> >         nx = GetElev(col - 1, row) - (col + 1, row);
> >     }
> >     else if (col > 0)
> >     {
> >         nx = 2.0f * (GetElev(col - 1, row) - GetElev(col, row));
> >     }
> >     else nx = 2.0f * (GetElev(col, row) - GetElev(col + 1, row));
> >
> >     if (row > 0 && row < m_fieldSize - 1)
> >     {
> >         nz = GetElev(col, row - 1) - GetElev(col, row + 1);
> >     }
> >     else if (row > 0)
> >     {
> >         nz = 2.0f * (GetElev(col, row - 1) - GetElev(col, row));
> >     }
> >     else nz = 2.0f * (GetElev(col, row) - GetElev(col, row + 1));
> >
> >     gridSpacing *= 2.0f;
> >
> >     denom = 1.0f / sqrt(nx * nx + gridSpacing * gridSpacing + nz * nz);
> >
> >     normal.x = nx * denom;
> >     normal.y = gridSpacing * denom;
> >     normal.z = nz * denom;
> > }