Trouble Calculating Height Field Normals

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
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):
Code:
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();
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #2
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...
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #3
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?
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #4
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/

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Member
Posts: 509
Joined: 2002.05
Post: #5
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

Code:
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

Code:
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;
        }
    }

Code:
- (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);
}
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #6
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.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #7
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?

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #8
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:
Code:
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:
Code:
//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.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #9
Do a zig zag

Code:
//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

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #10
Why do zig zags as opposed to rendering strips like i do? Any real advantage?
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #11
Jake, in your code, why are you generating two normals per vertex? Just curious. That's the only part that doesn't make sense.
Quote this message in a reply
Member
Posts: 509
Joined: 2002.05
Post: #12
Nick Wrote: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.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #13
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.
Quote this message in a reply
Member
Posts: 320
Joined: 2003.06
Post: #14
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

Chopper, iSight Screensavers, DuckDuckDuck: http://majicjungle.com
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #15
Quote: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.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Finding the height of a point on a given list of vertexes? mikey 10 5,297 Jan 4, 2010 05:36 AM
Last Post: mikey
  Smart Field Initializers IckyThump 6 3,407 Aug 11, 2009 03:58 PM
Last Post: IckyThump
  calculating X and Y coordinates w/ an angle and distance ferum 13 15,123 Jun 25, 2008 10:53 PM
Last Post: rosenth
  Calculating relative transformations TomorrowPlusX 3 2,845 Jul 11, 2007 06:15 PM
Last Post: Skorche
  Calculating direction of car from normal vector and angle spinner 1 3,287 Oct 21, 2006 10:43 AM
Last Post: imikedaman