[Closed] Speed up finding closest vertex?

That link doesn’t quite work. Anyway, to contribute a little bit, here’s yet another 3d grid (repurposed and not really tested thoroughly so watch out for subtle bugs):

(
  	struct grid3D
  	(
  		minPos,
  		maxPos,
  		gridUnit,
  		gridData = #(),
  		gridAddress = #(),
  
  		fn build =
  		(
  			local start = [int(minPos/gridUnit).x, int(minPos/gridUnit).y, int(minPos/gridUnit).z]
  			local end = [int(maxPos/gridUnit).x, int(maxPos/gridUnit).y, int(maxPos/gridUnit).z]
  
  			for x = start.x to end.x do
  				for y = start.y to end.y do
  					for z = start.z to end.z do
  					(
  						append gridAddress (getHashValue [x,y,z] 0)
  						append gridData #{}
  					)
  		),
  
  		fn getAddress pos =
  		(
  			pos /= gridUnit
  			[int(pos.x), int(pos.y), int(pos.z)]
  		),
  
  		fn addItem item pos =
  			append gridData[findItem gridAddress (getHashValue (getAddress pos) 0)] item,
  
  		fn reset =
  			gridData = for item in gridAddress collect #{},
  
  		fn getItemsNearPos pos tolerance:1 orig: items:#{} = 
  		(
  			local gridPos = getAddress pos
  
  			for x = gridPos.x - tolerance to gridPos.x + tolerance do
  				for y = gridPos.y - tolerance to gridPos.y + tolerance do
  					for z = gridPos.z - tolerance to gridPos.z + tolerance do
  					(
  						local index = findItem gridAddress (getHashValue [x, y, z] 0)
  						if index > 0 do join items gridData[index]
  					)
  
  			if orig != unsupplied do items[orig] = false
  			if items.isEmpty then getItemsNearPos pos tolerance:(tolerance + 1) orig:orig else items
  		)
  	)
  
  	fn getClosestVert obj pos verts getPos =
  	(
  		local cv, cd = 1e9
  
  		for v in verts do
  		(
  			local d = distance (getPos obj v) pos
  			if d < cd do (cv = v; cd = d)
  		)
  
  		#(cv, cd)
  	)
  
  	local obj = convertToPoly (Teapot segments:28)
  	local verts = obj.verts as bitarray
  	local getVertPos = case (classOf obj) of
  	(
  		editable_Mesh: getVert
  		editable_Poly: polyOp.getVert
  		polyMeshObject: polyOp.getVert
  	)
  
  	local start = timeStamp()
  	local grid = grid3D minPos:obj.min maxPos:obj.max gridUnit:(0.05 * length (obj.max - obj.min))
  	local addItem = grid.addItem
  	grid.build()
  	for v in verts do addItem v (getVertPos obj v)
  	format "Grid init: % ms
" (timeStamp() - start)
  
  	------------------------------------------------
  
  	start = timeStamp()
  	for i = 1 to 100 do
  	(
  		local testVert = random 1 verts.numberSet
  		local pos = getVertPos obj testVert
  		getClosestVert obj pos (grid.getItemsNearPos pos orig:testVert) getVertPos
  	)
  	format "Getting info for 100 vertices: % ms
" (timeStamp() - start)
  )

Of course, the main advantage here is ‘build the grid once, get the info faster later on’.

More on the naive algorithm, without any sorting or acceleration grids:

I gave it a try in c# just for fun, and surprisingly it was around 30 times faster than maxscript, including the time it takes to send the vertex data from maxscript to dotnet.

I expected it to be faster, but not by this much, especially since the distance function in maxscript is implemented in c++.

How do you explain this? Is the MXS bottleneck iterating over the array?

well… this is the method what is now way to bit using mxs only:

fn getClosestMeshVert mesh point:[0,0,0] verts: =
(
	local vert, dist = 1e9
	for v in verts where (d = distance (getvert mesh v) point) < dist do
	(
		vert = v
		dist = d
	)
	#(vert, dist)
)

with redraw off
(
	delete objects 
	s = geosphere segs:100
	gc()
	
	mesh = snapshotasmesh s
	verts = #{1..mesh.numverts}
	
	t1 = timestamp()
	m1 = heapfree
	
	getClosestMeshVert mesh verts:verts
	
	format "verts:% time:% memory:%
" verts.numberset (timestamp() - t1) (m1 - heapfree) 
	free mesh
)

it takes:

verts:100002 time:143 memory:584L

do you want to say that c# can do it 30 times faster?

Unless I’m missing something, seems it can do it more than 100 times faster.

Here’s some messy LINQPad code.

struct Vector3 
{ 
	public float X; 
	public float Y;
	public float Z;
	public Vector3(float x, float y, float z) { X = x; Y = y; Z = z; }
}

float Distance(Vector3 a, Vector3 b) 
{
	float dX = a.X - b.X;
	float dY = a.Y - b.Y;
	float dZ = a.Z - b.Z;
	return (float)Math.Sqrt(dX * dX + dY * dY + dZ * dZ);
}

int GetClosestPoint(List<KeyValuePair<int, Vector3>> verts, Vector3 pos)
{
	float closestD = Single.MaxValue;
	int closestInd = -1;
	foreach (var kvp in verts)
	{
		float d = Distance(pos, kvp.Value);
		if (d < closestD)
		{
			closestD = d;
			closestInd = kvp.Key;
		}
	}
	return closestInd;
	
}

Random r = new Random();

Vector3 RandomPoint() { return new Vector3 ((float)r.NextDouble(), (float)r.NextDouble(), (float)r.NextDouble()); }

void Main()
{
	var verts = new List<KeyValuePair<int, Vector3>>();
	for (int i = 0; i < 100002; i++)
	{
		verts.Add(new KeyValuePair<int, Vector3>(i, RandomPoint()));
	}
	
	Stopwatch sw = Stopwatch.StartNew();
	int x = 0; //so the loop doesn't get optimized away
	for (int i = 0; i < 100; i++)
	{
		x += GetClosestPoint(verts, new Vector3(0,0,0));
	}
	sw.Stop();
	Console.WriteLine(x);
	Console.WriteLine(sw.ElapsedMilliseconds); //126
}

And we can also optimize it more if we want, by removing the Sqrt from the distance function and comparing the distances squared.

If we really have a heavy mesh, we can easily convert the outer loop to a Parallel.For for multithreading it.

here is update… mxs vs sdk

fn getClosestMeshVert mesh point =
(
	local vert, dist = 1e9
	for v=1 to mesh.numverts where (d = distance (getvert mesh v) point) < dist do
	(
		vert = v
		dist = d
	)
	vert
)

/******************* c++ sdk ***********************
def_visible_primitive(getMeshClosestVert, "getMeshClosestVert");
Value* getMeshClosestVert_cf(Value** arg_list, int count)
{
	check_arg_count(getMeshClosestVert, 2, count);
	Mesh* mesh = arg_list[0]->to_mesh();
	Point3 point = arg_list[1]->to_point3();
	float dist = FLT_MAX, d;
	int vert;
	for (int k = 0; k < mesh->numVerts; k++)
	{
		d = (point - mesh->verts[k]).FLength();
		if (d < dist)
		{
			vert = k;
			dist = d;
		}
	}
	return Integer::intern(vert+1);
}
*/

with redraw off
(
	delete objects 
	s = geosphere segs:200
	gc()
	
	mesh = snapshotasmesh s 
	p = getvert mesh 100000
	
	t1 = timestamp()
	m1 = heapfree
	
	v = getClosestMeshVert mesh p
	--v = getMeshClosestVert mesh p
	
	format "% = verts:% time:% memory:%
" v mesh.numverts (timestamp() - t1) (m1 - heapfree) 
	free mesh
)

/*
mxs => 100000 = verts:400002 time:567 memory:7960L
sdk => 100000 = verts:400002 time:4 memory:176L
*/

snapshot time in not included.
both functions do exactly the same… but sdk is >500 times faster

the mxs’s bottleneck is a passing ‘mesh’ to sdk for every time we ask vertex position (getvert)

actually the ‘getvert’ itself is a bottleneck… i’ve checked the source code of this method:
#1 takes first argument
#2 checks is it geometry, node or mesh
#3 casts or converts to mesh
#4 checks that vertex index (second argument) valid
#5 checks existing of other arguments
#6 gets vertex position
#7 defines coordinates system
#8 if the coordinate system is not local transforms position to another coordinates

that’s it …

The main advantage of the c# code over the naive maxscript code is in every vertex of mesh vs every vertex of other mesh type calculations, i.e., many positions with the same vertex set, which is the problem we are trying to solve in the first place.

here is only distance:

fn getClosestMeshVert mesh point =
(
	local vert, dist = 1e9, vp = x_axis
	for v=1 to mesh.numverts do (distance point vp)
	vert
)
/*
undefined = verts:400002 time:363 memory:40591624L
*/

true… it looks too slow for me…
let’s do noting else than loop:

fn getClosestMeshVert mesh point =
(
	local vert, dist = 1e9, vp = x_axis
	for v=1 to mesh.numverts do ()
	vert
)
/*
undefined = verts:400002 time:141 memory:120L
*/  

so now you can see how time is distributed.

In conclusion… MAXScript is inherently a slow language no matter what we do.

	fn MxsIsSlow =
	(
		for v = 1 to 1000000 do ( )
	)

	ts = timestamp()
	MxsIsSlow()
	print (timestamp() -ts) --194

The same code in C++ would take probably less than 0.1ms, even if the loop doesn’t get optimized away by the compiler.

Between the advice posted here and a couple tweaks in my other function, I have a solution that is running ~3.5 times faster than the one I started with (done using only Maxscript).

I’m still wondering if I should consider using a voxel grid, given that I am testing the same mesh against a couple hundred different points at a time.