Discussion:
bump map from normal map ?
(too old to reply)
New Guy
2006-04-30 00:26:29 UTC
Permalink
Is it possible to go backwards, and (re)create a (correct) height map from
a normal map? Is there any code already out there that does this?

Thanks.
fungus
2006-04-30 08:37:01 UTC
Permalink
Post by New Guy
Is it possible to go backwards, and (re)create a (correct) height map from
a normal map?
It sounds nice but in practice I suspect it would
be very inaccurate.
Post by New Guy
Is there any code already out there that does this?
Try comp.graphics.algorithms
--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.

In science it often happens that scientists say, 'You know
that's a really good argument; my position is mistaken,'
and then they actually change their minds and you never
hear that old view from them again. They really do it.
It doesn't happen as often as it should, because scientists
are human and change is sometimes painful. But it happens
every day. I cannot recall the last time something like
that happened in politics or religion.

- Carl Sagan, 1987 CSICOP keynote address
Wolfgang Draxinger
2006-04-30 12:58:58 UTC
Permalink
Post by New Guy
Is it possible to go backwards, and (re)create a (correct)
height map from a normal map?
Theoretically: Yes.
A normal map represents the partial derivates of the height/bump
map. To get the height map back you have to integrate the total
differential. The total differential is the sum of all partial
derivates.

Now the problem: Usual normal maps have 8 bits precision per
channel/vector component. This is too low for numerical
integration. Allthough there is the HiLo format avaliable
(explicitly designed for normal maps BTW) almost nobody uses
them.

One thing you could do is to remap each normal map pixel into
[0.0; 1.0]^3 vectors and normalize each of them. Then use those
as input to a integration algorithm.
Post by New Guy
Is there any code already out there that does this?
None that I'm aware of, mainly because for normal maps there are
usually the corresponding height maps avalaible, too. Some
algorithms (e.g. for horizon clipped or steep parallax mapping)
need both normal and height map to work.

Wolfgang Draxinger
--
Dave Eberly
2006-04-30 17:01:33 UTC
Permalink
Post by New Guy
Is it possible to go backwards, and (re)create a (correct) height map from
a normal map? Is there any code already out there that does this?
Some posters have already hinted at the difficulties of
reconstructing the height map. The relevant issues in
constructing the normal map from a height field are:
1. The normal vectors are formulated treating x and y
as real-valued variables ("continuous" variables).
2. The expressions involve partial derivatives of the
height function. Finite differences are used to
approximate the derivatives from the height values.
Now you have "discrete" variables (the two-dimensional
indices into the height map image) to deal with.
3. A decision must be made about how to estimate the
partial derivatives at the boundaries of the domain
of the height function.
4. Adjustments to the process might have been made. For
example, a normal-map construction might allow scaling
of the height field or of the domain variables themselves.
The problem is that you generally are not given the specific
information in items 2, 3, or 4 for a particular normal map
image.

That said, you can still create algorithms that, hopefully, will
get you close enough to the original.

Using real-valued variables, the height field is z = H(x,y). The
graph is a surface defined implicitly by 0 = F(x,y,z) = z - H(x,y).
The gradient of F is normal to the surface,
gradient(F) = (-dH/dx, -dH/dy, 1)
where dH/dx and dH/dy are the first-order partial derivatives
of H. Unit-length normals are
N = (-dH/dx, -dH/dy, 1)/L = (N0,N1,N2)
where L^2 = 1 + (dH/dx)^2 + (dH/dy)^2. The reconstruction
problem is: Given normal vectors N, construct the height field H.
It is simple to show that
dH/dx = -N0/N2, dH/dY = -N1/N2

As Wolfgang pointed out, this is an integration problem--given
the first-order partial derivatives of H, compute H. This topic
is encountered in an undergraduate class in differential equations.
If you have dH/dx = A and dH/dy = B for any two continuously
differentiable functions A and B, it is not always possible that
such an H exists. For it to exist, you need an "exactness"
condition: dA/dy = dB/dx. All this says is that if you differentiate
dH/dx with respect to y, you need to get the same thing as
differentiating dH/dy with respect to x. Knowing that N was
created from the graph of a function H, the exactness condition
is necessarily true.

So far so good, but a "red herring". The normal map was created
by approximating derivatives with finite differences, taking you
from the continuous-variable setting to a discrete-variable setting.
You do not have continuous representations for A = -N0/N2 or
B = -N1/N2, so there is no "integration" so to speak here.
What you really have is a problem in solving a linear system
of equations where the coefficient matrix is large and sparse.

This brings us to item 2 in my list. The choices people make for
the finite-difference approximations are not always the same. If
you look at NVidia's Cg Tutorial book, the authors use one-sided
differences. The equalities I have here are so supposed to indicate
approximations. Also, for notation's sake, I will use H_x(x,y) as
dH/dx at (x,y) and H_y(x,y) = dH/dy at (x,y).
H_x(x,y) = (H(x+dx,y) - H(x,y))/dx
H_y(x,y) = (H(x,y) - H(x,y+dy))/dy
where dx > 0 and dy > 0 are small numbers. Since the only height
information available is from the height-map image, you think of
(x,y) as a pixel location and H(x,y) as the image value at that
location. Moreover, it is simplest to choose dx = 1 and dy = 1
so that you use neighboring pixels.
H_x(x,y) = H(x+1,y) - H(x,y)
H_y(x,y) = H(x,y+1) - H(x,y)
where 0 <= x <= xmax-2 and 0 <= y <= ymax-2. The image has xmax
columns and ymax rows. You have to decide what to do at
x = xmax-1, y = ymax-1. One choice is to use
H_x(xmax-1,y) = H_x(xmax-2,y)
H_y(x,ymax-1) = H_y(x,ymax-2)
Another choice is to allow wrap around, the idea being that an
adjacent height field must match the current one at the boundary.
H_x(xmax-1,y) = H(0,y) - H(xmax-1,y)
H_y(x,ymax-1) = H(x,0) - H(x,ymax-1)

I use centered differences for the approximations
H_x(x,y) = (H(x+1,y) - H(x-1,y))/2
H_y(x,y) = (H(x,y+1) - H(x,y-1))/2

Now for some reconstruction. First, notice that you have
one degree of freedom--translation in the height direction.
If H(x,y) is a height field with normal vectors N(x,y), then
the height field H(x,y)+c for any constant c also has the
same set of normal vectors. To eliminate this degree of
freedom, you will have to make an assumption. My choice is
to choose H(0,0) = 0 in the reconstruction.

To illustrate the process, consider a 4-by-4 normal map, so
xmax = 4 and ymax = 4. Use one-sided differences, with wrap
around at the image boundaries. You can reconstruct a row
at a time. In row y=0, you have
H(0,0) = 0 // the assumption
H(1,0) - H(0,0) = A(0,0) // A(x,y) = -N0(x,y)/N2(x,y)
H(2,0) - H(1,0) = A(1,0)
H(3,0) - H(2,0) = A(2,0)
H(0,0) - H(3,0) = A(3,0) // wrap around
The first four equations have the solution
H(0,0) = 0
H(1,0) = A(0,0)
H(2,0) = A(1,0) + A(0,0)
H(3,0) = A(2,0) + A(1,0) + A(0,0)
The last equation is a "consistency" equation. It says
A(3,0) + A(2,0) + A(1,0) + A(0,0) = 0
This is similar to the "exactness" condition. If the normal
map really was constructed using one-sided differences with
wrap-around at the borders, the consistency condition should
be true (modulo numerical round-off errors).

Moving on to the row y=1,
H(1,1) - H(0,1) = A(0,1)
H(2,1) - H(1,1) = A(1,1)
H(3,1) - H(2,1) = A(2,1)
H(0,1) - H(3,1) = A(3,1)
This is slightly different from handling row y=0. I had
assumed H(0,0) = 0, but there is no immediate information
here about H(0,1). Actually, you do have such information.
The normal map gives you H_y(0,0) = -N1(0,0)/N2(0,0). The
finite difference approximation is
H_y(0,0) = H(0,1) - H(0,0)
You can solve this for
H(0,1) = H(0,0) + H_y(0,0) = H_y(0,0)
Solve the remaining equations
H(1,1) = A(0,1) + H(0,1) = A(0,1) + H_y(0,0)
H(2,1) = A(1,1) + H(1,1) = A(1,1) + A(0,1) + H_y(0,0)
H(3,1) = A(2,1) + H(2,1) = A(2,1) + A(1,1) + A(0,1) + H_y(0,0)
The consistency equation is
A(3,1) + A(2,1) + A(1,1) + A(0,1) = 0

Repeat this process for the remaining rows.

In the reconstruction, you get a height field and you can
ignore the consistency equations. However, if the normal
map was not constructed using the finite difference scheme
you choose for the reconstruction, you can get "information"
about this by computing the consistency equations to see
how far off you are from satisfying them. In fact, you can
try reconstructing using a few finite difference schemes,
choosing the final result to be the one with a "smallest"
deviation from consistency.

If the centered difference approach is used, you have to be
careful about wrap around at the boundaries. For example,
in the first row of the 4-by-4 image, the equations you get
are
H(1,0) - H(3,0) = A(0,0) // wrap around
H(2,0) - H(0,0) = A(1,0)
H(3,0) - H(1,0) = A(2,0)
H(0,0) - H(2,0) = A(3,0) // wrap around
This gives you two decoupled sets of equations. Choosing
H(0,0) = 0 produces H(2,0) = A(1,0) with the consistency
condition A(1,0) + A(3,0) = 0. To solve the other subset
of equations, you need to know a value for H(1,0). Once
known, H(3,0) = H(1,0) + A(2,0) with consistency equation
A(0,0) + A(2,0) = 0. You have to decide how to choose
H(1,0). Probably the thing to do in the reconstruction is
to use one-sided differences at the boundary, but centered
differences elsewhere.

--
Dave Eberly
http://www.geometrictools.com
Yakov Galka
2015-09-08 20:58:56 UTC
Permalink
Post by New Guy
Is it possible to go backwards, and (re)create a (correct) height map from
a normal map? Is there any code already out there that does this?
Thanks.
I acknowledge that this thread is REALLY old, yet, for the sake of future googlers, here is a code that does correct reconstruction and *performs well under noise*:

#include <fftw3.h>
#include <complex>
#include <vector>

void reconstruct_height_map(const float *normal, float *dx, float *dy, int width, int height, float *result)
{
typedef std::complex<float> C;
fftwf_plan plan;

std::vector<float> nx(width*height), ny(width*height);
for(int y = 0, i = 0; y < height; ++y)
for(int x = 0; x < width; ++x, ++i, normal += 3)
nx[i] = normal[0]/normal[2], ny[i] = normal[1]/normal[2];

const int half_width = width/2 + 1;
std::vector<C> Nx(half_width*height), Ny(half_width*height);
std::vector<C> Dx(half_width*height), Dy(half_width*height);

plan = fftwf_plan_dft_r2c_2d(height, width, &nx[0], (fftwf_complex*)&Nx[0], FFTW_ESTIMATE);
fftwf_execute_dft_r2c(plan, &nx[0], (fftwf_complex*)&Nx[0]);
fftwf_execute_dft_r2c(plan, &ny[0], (fftwf_complex*)&Ny[0]);
fftwf_execute_dft_r2c(plan, &dx[0], (fftwf_complex*)&Dx[0]);
fftwf_execute_dft_r2c(plan, &dy[0], (fftwf_complex*)&Dy[0]);
fftwf_destroy_plan(plan);

std::vector<C> F(half_width*height);
for(int y = 0, i = 0; y < height; ++y)
for(int x = 0; x < half_width; ++x, ++i)
{
float denom = width * height * (norm(Dx[i]) + norm(Dy[i]));
F[i] = denom > 0 ? - (Dx[i] * Nx[i] + Dy[i] * Ny[i]) / denom : 0;
}

plan = fftwf_plan_dft_c2r_2d(height, width, (fftwf_complex*)&F[0], &result[0], FFTW_ESTIMATE);
fftwf_execute(plan);
fftwf_destroy_plan(plan);
}

void reconstruct_height_map1(const float *normal, int width, int height, float *result)
{
std::vector<float> dx(width*height), dy(width*height);
dx[0] = 1, dx[1] = -1;
dy[0] = 1, dy[width] = -1;
reconstruct_height_map(normal, &dx[0], &dy[0], width, height, result);
}

void reconstruct_height_map2(const float *normal, int width, int height, float *result)
{
std::vector<float> dx(width*height), dy(width*height);
dx[width-1] = 1, dx[1] = -1;
dy[width*(height-1)] = 1, dy[width] = -1;
reconstruct_height_map(normal, &dx[0], &dy[0], width, height, result);
}

Source (explains the math behind it): http://stannum.co.il/blog/1/reconstructing-a-height-map-from-a-normal-map
Loading...