My brain is cramped (Calculating terrain normals)
Author
I have been trying for the longest time to calculate normals in order for my terrain to have good looking lighting. Well I have finally found out what I needed to do and started coding it. I got the idea down that I need to average the surface normals surrounding each vertex. Well my terrain engine is basically just NeHe's exact implementation (uses quads for rendering.)
Ok so heres how I am calculating my normals right now:
I have a function called BuildNormals which loops through the HeightMap array the same way the rendering code does, and instead of rendering anything, it just takes a couple of edge vectors and calculates normals for the surface. This is implemented now and works fine except everything is very faceted.
So I wanted to blend my surface normals. So inside of my buildnormals function I have it shove all of the surface normals into an array of a structure I made called SurfaceNorm. SurfaceNorm has a CVector (this class I made) for the normal, and an array of 4 CVertexs called connectedTo, which stores the 4 surrounding vertices of that quad. So in my BuildNormals function, it takes the edge vectors of my quad and then calcs the normal, and stores it in surfnormalarray[QuadCounter].normal and then lists those 4 verts in the array under the connectedTo CVertex. Did any of that make sense :-)
So I got a function that creates all of the surface normals for the map and then stores them in an array including which vertices the quad is connected to.
Now I have a function called BuildDispLists which basically renders the terrain (in exactly the way NeHe does it) except instead of rendering it, it creates a display list (faster.)
Now inside of the BuildDispLists function, where you place your glNormal3f call, I have a call to my function ProcessNormals(int X, int Y, int Z). The three variables t takes are the x,y, and z of the vertice I am currently placing. Then it loops through my surfacenormalarray and for each one of them, it loops through the four connectedTo variables. And through each one of those it loops through the x, y, & z values of the stored vertice and the vertice I am working with. If they match then I push back the normal of the surface normal that I am working with back. It continues looping through the entire array. Then it goes back to the BuildDispLists function and on to the next vertice.
My MAP_SIZE is 1024, so you take 1024 x 1024 and I have got a 1MB array storing my HeightMap loaded from the RAW file. Then I have an array for the surface normals which is (1024 x 1024 / 4) x 60 (60 = the size of my SurfaceNorm struct)
So it works flawlessly in the game, I am zooming around and the lighting looks great... The only problem is, that after I started my game, it took about 1 hour to calculate the normals for my height map. That is UNACCEPTABLE. I am now writing a program that calculates it before hand and puts it into a file that I can load when starting my game. This should reduce the startup time to almost nothing, but the compile time for each map would still be an hour using this new program.
I have to be doing something wrong. I mean how could it take this long. Is there an easier way of calculating the averaged normals? And I know that there is an article on gamedev.net that explains how to calculate averaged normals but I didn't understand it and I can't use it because I am rendering using quads, while they are rendering using triangles.
Well any help will be appreciated because I cannot think anymore at 2:30 in the morning. If you need clarification, please ask.
The problem is that you're looping through the entire array to find the right quad... or something. I can't really see what or why. I'll write you some code off the top of my head, see if you can make any sense out of it. At least this way there is not chance a direct copy&paste will work ;).
Unless I've screwed up, that should leave normals filled with averaged normal at each vertex. What to do with that is up to you.
// Assumes vertices are 1 unit apartstd::vector<float> heights(width * height);std::vector<Vec3> normals(width * height);for (int i = 0; i < width * height; i++) normals = Vec3(0, 0, 0); // Zero the normals so we can add to them to combine face normals.for (int y = 0; y < height - 1; y++) // Iterate over all quads{ for (int x = 0; x < width - 1; x++) { Vec3 vertA(x, y, heights[y * width + x]); // Note z is considered to be up. Vec3 vertB(x + 1, y, heights[y * width + x + 1]); Vec3 vertC(x, y + 1, heights[(y + 1) * width + x]); Vec3 vertD(x + 1, y + 1, heights[(y + 1) * width + x + 1]); // Take the 3 vertices closest to vertA and make a triangle from them. // Cross product the edges involving vert a to find it's normal, and add this to A. // The other quads involving vertA will also add to A's normal, making it the average. // If the z of any of these comes out less than 0 then they are upside down, // so swap the left side of each minus sign (in this case swap B and C). // I can't be bothered working it out myself. normals[y * width + x] += normalise(crossProduct(B - A, C - A)); normals[y * width + x + 1] += normalise(crossProduct(A - B, D - B)); normals[(y + 1) * width + x] += normalise(crossProduct(A - C, D - C)); normals[(y + 1) * width + x + 1] += normalise(crossProduct(B - D, C - D)); }}// Now your corner normals are fine, edge ones are twice as big, and centre ones are 4 times.// But this is such a huge performance improvement anyway I can't see the point in all that logic.// You could just divide by 4 if you don't care about edges.for (int i = 0; i < width * height; i++){ normals = normalise(normals);}Unless I've screwed up, that should leave normals filled with averaged normal at each vertex. What to do with that is up to you.
Okay it should not take that long, I work my normals out on the fly, the colour of the terrain and texturing and it takes about 10-20 secs.
Here is a recap on how to do it.
CVector3 tempNormal = new CVector3[width][height];
Now loop through and find the normal of each quad (remember the normal of a quad is the average of it's two triangles)
tempNormal[x][y] = Normalize(Normal(quad[x][y].vertex1,quad[x][y].vertex2,quad[x][y].vertex3)+Normal(quad[x][y].vertex4,quad[x][y].vertex2,quad[x][y].vertex3));
Okay so now you have the normal of each quad, now we make the vertex normals
// Vertex normal is as global or class memeber
vertexNormal = new CVector3[width][height];
vertexNormal = Normalize(tempNormal[x][y]+tempNormal[x+1][y+1]+tempNormal[x+1][y]+tempNormal[x][y+1]);
// Okay and finally if you want to smooth your terrain a bit u can use box filtering, it is extremely useful for smoothing shadows and lighting.
Try making a very noisy non smooth heightmap and applying the box filter, you will see very nice results
Here is a recap on how to do it.
CVector3 tempNormal = new CVector3[width][height];
Now loop through and find the normal of each quad (remember the normal of a quad is the average of it's two triangles)
tempNormal[x][y] = Normalize(Normal(quad[x][y].vertex1,quad[x][y].vertex2,quad[x][y].vertex3)+Normal(quad[x][y].vertex4,quad[x][y].vertex2,quad[x][y].vertex3));
Okay so now you have the normal of each quad, now we make the vertex normals
// Vertex normal is as global or class memeber
vertexNormal = new CVector3[width][height];
vertexNormal = Normalize(tempNormal[x][y]+tempNormal[x+1][y+1]+tempNormal[x+1][y]+tempNormal[x][y+1]);
// Okay and finally if you want to smooth your terrain a bit u can use box filtering, it is extremely useful for smoothing shadows and lighting.
/*************************************************************************//* NOT MY BLENDING FUNCTIONS *//*************************************************************************/void BoxFilterHeightMap(bool smoothEdges,int Width,int Height,float *&H){ // width: Width of the height map in bytes // height: Height of the height map in bytes // heightMap: Pointer to your height map data // Temporary values for traversing single dimensional arrays long x = 0; long z = 0; long widthClamp = (smoothEdges) ? Width : Width - 1; long heightClamp = (smoothEdges) ? Height : Height - 1; long Length = Width*Height; float *HeightMap = H; // [Optimization] Calculate bounds ahead of time // Validate requirements if (!HeightMap) return; // Allocate the result float *result = new float[Length]; // Make sure memory was allocated if (!result) return; for (z = (smoothEdges) ? 0 : 1; z < heightClamp; ++z) { for (x = (smoothEdges) ? 0 : 1; x < widthClamp; ++x) { // Sample a 3x3 filtering grid based on surrounding neighbors float value = 0.0f; float cellAverage = 1.0f; // Sample top row if (((x - 1) + (z - 1) * Width) >= 0 && ((x - 1) + (z - 1) * Width) < Length) { value += HeightMap[(x - 1) + (z - 1) * Width]; ++cellAverage; } if (((x - 0) + (z - 1) * Width) >= 0 && ((x - 0) + (z - 1) * Width) < Length) { value += HeightMap[(x ) + (z - 1) * Width]; ++cellAverage; } if (((x + 1) + (z - 1) * Width) >= 0 && ((x + 1) + (z - 1) * Width) < Length) { value += HeightMap[(x + 1) + (z - 1) * Width]; ++cellAverage; } // Sample middle row if (((x - 1) + (z - 0) * Width) >= 0 && ((x - 1) + (z - 0) * Width) < Length) { value += HeightMap[(x - 1) + (z ) * Width]; ++cellAverage; } // Sample center point (will always be in Length) value += HeightMap[x + z * Width]; if (((x + 1) + (z - 0) * Width) >= 0 && ((x + 1) + (z - 0) * Width) < Length) { value += HeightMap[(x + 1) + (z ) * Width]; ++cellAverage; } // Sample bottom row if (((x - 1) + (z + 1) * Width) >= 0 && ((x - 1) + (z + 1) * Width) < Length) { value += HeightMap[(x - 1) + (z + 1) * Width]; ++cellAverage; } if (((x - 0) + (z + 1) * Width) >= 0 && ((x - 0) + (z + 1) * Width) < Length) { value += HeightMap[(x ) + (z + 1) * Width]; ++cellAverage; } if (((x + 1) + (z + 1) * Width) >= 0 && ((x + 1) + (z + 1) * Width) < Length) { value += HeightMap[(x + 1) + (z + 1) * Width]; ++cellAverage; } // Store the result result[x + z * Width] = value / cellAverage; } } // Release the old array delete [] HeightMap; // Store the new one H = result;};Try making a very noisy non smooth heightmap and applying the box filter, you will see very nice results
neonic, the behavior you describe is what happens when you consume too much memory and the OS starts swapping to the hard-drive. From the looks of it, you're using 1024 * 1024 ( = over a million!) std::vectors! That is a terrible waste, and likely the culprit.
You should be able to basically cut'n'paste RAZORUNREAL's code and it will calculate your normals in a few dozen milliseconds :)
You'll only need more complicated methods when dealing with non-regular grids, where you need to calculate adjacency info.
You should be able to basically cut'n'paste RAZORUNREAL's code and it will calculate your normals in a few dozen milliseconds :)
You'll only need more complicated methods when dealing with non-regular grids, where you need to calculate adjacency info.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
