Skip to main content
GameDev.net gamedev.net
🔒 Locked

Calculating Vertex-Normals [Solved]

Started by d h k Nov 1, 2005 at 4:49 AM 40 replies 61.5k views
Original Post
d h k
d h k
Hello, I have a terrain (heightmap) and the standard OGL lighting in place. It works fine, but now I want to switch away from using face normals and start to use vertex normals (I believe that's how the "better" ones are called, right?). I am talking about the normals, that will actually give a blurred look, and not this flat, blocky look: I do use this function to calculate my face normals: 

void get_face_normal ( float *norm, float pointa[3], float pointb[3], float pointc[3] )
// gets the normal of a face
{
	float vect[2][3];
	int a,b;
	float point[3][3];

	for ( a = 0; a < 3; ++a )
	// copies points into point[][]
	{
		point[0][a]=pointa[a];
		point[1][a]=pointb[a]; 
		point[2][a]=pointc[a];
	}

	for ( a = 0; a < 2; ++a )
	// calculates vectors from point[0] to point[1]
	{                       
		for ( b = 0; b < 3; ++b )
		// and point[0] to point[2]
		{
			vect[a] = point[2-a] - point[0];      
		}
	}

	// calculates vector at 90° to 2 vectors
	cross_product ( norm, vect[0], vect[1] );

	// makes the vector length 1
	normalize ( norm );
}
Now how would I best move on to using those vertex normals? I know that I'll have three normals for one polygon then and that I somehow need to average something, but nothing more. Heck, I don't even know if "vertex normals" is the correct word... Any help/links to articles would be great! [Edited by - d h k on November 6, 2005 10:49:00 AM]
haegarr
haegarr
There're simple ways to do so, and there are accurate ways. However, look at this www.gamedev.net/community/forums/topic.asp?topic_id=354136 thread. It has started 5 days ago and discusses several ways w/ pros and cons on computing vertex normals.

The simple way is to average the normals of all faces adjacent to the vertex. But also here meanings exist of whether or not, and if, how to weight the normals in dependence to the participation of the face to the vertex.

Quote:
Orignal post by d h k
Heck, I don't even know if "vertex normals" is the correct word...

Yes, "vertex normal" is a valid term for what you mean.
d h k
d h k
Thanks for your help. I was hoping for an easier way, as the thread seems to be quite... advanced. ;)

Anyways, is there any other tutorial/code snippet than the "Normal Computations For A Heightfield" out there? This one confuses me with all those DirectX terms. I can't seem to find anymore.
dimebolt
dimebolt
Quote:
Original post by d h k
Thanks for your help. I was hoping for an easier way, as the thread seems to be quite... advanced. ;)

Anyways, is there any other tutorial/code snippet than the "Normal Computations For A Heightfield" out there? This one confuses me with all those DirectX terms. I can't seem to find anymore.


In theory, getting the normals you want is very easy. The 'algorithm' is as follows:
- for every vertex in your model:
- sum the face normals (component wise) for avery triangle containing the vertex
- devide the summed normal (component wise) by the number of triangles containing the vertex to get the normal for the vertex

And that's it. Determining the list of triangles that contain a specific vertex can be tricky if your datatstructure does not support it (in that case you should probably redesign the way in which your terrain data is stored).

Tom

d h k
d h k
Thanks for your help. I understand what you mean, but am having troubles actually implementing it...

for ( int x = 0; x < ( MAP_SIZE - STEP_SIZE ); x += STEP_SIZE )	// loop through horizontal data	{		for ( int z = 0; z < ( MAP_SIZE - STEP_SIZE ); z += STEP_SIZE )		// loop through vertical data		{			float	vertex1[3];			float	vertex2[3];			float	vertex3[3];			float	vertex4[3];			float	normal1[3];			float	normal2[3];			float	normal3[3];			float	normal4[3];			// get vertex data			vertex1[0] = ( float ) x;										vertex1[1] = get_height ( ( float ) x, ( float ) z );				vertex1[2] = ( float ) z;			vertex2[0] = ( float ) x;													vertex2[1] = get_height ( ( float ) x, ( float ) z + STEP_SIZE );  			vertex2[2] = ( float ) z + STEP_SIZE;			vertex3[0] = ( float ) x + STEP_SIZE; 			vertex3[1] = get_height ( ( float ) x + STEP_SIZE, ( float ) z + STEP_SIZE ); 			vertex3[2] = ( float ) z + STEP_SIZE;			vertex4[0] = ( float ) x + STEP_SIZE; 			vertex4[1] = get_height ( ( float ) x + STEP_SIZE, ( float ) z ); 			vertex4[2] = ( float ) z;			// calculate normals			get_face_normal ( normal1, vertex1, vertex2, vertex3 );			get_face_normal ( normal2, vertex1, vertex3, vertex4 );			normal1[0] *= -1;			normal1[1] *= -1;			normal1[2] *= -1;			normal2[0] *= -1;			normal2[1] *= -1;			normal2[2] *= -1;			// draw the first triangle			glNormal3f ( normal1[0], normal1[1], normal1[2] );			glTexCoord2f ( 0.0f, 0.0f );			glVertex3f ( vertex1[0], vertex1[1], vertex1[2] );			glTexCoord2f ( 1.0f, 0.0f );			glVertex3f ( vertex2[0], vertex2[1], vertex2[2] );			glTexCoord2f ( 1.0f, 1.0f );			glVertex3f ( vertex3[0], vertex3[1], vertex3[2] );			// draw the second triangle			glNormal3f ( normal2[0], normal2[1], normal2[2] );			glTexCoord2f ( 0.0f, 0.0f );			glVertex3f ( vertex1[0], vertex1[1], vertex1[2] );			glTexCoord2f ( 1.0f, 0.0f );			glVertex3f ( vertex3[0], vertex3[1], vertex3[2] );			glTexCoord2f ( 0.0f, 1.0f );			glVertex3f ( vertex4[0], vertex4[1], vertex4[2] );		}	}


This is what I have to draw my terrain. So I need to calculate normal1 at vertex1, normal2 at vertex2, normal3 at vertex3 and normal4 at vertex4, right? I am quite confused at the moment, sorry for that. Could anybody explain just a little more?
dimebolt
dimebolt
Quote:
Original post by d h k
Thanks for your help. I understand what you mean, but am having troubles actually implementing it...

*** Source Snippet Removed ***

This is what I have to draw my terrain. So I need to calculate normal1 at vertex1, normal2 at vertex2, normal3 at vertex3 and normal4 at vertex4, right? I am quite confused at the moment, sorry for that. Could anybody explain just a little more?

No problem :)
Your assumption is not exactly correct. Look at the picture from the thread linked by heagarr:


As you can see, each cross-point has a single normal, eventhough such a point is shared by 6 triangles. From your screenshot, it looks that your surface is similar, in the sense that each vertex is part of 6 triangles. Looking through your drawing code, it seems you draw 2 triangles at a time. That's probably where your confusion comes from, because in that function you don't have the information of the other 4 triangles that is required to calculate the vertex normals.

To solve your problem, you'll probably have to pre-calculate the vertex normals, because doing this during the rendering phase is inconvenient (and not too good for performance either). To achieve this, I suggest you create a datastructure that contains vertex, normal, texturecoordinate and connectivity data (which vertices belong to which triangles and vice versa) and a function that draws such a structure using OpenGL. This datastructure will make it easier to calculate the desired vertex normals and can be re-used for all your other models as well (assuming that eventually you want something to populate your empty terrain :).

EDIT: Combining an OpenGL VBO with the connectivity data required to calculate the normals, would be an efficient choice for this datastructure.

Tom
haegarr
haegarr
The simplest algorithm is as follows:

For each vertex, find the faces adjacent to it. For each of that faces get the face normal (e.g. by cross product computation). Summarize the normals of all of those faces, and re-normalize the sum. So you've computed the simple average of all normals.

When rendering, push the belonging vertex normal just before pushing the vertex point (in a pseude-code)
for each vertex v do {   VertexNormal n = { 0,0,0 };   for each face f adjacent to v do {      n += f.getNormal();   }   n.normalize();   glNormal(n);   glVertex3f(v.point());}
d h k
d h k
Thanks a lot to both of you, I appreciate it, especially since terrain is going to be an important part of my project. I'll implement it right away.
deavik
deavik
When most model formats export data, they do so like this for each polygon:
numsides vertex1id vertex2id vertex3id ...
Anyway, given this, the easiest approach would be not to look for faces using a vertex, but to do the following:

1. Read the faces in your model file
2. Calculate the face normal
3. Add it to the normal of each vertex making up that face (if you look at the example line above, this is really easy)
4. After that's done, normalize all the vertex normals

So you don't have to go looking for faces which share a vertex at all. I personally found this approach much easier to implement.
OpenGL_Guru
OpenGL_Guru
i am going to go ahead and post my vertex normals function that i use. at the offset i should advise that you create a normals class to do all your stuff.. such as cross product and so forth. in some screenshots that i have posted in the past such as here and here , you can see the work of vertex normals. since ill assume you know how do cross product and all that stuff i will just go ahead and give you sample code with a simple data structure. hope this helps!

//class.h i define a few variables of type data
struct data{ double x; double y; double z;};data *terrain;data *normals


//in class.cpp i calculate what my xsize and ysize will be then allocate memory equally for my terrain and normals, then i store the x,y,z pairs in my terrain array. i have found its also helpful when storing your data to calculate the number of vertices you will have total which you can get by x_size * y_size * 3. you can read what your x,y & z values are through a file on disk or if your values are predefined you can do it manually.
terrain = new data[x_size * y_size * 3];normals = new data[x_size * y_size * 3];for(int i = 0; i < y_size; i++){ for(int j = 0; j < x_size; j++)  terrain[count].x = num_x; terrain[count].y = num_y; terrain[count].z = num_z;}


//in class.cpp you can call a load normals function that will load the normals in per vertex. i have a CVector class that is included in a header file that instantiates variables in the class for doing cross product, subtraction and addition of vectors as well as many other things. you can see some of them at work here.

void load_normals();{ int count; CVector V4; CVector V5; CVector V6;  for(int a = 0; a < ysize; a++)  {   for(int b = 0; b < x_size; b++)     {      if(count < x_size)      {       CVector V2(terrain[((a+1)*x_size)+b+1].x, terrain[((a+1)*x_size)+b+1].y, terrain[((a+1)*x_size)+b+1].z);       CVector V1(terrain[((a+1)*x_size)+b].x, terrain[((a+1)*x_size)+b].y, terrain[((a+1)*x_size)+b].z);       V4 = V2 - V1;       CVector V0(terrain[((a)*x_size)+b].x, terrain[((a)*x_size)+b].y, terrain[((a)*x_size)+b].z);       CVector V3(V1);       V5 = V0 - V3;       count++;      }     else if(count == x_size)      {              CVector V2(terrain[((a)*x_size)+b-1].x, terrain[((a)*x_size)+b-1].y, terrain[((a)*x_size)+b-1].z);       CVector V1(terrain[((a)*x_size)+b].x, terrain[((a)*x_size+b].y, terrain[((a)*x_size)+b].z);       V4 = V2 - V1;       CVector V0(terrain[((a+1)*x_size)+b].x, terrain[((a+1)*x_size)+b].y, terrain[((a+1)*x_size)+b].z);       CVector V3(V1);       V5 = V0 - V3;       count = 0;      }	  	        V6 = V5.Cross(V4);  //cross product      V6.normalize();     //normailizing to the unit vector = 1    //now lets store the normals after calculating them     normals[(a*x_size)+b].x = -V6.x;     normals[(a*x_size)+b].y = -V6.y;     normals[(a*x_size)+b].z = -V6.z;   } //end b  } //end a} //end load_normals()


now you have your terrain and normals stored and you are set up to draw your stuff. obviously my code could be lengthed by doing extra checking among all the vertices, to have some slight better results in the shading between vertices, but this works pretty well and i hope you understand it. so now you are read to do:

glNormal3f(normals[count].x, normals[count].y, normals[count].z)
glVertex3f(terrain[count].x, terrain[count].y, terrain[count].z)

or just however you decide to do this part.

again i hope this helps and i welcome comments!
heh
d h k
d h k
Thanks for your efforts, OpenGL_Guru. I went with your suggestion and think I have it pretty much working by now, except one thing, that is giving me some headache:

I am very sure it is this part:

	for ( int i = 0; i < MAP_SIZE; i++ )	{		for ( int j = 0; j < MAP_SIZE; j++ )		{			trn[i + ( j * MAP_SIZE )].x = ( float ) i;			trn[i + ( j * MAP_SIZE )].y = get_height ( ( float ) i, ( float ) j );			trn[i + ( j * MAP_SIZE )].z = ( float ) j;		}	}


I loop through the horizontal data and then the vertical data and then try to set the trn.x, .y and .z values to my actual datas, but the trn array is only one-dimensional, while my data is two-dimensional.

My hack above works kinda, but displays a wierd version of my height-map (looks kinda sliced):



How can I fix this issue?

[Edited by - d h k on November 1, 2005 4:47:04 PM]
OpenGL_Guru
OpenGL_Guru
it looks like you are overstepping your bounds in either you X loop or Y loop when storing your vertices. so it looks like the triangle is trying to be completed at the very beginning rather than just to stop drawing. i had this sort of thing happen to me before on a few occasions. at least from that angle thats what it looks like. any chance we could have a top down view?
heh
haegarr
haegarr
Yes, it looks also for me that the vertices used on the right at the horizon are positionally incorrect (I would wonder if this effect could be caused by an incorrect normal computation ;-) Either the drawing loops overshot (as OpenGL_Guru has mentioned) or some index computation is not limited correctly, or the vertex import is incorrect, or ... something else in this direction.
d h k
d h k
Yes, the problem is not normals-related. If you view the field from the top, then you don't see a thing, because the strips are all very thin on top. The normals do seem to work on those trips though. ;)

This is really strange, but still I believe that it comes from setting those trn values wrong somehow, as I stated in my first post.

Thanks though, you're helping me out big time!

EDIT: The whole thing varies, when I change...

trn[i + ( j * MAP_SIZE )].x = ( float ) i;

... to ...
trn[i * j].x = ( float ) i;


... the whole thing looks even worse (almost like a building or something) any my frames drop below 1...

I am sure I just need to find the proper method here to make my two-dimensional data one-dimensional and store it in trn.x, .y and .z...

I'll keep on experimenting.
d h k
d h k
Hmm... I can't get it to work, although it didn't seem too difficult in the beginning.

Let me show you three variations I tried of the little piece of code, that I posted before, and how it makes the terrain look like...

VERSION 1

	for ( int x = 0; x < MAP_SIZE; x++ )	{		for ( int z = 0; z < MAP_SIZE; z++ )		{			trn[x * MAP_SIZE + z].x = ( float ) x;			trn[x * MAP_SIZE + z].y = get_height ( ( float ) x, ( float ) z );			trn[x * MAP_SIZE + z].z = ( float ) z;		}	}



Strange terrain...

VERSION 2

	for ( int x = 0; x < MAP_SIZE; x++ )	// loop through horizontal data	{		for ( int z = 0; z < MAP_SIZE; z++ )		// loop through vertical data		{			// get vertex data			trn[x + ( z * MAP_SIZE )].x = ( float ) x;			trn[x + ( z * MAP_SIZE )].y = get_height ( ( float ) x, ( float ) z );			trn[x + ( z * MAP_SIZE )].z = ( float ) z;		}	}



Pretty much the same thing...

VERSION 3

	for ( int x = 0; x < ( MAP_SIZE - STEP_SIZE ); x += STEP_SIZE )	// loop through horizontal data	{		for ( int z = 0; z < ( MAP_SIZE - STEP_SIZE ); z += STEP_SIZE )		// loop through vertical data		{			// get vertex data			trn[x + ( z * MAP_SIZE )].x = ( float ) x;			trn[x + ( z * MAP_SIZE )].y = get_height ( ( float ) x, ( float ) z );			trn[x + ( z * MAP_SIZE )].z = ( float ) z;		}	}



This is interesting, too... ;)

When I try things like trn[x + z], I get nothing at all, and with trn[x * z], I get some really rare and strange artefacts...

I managed to find out the official name of this problem, though: HASHING A 2D-ARRAY INTO A 1-D ONE. Is anybody experienced in this?

Thanks in advance, I know I am really close, but this really gets me confused for several days now.
dimebolt
dimebolt 
trn[x + ( z * MAP_SIZE )]

This fragment from your third approach should be the proper way of addressing the array. In general, mapping a 2D array access:
array[x][y] (array was initialized as: array[x_size][y_size])

is done in 1D as:
array[x + x_size * y] (array was initialized as: array[x-size * y-size])

This stores rows first.

The reason why your third approach doesn't work is unclear from the presented code. One problem definately is the STEP_SIZE, which is subtracted from the MAP_SIZE in the for statements. This way (if STEP_SIZE != 0, which is always) you will not fill all elements of the array. Uninitialized elements also remain when MAP_SIZE % STEP_SIZE != 0. Uninitialized elements can be any value including 0. In the picture, it is clear that along the edges certain points are connected to a single point, which might very well be (0,0,0). Why do you use STEP_SIZE anyway? It seems rather error prone.

Tom
d h k
d h k
Thank you for your answer!

STEP_SIZE is used when I load the heightmap. If it is 1, it would create a polygon for every pixel of the heightmap, if it is 8, it would take 8 pixels of the heightmap and create one polygon for them.

I am not sure if it is a good idea to use the STEP_SIZE in the loops or not...
If I use my third approach, but get rid of the STEP_SIZE in the loops, then the terrain looks exactly like in my first, and second versions.

This is the code now:
	for ( int x = 0; x < MAP_SIZE; x++ )	// loop through horizontal data	{		for ( int z = 0; z < MAP_SIZE; z++ )		// loop through vertical data		{			// get vertex data			trn[x + ( z * MAP_SIZE )].x = ( float ) x;			trn[x + ( z * MAP_SIZE )].y = get_height ( ( float ) x, ( float ) z );			trn[x + ( z * MAP_SIZE )].z = ( float ) z;		}	}


If you need more code, then tell me as I am not sure which parts could be of interest (and I seriously still believe that it's this part, that is causing the error)...
dimebolt
dimebolt
Quote:
Original post by d h k
Thank you for your answer!

STEP_SIZE is used when I load the heightmap. If it is 1, it would create a polygon for every pixel of the heightmap, if it is 8, it would take 8 pixels of the heightmap and create one polygon for them.

I am not sure if it is a good idea to use the STEP_SIZE in the loops or not...
If I use my third approach, but get rid of the STEP_SIZE in the loops, then it looks exactly like in my first, and second versions.

This is the code now:
*** Source Snippet Removed ***

If you need more code, then tell me as I am not sure which parts coould be of interest (and I seriously still believe that it's this part, that is causing the error)...

I believe that in that case the error is in the rendering code.

Tom
d h k
d h k
Ah, that's a good idea... :)

Here we go:

void cterrain::draw ( void )// draws a terrain{	// set up render modes	glColorMask ( 1, 1, 1, 1 );	glColor4f ( 1.0f, 1.0f, 1.0f, 1.0f );	glDisable ( GL_BLEND );	glDisable ( GL_CLIP_PLANE0 );	glEnable ( GL_DEPTH_TEST );	glDisable ( GL_STENCIL_TEST );	// activate the texture	texture.activate ( );	// push the matrix	glPushMatrix ( );	// scale the terrain	glScalef ( scale, scale * HEIGHT_RATIO, scale );	// begin drawing the terrain	glBegin ( GL_TRIANGLES );	for ( int i = 0; i < ( ( MAP_SIZE - STEP_SIZE ) * ( MAP_SIZE - STEP_SIZE ) ); i += STEP_SIZE )	// loop through all data		{			// draw the first triangle			glNormal3f ( normals.x, normals.y, normals.z );			glTexCoord2f ( 0.0f, 0.0f );			glVertex3f ( trn.x, trn.y, trn.z );		}		// done drawing the terrain	glEnd ( );	// pop the matrix	glPopMatrix ( );}


This is the render function. Maybe it has to do with:
for ( int i = 0; i < ( ( MAP_SIZE - STEP_SIZE ) * ( MAP_SIZE - STEP_SIZE ) ); i += STEP_SIZE )

EDIT:

Hmm.. I changed the previously mentioned line to:
for ( int i = 0; i < MAP_SIZE * MAP_SIZE * 3; i++ )

But this creates tons of very small polygons... Looks kinda wierd, I may take a screenshot sooner or later.

Thanks for your help though!
haegarr
haegarr
At going through all the posts wriiten by dimebolt and dhk since my last constribution to this thread, there are two things that I've noticed:

(1) If you access a 2D defined array with a 1D index, then you have to know that the first index has the highest priority. So
int array[2][2];array[0][0] = 0;array[0][1] = 1;array[1][0] = 2;array[1][1] = 3;for(int index=0;index<3;++index)   printf("%d\n",((int*)array)[index]);

results in the sequence 0123 !

However, if you define a 1D array, and access it w/ a 2D index, then you may use either [x+y*x_size] or [y+x*y_size] w/ 0<=x
(2) The trn array is filled up linearly, say a vertex in trn[0], the next in trn[1], and so on, with an index dependency like this:
x,z=0,0 . x,z=1,0 . x,z=2,0 ... x,z=0,1 . x,z=1,1 . x,z=2,1 ... x,z=0,2 ...
So, when wrapping around at the limit of x == SIZE-1, one gets
x,z=0,0 . x,z=1,0 . x,z=2,0 ...
x,z=0,1 . x,z=1,1 . x,z=2,1 ...
x,z=0,2 . x,z=1,2 . x,z=2,2 ...

As a 1D index, the arrangement is (just that x+z*SIZE)
0 . 1 . 2 ...
SIZE+0 . SIZE+1 . SIZE+2 ...
2*SIZE+0 . 2*SIZE+1 . 2*SIZE+2 ...

When rendering, neighboured vertices have to be used to build up a tri. Since your glBegin uses GL_TRIANGLES, the indices for the first tri have to be {0,1,SIZE+0}, and for the second tri {1,SIZE+1,SIZE+0}.

If you still want to go with an incrementing index in your rendering routine, you should do something like this:
for(int i=0;i<(SIZE-1)*(SIZE-1);++i) {   glNormal3f ( normals.x, normals.y, normals.z );   glTexCoord2f ( 0.0f, 0.0f );   if((i&1)==0) {      glVertex3f ( trn.x, trn.y, trn.z );      glVertex3f ( trn[i+1].x, trn[i+1].y, trn[i+1].z );      glVertex3f ( trn[i+SIZE].x, trn[i+SIZE].y, trn[i+SIZE].z );   } else {      glVertex3f ( trn[i+1].x, trn[i+1].y, trn[i+1].z );      glVertex3f ( trn[i+SIZE+1].x, trn[i+SIZE+1].y, trn[i+SIZE+1].z );      glVertex3f ( trn[i+SIZE].x, trn[i+SIZE].y, trn[i+SIZE].z );   }}

This is, in fact, not optimal, but hopefully shows the dependency between the index calculations I mean. If I made no mistakes, then index i iterates the upper left corner of quads of your terrain, and the quad is rendered as two opposite tris.

I recommend to use tri-strips instead of particular tris, since it would make the rendering routine much more effective _and_ simpler.

BTW: Nice indexing problem ;-)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.