#### Archived

This topic is now archived and is closed to further replies.

# I spend too much time in computing normals

This topic is 5237 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello I''m actually writing an application to simulate ocean. This works fine but I got a problem, I spend too much time computing the normals. For each frame, I need to compute the normals at each vertex of the grid that define my sea. So first I compute the normal per face (cross product) then the normal per vertices (sum of neighboor normal''s face). When I perform profiling om my application, 30% of the time spent is in the evaluation of the normals. It seems huge for me. So is there a way to compute the normals faster (better algorithm, vertex shader...) ?

##### Share on other sites
Pre-compute a look up table. ie..compute the normal of each vertex of the grid. Then use them with some reference ... its alot of memory but also alot more speed.

##### Share on other sites
I don''t how I can precompute normals in my case because for each frame I don''t know which vertices will be modified and how.

##### Share on other sites
You don''t have to calculate the face normals if the vertices don''t move along x or z. For each vertex, just calculate the cross product of the two vectors going from the vertex and two neighbour vertices. Might not look as good, but it should be faster.

##### Share on other sites
How do you calculate your grid?
If you have two functions for it, one for x and for z you should be able to use the gradient which you calculate with partial derivates.

/__fold

##### Share on other sites
In facts, each vertex of the grid has an orbital movement, and its coordinates are modified along the 3 axis with sum of sinus functions.

##### Share on other sites
Can you post the code you use to calculate the normals? Perhaps there are some optimizations you missed..

##### Share on other sites
It sounds like you could use the gradient. I''ve implemented a renderer for Bezier-patches (4*4) and we used gradients to calculate the normals at each vertex. I don''t really recall how it worked and that annoys me a bit. It''s really fast and simple though.

/__fold

##### Share on other sites
> 30% of the time spent is in the evaluation of the normals

If you are normalizing after each and every vector operation, then that 'fsqrt()' is likely to be the culprit. Try normalizing only when you have to (i.e. when doing lighting calculations on _visible_ triangles only). Otherwise there is a 'quick&dirty' (aka via Taylor series) square root function you can find here or here

-cb

[edited by - cbenoi1 on August 13, 2003 7:31:23 PM]

##### Share on other sites
Ok here you are some code

Evalution of the grid's vertices :
r = wave amplitude
a = angle of the wave
phi = phase of the wave

for each wave
x += r * cos(angle) * sin(phi);
y += r * sin(angle) * sin(phi);
z -= r * cos(phi);

a wave only updates the needed vertices and not the whole grid.

Then when the new vertices are computed, I first compute the normal per face :

_faceList is a vector of face structure
struct Face {
int p1, p2, p3;
}

_cPos is the grid, ie an array of the current position of the vertices and _faceNormal is the array of the normals per face.

for(size_t i = 0; i < _faceList.size(); i++) {
float dx1 = _cPos[_faceList.p2].x - _cPos[_faceList[i].p1].x;
float dx2 = _cPos[_faceList[i].p3].x - _cPos[_faceList[i].p1].x;
float dy1 = _cPos[_faceList[i].p2].y - _cPos[_faceList[i].p1].y;
float dy2 = _cPos[_faceList[i].p3].y - _cPos[_faceList[i].p1].y;
float dz1 = _cPos[_faceList[i].p2].z - _cPos[_faceList[i].p1].z;
float dz2 = _cPos[_faceList[i].p3].z - _cPos[_faceList[i].p1].z;
_faceNormal[i].x = dy1 * dz2 - dz1 * dy2;
_faceNormal[i].y = dx2 * dz1 - dz2 * dx1;
_faceNormal[i].z = dx1 * dy2 - dy1 * dx2;
}

Then I compute normals for each vertex
for(size_t i = 0; i < _connect.size(); i++) {
Util3D::Float3 n(0.f, 0.f, 0.f);
for(size_t j = 0; j < _connect[i].size(); j++) {
n.x += _faceNormal[_connect[i][j]].x;
n.y += _faceNormal[_connect[i][j]].y;
n.z += _faceNormal[_connect[i][j]].z;
}
_verticesNormal[i] = n;
}

Some explanations here :
In my program, actually I use a regular grid for the tests but I can be a progressive mesh. In fact I generate a set of vertices, then I create the faces with a delaunay triangulation. At this time I don't know how many faces are sharing the same vertex so for each vertex, I build the list of face that contain it (this is done once at startup, after the triangulation).
So we have :
std::vector< std::vector > _connect;

For each vertex I sum the normals of the faces that contain it.

I do not normalize, not yet. Opengl does it but the rendering but after I'll have to do it manually because i'll need the normals for other stuffs.

In my test I have a regular grid => 128*128 vertices, 32768 faces and this piece of code takes 30% of the time.

I need to compute normals for all vertices, displayed or not because I'll use them later for the physical model of the sea.

[edited by - jourdan_thomas on August 14, 2003 3:27:45 AM]

##### Share on other sites
gradients could be a could idea, I remember that I used the sobel operator to compute gradients for a stuff an it was pretty fast but I never heard of it for the normals.

I''ll have a look for it.

##### Share on other sites
Is is possible, with vertex shaders, to compute the normals by the GPU, and get back the result on the main memory ? If I send vertices to the GPU they will go through the pipeline of the graphic card and at the ouput I got fragments but is it possible to "intercept" the vertices at the output of the vertex shader unit and send them back to the main memory ?

Sorry if this question seems weird but i''m newbie with vertex/pixel shaders.

##### Share on other sites
Would it be possible for you to precalculate the normals once, and then, whenever you modify a vertice do the same to the normal?

That is, when you rotate the vertice (sin, cos, looks like it?) just apply the same rotations to the face''s normal?

##### Share on other sites
only calculate normals for faces where a vertice actually change.. that should save you some time if you don''t got waves everywhere.

##### Share on other sites
The first loop takes 15 floating point operations, times 32768 to make a whopping 491520. The second loop takes 3 FP ops 128x128 times for a total of 49152, and a grand total of 540672 FP ops. I could be off a bit (I don't have the full source), but the magnitude order should be correct. Now, you'd expect this to run 30 times per second, giving a measure of 16.2 MFLOPS. No wonder this takes up a large chunk of CPU power.

Note that in the first loop, computing the line segments is done *twice*, 95% of the time (2 triangles share the same line segment, except on borders). Reducing this portion of the computation would require a different topology data structure for a reduction from 15 FP ops to 12 FP ops (15 minus the 6 subs divided by 2).

> I need to compute normals for all vertices {...}

Maybe and maybe not. Some suggested adding each vertex a flag so that vertices that don't change can be used to avoid some of the calculations. I'd go farther and say that if the wave doesn't affect more than 10% or 0.01 (or some other user-defined threshold) of the vertex, than it stays unaffected. OK, it's cheating, but users won't see ditch at 30 FPS.

All in all, I think you'd need to add more information to vertices and faces so to avoid calculating the same thing more than once and modifying vertices when you don't have to.

If all else fails, you could convert to fixed point arithmetic using CORDIC algorithms. They are *WAY* faster than FP operations, albeit at the cost of precision.

http://www.dspguru.com/info/faqs/cordic.htm
http://www.andraka.com/cordic.htm
http://www.gamedev.net/reference/articles/article406.asp

Hope this helps.

-cb

[edited by - cbenoi1 on August 14, 2003 10:43:41 AM]

##### Share on other sites
You can speed up your face-normal computation tremendously by fixing the X and Y (assuming Z is up) values to a uniform grid and only varying the height of each vertex. Then all sorts of computations are constant and/or cancel each other.

##### Share on other sites
possibly computer normals for water surface that is only within your view.

possibly computer normals for water surface that is only within a certain distance from the camera - for ex: if the distance is too far, perhaps using the same normal values would look just as good, maybe even better, since the farther its away the less visible it should be, depending on the "atmosphere" of your game i guess.

not so sure myself on how to let the GPU process it instead of the CPU. how would one go about programming that?

and one more thing, if you have a profiler, like Intel''s VTuner, then try giving that a try. It will give you a lot fo suggestions.