Unwrapping the same mesh results in different UVs and alter Export #47564

New Issue

Roman Nagornov · 2016-02-25T18:16:44+01:00

Roman Nagornov commented

2016-02-25 18:16:44 +01:00

System Information
Ubuntu 14.04.3 LTS 64bit
GeForce GT 440

Blender Version
Broken:
Blender 2.74 (sub 0)
Blender 2.76 (sub 0)

Short description of error
Importing the same mesh (a topological disk), applying "Unwrap" to it and then exporting it as .obj file results in different output files. I believe this behaviour is undesirable for the sake of testing and bug reproducibility.

Exact steps for others to reproduce the error

Start Blender with an empty scene.
Import mesh.obj (it's already cut into a topological disk). (mesh.obj)
Choose "UV Editing" Screen layout.
Select the object, go into Edit Mode and select all faces.
Open "Shading/UVs" tab and apply "Unwrap" under "UVs"
Export model as .obj file with "include UVs".
Restart Blender and repeat this process one more time.
Let's assume after going through this process you obtained two .obj files unwrapped1.obj (unwrapped1.obj) and unwrapped2.obj (unwrapped2.obj).
Compare these two files with "meld", "vimdiff" or other utility for file comparing.
You should see that vt-lines differ in the 5th digit after decimal point mostly. This behaviour must be caused by Unwrap function. You can construct a toy-example in Python console comparing UVs in uv_layer before and after bpy.ops.uv.unwrap() function call and running this experiment twice. I believe Unwrap must yield consistent output for the same input, so this behaviour seems to be wrong.
You should also see that vertex indices often differ in f-lines, so Blender exports UVs in different order every time. However shuffled UVs are not the cause of vt-lines difference, because there are vt-values in unwrapped1.obj that are not present in unwrapped2.obj (0.426069 in unwrapped1.obj for example).

This behaviour is believed to be reproducible with other file formats like .ply.

I've looked through Blender source code (uvedit module) for the cause of this random behaviour and have not found any clues (maybe I'm not experienced enough). The only function I found there that uses random numbers is initialized with the constant seed 31415926 (however this function doesn't seem to alter Unwrap), so I believe Blender is expected to yield consistent result for the same input.

**System Information** Ubuntu 14.04.3 LTS 64bit GeForce GT 440 **Blender Version** Broken: Blender 2.74 (sub 0) Blender 2.76 (sub 0) **Short description of error** Importing the same mesh (a topological disk), applying "Unwrap" to it and then exporting it as .obj file results in different output files. I believe this behaviour is undesirable for the sake of testing and bug reproducibility. **Exact steps for others to reproduce the error** - Start Blender with an empty scene. - Import mesh.obj (it's already cut into a topological disk). ([mesh.obj](https://archive.blender.org/developer/F285812/mesh.obj)) - Choose "UV Editing" Screen layout. - Select the object, go into Edit Mode and select all faces. - Open "Shading/UVs" tab and apply "Unwrap" under "UVs" - Export model as .obj file with "include UVs". - Restart Blender and repeat this process one more time. - Let's assume after going through this process you obtained two .obj files unwrapped1.obj ([unwrapped1.obj](https://archive.blender.org/developer/F285813/unwrapped1.obj)) and unwrapped2.obj ([unwrapped2.obj](https://archive.blender.org/developer/F285814/unwrapped2.obj)). - Compare these two files with "meld", "vimdiff" or other utility for file comparing. - You should see that vt-lines differ in the 5th digit after decimal point mostly. This behaviour must be caused by Unwrap function. You can construct a toy-example in Python console comparing UVs in uv_layer before and after bpy.ops.uv.unwrap() function call and running this experiment twice. I believe Unwrap must yield consistent output for the same input, so this behaviour seems to be wrong. - You should also see that vertex indices often differ in f-lines, so Blender exports UVs in different order every time. However shuffled UVs are not the cause of vt-lines difference, because there are vt-values in unwrapped1.obj that are not present in unwrapped2.obj (0.426069 in unwrapped1.obj for example). This behaviour is believed to be reproducible with other file formats like .ply. I've looked through Blender source code (uvedit module) for the cause of this random behaviour and have not found any clues (maybe I'm not experienced enough). The only function I found there that uses random numbers is initialized with the constant seed 31415926 (however this function doesn't seem to alter Unwrap), so I believe Blender is expected to yield consistent result for the same input.

Roman Nagornov commented

2016-02-25 18:16:44 +01:00

Changed status to: 'Open'

Roman Nagornov commented

2016-02-25 18:16:44 +01:00

Added subscriber: @RomanN

Bastien Montagne commented

2016-02-25 19:46:50 +01:00

Added subscriber: @mont29

Bastien Montagne commented

2016-02-25 19:46:50 +01:00

Changed status from 'Open' to: 'Archived'

Bastien Montagne closed this issue

2016-02-25 19:46:50 +01:00

Bastien Montagne self-assigned this 2016-02-25 19:46:50 +01:00

Bastien Montagne commented

2016-02-25 19:46:50 +01:00

No need to use an exporter to realize that, just make two copies of same mesh, unwrap both, you won’t get exact same results.

This comes from the fact that this 'Unwrap' function uses LSCM (least squares conformal map) which is complex mathematical stuff (see editor/uvedit/uvedit_parametrizer.c) and is, afaik, not totally deterministic… Don’t know the details here, though, you’d need to talk to a real math guy ;)

But anyway, thanks for the report, but no bug here.

No need to use an exporter to realize that, just make two copies of same mesh, unwrap both, you won’t get exact same results. This comes from the fact that this 'Unwrap' function uses LSCM (least squares conformal map) which is complex mathematical stuff (see `editor/uvedit/uvedit_parametrizer.c`) and is, afaik, not totally deterministic… Don’t know the details here, though, you’d need to talk to a real math guy ;) But anyway, thanks for the report, but no bug here.

Roman Nagornov commented

2016-02-26 10:31:41 +01:00

I've glanced through original LSCM paper by Levy et al. before and here are my thoughts:
LSCM parametrization is just a minimization problem which solves the Least-Squares problem (it's in the name – LSCM). That all boils down to just solving big and sparse linear system Ax = b. There is a catch: you have to pin at least two UVs in advance to make Ax=b system well-defined, that's it, to have a unique solution. So from mathematical point of view after you pinned some UVs, you must get the same answer, hence the choice of UVs to be pinned is a possible cause of random behaviour. Looking through the UVs pinning in (editor/uvedit/uvedit_parametrizer.c) makes me think it's not the case.
Another possible source of random behaviour is A*x=b system solver. It's said in (http://wiki.blender.org/index.php/Dev:Source/Textures/UV/Unwrapping) that SuperLU solver is used for solving and the code shows that it must be OpenNL implementation of this solver (never tried it though, only Eigen).
SuperLU is said to be a direct solver. These solvers will all arrive at the same answer for all well-conditioned finite element problems, which is their biggest advantage (quote from: https://www.comsol.com/blogs/solutions-linear-systems-equations-direct-iterative-solvers/). But anyway there might be randomity, because of solver implementation. For example in computer arithmetics summation is not associative, hence such random errors may occur because of different order of summation after parallelization of the algorithm and it's a side effect (they are no good).
The only functions in (editor/uvedit/uvedit_parametrizer.c) that uses random (BLI_rand.h) explicitly are p_chart_stretch_minimize(), param_stretch_begin(), param_stretch_end(). I mentioned them in my report. Their random generator is initialized with the constant seed 31415926.
However they all trace up to UV_OT_minimize_stretch() function in (editor/uvedit/uvedit_unwrap_ops.c) that seems to have nothing to do with Unwrap.

This random behaviour of the Unwrapper seems to be a side effect for me, not an expected behaviour. If it was an expected behaviour indeed, I would expect it to act pseudo-random as in UV_OT_minimize_stretch(), not random-random.

There is another different possible bug for me: shuffled vertex indices in f-lines in exported .obj file. Their order must not depend on particular unwrapping method and especially different trials of the one method, but only seams and mesh.

Anyway, thanks for your attention.
Regards, Roman.

I've glanced through original LSCM paper by Levy et al. before and here are my thoughts: LSCM parametrization is just a minimization problem which solves the Least-Squares problem (it's in the name – LSCM). That all boils down to just solving big and sparse linear system A*x = b. There is a catch: you have to pin at least two UVs in advance to make A*x=b system well-defined, that's it, to have a unique solution. So from mathematical point of view after you pinned some UVs, you must get the same answer, hence the choice of UVs to be pinned is a possible cause of random behaviour. Looking through the UVs pinning in (editor/uvedit/uvedit_parametrizer.c) makes me think it's not the case. Another possible source of random behaviour is A*x=b system solver. It's said in (http://wiki.blender.org/index.php/Dev:Source/Textures/UV/Unwrapping) that SuperLU solver is used for solving and the code shows that it must be OpenNL implementation of this solver (never tried it though, only Eigen). SuperLU is said to be a direct solver. These solvers will all arrive at the same answer for all well-conditioned finite element problems, which is their biggest advantage (quote from: https://www.comsol.com/blogs/solutions-linear-systems-equations-direct-iterative-solvers/). But anyway there might be randomity, because of solver implementation. For example in computer arithmetics summation is not associative, hence such random errors may occur because of different order of summation after parallelization of the algorithm and it's a side effect (they are no good). The only functions in (editor/uvedit/uvedit_parametrizer.c) that uses random (BLI_rand.h) explicitly are p_chart_stretch_minimize(), param_stretch_begin(), param_stretch_end(). I mentioned them in my report. Their random generator is initialized with the constant seed 31415926. However they all trace up to UV_OT_minimize_stretch() function in (editor/uvedit/uvedit_unwrap_ops.c) that seems to have nothing to do with Unwrap. This random behaviour of the Unwrapper seems to be a side effect for me, not an expected behaviour. If it was an expected behaviour indeed, I would expect it to act pseudo-random as in UV_OT_minimize_stretch(), not random-random. There is another different possible bug for me: shuffled vertex indices in f-lines in exported .obj file. Their order must not depend on particular unwrapping method and especially different trials of the one method, but only seams and mesh. Anyway, thanks for your attention. Regards, Roman.

Roman Nagornov commented

2016-03-01 17:11:22 +01:00

Changed status from 'Archived' to: 'Open'

Roman Nagornov reopened this issue

2016-03-01 17:11:22 +01:00

Roman Nagornov commented

2016-03-01 17:11:22 +01:00

I think I've figured out the source of random behaviour I've been talking about and it's not what Bastien 's claimed. So I feel like I can open this issue again.

Surprisingly it has nothing to do with particular Unwrapping method both LSCM or ABF. The cause is the hash table used for initialization of half-edge data structure. To be precise, just a line inside construct_param_handle_face_add() function in (editor/uvedit/uvedit_unwrap_ops.c):

key = (ParamKey)efa;

This means an element's key for hashing is initialized with random-random pointer value. So the order of iteration through faces, edges, vertices in half-edge data structure is different every program run, that might lead to side effects because the lack of summation associativity in computer arithmetic, that should show themselves in absence of repeatability. If you change this line with a key variable initialization with pseudo-random rand() function for example, you'll get the repeatability and consistency I was talking about above (see the attached file with a dirty workaround uvedit_unwrap_ops.c. My code is decorated with //del). I tested it with different meshes and it seems to work so far. Don't know if rand() or other pseudo-random function will slow down working with the hash table much due to collisions, though there must be reasons why one chose such random-random way of keys initialization.

It's up to you is it a bug or not, but I think this behaviour'd better at least be documented. I've already written above the reasons why I think it's rather an unwanted bahaviour. Anyway I want anyone who faced this issue to find a fast workaround here.

P.S. I've made a mistake claiming that SuperLU is implemented in OpenNL.
Sorry for my English.
Regards, Roman.

I think I've figured out the source of random behaviour I've been talking about and it's not what Bastien 's claimed. So I feel like I can open this issue again. Surprisingly it has nothing to do with particular Unwrapping method both LSCM or ABF. The cause is the hash table used for initialization of half-edge data structure. To be precise, just a line inside construct_param_handle_face_add() function in (editor/uvedit/uvedit_unwrap_ops.c): key = (ParamKey)efa; This means an element's key for hashing is initialized with random-random pointer value. So the order of iteration through faces, edges, vertices in half-edge data structure is different every program run, that might lead to side effects because the lack of summation associativity in computer arithmetic, that should show themselves in absence of repeatability. If you change this line with a key variable initialization with pseudo-random rand() function for example, you'll get the repeatability and consistency I was talking about above (see the attached file with a dirty workaround [uvedit_unwrap_ops.c](https://archive.blender.org/developer/F286522/uvedit_unwrap_ops.c). My code is decorated with //del). I tested it with different meshes and it seems to work so far. Don't know if rand() or other pseudo-random function will slow down working with the hash table much due to collisions, though there must be reasons why one chose such random-random way of keys initialization. It's up to you is it a bug or not, but I think this behaviour'd better at least be documented. I've already written above the reasons why I think it's rather an unwanted bahaviour. Anyway I want anyone who faced this issue to find a fast workaround here. P.S. I've made a mistake claiming that SuperLU is implemented in OpenNL. Sorry for my English. Regards, Roman.

Roman Nagornov commented

2016-03-01 17:35:37 +01:00

You don't even need pseudo-random. Something simple like this might do the job as good as the random-random way of initializing (because the pointer values increase sequentially) and it will be determenistic. See the pseudo-code:

construct_param_handle(args){
// Some code

for (unsigned int i = 0; i< max; i += step){
Some code Function call

  construct_param_handle_face_add(args, i){
        // Some code
        key = (ParamKey)i;
        // Some code
   }
  // Some code

}

// Some code
}

You don't even need pseudo-random. Something simple like this might do the job as good as the random-random way of initializing (because the pointer values increase sequentially) and it will be determenistic. See the pseudo-code: construct_param_handle(args){ // Some code for (unsigned int i = 0; i< max; i += step){ *Some code* Function call ``` construct_param_handle_face_add(args, i){ // Some code key = (ParamKey)i; // Some code } // Some code ``` } // Some code }

Bastien Montagne commented

2016-03-02 12:09:56 +01:00

Added subscriber: @brecht

Bastien Montagne commented

2016-03-02 12:09:56 +01:00

Oh, very nice catch! :)

Yes, think using faces' index somehow is best option here, attached a patch doing that (also doing same thing for live unwrap when subsurf modifier is present).

@brecht think you know that code best, do you see any issue with replacing BMFace/MPoly pointers by their indices as key here? As far as I can tell, those face keys are not used back anywhere…

P329: #47564

diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index 3f21813..9f2b0f1 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -217,7 +217,7 @@ void ED_uvedit_get_aspect(Scene *scene, Object *ob, BMesh *bm, float *aspx, floa
 }
 
 static void construct_param_handle_face_add(ParamHandle *handle, Scene *scene,
-                                            BMFace *efa, const int cd_loop_uv_offset)
+                                            BMFace *efa, int face_index, const int cd_loop_uv_offset)
 {
 	ParamKey key;
 	ParamKey *vkeys = BLI_array_alloca(vkeys, efa->len);
@@ -230,7 +230,7 @@ static void construct_param_handle_face_add(ParamHandle *handle, Scene *scene,
 	BMIter liter;
 	BMLoop *l;
 
-	key = (ParamKey)efa;
+	key = (ParamKey)face_index;
 
 	/* let parametrizer split the ngon, it can make better decisions
 	 * about which split is best for unwrapping than scanfill */
@@ -256,6 +256,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm,
 	BMLoop *l;
 	BMEdge *eed;
 	BMIter iter, liter;
+	int i;
 	
 	const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
 
@@ -273,7 +274,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm,
 	/* we need the vert indices */
 	BM_mesh_elem_index_ensure(bm, BM_VERT);
 	
-	BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
+	BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, i) {
 
 		if ((BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) || (sel && BM_elem_flag_test(efa, BM_ELEM_SELECT) == 0)) {
 			continue;
@@ -293,7 +294,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm,
 			}
 		}
 
-		construct_param_handle_face_add(handle, scene, efa, cd_loop_uv_offset);
+		construct_param_handle_face_add(handle, scene, efa, i, cd_loop_uv_offset);
 	}
 
 	if (!implicit) {
@@ -449,7 +450,7 @@ static ParamHandle *construct_param_handle_subsurfed(Scene *scene, Object *ob, B
 
 		/* We will not check for v4 here. Subsurfed mfaces always have 4 vertices. */
 		BLI_assert(mpoly->totloop == 4);
-		key = (ParamKey)mpoly;
+		key = (ParamKey)i;
 		vkeys- [x] = (ParamKey)mloop- [x].v;
 		vkeys- [x] = (ParamKey)mloop- [x].v;
 		vkeys- [x] = (ParamKey)mloop- [x].v;

Oh, very nice catch! :) Yes, think using faces' index somehow is best option here, attached a patch doing that (also doing same thing for live unwrap when subsurf modifier is present). @brecht think you know that code best, do you see any issue with replacing BMFace/MPoly pointers by their indices as key here? As far as I can tell, those face keys are not used back anywhere… [P329: #47564](https://archive.blender.org/developer/P329.txt) ```diff diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c index 3f21813..9f2b0f1 100644 --- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c +++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c @@ -217,7 +217,7 @@ void ED_uvedit_get_aspect(Scene *scene, Object *ob, BMesh *bm, float *aspx, floa } static void construct_param_handle_face_add(ParamHandle *handle, Scene *scene, - BMFace *efa, const int cd_loop_uv_offset) + BMFace *efa, int face_index, const int cd_loop_uv_offset) { ParamKey key; ParamKey *vkeys = BLI_array_alloca(vkeys, efa->len); @@ -230,7 +230,7 @@ static void construct_param_handle_face_add(ParamHandle *handle, Scene *scene, BMIter liter; BMLoop *l; - key = (ParamKey)efa; + key = (ParamKey)face_index; /* let parametrizer split the ngon, it can make better decisions * about which split is best for unwrapping than scanfill */ @@ -256,6 +256,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm, BMLoop *l; BMEdge *eed; BMIter iter, liter; + int i; const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); @@ -273,7 +274,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm, /* we need the vert indices */ BM_mesh_elem_index_ensure(bm, BM_VERT); - BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, i) { if ((BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) || (sel && BM_elem_flag_test(efa, BM_ELEM_SELECT) == 0)) { continue; @@ -293,7 +294,7 @@ static ParamHandle *construct_param_handle(Scene *scene, Object *ob, BMesh *bm, } } - construct_param_handle_face_add(handle, scene, efa, cd_loop_uv_offset); + construct_param_handle_face_add(handle, scene, efa, i, cd_loop_uv_offset); } if (!implicit) { @@ -449,7 +450,7 @@ static ParamHandle *construct_param_handle_subsurfed(Scene *scene, Object *ob, B /* We will not check for v4 here. Subsurfed mfaces always have 4 vertices. */ BLI_assert(mpoly->totloop == 4); - key = (ParamKey)mpoly; + key = (ParamKey)i; vkeys- [x] = (ParamKey)mloop- [x].v; vkeys- [x] = (ParamKey)mloop- [x].v; vkeys- [x] = (ParamKey)mloop- [x].v; ```

Brecht Van Lommel commented

2016-03-02 12:20:16 +01:00

It should be fine, patch looks good to me.

blender-admin commented

2016-03-02 12:21:53 +01:00

This issue was referenced by 0d12e086f5

This issue was referenced by 0d12e086f5dda74d43e3a2d011bfc848c95136de

Bastien Montagne commented

2016-03-02 12:29:48 +01:00

Changed status from 'Open' to: 'Resolved'

Bastien Montagne closed this issue

2016-03-02 12:29:48 +01:00

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Unwrapping the same mesh results in different UVs and alter Export #47564