View Full Version : Edges Connection Graph

devdept

05-04-2010, 06:08 AM

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

05-04-2010, 06:58 AM

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

05-04-2010, 07:34 AM

Thanks Ilian,

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

Alberto

Ilian Dinev

05-04-2010, 08:20 AM

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

06-01-2010, 10:24 AM

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

06-01-2010, 02:25 PM

I'd suggest a 16-bit hashmap;

struct LLNodeVtx{

LLNodeVtx* pNext;

union{

vec3 position;

int ipos[3];

}

int DifferentFrom(const LLNodeVtx& 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

06-02-2010, 08:43 AM

Thanks Ilian,

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

Alberto

devdept

06-02-2010, 11:32 AM

Ilian,

What do you mean we SHR in the following?

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

Thanks,

Alberto

Ilian Dinev

06-02-2010, 12:48 PM

shift-right, >> in C++

Basically I've been mentioning x86 asm opcodes as hints to the optimization.

devdept

06-07-2010, 08:08 AM

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

06-07-2010, 02:50 PM

// 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 &= 65535;

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

//-----[ find if already existing ]-------------[

LLNodeVtx* list = HashMap[hash16];

while(list){

if(list->ipos[0]==n.ipos[0] && list->ipos[1]==n.ipos[1] && 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

06-09-2010, 01:09 AM

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 &= 65535;

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

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

Thanks,

Alberto

Ilian Dinev

06-09-2010, 01:26 AM

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

06-09-2010, 01:52 AM

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

Powered by vBulletin® Version 4.2.2 Copyright © 2015 vBulletin Solutions, Inc. All rights reserved.