🔒 Locked

Deindexing triangles

Started by CableGuy Mar 25, 2009 at 5:51 PM 9 replies 2.3k views

Original Post

Mar 25, 2009 at 5:51 PM

Hi. I'm trying to deindex triangles read from a file. My current implementation uses a map to associate each vertex with an index. So say the vertices are made of position,normal and texture coordinates a vertex key would be a triplet. The current key used in the map is a string but it is painfully slow. I thought about using a number but using 32 bit is not enough to uniquely identify each vertex when there are 3 components. Thanks.

Thaligar

Mar 26, 2009 at 9:30 AM

Hi CableGuy,

what file format do you use??

because normally you have something like this

std::vector< vertex > vVertex;std::vector< normal > vNormals;std::vector< texcoord > vTexCoords;std::vector< int > vIndicies;

and then you can reference every vertex/normal/texcoord combination by an int, but this means that at location 'i' in your vectors the correct vertx/normal/texcoord is written.

Then you can say triangle 'X' consists from index '1' '5' and '10'.

greets,
tgar

CableGuy

Mar 26, 2009 at 11:06 AM

I'm loading Collada files. The way it works is you have a vector for position normal,etc and an array of ints representing indices into these vectors, so for example say I have three vectors(position,normal,texcoord) a triangle might be described like so : 0 0 1 , 1 2 3 , 3 2 1 which means that the first vertex position is at index 0, its normal is 0 and texcoord is 1. The problem here is that OpenGL expects a single index. That is why de-indexing the triangles is necessary and as I said earlier I need a better way to associate a key to a vertex.

Thaligar

Mar 26, 2009 at 2:14 PM

Ok then...

(in C++)

// key structurestruct VertexKey{   int nVertexIndex;   int nNormalIndex;   int nTextureIndex;   ...}// operator to comparebool operator==( const VertexKey & lhs, const VertexKey & rhs ){...};// definitionsstd::vector< VertexKey > vKeyList;std::vector< Vertex3f > vVertex;std::vector< Normal3f > vNormals;...while( ColladaFileHasInfo() ){   VertexKey key;   // get the indicies from the collada file   GetVertexIndicies( key );   // check if this key is already in the list   std::vector< VertexKey >::iterator it = vKeyList.find( key );    // in case that the key is not yet in the vector   if( it != vKeyList.end() )   {      Vertex3f v;      Normal3f n;      ...      // get the real data for each element (vertex, normal...)      // from the collada file      v = ColladaFile.Vertex[ key.nVertexIndex ];      ... // repeat for the normal an so on            vVertex.push_back( v );      vNormals.push_back( n );      ... // repeat       // store the key for the next turn      vKeyList.push_back( key );   }   else   {      // handle the case when the vertex is already in the list   };};

This is not complete, but in the end you have all verticies uniquely stored in
vectors.

Additionally you should store the data for the triangles, or process them too.

Best Regards,
Tgar

CableGuy

Mar 26, 2009 at 4:24 PM

The problem here is that I can't know the size of the struct at compile time. A vertex is a tuple with unknown size(at compile time).For example a vertex might have a position,normal,color,2 sets of texture coordinates,tangent,whatever. I can hardcode it but then I might as well encode it as an array of longs.

zeux

Mar 27, 2009 at 1:26 AM

I've hardcoded a structure with 9 uint32 (position, T/B/N, 4 UV sets, color) - this is more than enough for all practical purposes, it's even a bit much. Of course the total amount of streams in can be larger than that - for example, a pair of T/B for each texture set - but I fill this only with the components I need.

This structure is used as a key in a hash table, the value being the resulting index.

At work we have a different approach - we assemble a final set of vertices (3 per triangle, each vertex is a binary chunk of some length - it contains packed components, i.e. it's runtime-ready data) - it's a plain array (char*), then we make an array of pointers into it, each pointer pointing to a single vertex (initially this array contains incrementing pointers), then sort the array using comparator that does memcmp on vertex contents; after that we remove duplicate entries (pointers which point to the vertices with the same contents) - it's a simple linear pass; after that we build a final index buffer by iterating through the original chunk with vertices and looking for each vertex via binary search on the array of pointers. Sorting is NlogN, duplicate elimination is N, final VB building is NlogN.

CableGuy

Mar 27, 2009 at 4:18 AM

Thanks for your replies. I think I will hard code it for the time being.

Antheus

Mar 27, 2009 at 4:59 AM

Quote:
Original post by CableGuy
I can hardcode it but then I might as well encode it as an array of longs.

Do you expect to have more than 4 billion vertices? A vertex of floats is 12 bytes, which would imply 64-bit addressing space and 48 gigabytes of memory - just for coordinate, without normals, and everything else.

Quote:
a vertex might have a position,normal,color,2 sets of texture coordinates,tangent,whatever.

This "whatever" - if you don't know what it is at compile time, how would you process it?

struct Vertex {  // indices  int position;  int normal;  int texcoord1, texcoord2;  // other  RGB color;  int flags;};std::vector<Vector3D> positions;std::vector<Vector3D> normals;std::vector<Vector3D> texcoords;void Vertex::addNormal(Vector3D & v) {  v.normal = normals.size();  normals.push_back(v);  v.flags |= Flags::NORMAL;}

Maps can be used, but doing it efficiently takes slightly longer.

CableGuy

Mar 27, 2009 at 7:27 AM

Quote:

Do you expect to have more than 4 billion vertices? A vertex of floats is 12 bytes, which would imply 64-bit addressing space and 48 gigabytes of memory - just for coordinate, without normals, and everything else.

What I meant is that if a vertex have three attributes, each one taking a value between 1 and n there are n^3 possible vertices. Of course only a small portion of them will be actually present and 32 bit should be more than enough and that is why I asked for a most optimized way to pack the indices together.

Quote:

This "whatever" - if you don't know what it is at compile time, how would you process it?

Generally you are right and along the way something would have to be aware about this "whatever" but that something can be a shader expecting various attributes using glVertexAttribPointer for example.
Also can you elaborate a bit more about the code snippet you posted?

Thanks.

Thaligar

Mar 31, 2009 at 3:42 AM

What about this,

struct TBNKey{   int nTangent;   int nBitangent;   int nNormal;}// key structurestruct VertexKey{   int nVertexIndex;     std::vector<int> vTextureIndicies;   std::vector<TBNKey> vTBNIndicies;   ...}

then you should be prepared without too much hard coding
and you can it adept as you wish

best regards,
tgar

CableGuy

Mar 31, 2009 at 3:49 AM

Thanks for your replies again. I hard coded the key and surprisingly there was not much of a difference. Anyway I'll leave it as is until I'll find a better way to deindex the triangles(Suggestions are welcomed...).

Thanks.

Topic Locked

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