finding neighbour faces in a large mesh
Author
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?
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
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
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.
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.
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.
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.
Author
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
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);<br><br> </i>
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
T
i don''t get why it is that slow. the algorithm above runs in some milliseconds MAX for such a mesh..
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
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
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
T
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
