*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