Page MenuHome

Correctly merge uvs before exporting to alembic

Authored by Maxime Robinot (maxime.robinot) on Nov 29 2018, 9:52 AM.




I did this rewriting of get_uvs() function to correctly merge the uvs.
Previously would merge all uv points with exact same coordinates with no regard to actual topology, thus merging superposed uv islands.

Diff Detail

rB Blender

Event Timeline

@Sybren A. Stüvel (sybren), could you look into this? I have neither the Blender sources nor my Alembic files on my computer at the moment. Overall, apart from some style issues it looks good to me.

(On a side note, some loops (here and elsewhere in the Alembic code) could be parallelized.)

Brecht Van Lommel (brecht) requested changes to this revision.Nov 29 2018, 9:38 PM

This patch appears to be against an old version of the code, please update it to latest master.

This revision now requires changes to proceed.Nov 29 2018, 9:38 PM
Sybren A. Stüvel (sybren) requested changes to this revision.Nov 30 2018, 10:22 AM
Sybren A. Stüvel (sybren) added inline comments.

I have a few questions:

Why go from unordered_map to vector-of-vectors?

When do you expect the limit of int to be hit here, and not be large enough to warrant a long?

Adding a comment to explain what is contained in the type is a good idea. However, I don't think it explains it well -- which index into which vector is the vertex ID, and which covers the "more than one"? What is exactly in the uint64_t and what in the long?


Instead of those two lines you can just do vertex_index_map idx_map(config.totvert);


I'm all for more comments in Blender's source code, but they should add to what is already pretty clear in the code. Looping until num_poly already suggests that you're looping over all polygons. The same goes for current_poly = polygons[i]; the code is already clear that that is getting the current polygon.


As an example of comments that I miss, here I would welcome a comment that explains why the polys are looped over in reverse order. Of course this wasn't in the original code either, so it's not something you have to add now, but if you know please add ;-)


Thanks for renaming k to something way more expressive.


Here you do a linear search through the std::vector. This is more efficiently done with a std::map or std::unordered_map. From what I can see the ordering of the vector isn't relevant, so I'd use an std::unordered_map here and reduce the lookup complexity from O(n) to O(1).

However, if you've done some benchmarks of which approach is faster, and this one won, please let us know.

This revision now requires changes to proceed.Nov 30 2018, 10:22 AM

I can't edit an inline comment -- in the 3rd sentence remove "not be large enough to" to make it understandable ;-)

Maxime Robinot (maxime.robinot) added inline comments.

I agree this is not that much clear.

The first vector represents the vertex ids.
The second vector covers the "more than one". This is all uv coordinates possible for this vertex.
The pair is the uv hash (uint64_t) and the index (long) for the array uvidx.

I used a vector instead of an unordered map because we don't need to search in it, vertex ids are the vector indices.
Is direct random access slower than a search in an unordered map ?

Since the long is the index of the uv coordinates, with really big mesh it might one day be too short as an int.
And maybe I should use an unsigned long instead, since we don't expect negative indices.


Yes I could.


I agree they're not really useful^^


Because this vector represents the different uv position that a single vertex can have (because of seams), its size will unlikely be more than 5 or 6 elements, so I'm not sure if this is that much important.


It's fine to use a linear lookup, for most meshes this will be faster.

The main cause of slowness will be memory allocations, which is not great in either case but acceptable.


As an anecdote about unordered_map vs. vector :

I am currently working on a compiler for my own native programming langage, and when compiling functions I used to have an unordered_map for storing data about local variables (including function parameters). Then after some profiling I turned the unordered_map into a vector which ended up being faster. The reason being that most functions have few local variables meaning that looking up data in a small cache coherent vector was here much faster that hopping through the pointers indirection inherent to unordered_map.

And here this is the same : most polygons will have 3 to 4 vertices, and most polygon edges will be part of one UV island only, so small vectors should not be a problem.

So I would say that indeed the vector of vectors might be faster than a single unordered_map. Previously we had a single vector for all the UV data, so a map was bound to be faster than an algorithm that keeps iterating over a very large vector.

Then, we are supposed to be computer scientist, so we should time and profile and not suppose! :)

Maxime Robinot (maxime.robinot) marked 11 inline comments as done.Dec 3 2018, 5:59 PM
Maxime Robinot (maxime.robinot) added inline comments.

Cedric told me it was probably a copy-paste remnant. Reverse looping was used to get the correct winding order of the polygons, but it has probably no means here.

Brecht Van Lommel (brecht) accepted this revision.EditedDec 7 2018, 12:22 AM

This is more complicated than it needs to be, there is no need for UV hashing if we are going to compare them directly.

We also do not use long, because its size is platform dependent.

This revision was not accepted when it landed; it landed in state Needs Review.Dec 7 2018, 12:22 AM
This revision was automatically updated to reflect the committed changes.