[Addon] Copy Vertex Order By UVs v0.6 (update 2013-01-31)

http://nukengine.com/blender-addons/

— [update 2013-01-31 - new release v0.6] —
Twice as fast. Simplified algorithm.

— [update 2013-01-31 - new release v0.5] —
Faster now, again for blender 2.65a.

— [update 2013-01-29 - new release v0.4] —
Now for blender 2.65a. Support for older versions removed.

— [update 2012-04-19 - new release v0.3] —

Works with Blender 2.62 (non-BMesh) and 2.63rc1 (BMesh) now. However, in 2.63 it is about 10-20 times slower, because accessing the UV-Mapping is much slower. Will look into this later.

Since code has been improved you should also update if you are only using Blender 2.62.

— [original post] —

Creates copy of active mesh with vertex order of selected mesh. Many cool operations are only possible if vertex order matches. However, some external programs save the mesh back in other orders. The addon requires that the UV-Mapping of both meshes is identical.

Installation:

  • Copy nuke_copy_indices.py to blender-2.62-release-windows32\2.62\scripts\addons
  • Activate in “File -> User Preferences -> Addons -> Mesh -> Copy Vertex Order by UVs”

Usage:

  • Select two meshes (with identical UV mapping)
  • In Object Menu click “Copy Vertex Order by UVs”, creates copy of 2nd mesh with vertex order of 1st mesh

Errors:

Algorithm:

  • For both meshes build min-heap of vertex lists by number of occurance of a certain vertex degree in the mesh (degree as number of faces containing a vertex)
  • First step of the loop: map verts, candidate set is all unmapped verts with degree X [ aka map(pop(minheap1), pop(minheap2)) ]
  • second step of loop: loop: expand mappings found in step one: candidate set is a vertex that was mapped in step one or two.

Note: The Algorithm could be optimized. At the moment it is conservative in the sense that it verifies that a vertex is mapped to the same vertex for all its faces. It also checks all vertices of the current candidate set against each other. That way we are sure we find a single unique mapping. But since the candidate set is choosen by topological features it should still be orders of magnitude faster than any n*n approach just comparing all vertices, for meshes of a certain size.

This is what I was looking for.
Matching vertex order is very important for us.
I am also amazed by blenders transfer UV function.
It can copy UV from one object to another even if vertex order is different.
With combination of this addon and transfer UV function, I do not need to worry about vertex order anymore.

Currently this addon does not seem to work with Bmesh.

Thank you.

my english i very bad. i dont understand what this addon does.

I am also amazed by blenders transfer UV function.
Can you show me which script or function you mean? It depends on what that exactly does (lets assume it transfers uv mapping based on that the vertices are on the same location, then it will only work if the meshes have the same shape more or less).

Currently this addon does not seem to work with Bmesh.
Can I test that in blender 2.62 or do I have to download a special version? Will the old API still be available when using BMesh? Sorry, never used BMesh till now.

my english i very bad. i dont understand what this addon does.
I try it with other words:

  • Assume you have a mesh
  • Assume you have exported the mesh, sculped it in another application, imported the sculp back to blender
  • If the vertex order of the sculped mesh is not the same as your original mesh, then you cannot transfer the shape of the new mesh to your old mesh (as shape key).
  • With this addon you can select old mesh and new mesh and it will create a copy of the new mesh, but with vertex order of old mesh ==> you can now transfer the sculped shape from this new copy to your original mesh as shape key, because the vertex order of the new copy and your original mesh are identical.

Hope this helps.

hi, your best to get either a recent blender build from graphicall.org or a 2.63rc from blender.org
thanks for the cool addon.

Hi.
The vertex order and the shape is different.
But I still can transfer UVs.
Select two objects.
Then ctrl L and chose Join as UVs.

vertexOrder.zip (114 KB)

@mill: thanks, will look at that.

@Meta-Androcto: thanks a lot.

I downloaded 2.63rc, but now I have a massive performance problem.

In blender 2.62 the addon needs about 15 seconds in my case to map a mesh with 38k vertices. However, in 2.63rc it needs about 450 seconds to just map the first 3.8k vertices.

That means in 2.63rc it is about 300 times slower!

At the moment I use the following functions to support 2.62 and 2.63rc at the same time. I did not profile, but I assume retrieving the UVs that way is the problem (f is face index, F is MeshPolygon):

def faces(mesh):
    if isBMesh:
        return mesh.polygons
    else:
        return mesh.faces

def uvs(mesh, f, F):
    if isBMesh:
        uv_loops = mesh.uv_loop_layers.active.data
        lstart = lend = F.loop_start
        lend += F.loop_total
        return [uv.uv for uv in uv_loops[lstart:lend]]
    else:
        return mesh.uv_textures.active.data[f].uv

I should use a cache for UVs per face, but I assume it will still be much slower in 2.63rc if using that way to get the UVs.

Note: the “Vertex Randomize” function seems broken in 2.63rc, I used that in 2.62 for simple tests, but seems to have no effect in 2.63rc.

[Edit1:]
With UV cache it needs 210 seconds to finish. So “only” 14 times slower now.
Is there a faster way to get the UVs for all faces?

[Edit2:]
@mill: I tried “Join as UVs”, it does not work for my mesh if vertex order is different. I looked at the code, it just copies the UVs from one mesh to the other in order, without analyzing the structure. So I think it will only work if vertex order and?/or? (BMesh) loop order are identical.

New release v0.3, now BMesh compatible. See first post.

You are right.
“join as UVs” does not work for a mesh with different vertex order.
I wonder why it works for a simple object like a monkey.
The only software I know of which can handle the situation is 3D-coat.
Any way, thank you for the useful addon.

Hi,
any news on this? In 2.62 it works great, but in the current version (2.65) I get the following errors:

Traceback (most recent call last):
File “C:\Program Files\Blender\svn\2.65\scripts\addons
uke_copy_indices.py”, line 339, in execute
object_copy_indices(self, context)
File “C:\Program Files\Blender\svn\2.65\scripts\addons
uke_copy_indices.py”, line 263, in object_copy_indices
mapByUv(mesh1, mesh2, vList1, vList2, VertexFaces1, VertexFaces2, uvcache1, uvcache2, mapping, invmapping, newMaps)
File “C:\Program Files\Blender\svn\2.65\scripts\addons
uke_copy_indices.py”, line 137, in mapByUv
submatch = findMatchingVertsByUv(mesh1, v1, f1, mesh2, v2, f2, uvcache1, uvcache2)
File “C:\Program Files\Blender\svn\2.65\scripts\addons
uke_copy_indices.py”, line 80, in findMatchingVertsByUv
uvs1 = uvs(mesh1, f1, F1)
File “C:\Program Files\Blender\svn\2.65\scripts\addons
uke_copy_indices.py”, line 38, in uvs
uv_loops = mesh.uv_loop_layers.active.data
AttributeError: ‘Mesh’ object has no attribute ‘uv_loop_layers’

location: <unknown location>:-1

Will look at it this weekend or next week. Did not use it in a long time.

Thanks!
It seems to be a great tool for remeshing blender sculpt from an imported model (which requires the same vertex order).

uv_loop_layers was renamed to uv_layers!

You may be able to improve speed by using the bmesh module. It provides index_update() and sort() methods for bmesh faces.

A little experiment I did:


import bpy
from bpy import context as C


# Polygon with index 5 is selected


bm=bmesh.from_edit_mesh(C.object.data)
bm.faces[5].index = 3
bm.faces[3].index = 5
bm.faces.sort()


# No changes yet
C.object.data.polygons[3].select
#~ False
C.object.data.polygons[5].select
#~ True


bmesh.update_edit_mesh(C.object.data)


# Still nothing changed
C.object.data.polygons[3].select
#~ False
C.object.data.polygons[5].select
#~ True


# "Old" API requires mode switching for an update
bpy.ops.object.editmode_toggle()
#~ {'FINISHED'}


# There it is, selected polygon has now index 3!
C.object.data.polygons[3].select
#~ True
C.object.data.polygons[5].select
#~ False

Here’s a diff for two little changes:

--- C:/Users/CoDEmanX/AppData/Local/Temp/Temp1_nuke_copy_indices_v0.3_rev11.zip/nuke_copy_indices_CoDEmanX.py	So Jan 27 22:28:53 2013+++ C:/Users/CoDEmanX/AppData/Local/Temp/Temp1_nuke_copy_indices_v0.3_rev11.zip/nuke_copy_indices.py	So Jan 27 22:44:58 2013
@@ -3,8 +3,8 @@
 bl_info = {
     "name": "Copy vertex order by UVs",
     "author": "fxbar/f00bar",
-    "version": (0, 4),
-    "blender": (2, 62, 0),
+    "version": (0, 3),
+    "blender": (2, 6,0),
     "api": 40900,
     "location": "Object &gt; Copy vertex order by UVs",
     "description": "Copy vertex order by UVs",
@@ -35,10 +35,7 @@
 
 def uvs(mesh, f, F):
     if isBMesh:
-        if hasattr(mesh, 'uv_layers'):
-            uv_loops = mesh.uv_layers.active.data
-        else:
-            uv_loops = mesh.uv_loop_layers.active.data
+        uv_loops = mesh.uv_loop_layers.active.data
         lstart = lend = F.loop_start
         lend += F.loop_total
         return [uv.uv for uv in uv_loops[lstart:lend]]
@@ -212,16 +209,17 @@
     
     #ugly block, but fast to implement
     global isBMesh
-    if hasattr(mesh1, 'polygons'):
+    try:
+        face = mesh1.polygons
+        print("is BMesh")
         isBMesh = True
-        
+    except:
+        print("is not BMesh")
+        face = mesh1.faces
+        isBMesh = False
     if isBMesh:
-        face = mesh1.polygons
+        # be sure that both are bmesh, otherwise crash (should not be possible or I understand something wrong)
         face = mesh2.polygons
-    else:
-        face = mesh1.faces
-        face = mesh2.faces
-
     
     if not mesh1.uv_textures or len(mesh1.uv_textures) == 0 or not mesh2.uv_textures or len(mesh2.uv_textures) == 0:
         raise Exception("Both meshes must have a uv mapping. This operator even assumes matching uv mapping!")



I didn’t understand the actual algorithm, otherwise i would had tried to make it use the bmesh sort(). But i bet you can do that quickly, all you need is a list of the new indices instead of changing .loop_start / .loop_total

UPDATE, see first post. Now for blender 2.65a.

Thanks, but I do create the new mesh at the end with a single call. This is not the bottleneck. My problem is that access to UVs is much slower than in pre-bmesh blender. But I assume there is a faster way for that too. However, since I do not use the addon at the moment I’m not motivated to investigate that. If you find a way to make the function “def uvs(mesh, F)” (returns ordered UVs of a face) faster, I will happily use your changes.

Thanks. I just removed all backward compatibility code, so the ugly stuff is no longer in there. Blender 2.65a seems very stable, so no need for that anymore.

[QUOTE=fbar;2293189]UPDATE, see first post. Now for blender 2.65a.

Thanks fbar for updating this addon. :slight_smile: It’s one of my favorite.

Thanks for the update!

It seems to have a problem with high poly meshes though (no match for face errors)

well you could use the convenience property loop_indices to save the extra calculation of “lend”

e.g.
[uv_loops[i] for i in C.object.data.polygons[#].loop_indices]

and uv_loops should be a copy in a global var, that might make it faster…

ok, i tested two variations and here are the results:

original function, 30k suzanne test mesh, 21.2 seconds

def uvs(mesh, f, F):
    if isBMesh:
        if hasattr(mesh, 'uv_layers'):
            uv_loops = mesh.uv_layers.active.data
        else:
            uv_loops = mesh.uv_loop_layers.active.data
        lstart = lend = F.loop_start
        lend += F.loop_total
        return [uv.uv for uv in uv_loops[lstart:lend]]
    else:
        return mesh.uv_textures.active.data[f].uv

cleaned-up function, only for more recent blender versions, 5.9 seconds

def uvs_(mesh, f, F):
    uv_loops = mesh.uv_layers.active.data
    return [uv_loops[uv].uv for uv in F.loop_indices]

(just realized that the lower-case f parameter should be removed…)

global uv_loops variables and inline loops, 5.7 seconds

...
uv_loops_1 = None
uv_loops_2 = None
...
    global uv_loops_1
    global uv_loops_2
    uv_loops_1 = mesh1.uv_layers.active.data[:]
    uv_loops_2 = mesh2.uv_layers.active.data[:]
...
        uvs1 = [uv_loops_1[uv].uv for uv in F1.loop_indices]
...
        uvs2 = [uv_loops_2[uv].uv for uv in F2.loop_indices]
...
                        for x in [uv_loops_1[uv].uv for uv in faces(mesh1)[f1].loop_indices]:
...
                                for x in [uv_loops_2[uv].uv for uv in faces(mesh1)[f2].loop_indices]:

i recommend the cleaned-up function, as the inline and global var stuff isn’t nice code style, and it is almost as fast as the inlined version.

Update, see first post. Faster now.

@CoDEmanX: Thanks. Did the same in parallel after you gave me the idea to use globals. I use globals now with 2 functions (ugly, I know). Will consider the other approach for the next release.


uv_loops1 = None
uv_loops2 = None
def getUvs1(F):
    return [uv_loops1[i].uv for i in F.loop_indices]
def getUvs2(F):
    return [uv_loops2[i].uv for i in F.loop_indices]

I assumed the “uv_loops = mesh.uv_layers.active.data” is the slow part, but then it really was


        lstart = lend = F.loop_start
         lend += F.loop_total

Don’t understand why this is slow, but thanks a lot for testing.

@ania: I did a test with a 70k vertices model. It worked. Are you sure that the UV mappings are identical? The values must be identical in both mappings to a precision of 0.000001, if that is the problem you could try to increase the EPSILON defined at the beginning of the script. It could also be a bug. Can you upload the models somewhere? And there are cases where the addon will not work, e.g. if multiple faces sharing a vertex have the same UVs for all their vertices, then the addon maybe starts with mapping the wrong faces to each other and gets stuck later. Against that nothing can be done except making the code more complex and support back-tracking. I don’t plan to do that as long as I don’t need that. If that’s the problem and you feel lucky and have not too many such locations, you could try to randomize the vertex order (Mesh->Vertices->Sort Vertices) until you have enough luck (change seed).

[Edit:]
Another cause can be symmetrical vertices, at the beginning the algorithm tries to map vertices that have the same degree (number of faces containing the vertex). If the faces of these vertices have the same UVs, the algorithm can start with a wrong mapping. Same fix: randomize vertex order and have luck.
And another problem could be faces for which all vertices have the same UV.
Look at the console. The final lines should give a more precise error. With vertex and face index where it gets stuck. Question is how the find those in the models, but there should be an addon for that.

not sure if that’s really the slowest part

lstart = lend = F.loop_start
lend += F.loop_total

sure, it takes quite a lot operations:

  • create two vars
  • assign value to both (read from face prop)
  • increase a var by a value (read from face prop)

in the uncleaned version there are additional if-statements for every call to uvs()

but don’t forget about this line:

[uv.uv for uv in uv_loops[lstart:lend]]

a slice is used here, which means that the part lstart to lend gets copied to a new location in memory (unless python is smarter than that?)

using loop_indices is obviously much more efficient. It is a range-object and I suppose it makes python just copy and return the needed items instead of slicing off the relevant part first before reading the desired data. You could have used something like range(F.loop_start, F.loop_start + F.loop_total), but that would still be a little slower as the range-object has to be created.