6
$\begingroup$

I want to find the edge index of an edge, for the purpose of performing some operation on that edge programmatically.

If I know where that edge is in a simple mesh (for example if I know its Z location will always be higher than that of the other edges), how can I use that coordinate data to get the edge index?

$\endgroup$
4
  • 1
    $\begingroup$ Hello. Edge location is defined by its vertices but you mention only Z. Also that may depend on the accurcy you want. I mean, is it to test proximity or exact value. And it is to test all that is above somethin, in an interval, etc.? $\endgroup$
    – lemon
    Nov 17, 2020 at 8:24
  • $\begingroup$ Hi @lemon , thanks for dropping a comment. Testing for proximity sounds like a good way. I don't know all the possibilities, but I imagine one way could be to start with some variable of [x,y,z] coords and then try to find the nth number of edges nearest to that location. In my immediate case I only need to select the very nearest single edge though. $\endgroup$
    – Mentalist
    Nov 17, 2020 at 8:58
  • $\begingroup$ ok, so this is edge based (not searching for its vertices locations). And another question: is it to make several accesses like that (finding many edges from many locations) or just ponctually one edge from one location? $\endgroup$
    – lemon
    Nov 17, 2020 at 9:01
  • $\begingroup$ Correct; vertex locations are not needed in this case. Since getting at specific geometry using Python is new to me I would certainly be curious to learn how the process differs for verts / edges / faces, but it's not required for this task. If you can include info on that in an answer, it will certainly make the answer more universal for everyone, and if I could give "extra credit" for such an answer I would, lol. I only need to compare to one location, but if that location check was done using a function, it could be called repeatedly in a loop, which could potentially be useful. $\endgroup$
    – Mentalist
    Nov 17, 2020 at 9:16

1 Answer 1

11
$\begingroup$

Following a discussion in comments, there may be a point to consider: what does distance to edge means.

My first though was: the shortest distance to any point along the edge.

But you would prefer the distance as: the distance to the center point of the edge.

So two solutions below:

shortest distance to any point along the edge

A possible way is to use a BVHTree.

This tree usually queries for faces using find_nearest.

But we are looking here for edges and in consequence we can't use it directly (nearest face does not imply nearest edge and some edges may have no linked face).

The trick is to make polygons from edges and give it to the tree using FromPolygons to build the tree.

This is done below looping over edges and make a triangle from its two vertices.

import bpy
from mathutils import Vector
from mathutils.bvhtree import BVHTree

# Get the object and its mesh
obj = bpy.context.object
mesh = obj.data
matrix = obj.matrix_world

# Get vertices locations
vertices = [matrix @ v.co for v in mesh.vertices]
# Construct polygons from edges
polygons = [(e.vertices[0], e.vertices[1], e.vertices[0]) for e in mesh.edges]

# Create a BVH Tree from it
tree = BVHTree.FromPolygons( vertices, polygons, all_triangles = True )

# Search for a location
location = Vector( (0, 1, 1) )

# Query the tree
found_location, normal, index, distance = tree.find_nearest( location )

print( index )

Building the tree has a cost and generally we use it if several searches on the same tree. But as I tested it BVH is faster than direct calculation.

So it seems to be better to use a BVH tree.

Here is the code for min distance/index from a point (just for information: don't use it):

# Min distance calculation
def search_min_dist( mesh, location ):
    min_dist = None
    min_index = None
    for index, edge in enumerate(mesh.edges):
        e1 = mesh.vertices[edge.vertices[0]].co
        e2 = mesh.vertices[edge.vertices[1]].co
        length_squared = (e1 - e2).length_squared
        if length_squared == 0.0:
            # if edge is in fact one point
            d = (location - e1).length_squared
        else:
            # parametric projection on e1 e2
            p = (location - e1).dot(e2 - e1) / length_squared
            if p > 1:
                # if above e2
                projected = e2
            elif p < 0:
                # if before e1
                projected = e1
            else:
                # in between
                projected = e1 + p * (e2-e1)
            d = (location - projected).length_squared
        if min_dist is None or d < min_dist:
            min_dist = d
            min_index = index
    return min_index, sqrt(min_dist)

the distance to the center point of the edge

We can also use two approaches: using a Blender utility or direct calculation.

I've tested both and as this is equivalent in runtime, I give here a solution using Blender mathutils class KDTree.

KDTree is to work on points/locations in order to give nearest elements.

For our problem these points are the center of the segments.

So we can:

import bpy
import time
from math import sqrt
from mathutils import Vector
from mathutils.kdtree import KDTree

def search_min_dist_kd( obj, location ):
    mesh = obj.data
    matrix = obj.matrix_world
    # Get vertices locations
    vertices = [matrix @ v.co for v in mesh.vertices]

    #Create the kd tree     
    kd = KDTree(len(vertices))
    for e in mesh.edges:
        i1 = e.vertices[0]
        i2 = e.vertices[1]
        median = (vertices[i1] + vertices[i2]) / 2.0
        #populate it
        kd.insert(median, e.index)
    #initialize it
    kd.balance()

    #get closest median point    
    found_location, index, distance = kd.find(location)
    return index, distance
$\endgroup$
10
  • $\begingroup$ This is great! I was able to modify the code of your BVH tree solution to print the index of the edge nearest each empty, in a series of empties. Here's the .blend There's something I still don't understand - if each edge's location is the midpoint between 2 verts, but with a BVH tree triangles are created, does that mean the median point of those 3 verts is not the same as that of the edge's 2 verts? Looking at polygons and trying to visualize in my mind what's happening, I began to wonder about this. Could you plz explain it to me? $\endgroup$
    – Mentalist
    Nov 17, 2020 at 20:13
  • $\begingroup$ To clarify what I mean about the vert count - imagine you're holding 2 marbles in your left hand (representing e.vertices[0] twice), and 1 in your right (representing e.vertices[1]). They form an imaginary triangle in space if you connect their lines, even if it's a really stretched out triangle. But since there are 2 marbles in your left hand, the average location of the 3 will weigh left, due to there being more marbles (verts) there. Based on this analogy, am I correctly understanding what is happening in your code? $\endgroup$
    – Mentalist
    Nov 18, 2020 at 1:30
  • $\begingroup$ The tree tests the face, regardless of its shape, it seems. So if the face is a flat triangle, I think the distance to the face is the same as the distance to the initial edge. $\endgroup$
    – lemon
    Nov 18, 2020 at 7:14
  • $\begingroup$ @Mentalist, i have edited the question to add the use of matrix_world of the object. As you are talking about empties (external objects) you may need to take into account the mesh object transforms. $\endgroup$
    – lemon
    Nov 18, 2020 at 8:02
  • $\begingroup$ also I gave a look at your code for several empties. In this case, you should build the tree once and loop on the empty for find_nearest only $\endgroup$
    – lemon
    Nov 18, 2020 at 8:10

You must log in to answer this question.

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