1

I want to find all vertices that have distance smaller than 0.0003 and return them as a list. I use the following algorithm but is quite slow for a big scene. Do you have any tips on improving the speed?

listOfAllMesh = cmds.ls(geometry=True,type="mesh")
overlapping = []
for meshToCek in listOfAllMesh:
    listOFVertex=[]
    cmds.select(meshToCek)
    mel.eval("ConvertSelectionToVertices")
    AllVertexes = cmds.ls(selection=True, flatten=True)
    listOFVertex.append(AllVertexes[0])
    Flag=False
    for VertexToCek in AllVertexes[1:]:
        c1=cmds.xform(VertexToCek, q=True, os=True, a=True, t=True)
        for cek in listOFVertex:
            c2=cmds.xform(cek, q=True, os=True, a=True, t=True)
            distance = math.sqrt(math.pow(c2[0] - c1[0], 2) + math.pow(c2[1] - c1[1], 2) + math.pow(c2[2] - c1[2], 2))
            if distance<0.0003:
                overlapping.append(VertexToCek)
                overlapping.append(cek)
                Flag=True
        if not Flag:
            listOFVertex.append(VertexToCek)
            Flag=False
return overlapping
jhoepken
  • 1,842
  • 3
  • 17
  • 24
Antonio
  • 13
  • 3
  • You could first check if the bounding boxes even intersect. You shouldn't have intersecting vertices if the bounding boxes don't intersect – UnholySheep Oct 26 '16 at 11:16

2 Answers2

2

I hope I understand it correctly that you're trying to test an object's vertices against itself!

A few things I can think of that may be slowing down your code:

xform will likely be a slower way to get a point's position.

distance = math.sqrt(math.pow(c2[0] - c1[0], 2) + math.pow(c2[1] - c1[1], 2) + math.pow(c2[2] - c1[2], 2)) This may be another culprit. Usually when calculating distances, it's the square root that will slow it down. One way to get around it would be to calculate the squared distance instead, so you avoid having to use math.sqrt at all.

cmds.select(meshToCek)
mel.eval("ConvertSelectionToVertices")

This probably doesn't slow it down much but to get the vertices in memory may be better.

I tried doing a mostly strictly maya api approach, and the performance seems better. Maybe there's a better way to optimize, but we got some progress here!

import maya.cmds as cmds
import maya.OpenMaya as OpenMaya


def mfn_mesh_generator():
    selection_list = OpenMaya.MSelectionList()
    for mesh in cmds.ls(l=True, geometry=True,type="mesh"):
        selection_list.add(mesh)

    for i in range(selection_list.length()):    
        dag_path = OpenMaya.MDagPath()
        selection_list.getDagPath(i, dag_path)
        print dag_path.fullPathName()

        mfn_mesh = OpenMaya.MFnMesh(dag_path)
        yield mfn_mesh


def get_overlapping_vertices(mfn_mesh, threshold=0.0003):
    points_list = OpenMaya.MPointArray()
    mfn_mesh.getPoints(points_list, OpenMaya.MSpace.kWorld)

    overlapping = []

    for i in range(points_list.length()):
        for j in range(points_list.length()):
            if i == j:
                continue

            dist = points_list[i].distanceTo(points_list[j])
            if dist < threshold:
                if i not in overlapping:
                    overlapping.append(i)

                if j not in overlapping:
                    overlapping.append(j)

    return overlapping


for mfn_mesh in mfn_mesh_generator():
    get_overlapping_vertices(mfn_mesh)

mfn_mesh_generator is a python generator that you can loop through all MFnMesh objects in the scene. Feel free to change this if you want to collect your meshes in another way (I only did it this way to separate things out and to make it more generic). Luckily the api's MPoint object has a method, distanceTo, to calculate the distance of another MPoint! Also MFnMesh has a method to get all vertices in one swoop with getPoints. This optimizes it a bit than getting them one by one.

With a scene of 5 poly spheres, it came to about 0.667850017548 seconds. The same scene with your method comes out to about 12.1129710674 seconds. A pretty decent boost in speed!

Hope that helps out and gives you some ideas.

Green Cell
  • 4,677
  • 2
  • 18
  • 49
  • Most of the time it works but i get this error: # Error: RuntimeError: file S:\Maya_2017_DI\build\Release\runTime\Python\Lib\site-packages\maya\OpenMaya.py line 6049: (kInvalidParameter): Object is incompatible with this method #.Any suggestions? – Antonio Oct 27 '16 at 14:13
  • Can you narrow down what object that is causing that? Maybe it's grabbing an object that `MFnMesh` doesn't support. I have a feeling there's some invalid object when using `cmds.ls(l=True, geometry=True,type="mesh")` – Green Cell Oct 27 '16 at 15:29
  • I updated the code so it will print the name of the object before running `mfn_mesh_generator`. Hopefully that will catch the object it errors on. – Green Cell Oct 27 '16 at 15:40
  • The problem was with geometry=True,now it works.But its still slow,for 228 784 vertexes it takes about 268 seconds and i need it for full scenes with millions of vertexes.I thought not to check all of the vertexes in the mesh but i don't know witch one to eliminate.Any suggestions? – Antonio Oct 28 '16 at 09:13
  • I think the fact that there's a loop with a nested loop to get every other vert is what's really slowing it down. In fact just trying to access `points_list` slows it down. With the amount of vertices you're doing this may not be the best approach. One thing I can think on the top of my head is to use `threading`. Right now objects are being executed one by one in Maya's main thread so they're in a "queue" to be processed. With threading you can try to process many meshes at the same time, hopefully cutting time down significantly. – Green Cell Oct 28 '16 at 10:40
  • Another idea: Try to separate the mesh into a series of bounding boxes, then sort what vertices belong to what box. After that you can loop through the vertices that belong to the same bounding box, instead of looping through the whole mesh. – Green Cell Oct 28 '16 at 10:49
0

@UnholySheep`s bb intersect checking should be the first step, but there are two topics in your question:

  • the first would be to find all vertices position, fast in python api in maya
  • the second one is comparing the distance between N points, really fast with numpy

for the second step i would recommend writing your own C module which can call in python. create a sandbox maya scene and measure the time by different methods

run_t = timeit.default_timer()
test_find_all_vertices_method_a()
print(timeit.default_timer() - run_t)

run_t = timeit.default_timer()
test_find_all_vertices_method_b()
print(timeit.default_timer() - run_t)
Community
  • 1
  • 1
Ari Gold
  • 1,528
  • 11
  • 18