Jump to content
  • Advertisement
Sign in to follow this  
rajesh_nest

Shared triangles using hash method

This topic is 2638 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 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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!