Jump to content
  • Advertisement

Archived

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

James Trotter

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Thanks for the quick reply.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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;
}

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!