[GOOD NEWS! READ PLEASE] How to generate adjacency?
This is my best guess -
For each face:
Determine if any 2 indices (looked at in a specific order) coincides with any 2 indices for another face and store the vertex index from the second face that doesn't match.
For face vertex 0, look for another face that uses vertex indices 0 and 1
For face vertex 1, look for another face that uses vertex indices 1 and 2
For face vertex 2, look for another face that uses vertex indices 2 and 0
For example:
face 0 uses vertices 0,1,2
face 12 uses vertices 1,6,0
face 26 uses vertices 2,1,18
face 7 uses vertices 0,2,3
Index buffer:
0 : store 0 (the first vertex of face 0)
1 : store 6 (the index of the vertex from face 12 because face 12 shares 0 and 1)
2 : store 1 (the second vertex of face 0)
3 : store 18 (the index of a vertex from face 26 which shares indices 1 and 2)
4 : store 2 (the third vertex of face 0)
5 : store 7 (the index of a vertex from face 7 which shares indices 2 and 0)
Another example:
face 3 uses vertices 6,7,8
face 12 uses vertices 1,6,8
face 26 uses vertices 7,10,8
face 7 uses vertices 12,7,6
Index buffer:
n+0 : store 6 (the first vertex of face 3)
n+1 : store 12 (the index of the vertex from face 7 because face 7 shares 6 and 7)
n+2 : store 7 (the second vertex of face 3)
n+3 : store 10 (the index of a vertex from face 26 which shares indices 7 and 8)
n+4 : store 8 (the third vertex of face 3)
n+5 : store 1 (the index of a vertex from face 12 which shares indices 8 and 6)
I hope I got that all right. [smile]
EDIT: By the way, just because it's indexed doesn't mean vertices are shared. Also, if you can't find an adjacent face for an edge, DX9 adjacency stores 0xffffffff. I'm not sure about DX10.
For each face:
Determine if any 2 indices (looked at in a specific order) coincides with any 2 indices for another face and store the vertex index from the second face that doesn't match.
For face vertex 0, look for another face that uses vertex indices 0 and 1
For face vertex 1, look for another face that uses vertex indices 1 and 2
For face vertex 2, look for another face that uses vertex indices 2 and 0
For example:
face 0 uses vertices 0,1,2
face 12 uses vertices 1,6,0
face 26 uses vertices 2,1,18
face 7 uses vertices 0,2,3
Index buffer:
0 : store 0 (the first vertex of face 0)
1 : store 6 (the index of the vertex from face 12 because face 12 shares 0 and 1)
2 : store 1 (the second vertex of face 0)
3 : store 18 (the index of a vertex from face 26 which shares indices 1 and 2)
4 : store 2 (the third vertex of face 0)
5 : store 7 (the index of a vertex from face 7 which shares indices 2 and 0)
Another example:
face 3 uses vertices 6,7,8
face 12 uses vertices 1,6,8
face 26 uses vertices 7,10,8
face 7 uses vertices 12,7,6
Index buffer:
n+0 : store 6 (the first vertex of face 3)
n+1 : store 12 (the index of the vertex from face 7 because face 7 shares 6 and 7)
n+2 : store 7 (the second vertex of face 3)
n+3 : store 10 (the index of a vertex from face 26 which shares indices 7 and 8)
n+4 : store 8 (the third vertex of face 3)
n+5 : store 1 (the index of a vertex from face 12 which shares indices 8 and 6)
I hope I got that all right. [smile]
EDIT: By the way, just because it's indexed doesn't mean vertices are shared. Also, if you can't find an adjacent face for an edge, DX9 adjacency stores 0xffffffff. I'm not sure about DX10.
1)The index buffer might result bigger than the first one?
2) What about the idea of ordering indices following this picture, as i said before (http://msdn.microsoft.com/en-us/library/bb205124(VS.85).aspx)
Thinking better, i can't use this solution becouse indices are made in a "random" order...but i want a confirm.
2) What about the idea of ordering indices following this picture, as i said before (http://msdn.microsoft.com/en-us/library/bb205124(VS.85).aspx)
Thinking better, i can't use this solution becouse indices are made in a "random" order...but i want a confirm.
The example for the triangle list with adjacency in the link you provided is similar to the diagram in
http://msdn.microsoft.com/en-us/library/bb172445(VS.85).aspx
Note also at the above link:
"The index buffer will double in size due to the extra information being stored."
The algorithm I outlined above should work for any order of indices. That's why I generalized it.
http://msdn.microsoft.com/en-us/library/bb172445(VS.85).aspx
Note also at the above link:
"The index buffer will double in size due to the extra information being stored."
The algorithm I outlined above should work for any order of indices. That's why I generalized it.
Ok, thank you, i will try to write some code after.
If the buffer doubles in size, it should be generated only when it's needed.
What a problem! The ID3D10Buffer can be read in Map() function only if it's declarated as D3D10_USAGE_STAGING.
Unfortunately, D3D10_USAGE_STAGING buffers can't be used in input and output pipeline.
I have to matein a copy of indices in memory, discard the old ones and rewrite them.
Why all this???
Anyway, for now i'm manteining a copy of vertices and indices in memory, for a quick access.
I started to write this code
Considering that the index buffer format, from documentation, must be
Vertex-Adjacency-Vertex-Adjacency, i make a initial copy of indices[0] in new indices[0]
After i make a cycle to understand the adjacency, and then i can copy the indices with i and i+1 statements.
I know my english is bad, mabye the code will speak better than me.
But now, in your previous post i read
But, should not i check every combination of three vertices?
01 - 02 - 12 - 20
There are 4 possibiles edges, while in your advices i can see only three...
Thank you again.
[Edited by - XVincentX on June 28, 2008 4:50:18 AM]
If the buffer doubles in size, it should be generated only when it's needed.
What a problem! The ID3D10Buffer can be read in Map() function only if it's declarated as D3D10_USAGE_STAGING.
Unfortunately, D3D10_USAGE_STAGING buffers can't be used in input and output pipeline.
I have to matein a copy of indices in memory, discard the old ones and rewrite them.
Why all this???
Anyway, for now i'm manteining a copy of vertices and indices in memory, for a quick access.
I started to write this code
Considering that the index buffer format, from documentation, must be
Vertex-Adjacency-Vertex-Adjacency, i make a initial copy of indices[0] in new indices[0]
After i make a cycle to understand the adjacency, and then i can copy the indices with i and i+1 statements.
I know my english is bad, mabye the code will speak better than me.
void CMesh::GenerateAdjacency(){ UINT *pAdjacency = new UINT[2 * this->MeshData.ColladaBuffer.Indici]; pAdjacency[0] = this->MeshData.Indices[0]; for (unsigned int i = 0; i < this->MeshData.ColladaBuffer.Indici; i+=3) { } for (unsigned int i = 0; i < this->MeshData.ColladaBuffer.Indici; i++) { pAdjacency[i+1] = this->MeshData.Indices; for (unsigned int i = 0; i < this->MeshData.ColladaBuffer.Indici; i+=3) { } }}
But now, in your previous post i read
Quote:
For face vertex 0, look for another face that uses vertex indices 0 and 1
For face vertex 1, look for another face that uses vertex indices 1 and 2
For face vertex 2, look for another face that uses vertex indices 2 and 0
But, should not i check every combination of three vertices?
01 - 02 - 12 - 20
There are 4 possibiles edges, while in your advices i can see only three...
Thank you again.
[Edited by - XVincentX on June 28, 2008 4:50:18 AM]
Quote:There are 4 possibiles edges
A triangle only has 3 edges and only 3 possible adjacent triangles.
The three edges are:
between vertex 0 and vertex 1
between vertex 1 and vertex 2
between vertex 2 and vertex 0
I have been assuming you're trying to generate the triangle list with adjacency as show on:
http://msdn.microsoft.com/en-us/library/bb205124(VS.85).aspx
Is that correct?
EDIT: Ah! From your comment, "20" is the same as "02" and does not comprise a different edge.
The order in which the checks for adjacent triangles are made and which indices you check for is important.
Right! The possibiles edges are only three, i did not see the 02 edge.
I'm working in this way
But it looks like too difficult to see all cases...is this the right way?
It looks like also that all these if statements could be grouped into a for cycle, but the for-value should not ever be +1...suggestions?
[Edited by - XVincentX on June 28, 2008 8:36:08 AM]
I'm working in this way
void CMesh::GenerateAdjacency(){ UINT *pAdjacency = new UINT[2 * this->MeshData.ColladaBuffer.Indici]; for (unsigned int i = 0; i < this->MeshData.ColladaBuffer.Indici; i++) { for (unsigned int z = 0; i < this->MeshData.ColladaBuffer.Indici; z++) { if ((this->MeshData.Indices == this->MeshData.Indices[z]) && (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+1]) && (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2])) { //Sto leggendo lo stesso indice, vai avanti. continue; } else { if (this->MeshData.Indices == this->MeshData.Indices[z]) { if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+1]) { //Edge continue; } if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z+2]) { //Edge continue; } if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+1]) { //Edge continue; } if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2]) { //Edge continue; } } if (this->MeshData.Indices[i+1] == this->MeshData.Indices[z]) { if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+1]) { //Edge continue; } if (this->MeshData.Indices[i+2] == this->MeshData.Indices[z+2]) { //Edge continue; } if (this->MeshData.Indices[i-1] == this->MeshData.Indices[z+1]) { //Edge continue; } if (this->MeshData.Indices[i-2] == this->MeshData.Indices[z+2]) { //Edge continue; } } } } } delete[] pAdjacency; }
But it looks like too difficult to see all cases...is this the right way?
It looks like also that all these if statements could be grouped into a for cycle, but the for-value should not ever be +1...suggestions?
[Edited by - XVincentX on June 28, 2008 8:36:08 AM]
The comparisons have to be done for each face, which is a set of 3 indices in a row in the index buffer. You had a good start in your previous post (with the i += 3 loop).
I just wrote this so it should be checked carefully. Also, it is not optimized and goes through the buffer too many times.
I just wrote this so it should be checked carefully. Also, it is not optimized and goes through the buffer too many times.
uint i0, i1, i2;uint j0, j1, j2;for(uint i=0; i<numIndices; i+=3){ i0 = Indices[i*3+0]; i1 = Indices[i*3+1]; i2 = Indices[i*3+2]; pAdj[i*6+0] = i0; pAdj[i*6+1] = 0xffffffff; pAdj[i*6+2] = i1; pAdj[i*6+3] = 0xffffffff; pAdj[i*6+4] = i2; pAdj[i*6+5] = 0xffffffff; for(uint j=0; j<numIndices; j+=3) { if( j != i ) // don't check a triangle against itself { j0 = Indices[j*3+0]; j1 = Indices[j*3+1]; j2 = Indices[j*3+2]; // check for i0 and i1 if( j0 == i0 ) { if(j1==i1) pAdj[i*6+1] = j2; else if(j2==i1) pAdj[i*6+1] = j1; } else if( j1==j0 ) { if(j0==i1) pAdj[i*6+1] = j2; else if(j2==i1) pAdj[i*6+1] = j0; } else if( j2==i0 ) { if(j0==i1) pAdj[i*6+1] = j1; else if(j1==i1) pAdj[i*6+1] = j0; } // check for i1 and i2 if( j0 == i1 ) { if(j1==i2) pAdj[i*6+3] = j2; else if(j2==i2) pAdj[i*6+3] = j1; } else if( j1==i1 ) { if(j0==i2) pAdj[i*6+3] = j2; else if(j2==i2) pAdj[i*6+3] = j0; } else if( j2==i1 ) { if(j0==i2) pAdj[i*6+3] = j1; else if(j1==i2) pAdj[i*6+3] = j0; } // check for i2 and i0 if( j0 == i2 ) { if(j1==i0) pAdj[i*6+5] = j2; else if(j2==i0) pAdj[i*6+5] = j1; } else if( j1==i2 ) { if(j0==i0) pAdj[i*6+5] = j2; else if(j2==i0) pAdj[i*6+5] = j0; } else if( j2==i2 ) { if(j0==i0) pAdj[i*6+5] = j1; else if(j1==i0) pAdj[i*6+5] = j0; } } } }
I think there is an error
If each for cycle i+=3, then pAdj must be multiplicated by...2 and not 6.
If i++ then the value should be 6...or not?
[Edited by - XVincentX on June 28, 2008 8:20:55 AM]
for(unsigned int i=0; i < this->MeshData.ColladaBuffer.Indici; i+=3) { i0 = this->MeshData.Indices[i*3+0]; i1 = this->MeshData.Indices[i*3+1]; i2 = this->MeshData.Indices[i*3+2]; pAdj[i*6+0] = i0; pAdj[i*6+1] = 0xffffffff; pAdj[i*6+2] = i1; pAdj[i*6+3] = 0xffffffff; pAdj[i*6+4] = i2; pAdj[i*6+5] = 0xffffffff;
If each for cycle i+=3, then pAdj must be multiplicated by...2 and not 6.
If i++ then the value should be 6...or not?
[Edited by - XVincentX on June 28, 2008 8:20:55 AM]
Sorry. I used pAdj for the index buffer to be filled with adjacency information, the buffer to be used by the shader. I used "Indices" for the index buffer you load.
"Indices" has 3 indices per face so i+=3 and i*3.
"pAdj" has 6 indices* per face so i*6.
*3 indices for the face, 3 indices for adjacent vertices, interleaved.
For instance, if i=7, then you want to point to Indices[7*3] for the beginning of the face vertices. The corresponding location for the beginning of the face vertices in pAdj is at 7*6, because there are 6 (and not 3) indices per face.
"Indices" has 3 indices per face so i+=3 and i*3.
"pAdj" has 6 indices* per face so i*6.
*3 indices for the face, 3 indices for adjacent vertices, interleaved.
For instance, if i=7, then you want to point to Indices[7*3] for the beginning of the face vertices. The corresponding location for the beginning of the face vertices in pAdj is at 7*6, because there are 6 (and not 3) indices per face.
I have implemented a pure opengl adiacency finder , both for vertices and surfaces, they use a 3d hash for fast indexing.
If you are interested, send a pm
The code is still free for non commercial use
If you are interested, send a pm
The code is still free for non commercial use
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement