1
$\begingroup$

I'm trying to develop an addon which takes all of the individual UV vertices of two meshes.
Then it compares the target UV to the source one.
If two UV vertices match, then I want to find the vertex's 3d source position.

I'm trying to find a more efficient way to look for each target UV vertex through source UVs.
Right now, for each target UV vertex, I'm looping through every UV vertex of source UVs until I find the same one.
I wanted to see if there is any better way to do it or not.
Thanks in advance.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

A KDTree is a structure for fast comparison/search based on 3D coordinates (more information here).

In your context, you can create a KDTree from the uvs of the first object (translating 2d coordinates into 3d for the KDTree).

Then loop over the uvs of the second and query the KDTree using find (or find_n, find_range depending on what you exactly need).

find will return a tuple of (coordinate, index, distance) of the vertex that is found.

The script.

import bpy
import time
from mathutils import Vector, kdtree


def make_kd_from_uvs(uvs):
    #Create a kd tree
    size = len(uvs)
    kd = kdtree.KDTree(size)
    #Populate it
    for i, uv in enumerate(uvs):
        kd.insert(uv.uv.to_3d(), i) #With 3d coordinates
    #Prepare for querying
    kd.balance()
    return kd

def loop_to_vertex_map(obj):
    #Create an array of loop indices to vertex indices
    polygons = obj.data.polygons
    return [v for p in polygons for v in p.vertices]

def compare_kd(obj1, uv_name1, obj2, uv_name2):
    #Get uvs for each
    uvs1 = obj1.data.uv_layers[uv_name1].data
    uvs2 = obj1.data.uv_layers[uv_name2].data
    
    #Get maps to look up from loop indices to vertex indices
    map1 = loop_to_vertex_map(obj1)
    map2 = loop_to_vertex_map(obj2)

    #Make a kd tree from the first
    kd = make_kd_from_uvs(uvs1)

    #Loop over the second
    for index2, uv2 in enumerate(uvs2):
        co2 = uv2.uv.to_3d() #With 3d coordinates
        #Query the kd tree
        co1, index1, distance = kd.find(co2)
        uv1 = uvs1[index1]
        
        v1 = obj1.data.vertices[map1[index1]]
        v2 = obj2.data.vertices[map2[index2]]
        
        #print(v1.co, v2.co)
        #print(uv1.uv, uv2.uv)

obj1 = bpy.data.objects["Cube"]
obj2 = bpy.data.objects["Cube.001"]

start = time.time()
compare_kd(obj1, "UVMap", obj2, "UVMap")
end = time.time()
print(end-start)
$\endgroup$
3
  • $\begingroup$ Great! Thanks! but I wanted to find their 3d position as well. To be exact, I want to find the same UV in the source object, then find it's original 3d position. $\endgroup$ Nov 10, 2020 at 8:48
  • 1
    $\begingroup$ Should mention that in the question... but answer edited. $\endgroup$
    – lemon
    Nov 10, 2020 at 9:07
  • $\begingroup$ Question edited. Thanks for mentioning. But I couldn't figure out the last function. How should I use that exactly? $\endgroup$ Nov 10, 2020 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .