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

finding edges

This topic is 5128 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 goth 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
well... do you have a list of verticies, which you just render a triangle out of each set of three verticies... do you use triangle strips, or triangle fans? or is your array indexed? All of those are factors that will affect your finding of an efficient search algorithm.

Share this post

Link to post
Share on other sites
I used a brute force approach, which works but can be goddamn slow. The most noticeable slowdown occurs when detecting up identical vertices. in that case, building a 3D kd-tree would sort them quickly, and it''s easy to build. A KDtree is nothing more than a BSP tree with axis aligned split planes. Done on vertices, it will be very efficient.

You add vertices in a pool, when adding, you retrieve an index, and convert your triangle into 3 indices to vertices. then you had these triangle (with indices) into a pool of triangles, and possibly add to the vertex in the pool the triangle index, so you can query for neighbouring triangles.

// the input triangles

List<CPrimitive> Primitives;

// the output triangles (with indices and neighbours)

List<CTriangle> Triangles;

// the output triangles (with indices and neighbours)

List<CEdge> Edges;

// stores the vertices in a KDtree

// CVertex are 3D vectors, plus list of attached triangles

KDTree<CVertex> Tree;

for(int i = 0; i < Primitives.Size(); i ++)
CVertex* pxVertex0 = Tree.Add(Primitives[i].V[0]);
CVertex* pxVertex1 = Tree.Add(Primitives[i].V[1]);
CVertex* pxVertex2 = Tree.Add(Primitives[i].V[2]);

if (!pxVertex0 || !pxVertex1 || pxVertex2) continue;

CTriangle* pxTriangle = Triangles.Add(pxVertex0, pxVertex1, pxVertex2);

if (!pxTriangle) continue;

Edges.AddEdge(pxVertex0, pxVertex1, pxTriangle);
Edges.AddEdge(pxVertex1, pxVertex2, pxTriangle);
Edges.AddEdge(pxVertex2, pxVertex0, pxTriangle);

when you add a vertex to the tree, you go down the tree, and check if the vertex is already added. if so, return that vertex, else add a new one and return its address.

when you add a triangle to the tree, you check if the triangle is valid, if it is already present, if its area is not 0, ect...

then you can add the triangle edges to the list of edges. The list of edges will check if such an edge exists, if so, it will add a triangle reference to the edge, else create a new one.

to make things faster, vertices should have a list of triangles attached to it, as well as a list of edges. Basically, interconnect everything. Triangles with list of edges (3 of them), list of vertices (3 vertices), vertices with lists of edges and lists of triangles, edges with list of vertices (2 of them) and list of triangles...

then you have a complete topology of the model, with the cracks showing

Share this post

Link to post
Share on other sites