Archived

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

finding edges

This topic is 5129 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 need a quick algorithm for finding shared edges between two triangles within a huge list of triangles held as a bunch of vertices, I need it to find all edges that have the same position but not normals on both verts on both triangles so I can patch up some cracks in my N-patched models Bobboau, bringing you products that work... in theory

Share this post


Link to post
Share on other sites
It would help if you gave us a bit more information about how your vertices are stored...

Assuming vertices are held as x,y,z...


Vertex_S { float x,y,z; };

__forceinline bool CompareVerts(Vertex_S &v1, Vertex_S &v2)
{
if (v1.x==v2.x && v1.y==v2.y && v1.z==v2.z)
return true;
return false
}

void FindShared(Vertex_S *ptrVertList, long NumVerts)
{
long ct1, ct2;
for (ct1=0;ct1<NumVerts-2;++ct1)
{
//Only have to compare against whatever is left!

for (ct2=ct1+1;ct2<NumVerts;++ct2)
{
if (CompareVerts(ptrVertList[ct1],ptrVertList[ct2]))
{
/*These 2 vertices are the same!
Now you'd search for each face that used ct2 as an index
and change it to ct2, then you'd copy all the data in your
vertex list back one (overwriting ct2), and subtract one from
NumVerts! Make sure you check fi the u,v are the same, and
possibly the normal as well, because sometimes you WANT a
break where a texture coord and/or normal change (sharp edges
or sections that you want to use another part of the texture map).
*/

}
}
}
}



--- Edit ---
This only checks on a per vertex, not per side... but it accomplishes the same thing.

[edited by - Ready4Dis on November 29, 2003 4:40:05 PM]

Share this post


Link to post
Share on other sites
well the triangles are stored in two places one is in a BSP-like thing the other is in this

struct poly_list{
poly_list():n_poly(0),vert(NULL),norm(NULL){};
~poly_list(){if(vert!=NULL)delete[] vert; if(norm!=NULL)delete[] norm;};
int n_poly;
vertex *vert;
vector *norm;
};

vector is a simple x,y,z, vertex holds a x,y,z as well as a u,v and r,b,g, and some other stuff that is of no real importance

vert and norm are dynamicly alocated to be 3*n_poly
there is an array of 64 poly_lists (one fore each posable texture in the model, normaly only 1-4 are used) wich is used to temporarily store all the data from the BSP tree before a vertex buffer is made for rendering. (this is all done only once when the model is first loaded). I need to search through all 64 poly_lists and find edges that don't share both normals so I can generate a patch for the cracks wich will result along that edge when useing n-patching
now I could do this ether in the BSP tree before I make the poly_list (wich would have the advantavge of useing polygons rather than just triangles, as well as haveing the positions and normals as both seperate indexes, but useing the BSP tree is quite a bit slower)or useing the poly_list(s) before I send them off to make the buffers(wich is my current aproche).

Bobboau, bringing you products that work... in theory

[edited by - Bobboau on November 29, 2003 7:19:17 PM]

Share this post


Link to post
Share on other sites