Edges Connection Graph

[devdept]

Hi All,

Does an efficient implementation to extract edges from a mesh of triangles without duplicates?

I mean:

1) Vertices are a list of 3D points
2) Triangles are a list of 3 indices pointing to vertices above

We want to find very quickly:

1) A list of 2 indices representing the triangle sides but *without* duplicates (of course, you always get two with opposite direction)

Thanks,

Alberto

[Ilian Dinev]

struct LLNodeEdge{
LLNodeEdge* pNext;
int otherVtx; // index of other vertex
};

int NumTris = ; // arg
int NumVerts= ; // arg
int* TriIndices = ; // arg



LLNodeEdge** edges = new LLNodeEdge*[NumVerts];
int outNumEdges=0;
memset(edges,0,NumVerts*4);

LLNodeEdge* scratch_original = new LLNodeEdge[NumTris*3];

LLNodeEdge* scratch = scratch_original;


int* pidx = TriIndices;
int pcount = NumTris;
do{
for(int i=0;i<3;i++){ // unroll manually
int idx1 = pidx[i];
int idx2 = pidx[(i+1)%3]; // fix in manual unroll

if(idx1>idx2){ SWAP(idx1,idx2); } // cmovgt

LLNodeEdge* n = edges[idx1];
while(n){
if(n->otherVtx==idx2)break;
n = n->pNext;
}
if(!n){
n = scratch; scratch++;
n->otherVtx = idx2;
n->pNext = edges[idx1];
edges[idx1]=n;
outNumEdges++;
}
}
pidx+=3;
}while(--pcount); // dec + jnz



int* outEdges = new int[outNumEdges *2];
// now cycle through linked-lists, to fill-in data. Then delete "scratch_original" and "edges"

[devdept]

Thanks Ilian,

We'll give this a try, has this approach a specific name or it is your own ?

Alberto

[Ilian Dinev]

It's fairly simple and natural; the key point is to search by tuples of {idx1,idx2} where idx1<idx2. I've also seen this idea elsewhere, but it was wrapped in STL hell. I just embedded this keypoint around a bunch of optimizations:
- pre-allocate a scratch array. Homework: Actually only one "new char[xyz]" chunk is necessary, instead of two. (wrote them as two for clarity). Do pointer-maths.
- don't store idx1 (in the linked-list). Homework: after "do{" add idx3, make idx1<idx2<idx3 ; can get nicely optimized.


Another natural approach is to use "int NumUsersOfVertex[NumVerts]; int* edges[NumVerts]; " to replace the linked-lists by arrays, for nice memory prefetch pipelining.

[devdept]

Hi Ilian,

You're algorithm is very fast, thanks.

Do you have something to share also to convert Mesh of triangles defined as three 3D points to vertices and indices?

I mean from this format:

Triangle 1:
p1 = 4.22, 23.54, 32.444
p2 = 4.22, 66.54, 32.444
p3 = 4.22, 23.54, 77.444
Triangle 2:
p1 = 4.22, 11.54, 44.444
p2 = 6.22, 6.54, 32.666
p3 = 7.22, 23.54, 77.444
...

To this format:

Vertices:
v1 = 4.22, 23.54, 32.444
v2 = 4.22, 66.54, 32.444
v3 = 4.22, 23.54, 77.444
v4 = 4.22, 11.54, 44.444
...
Triangles:
t1 = 0,1,2
t2 = 0,1,3
...

Now we are doing this without optimizations and it is very slow.

Thanks,

Alberto

[Ilian Dinev]

I'd suggest a 16-bit hashmap;


struct LLNodeVtx{
LLNodeVtx* pNext;
union{
vec3 position;
int ipos[3];
}

int DifferentFrom(const LLNodeVtx&amp; v2); // optimize with XOR and OR of ipos[]
int CalculateHash(); // XOR and SHR of ipos[]
}; // 16 bytes


Reuse the ideas of
LLNodeEdge* scratch_original = new LLNodeEdge[NumTris*3];
LLNodeEdge* scratch = scratch_original;

for the fast allocation of nodes.


kd-trees might be helpful, too. I've only met this in offline preprocessing code, so I only use a simple HashMap.

[devdept]

Thanks Ilian,

Althought your code snippet looks to much concise to me, I will study hashmaps before asking.

Alberto

[devdept]

Ilian,

What do you mean we SHR in the following?


int CalculateHash(); // XOR and SHR of ipos[]

Thanks,

Alberto

[Ilian Dinev]

shift-right, >> in C++
Basically I've been mentioning x86 asm opcodes as hints to the optimization.

[devdept]

Ilian,

Do you use hash codes to quickly compare XYZ values? What does int iPos[3] holds?

We can't use your code without some more help, sorry.

Thanks.

Alberto

[Ilian Dinev]

// NUM_VERTICES = NUM_TRIANGLES * 3
vec3 Vertices[NUM_VERTICES]; // input


int Indices[NUM_TRIANGLES*3]; // output . For triangles
int NumUniqueVertices=0; // output
vec3* outVertices; // output


//----------------------------------------------




struct LLNodeVtx{
LLNodeVtx* pNext;
int index;
union{
vec3 position;
int ipos[3];
}
};

LLNodeVtx* HashMap[65536]={0};




for(int vertexIdx=0;vertexIdx<NUM_VERTICES;vertexIdx++){
LLNodeVtx n;
n.position = Vertices[vertexIdx];

//-------[ calculate hash ]----------------------[
int hash16 = (n.ipos[0] ^ n.ipos[1] ^ n.ipos[1]);
hash16 = hash16 ^ (hash16>>16);
hash16 &amp;= 65535;
//------------------------------------------------/


//-----[ find if already existing ]-------------[
LLNodeVtx* list = HashMap[hash16];
while(list){
if(list->ipos[0]==n.ipos[0] &amp;&amp; list->ipos[1]==n.ipos[1] &amp;&amp; list->ipos[2]==n.ipos[2]){
break;
}
list=list->pNext;
}
//----------------------------------------------/

if(list){ // found
Indices[vertexIdx] = list->index;
}else{
n.index = NumUniqueVertices;
n.pNext = HashMap[hash16];

list = new LLNodeVtx; // allocate LL node
*list = n; // copy from cache
HashMap[hash16] = list;

outVertices[NumUniqueVertices] = n.position;

NumUniqueVertices++;
}

}

[devdept]

Hi Ilian,

Thanks so much for your patience. Can you tell me what iPos contain here:


//-------[ calculate hash ]----------------------[
int hash16 = (n.ipos[0] ^ n.ipos[1] ^ n.ipos[1]);
hash16 = hash16 ^ (hash16>>16);
hash16 &amp;= 65535;
//------------------------------------------------/

Initially ipos[0], ipos[1], ipos[2] are all zero.

Thanks,

Alberto

[Ilian Dinev]

http://msdn.microsoft.com/en-us/library/5dxy4b7b%28VS.80%29.aspx

During the "n.position = Vertices[vertexIdx]; " operation, the ipos[] get filled-in.

Also, I just noticed there's a typo in
"int hash16 = (n.ipos[0] ^ n.ipos[1] ^ n.ipos[1]);"
Has to be
"int hash16 = (n.ipos[0] ^ n.ipos[1] ^ n.ipos[2]);"

[devdept]

Vertices[vertexIdx] is a vec3 (3 floats), right?

How can you fill a 3 floats and 3 integers from 3 floats only?



union {
vec3 position;
int ipos[3];
}

In addition what it the name of this union?

Thanks again,

Alberto