"New Guy" <firstname.lastname@example.org> wrote in message
> 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
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
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