Thomas Greenleaf

I have a mesh of 100.000 triangles where I need to calculate the normals for the vertices.

The datastructure, I am using, does not point from vertices to triangles, but only the other way arround.

I therefore defined my vertex normals as the sum of the triangles using them, weighted by the triangles size. I simply set all vertex normals to zero and then run through my triangles (when running through them anyway for some other task) and add a triangles normal (weighted) to the vertices it uses.

The I run through all vertices and normalize the normals. This is suposed to give me a valid normal for the vertices. I am not much liking waht i see though. The entire terrain is filled with little pyramids. Light ones and dark ones. When I look at the normals, by a pixelshader that outputs the normal as a color, it is obvious that the problem is in the normals.

I can however not figure out what the problem is. I would say that my method is correct, and I am rendering pr pixel diffuse lighting, which should be correct as well. The result is not right though. It looks like a silly impersonation of goraud shading.

A problem that I can see is normals which are summed together to form a null normal, which is thisn normalized to either an error, or if there was some roundoff error, it can be normalized into anything. It doesnt apear to what happens, and if it was, I would not expect to see it that often.

I have been cursing at this for two days now, and I could really need some advice. Any hints, as to where I might be doing something silly, will be greatly apresiated.

screenshots:

www.greenleaf.dk/pyramid/terrainSolid.JPG

www.greenleaf.dk/pyramid/terrainWire.JPG

www.greenleaf.dk/pyramid/terrainNormals.JPG

www.greenleaf.dk/pyramid/terrainNormalsCloser.JPG



Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

Etienne2005

I don't see why you have to Weight by the size of the triangle
You simply have to add the Normal of all triangle that touch your vertex
And Normalize the final direction

Your concerned with a direction not the size of the final normal direction

If you have a triangular roof top and what the normal at the top of it
you would add both normal to each side of the roof and then Normalize it
The resulting normal would be strait up since the Roof is symetrical (in slope)
But you would not care if one side of the roof extend for twice as long on one side





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

BLANC Guillaume

I've used the same technique you're describing to calculate smooth normals for arbitrary meshes and it works fine :

1. Iterate through all faces

2. Compute face normal using a cross product

3. Sum that normal to the normal of each vertex of the face (initialy set to 0)

4. When iteration ends, normalize all normals.

I'm was not using the triangle size weighting stuff, but it seems to be an interesting idea. Anyway, did you try to remove this coefficient to see if it looks better

Also I've checked terrainNormals.JPG file using an image tool to see what the normals were looking like. I've noticed that there were nearly no red component where I think there should be. To me it means, if normals rendering shader's correct, that you're normal computation algorithm does not output one of the component.

Even if the color output is a very usefull thing for per pixel debugging, another way to debug this is to draw normals at each points using small lines (it avoid shader/rendering mistakes). I'm wondering if Pix is not able to do that by itself. If not it could...






Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

Wessam Bahnassi

Have you tried D3DXComputeNormals()




Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

Imagine a pyramid with its top cut off. Only the very very last bit of the top is removed leaving a square of 1mm^2, while the pyramids base area is 100x100 meters.

You would calculate the four normals at the top as the average of the connected faces. In a way this is correct, but then you interpolate the normal down the sides to calculate lighting and you get the effect of a 1mm^2 horizontal surface imposing its normal on the sides and influencing it just as much as the huge surface.

That explanation may be somewhat wanting without actual numbers, but the normals will be calculated wrong. Yes, on the very vertex where you calculate the normal, it will be correct, but when interpolating it away from that exact vertex position, it is very much wrong. This is ofcourse for smooth shading. When rendering facets, its diferent





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

I have tried dropping the scaling and it looks the same.

I have done a test, which I assume is correct, but it is a little odd. In the pixelshader I draw the surface with the color of the normal. color is nx,ny,nz,1. This image is then saved as a 24 bit bitmap and i go in an pick a pixel which I think is too dak and see perhaps a color of 90,2,7. That corrosponds to a normal of arround 0.36 0 0.02, which has a length of 0.36 and not one. This surprises me since I explicitly in the pixelshader normalize the normal.

Perhaps someone can tell me why this happens. I know that there will be rounding errors here and there and that the GPU is more relaxed than the CPU, but this is a very large error.

The tool you used to show the normals, it is something I can get my hands on Did it show the little normal vectors I guess I should just get to work and render them myself, but the way I render does make it a little messy.

The reson there is no red might be that this is part of the planet (did I mention this is a huge round planet ) which doesnt have terrain with normals with large x components. In other places, the red will be the dominant color, so all three are output.

I just recently discovered Pix, so I dont really know if it can show the normals. It can however let me debug a specific pixel, so i should probably give that a try as well.





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

When I wrote "mesh" i ment a connected collection of triangles and not a d3d mesh class.

I have it in a vertexbuffer and an indexbuffer and am using my own vertexformat (witch does have a position). I tried stuffing those into a mesh class but I couldnt figure out how to do it before i lost patience and dropped it. Should this be easy to do





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

I am about to scream, but I have to figure out exactly which cry of agony is best.

I have made a very simple test case now, and it still looks like... it is not suposed to.

www.greenleaf.dk/normal.BMP

www.greenleaf.dk/terrain.BMP

Now I have red as my terrain color. I have light comming directlyfrom 0,0,1.

I was (as was hinted in the answers previously) making an error in how i colored by normal before. I had forgotten that a color with a negative component, didnt quite work. Now the normal components are scaled to fit in 0..1, which is what I have colored by.

The normals are quite smooth arround the center, while the lighting shows huge errors. The shader has been cut down to a simple case now.

float4 PS_LAND(VS_OUTPUT Input) : COLOR

{

float4 Color=float4(1,0,0,1);

Input.Normal=normalize(Input.Normal);

if(normals)

{

Input.Normal=Input.Normal/2.0;

Input.Normal=Input.Normal+0.5;

Color=float4(Input.Normal.x,Input.Normal.y,Input.Normal.z,1);

}

else

{

float3 LightDir = normalize(vecLightDir); ///this is always 0,0,1

float dp = dot(Input.Normal,LightDir);

if(dp<0) dp=0;

Color=dp*Color;

Color.w=1; //just to make sure that alpha is always 1

}

return Color;

}

I am new to shader coding, so I might be doing something silly in there, but as far as I can see this should calculate the diffuse lighting.

Aparently it is not. The pr. pixel lighting is more uneven than the normals. When stepping through the shader with pix, it looks like it is working all right.

Is there something I should look at Any renderstate that can mess this up anything





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

bcristian

First, you need to watch out for that signed/unsigned stuff, but I guess you figured that out already by now :D

More to the point, the problem arises because of the topology of the mesh (triangulated quads). Namely, you have vertices where 8 triangles meet and vertices where only 4 triangles meet, so you will get slight (but visible) variations in the normals because of that. The only way I know of to get around that is to actually compute the normals based on the original quads, not the triangles - this should be fairly easy if your terrain comes from a height map.

It is fairly easy to prove this mathematically, but an easier way to test it is like this: create a sphere mesh in, say, Maya - it will start as being made of quads, and notice that it is perfectly smooth. Now triangulate it  - it is still smooth, because the normals are those computed on the quads. Now do a "Average normals" (i.e. exactly what you are doing on your mesh) and you'll notice the same effect.





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

Yes. The signed stuff *sigh*. I don't know exactly why, but I simply thought (without really thinking) that -0.5 0.5 0.5 would convert into 0.5 0.5 0.5. That was silly.

My terrain is not from a height map. It starts as a cube and is subdivided and subdivided to optimize the mesh that you actually see. I can not really get arround the triangles, but perhaps I should consider calculating normals based on neighbour vertices rather than connected triangles. I just need to rip up my entire datastructure to stuff in that neighbourhood information.

Would it get arround the problem to do it like this Some vertices will still have more neighbours than others, from 8 to 4, as far as I can tell.

It sounds as if you actually recognize this problem. You have seen this effect before What confuses me is that the normals seem smooth while the lighting calculation is every thing but. That appers to be wrong. I just can't see what the errornous (is that a word ) step should be.





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

Unless I misunderstood you, the images

www.greenleaf.dk/smooth1.bmp

www.greenleaf.dk/smooth2.bmp

www.greenleaf.dk/smooth3.bmp

Shoould show the artifact. They do not. Smooth2 is a wireframe view of the planet after moving in close to the surface with optimization and then turning optimization off and moving out. The mesh shows all sorts of triangles at various sizes, but the shading is smooth as... uhm.. something very smooth.

According to your maya example, which I cant recreate right now since I don't have maya or 3dsmax or anything like it here, I should get visible seams here as well... or am I missing the point

Anyway... again it looks like the normals are allright... just... I dislike the artifacts which i do not understand.





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

bcristian

Yes, I have seen the problem before, at very close range I might say :D, since I worked on this kind of stuff.
It is not that the normals are not "smooth", in the strict mathematical sense they are. The problem is how they are computed. The fact that there are varying numbers of faces sharing a vertex is also not an issue, but you need to compute them using a uniform basis. Using the example I mentioned earlier with the sphere, it will not show any artifacts as long as the normals are computed based on the quads (a uniform basis, each vertex being shared by 4 faces), even if triangles are used.
The reason the samples you posted here do not show the same issue is simply a matter of scale.




Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

bcristian

I have seen that you are using several (I guess) methods of adaptive subdivision (or whatever other fancy words some people might use for it :D ).
Indeed, that poses a bit of a problem, since the mesh is even more irregular than the simple case of a displaced regular grid, and more importantly even the data might not be readily available in a regularly-sampled form.
What comes to my mind right now is to find a way to compute the normals on a uniform basis, i.e. one with regular connectivity, and then use interpolation to get the values at the actual vertex positions, instead of trying to analyze the mesh topology.
Of course, what the best solution actually is depends on the details of your particular application. Also, if it comes to that, you might want to consider if this really is that much of a problem. Once you put textures on, you'll see that the artifacts are virtually invisible in all but the most extreme cases, so it might not be worth wasting a lot of CPU cycles on something that makes little difference. But then again, this is something that is completely related to what you need to achieve.




Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

ThomasAG

Is there a name for this effect, so I could read up on it

I tried calculating vertex normals in a uniform way now. Each vertex is based on four triangle normals. The way this mesh is built means that whenever it is refined, two triangles are split into four with a common center vertex. This means that I can define the vertex's normal to be the average of the four new ones.

The pyramids are gone, but the terain looks like a mic between faceted and smooth shading. Aparently that is not good enough. Perhaps some ofter weithing of the normals, when using more triangles, can be used I





Re: Game Technologies: Graphics Calculating normals for large mesh with no vertex to triangle info

bcristian

I do not know if there is a standard name for this or not, I did not read about it anywhere. I simply ran into the problem when I first wrote the code for computing the normals and got the "pyramids" effect when averaging the normals of the triangles around the vertex. I gave the example with the sphere because that is where I actually got my hints from, by thinking about how the normals were computed in the two situations.

I do not quite understand your new tesselation scheme, so I am not sure what the problem is now - as I said, I dealt with a regular grid (height map), which is a simpler case. But if you post some screenshots I will have a look.