Archived

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

vicviper

finding neighbour faces in a large mesh

Recommended Posts

vicviper    130
Hi! I have a little big problem, I want to compute normals of a mesh with a large amount of triangles(+20000) , and they have to be computed in a way that every vertex shares the normal of all its neightbour triangles (so triangles will be rendered smoothed). I already have the loop running, the problem is that it is painfully slow, it takes near 15min to go. I''m not using that for computing terrain normals, but to compute normals of typical 3D meshes. So far, I noticed that most of the time what the loop does is to try to find the neighbour triangles of every vertex, since the triangle table is +20000, the loops are painfully slow... after finding the triangles I have no problem computing the normals. So, the question is: is there any way to rearrange the triangles of a mesh, or any other trick (like building a tree, a lookup table, whatever), to find the triangles that share a vertex in a large table?

Share this post


Link to post
Share on other sites
Tessellator    1394
I don''t have long to write a decent reply, so i''ll just point you to where I got the info from the first time when I had the same problem:

http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00004040&forum=3dtheory&id=-1

The approach I use is the one explained by wogotus a little down the conversation. This basically explains how to use a vertex hash to hash geometricaly close vertices into the same bucket.

T

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
It shouldn''t be that slow. Are you finding the neighbours for each vertex?

A simple way to calculate the vertex normals quickly is create the array for the normals and initialize them to the zero vector. Then visit each triangle, add its normal (weighted if you like) to the each of the triangle''s three vertices'' normals. Once you have visited all the triangles normalize the vertex normals and you are done.

Share this post


Link to post
Share on other sites
cseger    122
I do it like this, it''s really fast:

Build a temp vertex struct

struct TempVert {
vertIndex
vector<triangle*> triangles
}

Build a copy of your vertex list with the temp vertex struct.

Then I loop thru the triangles and put a pointer
to the triangles in the vertices it is connected to, like this:

for (t < tris){
for (v < 3)
tempvertlist[tri->vertIndices[v]].push_back(tris[t]);
}

Then you have a list which incluedes the triangles each
vertex is connected to, then just loop thru it and
calculate the smoothed normal for all vertex.

Hope it helps.

Share this post


Link to post
Share on other sites
vicviper    130
quote:
Original post by cseger
I do it like this, it''s really fast:

Build a temp vertex struct

struct TempVert {
vertIndex
vector<triangle*> triangles
}

Build a copy of your vertex list with the temp vertex struct.

Then I loop thru the triangles and put a pointer
to the triangles in the vertices it is connected to, like this:

for (t < tris){
for (v < 3)
tempvertlist[tri->vertIndices[v]].push_back(tris[t]);
}

Then you have a list which incluedes the triangles each
vertex is connected to, then just loop thru it and
calculate the smoothed normal for all vertex.

Hope it helps.



yes, this is exactly what I did, thanks anyway

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
quote:
Original post by cseger
I do it like this, it''s really fast:

Build a temp vertex struct

struct TempVert {
vertIndex
vector<triangle*> triangles
}

Build a copy of your vertex list with the temp vertex struct.

Then I loop thru the triangles and put a pointer
to the triangles in the vertices it is connected to, like this:

for (t < tris){
for (v < 3)
tempvertlist[tri->vertIndices[v]].push_back(tris[t]);
}

Then you have a list which incluedes the triangles each
vertex is connected to, then just loop thru it and
calculate the smoothed normal for all vertex.



Why to unnecessarily calculate the normal of the traingles (or have extra storage space) for them.

What I had mentioned earlier was:

for(i < numVertices)
vertexNormal = {0,0,0}

for(t < numTris)
{
calc triNormal;
for(v<3)
vertexNormal[tri->vertIndices[v]] += triNormal;
}
for(n < numVertices)
normalize(vertexNormal[i]);

Share this post


Link to post
Share on other sites
Tessellator    1394
The only problem with that approach is that you may have more than one vertex on exactly the same spot, but referenced by different indices. This can happen on the boundaries of differing textures/materials etc. If this is the case, just smoothing based on geometry indexing can leave parts of the mesh unsmooth.

T

Share this post


Link to post
Share on other sites
davepermen    1047
i don''t get why it is that slow. the algorithm above runs in some milliseconds MAX for such a mesh..


for each vertex v in mesh {
v.normal = 0,0,0;
}

for each face f in mesh {
n = calcnormal(f);
mesh.vertex[f.a].normal += n;
mesh.vertex[f.b].normal += n;
mesh.vertex[f.c].normal += n;
}

for each vertex v in mesh {
normalize(v.normal);
}


this is NEVER that slow. you don''t need to search ANY vertex at ANY time..

smooths where its smooth..

yes, doesn''t bother about same vertices with different texcoords..
but its blazingly fast! possible in realtime even..

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Tessellator    1394
I was going to suggest that approach at first, but then I realised vicviper wanted to know every triangle that touches the vertex, and that requires something a bit more complex as I said above (except when you know the model data to have only one unique vertex at every location i.e. often in a terrain mesh).

T

Share this post


Link to post
Share on other sites
blue_knight    194
If you split vertices based on texcoords, materials or whatever calculate your normals BEFORE you split your vertices that way you can use the fast method.

Share this post


Link to post
Share on other sites