I have a very simple function I am using to find the closest object vertex in a specified array to a particular point in space. In the course of my script, this function is called repeatedly, and I would like to make it faster if possible.
I have done a bunch of looking around on here and I understand the basic concept behind using a voxel grid, but the specific implementations posted are maybe a bit more complex than what I am looking for, and a bit too far over my head for me to easily break down.
If I am interpreting correctly, there is no real way to make a single instance go faster, but by pre-dividing the vertices into blocks, you can limit the vertices which are checked in each iteration. I’m sure I could even write something up that would do this myself, but since I am looking for the /best/ solution (the one that will save the most overall time in the long run), I thought I would ask here. How do I decide what number of blocks I want to divide the vertices into? And then, what is the most efficient way to check for the blocks in proximity of the specified point?
The following is the simple function I am currently using. What additions or changes should I make in order to speed up this process, assuming the function will be called hundreds of times?
fn getClosestVert obj p vArray:#{} = (
-- Purpose: Get the closest vertex in a set to the specified point
local cv, cd = 1e9
for v in vArray do (
vPos = case (classOf obj) of (
editable_Mesh: getVert obj v
editable_Poly: polyOp_GetVert obj v
polyMeshObject: polyOp_GetVert obj v
)
d = distance vPos p
if d < cd do (cv = v; cd = d)
)
#(cv, cd) -- return ID and distance of closest vertex in array
)
first of all you should move “case” out of loop…
You know, it’s funny you say that. That actually occurred to me like a few minutes after I posted. Unfortunately, it made no discernible difference in speed.
it doesn’t matter. every code must be perfect.
so… your algorithm is not fast enough for your task. ok. now tell us a little about the task.
why?
because there are two different scenarios:
#1 find a closest point in a point cloud to a specified point: (with your algorithm it should take about 0.02 sec for 10K cloud)
#2 find a closest points of two point clouds: (with your algorithm it might take 0.02X10000 = 200 sec)
what is your scenario?
This is around 1.9 times faster and uses almost the same memory:
fn getClosestVert obj p vArray:#{} = (
local cv, cd = 1e9
obj = snapshotasmesh obj
for v in vArray do
(
d = distance (getVert obj v) p
if d < cd do (cv = v; cd = d)
)
delete obj
#(cv, cd)
)
– time:2324 ram:2552L verts:1240054
– time:1201 ram:2704L verts:1240054
this is almost the same number i guested… 0.013 sec for 10K cloud…
but it seems like we are talking about scenario #2 where 0.013X10000 = 130 sec
this is a practical task of scenario #2:
- transfer skin weights from one mesh to another
the most obvious solution is to do it by finding a closest pair of verts…
i’m going in my archive – 2003…
we had those days a budget for characters as 10K
in 2003 my algorithm made this mapping in ~20 seconds. today it’s 8 secs (just because machines are much faster now).
today i have new algorithm and c++ realization… it takes 0.2 sec for 10Kx10K clouds
but… let’s look at my 2003 algorithm
#1 put both point clouds in a array of structs (index, position)
#2 sort both of them in Z direction
#3 using qsearch (half cut) find the closest pair
today it’s ~8 secs vs ~130 secs of the algorithm showed above
The previous function with an small change is around 2.4 times faster than the source:
fn getClosestVert obj p vArray:#{} =
(
local cv, cd = 1e9
obj = snapshotasmesh obj
for v in vArray where distance (getVert obj v) p < cd do
(
cv = v
cd = distance (getVert obj v) p
)
delete obj
#(cv, cd)
)
– time:2325 ram:2552L verts:1240054
– time:967 ram:2704L verts:1240054
I’m actually just using scenario #1. The main issue is that, in my test scene for example, I end up calling it several times in a row as part of a larger function, which itself is executed hundreds of times consecutively on a button click, on a test mesh with ~5200 verts. So it’s not that the function was taking a long time, but rather that every little bit adds up over a large number of iterations.
I’m currently trying to figure out some other ways to increase the efficiency of the larger function, though that is a discussion for another thread.
Getting back to your original question, I think 2.4 times faster optimization for this very simple function isn’t bad.
Here is a different approach, which in worst case scenario is pretty much the same as my previous function but in best case scenario it can be about 10 times faster.
I assumed the variable “p” is an arbitrary point. If it is the position of another vertex in the object, then the algorithm could be different.
fn getClosestVert obj p vArray:#{} =
(
local cv
local obj = snapshotasmesh obj
local lastvert = obj.numverts + 1
setnumverts obj lastvert true
setvert obj lastvert p
local cd = meshop.minvertexdistancefrom obj lastvert vArray
for v in vArray where distance (getvert obj v) p == cd do exit with cv = v
delete obj
#(cv, cd)
)
PD: minvertexdistancefrom() would have been much more useful if it would take an arbitrary point instead of a vertex index and if it returned both closest position and vertex index.
The only way I see to make this much faster is with the SDK, not C#.
it’s not very new i showed the idea on this forum http://forums.cgsociety.org/newreply.php?do=newreply&p=7032014
for big meshes 3d grid needs a lot of memory… it’s fast but very expensive for mxs. with c++ everything becomes much cheaper.
another problem in mxs is using of arrays and bitarrays. they are much slower than c++ sdk values.