Hello,

I coded a function, which takes as a input a vertex buffer. Output is a vertex buffer with removed duplications and index buffer.

It's working well, but the main problem of this function is, it's very slow. It contains three for loop and its complexity is roughly O( n^2 * log n ).

I just go though vertex array and adding index numbers, but when duplication is found, i delete it, i have to search, what index this duplication had and used it. Of course, i have to search whole vertex array again and again and search for duplication. ( i am comparing not only vertices, but normals, uvs too, they have to be same then i can mark it as duplication )

I would like to ask, if you know any technique, which is faster. I am searching the internet and i still did not find aynthing :(

thank you very much.

Linear time, wau.

When i am building that hash and storing what i have seen so far, it's getting bigger and bigger and i have to search it to find a vertex if it's there or not, it doesn't look like linear. Perhaps i have to think about it more it will be nice to see some pseudocode.

thank you

edit: i just saw some small examples using hashes and i have a better view now

edit2: there can be another problem, most of verticles don't have to be exact same, but there can be small difference 0.001, so these will be "warped" into one.

It seems to me that if indexing would be a significant optimization, then you preferably would want some kind of shared-node structure where you don't need to post-process vertices. But that might not always be easy to do, depending of where the vertices are originated.

This is for my exporter to my model format. I would like to make indices and sort them, but my current solution .. is working, but it's not fast :)

I checked the hashing. it looks like, the main problem is, duplicates doesn't mean same values but values which are VERY close to be same ( for example two vertex very very very close to each other ).

Chris: Yep, that's good idea :)

I have no experience in hashing. Let's say, it's a function, where input gives you an index for an array.

How do i hash a struct, where are vertex positions, normals, uvs and colours? should i hash a part of memory, where struct is stored ?

I have headache from it, lol.

It seems .. i will just drop a "duplicating vertex, when their distance is very small" feature ... graphic designer should be careful, where he puts verticles hehe.

Then .. i can use hash table and a great function called "IsVertexAlreadyInTable". That should help.