Edges Connection Graph

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



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"



Thanks Ilian,

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

Alberto

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.

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

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[NumTris3];
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.

Thanks Ilian,

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

Alberto

Ilian,

What do you mean we SHR in the following?

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

Thanks,

Alberto

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

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


// 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++;
	}
	
}

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

http://msdn.microsoft.com/en-us/library/5dxy4b7b(VS.80).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]);”

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