#### Archived

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

# Optimization help...

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

## Recommended Posts

I'm a little stuck here, and I need some help. Basically I have a huge loop with a huge bottleneck. It's too slow. Here's the entire function:
void CalculateNormals() {
unsigned int numPolygons = (unsigned int)ceil(double(numIndex / 3.0));
Vector3d *FaceNormal = new Vector3d[numPolygons + 1];

unsigned int Counter = 0;
for (unsigned int i = 0; i < numIndex; i += 3) { // Calculate the face normals

FaceNormal[Counter++] = Cross(Vertex[Index[i]] - Vertex[Index[i + 1]],
Vertex[Index[i]] - Vertex[Index[i + 2]]);
}

Normal = new Vector3d[numVertex];
for (i = 0; i < numVertex; i++) { // Loop through every vertex

for (unsigned int j = 0; j < numIndex; j += 3) { // Loop through every face

if (Index[j] == i || Index[j + 1] == i || Index[j + 2] == i) {
Normal[i] += FaceNormal[j / 3]; // If the face indexes the vertex, add the face's normal to the vertex normal

}
}
Normal[i].Normalize();
}
delete[] FaceNormal;
}
This loop is the bottleneck:

for (i = 0; i < numVertex; i++) { // Loop through every vertex

for (unsigned int j = 0; j < numIndex; j += 3) { // Loop through every face

if (Index[j] == i || Index[j + 1] == i || Index[j + 2] == i) {
Normal[i] += FaceNormal[j / 3]; // If the face indexes the vertex, add the face's normal to the vertex normal

}
}
Normal[i].Normalize();
}
I'm hoping to get some tips or ideas on how to optimize it. Thanks! [Edit: Fixed source tags] [edited by - James Trotter on June 6, 2004 3:29:13 PM]

##### Share on other sites
Odds are the normal.normalise is the costly bit, with a square root to calculate. Assuming your face normals are all pre-normalised then you could just divide your normal by the number of face normals you''ve added together.

##### Share on other sites

Oddly enough, when I comment out the normalization I gain no noticeable speed whatsoever. I'm profiling it, and it takes the same amount of time.

It is probably the if statement inside the inner loop... But I'm not sure what to do to make it more efficient. Any tips?

[Edit: Spelling]

[edited by - James Trotter on June 6, 2004 3:36:51 PM]

##### Share on other sites
quote:
Original post by PouyaCatnip
Odds are the normal.normalise is the costly bit, with a square root to calculate. Assuming your face normals are all pre-normalised then you could just divide your normal by the number of face normals you''ve added together.

No. Simple example:
n1 = (1, 0, 0)
n2 = (0, 1, 0)
n = (n1 + n2) / 2 = (1, 1, 0) / 2 = (0.5, 0.5, 0)
length(n) = sqrt(0.25 + 0.25) != 1

##### Share on other sites
quote:
Original post by BitMaster
No. Simple example:

Dang. Silly me, I should have thought that one through.

##### Share on other sites
OK, so the function calculates face and vertex normals. Do need face normals or are you just using them to get to vertex normals.

Anyways.. this can be optimized quite a bit. It''s basicly just 3 single loops. First go trough all vertices and set normal to zero. Then go trough all faces and calculate face normal and add it to coresponding 3 vertices. The last loop is simply to normalize all normals.

You should never let your fears become the boundaries of your dreams.

##### Share on other sites
Hi, DarkWing.

Thanks for the insightful comment. I really hadn''t thought of doing it that way. I''ll try it out, and inform you of the results.
Much appreciated!

##### Share on other sites
quote:
Original post by James Trotter
Hi, DarkWing.

Thanks for the insightful comment. I really hadn''t thought of doing it that way. I''ll try it out, and inform you of the results.
Much appreciated!

Show us the code after you implemented this and we''ll see if anything else can be done.

You should never let your fears become the boundaries of your dreams.

##### Share on other sites
It works elegantly. Performance has increased ten-fold in that function. It''s no longer the bottleneck. But there are other places in the code that needs optimization. I''ll have a look at it, and if there''s anything I need help with I might be back.

Thanks a million, DarkWing!

##### Share on other sites
quote:
Original post by _DarkWIng_
Show us the code after you implemented this and we''ll see if anything else can be done.

You should never let your fears become the boundaries of your dreams.

Sure, no problem. Here''s the code:

void CTerrain::CalculateNormals() {
if (!Vertex || !Index) {
Log->Output("Error in CTerrain::CalculateNormals(): Missing data!");
return;
}

if (Normal) {
Log->Output("Error in CTerrain::CalculateNormals(): Normals already exist!");
return;
}

unsigned int numPolygons = (unsigned int)ceil(double(numIndex / 3.0));
Vector3d *FaceNormal = new Vector3d[numPolygons + 1];
Normal = new Vector3d[numVertex];

int Counter = 0;
for (unsigned int i = 0; i < numIndex; i += 3) { // Calculate the face normals

FaceNormal[Counter] = Cross(Vertex[Index[i]] - Vertex[Index[i + 1]],
Vertex[Index[i]] - Vertex[Index[i + 2]]);

Normal[Index[i]] += FaceNormal[Counter];
Normal[Index[i + 1]] += FaceNormal[Counter];
Normal[Index[i + 2]] += FaceNormal[Counter];
}

for (i = 0; i < numVertex; i++)
Normal[i].Normalize();

delete[] FaceNormal;
}

1. 1
Rutin
69
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633421
• Total Posts
3011794
• ### Who's Online (See full list)

There are no registered users currently online

×