Sign in to follow this  
fazekaim

VBO with indexed or non-indexed geometry?

Recommended Posts

Hello, What could be the fastest? The indexed or non-indexed geometry using VBO? I'm using non-indexed geometry now, sould i change-it? Thanks.

Share this post


Link to post
Share on other sites
Indexed should definitely be faster for two reasons:

1. you have less vertices to send to the video card
2. OpenGL "knows" where your vertex is when you are repeating it, and probably there are some calculations in the vertex plotting process that don't need to be repeated

nVidia's performance documents also stress - always use indexed arrays, ie glDrawElements; and you have to say they know better than most people what's faster.

About whether you should overhaul your engine, I can't say but it could be very little work to a lot of work depending on how your model data is stored / accessed.

Share this post


Link to post
Share on other sites
As far as I know, indexed geometry will only be faster if your mesh data is optimized for it. With indexed geometry you can avoid having duplicate vertices. I was able to go from 50fps to 75fps in my renderer by switching to indexed geometry, but I had to write a special function that goes through the mesh and gets rid of duplicate vertices. You might want to write a "crunch" app that you can use offline because the optimization algorithm could take a really long time.

Share this post


Link to post
Share on other sites
deathkrush is right. That's what I had to do, I have a program that takes the raw model data (which unintelligably duplicates normals and texcoords), finds the duplicates and virtually creates a dump of an indexed vertex array.

Another thing I forgot to point out, is that indexed arrays are not always advantageous. eg, for a cube, the normal at 1 vertex is in 4 different directions for the 4 faces which share it. Clearly you have to duplicate the data, and you'd much rather use glDrawArrays.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
the indexed geometry is little bit faster, i tested. Thanks, guys.

i have a new problem. i don't know how to sort the vbo's data.

i load wavefront obj files, and i read triangle data as indexes like these:
4/1/4 2/2/2 3/3/3
so:
4,2,3 -vertex indexes
1,2,3 -texture indexes
4,2,3 -normal indexes

4/283/4 5/284/5 2/285/2
so:
4,5,2 -vertex indexes
283,284,285 -texture indexes
4,5,2 -normal indexes

So the texture indexes are different. For the 4. vertex i should use texture no 1 and in other triangle no 283.

How can i sort the texture indexes to able to use indexes geometry?
the file was saved using blender....

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
the indexed geometry is little bit faster, i tested. Thanks, guys.

i have a new problem. i don't know how to sort the vbo's data.

i load wavefront obj files, and i read triangle data as indexes like these:
4/1/4 2/2/2 3/3/3
so:
4,2,3 -vertex indexes
1,2,3 -texture indexes
4,2,3 -normal indexes

4/283/4 5/284/5 2/285/2
so:
4,5,2 -vertex indexes
283,284,285 -texture indexes
4,5,2 -normal indexes

So the texture indexes are different. For the 4. vertex i should use texture no 1 and in other triangle no 283.

How can i sort the texture indexes to able to use indexes geometry?
the file was saved using blender....

Exactly the problem I had a week or two ago - read my previous post. If your model generally has shared normals for vertices, then there is a little trick that you can apply (offline, don't do this while loading the model).

Your vertex indexed '4' has texcoord index '1' and '283'. Open the obj file in an editor and check, I'm prepared to bet that the texcoords in the texcoord list with index '1' and '283' are identical (remember that the index of the first texcoord is '1' not '0' as in C). So you just have to find which texcoords and normals belong to a vertex and store it along with the vertex. Going this way, vertex '4' will be stored just once in your vertex array, and the accompanying texcoord will be texcoord # 1 or 283.

Share this post


Link to post
Share on other sites
> read my previous post.
What is the forum post title?

> Your vertex indexed '4' has texcoord index '1' and '283'....
The texture coords are the same... i tried to replace the 283 to 1 and the modell rendering has texture problem. Some texture coords slips everywhere, so i think i should make some other changes...

Share this post


Link to post
Share on other sites
I ran into this problem when using Wavefront OBJ files. The way I solved is with this algorithm:

1. Using OBJ's indexes get the values for vertex, texcoord and normal.
2. Search your app's vertex, texcoord and normal arrays until you find an index that points to similar values (within precision range)
4. If you find a matching index, you can avoid inserting data and just insert an index to that data.
5. If you don't find a matching index, insert both data and index into your arrays.

I hope thats clear. This algorithm doesn't take too long if your mesh is around 10,000 polygons, but at 100,000 it could take a couple of minutes, in which case you would need to use hashing or sorting / binary search techniques to improve performance.

Share this post


Link to post
Share on other sites
1. Using OBJ's indexes get the values for vertex, texcoord and normal.
--- OK, i read the indexes....

2. Search your app's vertex, texcoord and normal arrays until you find an index that points to similar values (within precision range)
--- so, i should check each triangle, and search a triangle with equals normal, vertex and texture index?

4. If you find a matching index, you can avoid inserting data and just insert an index to that data.
5. If you don't find a matching index, insert both data and index into your arrays.

i don't know how do you mean it... can you describe it with more details? thanks...

Share this post


Link to post
Share on other sites
I forgot to explain that you need to copy OBJ data into a new set of arrays. Say, the OBJ data is represented by OBJvertex array, OBJtexcoord array, OBJnormal array and OBJindex array where there are 3 separate indices for vertex, texcoord and normal. I imagine you are using only triangular meshes?

Create a new set of arrays: GLvertex, GLnormal, GLtexcoord and GLindex arrays that you will be using with OpenGL. You know the size of the GLindex array in advance, it's the same as the number of faces * 3, but you don't know the size of GLvertex, GLtexcoord and GLnormal arrays, so I suggest using std::vector. Initialy these arrays are empty.

For each 3 indices in OBJindex array you retrieve the values for vertex, normal and texcoord from equivalent OBJ* arrays. Using these values you search your GLvertex, GLnormal and GLtexcoord arrays to find if you have an index where the values are the same (within precision).

If there is such an index, you insert this index into your GLindex array. If there isn't such an index, you insert the values of vertex, normal and texcoord into the respective GL* arrays and insert an appropriate index into GLindex array.

Keep going until you have covered all indices. I can probably post the code, if I can find it.

Share this post


Link to post
Share on other sites
Quote:
Original post by fazekaim
> read my previous post.
What is the forum post title?

> Your vertex indexed '4' has texcoord index '1' and '283'....
The texture coords are the same... i tried to replace the 283 to 1 and the modell rendering has texture problem. Some texture coords slips everywhere, so i think i should make some other changes...

I didn't mean change the Wavefront OBJ file.

Since texcoord # 1 and 283 are the same, you ultimately see that each vertex in your model has but one normal and texcoord. For your vertex # 1 the texcoord is texcoord # 1 and normal is normal # 4, even though you see texcoord # 283 with vertex # 4 later in your file.

The implementation can be like this for noninterleaved data in separate arrays:

1. Arrange the vertices in linear order (ie. #1, #2, #3, ..., #n) in an array (which is your vertex array). Note that vertices are not repeated in the Wavefront obj file, unlike normals or texcoords.

2. Create texcoord array and normal array large enough to hold n normals and texcoords.

3.
loop n times
Find which normal and texcoord belong to vertex #i (as stated above)
Put these in the ith position in your normal array and texcoord array respectively.
end loop


And your index array should just contain the index of the vertex required for a triangle. I hope you understand what I'm trying to say!

Share this post


Link to post
Share on other sites
deavik, i started with your description:


for (int i=0;i<vertexes.size(); ++i) {
boolean b = true;
for( Triangle t : triangles ){
if( t.vertexIndex1 == i+1 ){
newtexels.add( texels.elementAt(t.textureIndex1-1) );
newnormals.add( normals.elementAt(t.normalIndex1-1) );
b = false; break;
}
if( t.vertexIndex2 == i+1 ){
newtexels.add( texels.elementAt(t.textureIndex2-1) );
newnormals.add( normals.elementAt(t.normalIndex2-1) );
b = false; break;
}
if( t.vertexIndex3 == i+1 ){
newtexels.add( texels.elementAt(t.textureIndex3-1) );
newnormals.add( normals.elementAt(t.normalIndex3-1) );
b = false; break;
}
}
if( b ){ newtexels.add( new Texel() ); newnormals.add( new Normal() ); }
}




the result: http://www.kepfeltoltes.hu/view/060501/objTest_www.kepfeltoltes.hu_.jpg

I have some strange texture index problem.
If i make a for loop for every triangles, and i put everey vertex, texture and normal value into a vbo, the rendering is fine, just the indexes vbo is problematic, i don't know why.
have i make errors?

Share this post


Link to post
Share on other sites
Quote:
Since texcoord # 1 and 283 are the same, you ultimately see that each vertex in your model has but one normal and texcoord. For your vertex # 1 the texcoord is texcoord # 1 and normal is normal # 4, even though you see texcoord # 283 with vertex # 4 later in your file.


deavik,

Are you sure you can do that with OBJ files? In my experience, at least with Blender generated OBJ files there could be many different normals and texture coordinates for the same vertex. The simplest way to turn an OBJ file into OpenGL compatible vertex array is to:

for all indices in OBJ file
get vertex, texcoord and normal for the current index
insert vertex, texcoord and normal into GL arrays

Of course, this way you will get many duplicate vertices but at least the mesh will be drawn correctly.

Share this post


Link to post
Share on other sites
deathkrush: Well, technically you shouldn't use the trick I mentioned because the texcoords and normals indexed with the same vertex could be different.

However, with many models, the texture coord and normal is unique for one vertex. Even in those cases, Blender wants to repeat the normal and texcoord. Result: 2 different texcoord / normal exntries for an identical texcord / normal. That was what I was driving at, and trying to eleiminate. It's worked for me - and to prove that it's not just for very specialized models, it worked for a car imported (with textures) from the GTAIII game out of the box. It was even true for the one texcoord fazekaim checked in his model file.

But you can see, as you rightly said, that this will fail miserably for something like a cube, in which case you must repeat the vertices. deathkrush, I think that is what you were saying, but fazekaim says that he has already got the non-indexed linear array to work.

fazekaim, I can't see a problem with your code at the moment. If it doesn't work out, you can use non-indexed arrays as you have been until you find a model format that is more "indexed arrays friendly" (If you do, let me know me so that I can start using it as well!).

Share this post


Link to post
Share on other sites
deathkrush,

> for all indices in OBJ file
> get vertex, texcoord and normal for the current index
> insert vertex, texcoord and normal into GL arrays

i do this now, and it is working using vbos. i just thought to use indexed geometry :)

deavik,
> more "indexed arrays friendly"? like 3ds? i would like to try collada, but the export plugin is in hard development (no textures and animation yet), so the 3ds could be a better choise now.

Thanks...

Share this post


Link to post
Share on other sites
i wrote a collada importer to my engine, and the result is the same.

Using vbo, the modell is rendered well, but using indexed vbos, the modell texture isn't good at some points. So, i think it isn't the obj format problem, it's a generic problem. To tell the truth, i don't understand how can it happens exactly.

Has anyone a good idea, or a good fix algorithm?

Thanks a lot in advance....

Share this post


Link to post
Share on other sites
i wrote a mesh data modifier code:

// model.triangleIndex[i][0] vertexindex, model.triangleIndex[i][2] textureindex, model.triangleIndex[i][1] normalindex
for( int i=0; i<model.triangleIndex.length; ++i ){
for( int j=i+1; j<model.triangleIndex.length; ++j ){
if(
(model.triangleIndex[i][0] == model.triangleIndex[j][0]) &&
(
(model.triangleIndex[i][1] != model.triangleIndex[j][1]) ||
(model.triangleIndex[i][2] != model.triangleIndex[j][2])
)
){
vertexes.add( testVertexes.elementAt( model.triangleIndex[j][0] ) ); // add new vertex
model.triangleIndex[j][0] = vertexes.size()-1; // modify index
model.vertexCount++;
}
}
}





i think, the deathkrush's description was something like that, but my english...
so, the indexed geometry is done, but my code hasn't speed up at all...
the bottleneck could be elsewhere? i should look at ati's opengl performance papaer...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this