Trouble Calculating Height Field Normals

[Nick]

I can't seem to figure out a good method of figuring out my height field normals. Can anyone help me out? I've tried a few different situations and nothing really works. Here's how the surface is drawn (figure that might help):

int i,j;
list = glGenLists(1);
glNewList(list,GL_COMPILE);

for(i = 0; i <= width - HEIGHTFIELD_STEP; i+=HEIGHTFIELD_STEP)
{
glBegin(GL_TRIANGLE_STRIP);
for(j = 0; j <= depth - HEIGHTFIELD_STEP; j+=HEIGHTFIELD_STEP)
{
if((i+HEIGHTFIELD_STEP) <= (width - HEIGHTFIELD_STEP))
{
glNormal3f(normal[i+HEIGHTFIELD_STEP][j].x,
normal[i+HEIGHTFIELD_STEP][j].y,
normal[i+HEIGHTFIELD_STEP][j].z);
glVertex3f(height[i+HEIGHTFIELD_STEP][j].x,
height[i+HEIGHTFIELD_STEP][j].y,
height[i+HEIGHTFIELD_STEP][j].z);
}

glNormal3f(normal[i][j].x,
normal[i][j].y,
normal[i][j].z);
glVertex3f(height[i][j].x,
height[i][j].y,
height[i][j].z);
}
glEnd();
}

glEndList();

[TomorrowPlusX]

When I calculate heightfield normals, I ( and this may not be a great approach ) average the normals of each triangle touching that point. Works well enough for me...

[Nick]

That was kind of my plan in the end. Trouble is that I can't even get proper polygon normals. Can you help me out any?

[unknown]

Well here is how to calculate the normal of the plane from three points.
Theres lots of other really good geometry stuff here too.

http://astronomy.swin.edu.au/~pbourke/geometry/planeeq/

[Jake]

Heres some code I use to get normals for my height map -

Let me know if this helps because it should be exactly what you want


for (i=0; i < size-1; i++)
{
for (j=0; j <size-1; j++)
{
v1.x = i;
v1.y = hm[i][j];
v1.z = j;
v2.x = i+1;
v2.y = hm[i+1][j];
v2.z = j;
v3.x = i+1;
v3.y = hm[i+1][j+1];
v3.z = j+1;
v4 = [self subVector:v1 plus:v2];
v5 = [self subVector:v3 plus:v2];

normal[0][i][j] = [self getNormal: v4 plus: v5 ];

if (normal[0][i][j].y < 0) {
normal[0][i][j].x = -normal[0][i][j].x;
normal[0][i][j].y = -normal[0][i][j].y;
normal[0][i][j].z = -normal[0][i][j].z;
}

v1.x = i;
v1.y = hm[i][j];
v1.z = j;
v2.x = i;
v2.y = hm[i][j+1];
v2.z = j+1;
v3.x = i+1;
v3.y = hm[i+1][j+1];
v3.z = j+1;
v4 = [self subVector:v1 plus:v2];
v5 = [self subVector:v3 plus:v2];

normal[1][i][j] = [self getNormal: v4 plus: v5 ];

if (normal[1][i][j].y < 0) {
normal[1][i][j].x = -normal[1][i][j].x;
normal[1][i][j].y = -normal[1][i][j].y;
normal[1][i][j].z = -normal[1][i][j].z;
}
}
}


I use this to smooth everything


for (i=1; i < size-2; i++)
{
for (j=1; j <size-2; j++)
{
smoothNormal[i][j].x = 0;
smoothNormal[i][j].y = 0;
smoothNormal[i][j].z = 0;
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[0][i][j]];
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[1][i][j]];
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[0][i-1][j-1]];
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[1][i-1][j-1]];
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[0][i-1][j]];
smoothNormal[i][j] = [self addVector:smoothNormal[i][j] plus:normal[1][i][j-1]];
}
}

for (i=1; i < size-2; i++)
{
for (j=1; j <size-2; j++)
{
smoothNormal[i][j].x = smoothNormal[i][j].x/6;
smoothNormal[i][j].y = smoothNormal[i][j].y/6;
smoothNormal[i][j].z = smoothNormal[i][j].z/6;
}
}



- (VECTOR) addVector:(VECTOR)a plus:(VECTOR)b
{
VECTOR r;

r.x = a.x + b.x;
r.y = a.y + b.y;
r.z = a.z + b.z;

return r;
}

- (VECTOR) subVector:(VECTOR)a plus:(VECTOR)b
{
VECTOR r;

r.x = a.x - b.x;
r.y = a.y - b.y;
r.z = a.z - b.z;

return r;
}

- (VECTOR) getNormal:(VECTOR)a plus:(VECTOR)b
{
VECTOR result;
float distance;

result.x = a.y * b.z - a.z * b.y;
result.y = a.z * b.x - a.x * b.z;
result.z = a.x * b.y - a.y * b.x;

distance = sqrt(result.x*result.x + result.y*result.y + result.z*result.z);

result.x = -result.x/distance;
result.y = -result.y/distance;
result.z = -result.z/distance;

return result;
}

- (VECTOR) normalize:(VECTOR)a
{
VECTOR result;
float distance;

result.x = a.x;
result.y = a.y;
result.z = a.z;

distance = sqrt(result.x*result.x + result.y*result.y + result.z*result.z);

result.x = result.x/distance;
result.y = result.y/distance;
result.z = result.z/distance;

return result;
}

- (float) dot:(VECTOR)a plus:(VECTOR)b
{
return (a.x * b.x) + (a.y * b.y) + (a.z * b.z);
}

[Nick]

Thanks, unknown, but I know how to find normals. It's just when trying to figure out all the normals for a triangulated height map, it becomes a bit trickier.

Jake, I'll try that out in a bit and let you know. I'm suddenly very glad I took a few months to get comfortable with Objective-C.

[unknown]

So are you using a uniform grid of points each with a specified height?
If this is your grid
A B C D
E F G H
I J K L
surely just calculate the normals ABE, BEF as two seperate triangles.
If you want the normals smooth, just to a blur filter to the grid before calculating normals,
F = 0.8*F+0.2*(A+B+C+E+F+I+J+K+L)

Have you checked if the winding is clockwise or anticlockwise?

[Nick]

I'm not sure what you mean by 'winding'.

I understand that ABE and BEF would be two separate triangles and that's why I want to find normals for each separately, but for a variable size of the grid (sometimes I use a 250x250, sometimes a 1000x1000), I'm trying to use a couple for loops. You can see how I'm setting the triangles by using a nested for loop making a GL_TRIANGLE_STRIP for each row of triangles. Thus if this was my grid:

A B C D
E F G H
I J K L

and each letter was a point, AEB, BEF, BFC, CFG, CGD, DGH (as triangles) would all render as one strip. The way I'm doing this is like this:

//pseudo-code of course
from x=0 to max points in row - 1
glBegin(triangle strip)
from y=0 to max points in row - 1
create vertex at point x+1,y
create vertex at point x,y
next
glEnd()
next
//to see the actual code, my first post has the code

If there is a way to render around in a circle of sorts, that'd be great (to make just one triangle strip) but this is the best way I've come up with.

Like I said, smoothing will come later. I just want polygon normals. I'm also considering not smoothing at all and going with cel-shading (if I can figure it out) but that's also a later point to think about.

[unknown]

Do a zig zag


//pseudo-code of course!!
from x=0 to max points in row - 1
glBegin(triangle strip)
from y=0 to max points in row - 1
if(x mod 2 == 0) {
create vertex at point max points-x-1,y
create vertex at point max points-x,y
else
create vertex at point x+1,y
create vertex at point x,y
end
next
glEnd()
next

[Nick]

Why do zig zags as opposed to rendering strips like i do? Any real advantage?

[Nick]

Jake, in your code, why are you generating two normals per vertex? Just curious. That's the only part that doesn't make sense.

[Jake]

Jake, in your code, why are you generating two normals per vertex? Just curious. That's the only part that doesn't make sense.

Because there are two triangles in a quad. The first part generates normals for the triangles of it, x+1,y x+1,y+1 x,y+1. The second part smoothes all of the normals per vertex.

[Nick]

I see. Thanks for that. I'll look at the smoothing part later. I'll first see if the normals themselves work with my project.

[reubert]

Just a question, why are you using height maps?
I'm guessing you are creating a terrain engine, but it might be wise to think about what this engine might be used for, and what is the best way to go about it.
There are only two reasons I can think of to use height maps; if you are planning on using real DEM (digital elevation model) data and wish to miss out a conversion step, or if you are doing the art yourself, and don't like the idea of using a modeling app.
Otherwise, it seems much easier to create a bunch of models in your modeling app, and write a good renderer that only draws what it needs to and allows for good LOD.

A height-map based engine is hard to create levels for, (you can't see what it looks like until it's done) and it's an extra chunk of code that needs to be created and maintained. Creating a good height map based terrain renderer is a massive task. I re-wrote the one for the ill-fated Chopper2 at least half a dozen times, and still wasn't happy with it.

Perhaps In your case it's OK, but give it some thought.

David

[unknown]

If there is a way to render around in a circle of sorts, that'd be great (to make just one triangle strip)

I meant to do a triangle strip back and forth like a crt ray instead of a more complicated circle method.

[Nick]

Just a question, why are you using height maps?
I'm guessing you are creating a terrain engine, but it might be wise to think about what this engine might be used for, and what is the best way to go about it.
There are only two reasons I can think of to use height maps; if you are planning on using real DEM (digital elevation model) data and wish to miss out a conversion step, or if you are doing the art yourself, and don't like the idea of using a modeling app.
Otherwise, it seems much easier to create a bunch of models in your modeling app, and write a good renderer that only draws what it needs to and allows for good LOD.

A height-map based engine is hard to create levels for, (you can't see what it looks like until it's done) and it's an extra chunk of code that needs to be created and maintained. Creating a good height map based terrain renderer is a massive task. I re-wrote the one for the ill-fated Chopper2 at least half a dozen times, and still wasn't happy with it.

Perhaps In your case it's OK, but give it some thought.

David

Pretty much I have two reasons for this:
1) To see if I can do it
2) I want to make a simulation with very large areas of terrain. I suppose I could model it, but to use this I just apply a few filters to a blank document in Photoshop and I have a perfect hilly or mountainous area.

I may just wind up using a model anyway in the end for the ease you've described as well as the trouble this is causing me. It started merely to see if I could make a heightmap because they always looked so cool.