🔒 Locked

Performance issue

Started by scramble Jun 30, 2000 at 5:01 AM 3 replies 250+ views

Original Post

Jun 30, 2000 at 5:01 AM

Hi there! First of all, I have to thank u all for the great help we got in writin'' our 3ds loader. Now there is just a little problem. I tried to import a 3ds mesh of a space-ship. A GREAT mesh. I mean countin'' about 130.000 faces (ugh!). Our loader load this mesh in about 1 minutes and 10 seconds, VS the 10 seconds (!!!) of 3DExploration! I made a profile of our program execution, and I found out that the great part of the time is due to the vertex normals calculation. I''ve read that there is no other alguritm to do that (we calculate the normals by doin'' an average the normals of all the faces that share that vertex). But I can''t figure out HOW 3dEsploration load the mesh in such a small time!!! It doesn''t calculate the normals? It''s impossible, as the lightin'' is rendered. Have the developers of 3dExploration implemented an alguritm to calculate normals that reduce the time by the 80%?!?!? I would be gratefull if someone could help us! Byez!

MadKeithV

Mod

155

MadKeithV

Jun 30, 2000 at 6:16 AM

They probably just made a much more efficient version of the same algorithm you are using. You could first calculate all the face normals, and then do the normal averaging, to be able to leverage the cache and loop optimisations maximally.

It''s hard to tell you what to do exactly, since I don''t know exactly HOW you''ve programmed the normal calculation.

Give me one more medicated peaceful moment..
~ (V)^|) |<é!t|-| ~
ERROR: Your beta-version of Life1.0 has expired. Please upgrade to the full version. All important social functions will be disabled from now on.

Ratsia

Jul 3, 2000 at 1:09 AM

You could try this:

for each_face{
calculate_face_normal;
for each_face_vertex{
count[vertex]++;
vertex_normal[vertex]+=face_normal;
}
}

for each_vertex{
vertex_normal[vertex]/=count[vertex];
}

It should be much more efficient because you don''t have those nested loops.

tcs

Jul 7, 2000 at 3:39 PM

I think all those optimisations are right, but they don''t go to the point: You have to loop trough every vertex and compare it with about 50% of all vertices. That''s slow... Maybe you should use some clever presorting. I wrote a lightmap renderer that had the same problem:

Imagine you have 5 light sources, 1000 triangles and 32x32 pixel per lightmap. That means: 5x32x32x1000x1000=5120000000 calculations.

The key is the "early-out" concept. Get rid of all edges that can''t touch the current vertex. There are LOTS of conecepts, you even want to use Octrees. I promise you that you can built an Octree for 100.000 polys under 1 minute, even on low end systems. If you want to know more about Ocrtrees, there''s a tutorial on my site. If you want to know how to implement some ease "early-out" alogrithms, you can download my lightmap-triangle class from my site,

Tim

--------------------------
www.gamedev.net/hosted/glvelocity
glvelocity.gamedev.net
www.glvelocity.com

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.