1
$\begingroup$

I have a problem similar to my last one but yet I can't find an efficient solution.

Having an array of [x,y] coordinate that indicate position on the UV map I want to select the closest vertices ( in 3D )

I'm guessing the main idea would be to iterate upon my array of coordinate and then compute the distance to each vertices on the UV map with 2 for loop ( one for face in bm.faces, and another for loop in loop in face.loops ) but that would be not efficient.

What is my best option here ?

Any help is welcome.

thx.

$\endgroup$
  • 1
    $\begingroup$ Possible performance issues? I mean what is the size of the array and what is the size of the mesh? $\endgroup$ – lemon Jul 25 at 13:55
  • $\begingroup$ like I have 200 hundred coordinates on a 200k+ vertices mesh so that would make 40 millions distance to test. I feel like I could maybe use the operator bpy.ops.uv.select_circle() that would but I don't understand how to use it. $\endgroup$ – Edmond Boulet-Gilly Jul 25 at 14:00
  • 1
    $\begingroup$ Just an idea: handle the UV map as if it is a mesh (make a mesh from it), then build a bvh tree and ray cast on it. If you handle this pseudo mesh faces index correctly you should retrieve easily the corresponding face of the mesh in 3D. Reference docs.blender.org/api/current/… $\endgroup$ – lemon Jul 25 at 14:03
  • 2
    $\begingroup$ Close to what you need blender.stackexchange.com/questions/79236/… and this also blender.stackexchange.com/questions/77607/… (use ray cast) $\endgroup$ – lemon Jul 25 at 14:11
3
$\begingroup$

I propose to use a kdtree so that we'll have an efficient search tree over the UV Map, for all the coordinates you have in input.

The principle is the following:

  • Create a kdtree and populate it with UV coordinates
  • Initialize it
  • Search on it from the input coordinates you have
  • From this index, get the corresponding vertex index (in the 3D mesh) using the loops

The tree is initialized once per mesh and allows multiple searches.

The commented code:

import bpy
import bmesh
from mathutils import Vector
from mathutils.kdtree import KDTree


print( '-------------------------------' )

# Do all that in object mode
bpy.ops.object.mode_set(mode = 'OBJECT')

# Get the mesh
obj = bpy.context.active_object

# Get its UV map
uvmap = obj.data.uv_layers['UVMap']

# Make an array of uv coordinates in 3D
coordinates = [(d.uv.x, d.uv.y, 0) for d in uvmap.data]

# Create a jd tree from that
kd = KDTree( len( coordinates ) )

# Populate it
for i, v in enumerate( coordinates ):
    kd.insert( v, i )

# Initialize it
kd.balance()

# Input UV coordinates
x = 0.41
y = 0.96

# Search
coordinate, index, distance = kd.find( (x, y, 0) )

print( coordinate )
print( index ) 
print( distance )

# Corresponding vertex (in the mesh) and its index
vertex_index = obj.data.loops[index].vertex_index
vertex = obj.data.vertices[vertex_index]

print( vertex.index )

Note: there is also a bvhtree version in the blend file. If you have time you could compare the results and perfomence

The main diff between bvh and kd is that bvh will test on faces and kd will test on vertex proximity (so this can be outside the face). I don't know what is important in your context.

In the blend file, there is two script in the text editor 'KDTree' and 'BVHTree' so that you can choose.

$\endgroup$
  • 2
    $\begingroup$ Wondering is it worth extending to get all uv's at uv of closest, and the associated verts? $\endgroup$ – batFINGER Jul 26 at 7:52
  • 1
    $\begingroup$ @batFINGER, we'll see if the OP ask about that and what is his goal. In the same spirit I'd first though about bvh raycats which ensures to be inside a face (as kdtree does not). $\endgroup$ – lemon Jul 26 at 8:08
  • 1
    $\begingroup$ While your here, how is your python file io? Mine is crap. Re blender.stackexchange.com/questions/145906/… I have the struct TextLine and know where the blocks are, but can't get my head around reading the field string values. Note the blendfile walker module in the same folder. $\endgroup$ – batFINGER Jul 26 at 8:16
  • 1
    $\begingroup$ @EdmondBoulet-Gilly Yes. see docs.blender.org/api/current/… $\endgroup$ – lemon Jul 26 at 8:56
  • 1
    $\begingroup$ thx now i should be able to go on by myself. $\endgroup$ – Edmond Boulet-Gilly Jul 26 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.