# Shared triangles using hash method

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

## Recommended Posts

I have an application for finding shared triangles of each triangle in the mesh.
It is a brute force method and it takes minutes together to finish for mesh of large size.

How can I use hashmap or map and achieve significant speed up.
 long* FindAdjacent(IN unsigned long* pulIndices, IN unsigned long ulFaceCount) { int nAdjTriCount, nCommonIntersectpnt; long lAdjTriIndices[10000]; unsigned long i, j, iii, ulMin; /* Array Stores the adjacent triangles of a given triangle */ long* plAdjTriList = new long[ulFaceCount * 3](); for (unsigned long itr = 0; itr < 3 * ulFaceCount; ++itr) { plAdjTriList[itr] = -1; } for (i = 0; i < ulFaceCount; i++) { nAdjTriCount = 0; for (j = i; j < ulFaceCount; j++) { if (i != j) { nCommonIntersectpnt=0; /* Checks whether it is a common edge */ for (int k = 0; k < 3; k++) { if ((pulIndices[i*3 + k] == pulIndices[j*3 + 0]) || (pulIndices[i*3 + k] == pulIndices[j*3 +1]) || (pulIndices[i*3 + k] == pulIndices[j*3 + 2])) { nCommonIntersectpnt++; } } if (nCommonIntersectpnt == 2) { lAdjTriIndices[nAdjTriCount] = j; nAdjTriCount++; } else if (nCommonIntersectpnt == 3) { break; } } } if(nAdjTriCount <= 3) { for (int k = 0; k < nAdjTriCount; k++) { plAdjTriList[i*3 + k] = lAdjTriIndices[k]; } } } } return plAdjTriList; } 

##### Share on other sites
Is your mesh well-formed - i.e. can any edge be shared by at most by 2 triangles? (and if it well-formed closed mesh, then exactly by 2 triangles).

If yes, then I'd probably initially go with

[font="Courier New"]std::map<std::pair<int,int>,std::pair<int,int> >[/font]

Where the first pair is ORDERED pair of vertex indices (i.e. first vertex index has to be < than second index), and the second is pair of triangle indices
• Then for each face of the mesh you iterate over three edges (0-1, 1-2 and 2-0) and construct ordered pair of vertex indices
• Use this pair to look into map
• If found, set current face index, as second triangle of this edge
• If not found, set current face index as the first triangle of this edge and set other to -1
• You can update your adjacency list in the same step - i.e. if pair is found, add second triangle to the adjacency list of first triangle and vice-versa

##### Share on other sites
It looks like you are checking twice as much as you need to (you are doing a M vs N array intersection when your may only need to compare the fisrt occurance of the intersection Mi with Nj instead of doing Mi:Nj and Ni:Mj

for I =1to maxmesh
for J = 1 to ( I-1)
{ Check points for mesh against mesh[j] }

will only check the intersection set once and also get rid of that i==j (self) clause as well

##### Share on other sites

Yes I solved i using GetAdjaceny. Its more speed up than my earlier method.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 21
• 22
• 11
• 25