Skip to main content
GameDev.net gamedev.net
🔒 Locked

[GOOD NEWS! READ PLEASE] How to generate adjacency?

Started by XVincentX Jun 26, 2008 at 5:31 PM 34 replies 10.8k views
Original Post
XVincentX
XVincentX
Hello! I'm trying to implement a Shadow Volume example. I'm not using .x file format but a class containing Index and Vertex Buffer. Now, even if i try to set D3D10_PRIMITIVE_TOPOLOGY_TRIANGLELIST_ADJ and triangleadj in the Geometry Shader input, the silohuette detecting does not works. I read on internet that adjaceny must be generated and inserted in the index buffer, but how? How to understant the adjacency from an existing vertex-index buffer? Thank you! [Edited by - XVincentX on June 30, 2008 9:24:50 AM]
vs322
vs322
Don't know about DX10... and I may be telling you something you already know, but: 

int iFaces = pMeshToPrep->GetNumFaces();DWORD* adjInfo = new DWORD[iFaces *3];pMeshToPrep->GenerateAdjacency(00.0000125f, adjInfo);


Edit-
Sorry just re-read your post, Yeah I don't know how to explicitly attach or insert that info into a mesh :/
XVincentX
XVincentX
Infact; i need to get them without using D3DX Mesh interface, i've got only vertex and index buffer.

Noone knows how?
Buckeye
Buckeye
Quote:
I read on internet that adjaceny must be generated and inserted in the index buffer

Could you post a link to that info? It's not clear what "inserting" something into an index buffer means. It may be that, by looking at it, others may get an idea of what is intended and be able to provide you with recommendations.

In general, determining adjacency is not a trivial algorithm. Even if you come up with an algorithm, making it efficient could be difficult as it requires the comparison of multiple face vertices with vertices of other faces, easily resulting in 100's (if not 1000's) of vector comparisons.

A general outline (just off the top of my head):

Set up an array of DWORDs of size 3*numFaces (3 DWORDs per face). Set all values in the array to 0xffffffff.

for each face: compare the 3 sets of 2 vertices (each forming the line on one side of the face) in order with all sets of vertices for all other faces of a higher number.

For each comparison: If set "n" (n=0,1 or 2) from the first face IS sufficiently close (you must decide "how close" is "close") to a set from the second face, store the number of the second face in the array at position "n" for the first face. If the comparison is valid (the vertex sets are "close"), store the number of the first face in the appropriate position for the adjacency of the second face.

NOTE: this will not work if a vertex position is common to more than 3 faces.


[Edited by - Buckeye on June 27, 2008 2:55:18 PM]
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
Sure!

My goal it's to have in the geometry shader 3 primitive vertices and 3 vertices of adiacency.
In this way, i will be able to... bla bla bla bla...

I've got Vertex and Index buffer, and so i tried to search in D3D documentation. I found this, in ID3DX10Mesh

Generate a list of mesh edges, as well as a list of faces that share each edge.HRESULT GenerateAdjacencyAndPointReps(  FLOAT Epsilon);


But there is also this other function:

Adds adjacency data to the mesh's index buffer. When the mesh is to be sent to a geometry shader that takes adjacency data, it is neccessary for the mesh's index buffer to contain adjacency data.HRESULT GenerateGSAdjacency();


So i think that the right way to generate adjacency for geometry shader using, it's to add the right indices in the index buffer.
So for each primitive i should have got 6 indices...

From D3D10 FAQ, there is also this:

Quote:

How does D3D10 know how to generate adjacency indices for my mesh? Or, why does D3D10 not render correctly when I specify that the geometry shader needs adjacency information.

The adjacency information is not created by D3D10, but by the application. Adjacency indices are generated by the application and must contain six indices per primitive; of the six, the odd numbered indices are the edge adjacent vertices. ID3DX10Mesh::GenerateAdjacencyAndPointsReps can be used to generate this data.

XVincentX
XVincentX
Quote:
Original post by Buckeye
In general, determining adjacency is not a trivial algorithm. Even if you come up with an algorithm, making it efficient could be difficult as it requires the comparison of multiple face vertices with vertices of other faces, easily resulting in 100's (if not 1000's) of vector comparisons.


Urgh!!!
mmm, and then how can Microsoft Implementation be so quick?
Buckeye
Buckeye
Okay. See my previous (edited) post for a possible algorithm.

From the description, it appears that the interleaved indices for a single face are:

1. index of the first vertex.
2. index of the face (or 0xffffffff if no other face is adjacent <-- guessing) that shares the current face's vertex 0 and vertex 1.
3. index of the second vertex.
4. index of the face that shares the current face's vertex 1 and 2.
5. index of the third vertex.
6. index of the face that shares the current face's vertex 2 and vertex 0.

Quote:
the odd numbered indices are the edge adjacent vertices

Sorry. I'm not sure, in this context, what "edge adjacent vertices" could mean other than the index of a face that shares that edge.

By the way, the "epsilon" mentioned in the GenerateAdjacency call is some small number that you supply that determines "how close" one vertex position must be to another to be considered "the same position."

EDIT: if you implement an algorithm and it's at all possible, generate a mesh and the index buffer described and compare your result with DX10's.

EDIT2: with regard to speed, you should, in general, only have to generate the adjacency info once, unless you rearrange your mesh often. By the way, how do you know that the DX10 algorithm is fast? [smile]

EDIT3: note, also, if you implement such an algorithm, you have to pay careful attention to the order of comparision with the second face vertices. I.e., if you're comparing v0 and v1 of the first face (the first of the three sets to compare), you'll compare them to the three sets (v1,v0), (v2,v1), (v0,v2) of the second face because the edge direction reverses on each edge.

[Edited by - Buckeye on June 27, 2008 2:22:07 PM]
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
mmm, i found another thing interesting.
Take a look in this page of Direct3D10 Doc

direct3D10->programming guide->pipeline stage->input assembler stage->getting started->primitive topologies, and look for TriangleList with adjacency.

I thought...mabye i have just to order indices in that way, to have adjacency...or not?
Buckeye
Buckeye
Okay. In the ShadowVolume10 Sample on msdn (I don't have the DX10 docs), it has a diagram that shows that, indeed, the interleaved index is the vertex index for the non-coincident vertex of an adjacent face. That makes sense for an indexed mesh (or array of vertices) which share vertices, one of two types of indexed meshes. In my previous post, I was considering a mesh that may contain triangles comprised of vertices that are not shared with any other face.

It appears that it would not work for a mesh comprised of faces which do not share vertices.

Is your setup (vertices and indices) strictly comprised of shared vertices to form adjacent faces?
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
Yes, i use Indexed Mesh, and all shares vertices.
Simple example here -> http://xvincentx.netsons.org/programBlog/wp-content/v2ydbb6tmp.jpg

I'm sorry if i did not specify this particular, i thought it was implicit

Ok, now how have i to proceed?
Buckeye
Buckeye
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.
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
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.
Buckeye
Buckeye
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.
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
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.

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]
Buckeye
Buckeye
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.
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
Right! The possibiles edges are only three, i did not see the 02 edge.

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]
Buckeye
Buckeye
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.
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;			}		}	}	}

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
XVincentX
XVincentX
I think there is an error

	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]
Buckeye
Buckeye
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.
Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly. You don't forget how to play when you grow old; you grow old when you forget how to play.
openglaussie
openglaussie
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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.