I spend too much time in computing normals
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...) ?
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.
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.
Could you explain a little bit more please your idea ?
Could you explain a little bit more please your idea ?
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.
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
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
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.
Can you post the code you use to calculate the normals? Perhaps there are some optimizations you missed..
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
/__fold
> 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]
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]
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.p1].x;<br>float dx2 = _cPos[_faceList.p3].x - _cPos[_faceList.p1].x;<br>float dy1 = _cPos[_faceList.p2].y - _cPos[_faceList.p1].y;<br>float dy2 = _cPos[_faceList.p3].y - _cPos[_faceList.p1].y;<br>float dz1 = _cPos[_faceList.p2].z - _cPos[_faceList.p1].z;<br>float dz2 = _cPos[_faceList.p3].z - _cPos[_faceList.p1].z;<br>_faceNormal.x = dy1 * dz2 - dz1 * dy2;<br>_faceNormal.y = dx2 * dz1 - dz2 * dx1;<br>_faceNormal.z = dx1 * dy2 - dy1 * dx2;<br>}<br> <br>Then I compute normals for each vertex<br>for(size_t i = 0; i < _connect.size(); i++) {<br> Util3D::Float3 n(0.f, 0.f, 0.f);<br> for(size_t j = 0; j < _connect.size(); j++) {<br> n.x += _faceNormal[_connect[j]].x;<br> n.y += _faceNormal[_connect[j]].y;<br> n.z += _faceNormal[_connect[j]].z;<br> }<br> _verticesNormal = n;<br>}<br><br>Some explanations here :<br>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).<br>So we have :<br>std::vector< std::vector<int> > _connect;<br><br>For each vertex I sum the normals of the faces that contain it.<br><br>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.<br><br>In my test I have a regular grid => 128*128 vertices, 32768 faces and this piece of code takes 30% of the time.<br><br>I need to compute normals for all vertices, displayed or not because I'll use them later for the physical model of the sea. </i> <br><br><SPAN CLASS=editedby>[edited by - jourdan_thomas on August 14, 2003 3:27:45 AM]</SPAN>
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.p1].x;<br>float dx2 = _cPos[_faceList.p3].x - _cPos[_faceList.p1].x;<br>float dy1 = _cPos[_faceList.p2].y - _cPos[_faceList.p1].y;<br>float dy2 = _cPos[_faceList.p3].y - _cPos[_faceList.p1].y;<br>float dz1 = _cPos[_faceList.p2].z - _cPos[_faceList.p1].z;<br>float dz2 = _cPos[_faceList.p3].z - _cPos[_faceList.p1].z;<br>_faceNormal.x = dy1 * dz2 - dz1 * dy2;<br>_faceNormal.y = dx2 * dz1 - dz2 * dx1;<br>_faceNormal.z = dx1 * dy2 - dy1 * dx2;<br>}<br> <br>Then I compute normals for each vertex<br>for(size_t i = 0; i < _connect.size(); i++) {<br> Util3D::Float3 n(0.f, 0.f, 0.f);<br> for(size_t j = 0; j < _connect.size(); j++) {<br> n.x += _faceNormal[_connect[j]].x;<br> n.y += _faceNormal[_connect[j]].y;<br> n.z += _faceNormal[_connect[j]].z;<br> }<br> _verticesNormal = n;<br>}<br><br>Some explanations here :<br>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).<br>So we have :<br>std::vector< std::vector<int> > _connect;<br><br>For each vertex I sum the normals of the faces that contain it.<br><br>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.<br><br>In my test I have a regular grid => 128*128 vertices, 32768 faces and this piece of code takes 30% of the time.<br><br>I need to compute normals for all vertices, displayed or not because I'll use them later for the physical model of the sea. </i> <br><br><SPAN CLASS=editedby>[edited by - jourdan_thomas on August 14, 2003 3:27:45 AM]</SPAN>
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement