Page MenuHome
Differential D4006 Diff 12793 source/blender/alembic/intern/abc_customdata.cc

Changeset View

Standalone View

View Options

source/blender/alembic/intern/abc_customdata.cc

Show First 20 Lines • Show All 46 Lines • ▼ Show 20 Lines
using Alembic::Abc::C4fArraySample; using Alembic::Abc::C4fArraySample;
using Alembic::Abc::UInt32ArraySample; using Alembic::Abc::UInt32ArraySample;
using Alembic::Abc::V2fArraySample; using Alembic::Abc::V2fArraySample;
using Alembic::AbcGeom::OV2fGeomParam; using Alembic::AbcGeom::OV2fGeomParam;
using Alembic::AbcGeom::OC4fGeomParam; using Alembic::AbcGeom::OC4fGeomParam;
typedef std::unordered_map<uint64_t, int> uv_index_map;
static inline uint64_t uv_to_hash_key(Imath::V2f v)
{
/* Convert -0.0f to 0.0f, so bitwise comparison works. */
if (v.x == 0.0f) {
v.x = 0.0f;
}
if (v.y == 0.0f) {
v.y = 0.0f;
}
/* Pack floats in 64bit. */
union {
float xy[2];
uint64_t key;
} tmp;
tmp.xy[0] = v.x;
tmp.xy[1] = v.y;
return tmp.key;
}
static void get_uvs(const CDStreamConfig &config, static void get_uvs(const CDStreamConfig &config,
std::vector<Imath::V2f> &uvs, std::vector<Imath::V2f> &uvs,
sybrenUnsubmitted
Done
Inline Actions

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?

sybren: I have a few questions: Why go from `unordered_map` to vector-of-vectors? When do you expect…
sybrenUnsubmitted
Done
Inline Actions

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

sybren: I can't edit an inline comment -- in the 3rd sentence remove "not be large enough to" to make…
maxime.robinotAuthorUnsubmitted
Done
Inline Actions

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.

maxime.robinot: I agree this is not that much clear. The first vector represents the vertex ids. The second…
std::vector<uint32_t> &uvidx, std::vector<uint32_t> &uvidx,
void *cd_data) void *cd_data)
{ {
MLoopUV *mloopuv_array = static_cast<MLoopUV *>(cd_data); MLoopUV *mloopuv_array = static_cast<MLoopUV *>(cd_data);
if (!mloopuv_array) { if (!mloopuv_array) {
return; return;
} }
const int num_poly = config.totpoly; const int num_poly = config.totpoly;
MPoly *polygons = config.mpoly; MPoly *polygons = config.mpoly;
MLoop *mloop = config.mloop;
if (!config.pack_uvs) { if (!config.pack_uvs) {
int cnt = 0; int cnt = 0;
uvidx.resize(config.totloop); uvidx.resize(config.totloop);
uvs.resize(config.totloop); uvs.resize(config.totloop);
/* Iterate in reverse order to match exported polygons. */
for (int i = 0; i < num_poly; ++i) { for (int i = 0; i < num_poly; ++i) {
MPoly &current_poly = polygons[i]; MPoly &current_poly = polygons[i];
MLoopUV *loopuvpoly = mloopuv_array + current_poly.loopstart + current_poly.totloop; MLoopUV *loopuv = mloopuv_array + current_poly.loopstart + current_poly.totloop;
for (int j = 0; j < current_poly.totloop; ++j, ++cnt) { for (int j = 0; j < current_poly.totloop; ++j, ++cnt) {
--loopuvpoly; --loopuv;
uvidx[cnt] = cnt; uvidx[cnt] = cnt;
uvs[cnt][0] = loopuvpoly->uv[0]; uvs[cnt][0] = loopuv->uv[0];
uvs[cnt][1] = loopuvpoly->uv[1]; uvs[cnt][1] = loopuv->uv[1];
} }
} }
} }
else { else {
uv_index_map idx_map; /* Mapping for indexed UVs, deduplicating UV coordinates at vertices. */
std::vector<std::vector<uint32_t>> idx_map(config.totvert);
int idx_count = 0; int idx_count = 0;
for (int i = 0; i < num_poly; ++i) { for (int i = 0; i < num_poly; ++i) {
MPoly &current_poly = polygons[i]; MPoly &current_poly = polygons[i];
MLoopUV *loopuvpoly = mloopuv_array + current_poly.loopstart + current_poly.totloop; MLoop *looppoly = mloop + current_poly.loopstart + current_poly.totloop;
MLoopUV *loopuv = mloopuv_array + current_poly.loopstart + current_poly.totloop;
for (int j = 0; j < current_poly.totloop; ++j) { for (int j = 0; j < current_poly.totloop; ++j) {
loopuvpoly--; --looppoly;
Imath::V2f uv(loopuvpoly->uv[0], loopuvpoly->uv[1]); --loopuv;
uint64_t k = uv_to_hash_key(uv);
uv_index_map::iterator it = idx_map.find(k); Imath::V2f uv(loopuv->uv[0], loopuv->uv[1]);
if (it == idx_map.end()) { bool found_same = false;
idx_map[k] = idx_count;
uvs.push_back(uv); /* Find UV already in uvs array. */
uvidx.push_back(idx_count++); for (uint32_t uv_idx : idx_map[looppoly->v]) {
if (uvs[uv_idx] == uv) {
found_same = true;
uvidx.push_back(uv_idx);
break;
} }
else { }
uvidx.push_back(it->second);
sybrenUnsubmitted
Done
Inline Actions

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

sybren: Instead of those two lines you can just do `vertex_index_map idx_map(config.totvert);`
maxime.robinotAuthorUnsubmitted
Done
Inline Actions

Yes I could.

maxime.robinot: Yes I could.
/* UV doesn't exists for this vertex, add it. */
if (!found_same) {
uint32_t uv_idx = idx_count++;
sybrenUnsubmitted
Done
Inline Actions

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.

sybren: I'm all for more comments in Blender's source code, but they should add to what is already…
maxime.robinotAuthorUnsubmitted
Done
Inline Actions

I agree they're not really useful^^

maxime.robinot: I agree they're not really useful^^
idx_map[looppoly->v].push_back(uv_idx);
uvidx.push_back(uv_idx);
uvs.push_back(uv);
} }
sybrenUnsubmitted
Not Done
Inline Actions

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 ;-)

sybren: As an example of comments that I miss, here I would welcome a comment that explains why the…
maxime.robinotAuthorUnsubmitted
Not Done
Inline Actions

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.

maxime.robinot: Cedric told me it was probably a copy-paste remnant. Reverse looping was used to get the…
} }
} }
} }
} }
const char *get_uv_sample(UVSample &sample, const CDStreamConfig &config, CustomData *data) const char *get_uv_sample(UVSample &sample, const CDStreamConfig &config, CustomData *data)
{ {
sybrenUnsubmitted
Done
Inline Actions

Thanks for renaming k to something way more expressive.

sybren: Thanks for renaming `k` to something way more expressive.
const int active_uvlayer = CustomData_get_active_layer(data, CD_MLOOPUV); const int active_uvlayer = CustomData_get_active_layer(data, CD_MLOOPUV);
if (active_uvlayer < 0) { if (active_uvlayer < 0) {
return ""; return "";
} }
sybrenUnsubmitted
Done
Inline Actions

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.

sybren: Here you do a linear search through the `std::vector`. This is more efficiently done with a…
maxime.robinotAuthorUnsubmitted
Done
Inline Actions

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.

maxime.robinot: Because this vector represents the different uv position that a single vertex can have (because…
brechtUnsubmitted
Done
Inline Actions

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.

brecht: It's fine to use a linear lookup, for most meshes this will be faster. The main cause of…
kevindietrichUnsubmitted
Done
Inline Actions

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! :)

kevindietrich: As an anecdote about unordered_map vs. vector : I am currently working on a compiler for my…
void *cd_data = CustomData_get_layer_n(data, CD_MLOOPUV, active_uvlayer); void *cd_data = CustomData_get_layer_n(data, CD_MLOOPUV, active_uvlayer);
get_uvs(config, sample.uvs, sample.indices, cd_data); get_uvs(config, sample.uvs, sample.indices, cd_data);
return CustomData_get_layer_name(data, CD_MLOOPUV, active_uvlayer); return CustomData_get_layer_name(data, CD_MLOOPUV, active_uvlayer);
} }
/* Convention to write UVs: /* Convention to write UVs:
▲ Show 20 Lines • Show All 331 Lines • Show Last 20 Lines