#### Archived

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

# finding edges

This topic is 5434 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites

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 indexand change it to ct2, then you'd copy all the data in yourvertex list back one (overwriting ct2), and subtract one fromNumVerts!  Make sure you check fi the u,v are the same, andpossibly the normal as well, because sometimes you WANT abreak where a texture coord and/or normal change (sharp edgesor 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 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]

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 14
• 9
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
632912
• Total Posts
3009191
• ### Who's Online (See full list)

There are no registered users currently online

×