[Closed] [maxscript] KDTree. Can we make it faster?

global AutodeskOctree
(
	struct AutodeskOctreeStruct
	(
	private
		object_class = dotnetobject "system.object",
		vec3_class = dotnetclass "microsoft.xna.framework.vector3",	
		vec3_arr_class = dotnetclass "microsoft.xna.framework.vector3[]",
		octree_class = dotnetclass "autodesk.geometry3d.vertexoctree",
		iarray_class = dotnetclass "autodesk.sequences.immutablearray",
	public
		points,
		octree,
		
		fn create_generic_list class = 
		(
			local genericType = dotnet.GetType "System.Collections.Generic.List`1"
			if iskindof (local elementType = dotnet.GetType class) dotnetobject do
			(
				(dotnetclass "System.Activator").CreateInstance (genericType.MakeGenericType #(elementType))
			)
		),

		fn as_vec3 vec = dotnetobject vec3_class vec.x vec.y vec.z,
			
			
		fn create_from_points vecs =
		(
			vec3_arr = dotnet.valuetodotnetobject vecs vec3_arr_class

			method = 
			(
				iarray_type = dotnet.GetType iarray_class
				for m in iarray_type.GetMethods() where m.Name == "ToIArray" and (m.GetParameters())[1].ParameterType.Name == "T[]" do
					exit with (m.MakeGenericMethod #(dotnet.GetType vec3_class))
			)
			vec3_iarray = method.invoke object_class #(vec3_arr)
			
			/*			
			method = 
			(
				vec3_list = create_generic_list vec3_class
				vec3_list.addrange vec3_arr

				iarray_type = dotnet.GetType iarray_class
				for m in iarray_type.GetMethods() where m.Name == "ToIArray" and (m.GetParameters())[1].ParameterType.Name == "List`1" do
					exit with (m.MakeGenericMethod #(dotnet.GetType vec3_class))
			)
			vec3_iarray = method.Invoke object_class #(vec3_list)
			*/		
			
			dotnetobject octree_class vec3_iarray
		),
		
		fn create_from_object obj =	
		(
			vecs = for k=1 to numpoints obj collect as_vec3 (getpointpos obj k)
			create_from_points vecs
		),
		
		fn find_nearest_index p =
		(
			octree.FindClosestPoint (as_vec3 p) + 1
		),
		fn find_nearest_point pt =
		(
			if (i = find_nearest_index p) > 0 do points[i]
		),
		
		on create do
		(
			dotnet.loadassembly @"geometry3d.dll"
			dotnet.loadassembly @"immutablearray.dll"
			dotnet.loadassembly @"monogame.framework.dll"			
		)	
	)
	AutodeskOctree = AutodeskOctreeStruct
	ok
)


delete objects
gc()


s = geosphere segs:100 
addmodifier s (Edit_Poly())
pp = for k=1 to numpoints s collect (getpointpos s k)

_oc = AutodeskOctree()
	
	
(
	format ">>>>>>>>\n"

	t0 = timestamp()
	h0 = heapfree

	if (oc_tree = _oc.create_from_object s) != undefined do 
	(
		_oc.octree = oc_tree
	)
	
	format "\t octree:(%) time:% heap:%\n" (numpoints s) (timestamp() - t0) (h0 - heapfree)
)	

(
	num = 1000
	v = -1
	seed 2
	index = random 1 pp.count
	
	t0 = timestamp()
	h0 = heapfree

	for k=1 to num do
	(
		v = _oc.find_nearest_index pp[index]
	)

	format "\t closest:(% >> %) time:% heap:%\n" index v (timestamp() - t0) (h0 - heapfree)
)

after some improvements, everything works much faster …

… but not use the absolute path. The path has to be common for all versions and relative

Absolutely! It would be nice to access them through the struct methods. It’s also a good idea to add different constructors:

1. from points
2. from mesh
3. from object
4. from nodes
   etc.

Octree initialization time for large point clouds is still an issue. The octree building itself is quick … the problem is converting mxs point3 to vector3

I use absolute path just for the sake of testing in 2014, since these dlls first added in 2016 I guess.

Making IArray from trimesh verts handle is defnintely a way to go for highpoly meshes. It is 10 times faster than making it from the object.

...

fn UnmananagedArray2Struct first_item_handle count =
(
	local mi   = (::MemUtils.gettype()).getmethod "MarshalUnmananagedArray2Struct"
	local meth = mi.makegenericmethod (dotNet.ValueToDotNetObject #( dotNet.getType (dotNetClass "microsoft.xna.framework.vector3") ) (dotNetClass "system.type[]"))
	meth.invoke (dotNetObject "system.object") (dotNet.ValueToDotNetObject #( first_item_handle, count ) (dotNetClass "system.object[]")) asdotnetobject:true
),

fn GetVertsHandleFromTriMesh tri =
(
	global tmp_global_var = tri
	local fpv = g.fpvalue.create()
	g.executemaxscriptscript "::tmp_global_var" true fpv true -- this differs from version to version
	
	local first_vert_handle = (fpv.Msh.verts.item 0).INativeObject__NativePointer
	
	globalVars.remove #tmp_global_var
	gc light:true
	
	first_vert_handle	
),

fn create_from_trimesh tri_mesh =
(
	local handle = GetVertsHandleFromTriMesh tri_mesh
	local vec3_arr = UnmananagedArray2Struct handle tri_mesh.numverts
				
	method = 
	(
		iarray_type = dotnet.GetType iarray_class
		for m in iarray_type.GetMethods() where m.Name == "ToIArray" and (m.GetParameters())[1].ParameterType.Name == "T[]" do
			exit with (m.MakeGenericMethod #(dotnet.GetType vec3_class))
	)
	vec3_iarray = method.invoke object_class #(vec3_arr)
	
	dotnetobject octree_class vec3_iarray
	
)
...

octree:(100002) time:156 heap:-5592L – create_from_trimesh
octree:(100002) time:1721 heap:8574396L – create_from_object

Just to jump in – if your max version is 2018+ you can use the numpy/scipy ckdtree which is super fast:
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html

It is easier if you are 2021+ as you can install numpy & scipy from pip rather than compiling it yourself.

Edit to say it is very cool that you have been able to do this so efficiently in mxs!

Yes, we know Python is an option. But this is not a built-in feature (module), and it makes any tool using additional modules complicated to distribute. Thus, the idea is to avoid additional installations for users.

BTW. I have used numpy / scipy for several tasks and know how efficient it is in many areas that require math and algorithms.

Surely the difference between distributing a maxscript file and a python module is only file size?
You can even write a mxs script to install pip + numpy + scipy locally for each user if there is no means of distribution via a network or server.

As an academic exercise this is very cool, but I figured it would be less effort to distribute num/scipy and much faster performance as it is a c implementation.

Anyways – like I said before, very cool to have done this in mxs

global OctreeClass
(
	struct AutodeskOctreeClassStruct
	(
	private
		assemblies = 
		#(
			dotnet.loadassembly @"geometry3d.dll",
			dotnet.loadassembly @"immutablearray.dll",
			dotnet.loadassembly @"monogame.framework.dll"			
		),
		
		vec3_class = dotnetclass "microsoft.xna.framework.vector3",
		vec3_type = dotnet.gettype vec3_class,
		vec3_arr_class = dotnetclass "microsoft.xna.framework.vector3[]",
		
		pnt3_class = dotnetclass "Autodesk.Max.Wrappers.Point3",
		pnt3_type = dotnet.gettype pnt3_class,
		pnt3_arr_class = dotnetclass "Autodesk.Max.Wrappers.Point3[]",
		
		octree_class = dotnetclass "autodesk.geometry3d.vertexoctree",

		iarray_class = dotnetclass "autodesk.sequences.immutablearray",
		iarray_type = dotnet.gettype iarray_class,

		_global = (dotnetclass "autodesk.max.globalinterface").Instance, 
		_point3_create = _global.Point3.Create, 
		
	public
		points,
		octree,
		
		MemUtilsStruct = 
		(
			struct MemUtilsStruct
			(
			private
				_global = (dotnetclass "autodesk.max.globalinterface").Instance,

				vec3_class = dotnetclass "microsoft.xna.framework.vector3",
				vec3_type = dotnet.gettype vec3_class,

			public 
				fn make_utils_assembly =
				(
					source = @"
						using System;
						using System.Runtime.InteropServices;
						class MemUtils
						{
							public static T[] MarshalUnmananagedArray2Struct<T>(Int64 unmanagedArray, int length )
							{
								var size = Marshal.SizeOf(typeof(T));
								var mangagedArray = new T[length];

								for (int i = 0; i < length; i++)
								{
									IntPtr ins = new IntPtr(unmanagedArray + i * size);
									mangagedArray[i] = Marshal.PtrToStructure<T>(ins);
								}
							
								return mangagedArray;
							}
						}"

					csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
					compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
					
					compilerParams.ReferencedAssemblies.AddRange #("System.dll")
					compilerParams.GenerateInMemory = on
					compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(source)
					compilerResults.CompiledAssembly.CreateInstance "MemUtils"
				),
				
				mem_utils = make_utils_assembly(),
				array_marshal_method = (dotnet.gettype mem_utils).GetMethod "MarshalUnmananagedArray2Struct",
				
				fn get_first_handle arr = 
				(
					(arr.item 0).INativeObject__NativePointer
				),
				
				fn get_vec3_array unmananaged_ptr count =
				(
					method = array_marshal_method.MakeGenericMethod #(vec3_type)
					method.Invoke 0 #(unmananaged_ptr, count) asdotnetobject:true
				),

				fn get_node_imesh node &vertPtr: &count: = if iskindof node GeometryClass do 
				(
					inode = _global.Animatable.GetAnimByHandle (gethandlebyanim node)
					os = inode.EvalWorldState 0 true
					imesh = if os.Obj.ClassID == _global.TriObjectClassID then
					(
						os.Obj.Mesh_
					)
					else if os.Obj.CanConvertToType _global.TriObjectClassID == 1 do
					(
						tri = os.Obj.ConvertToType 0 _global.TriObjectClassID
						tri.Mesh_
					)
					
					if imesh != undefined do
					(
						vertPtr = imesh.Verts.item[0].INativeObject__NativePointer
						count = imesh.NumVerts_
					)
					imesh
				),  
				
				fn get_mesh_verts node = 
				(
					imesh = get_node_imesh node vertPtr:&_ptr count:&_num
					if (imesh != undefined) do
					(
						vec3_arr = get_vec3_array _ptr _num
					)
				),
				
				on create do
				(
				)
			)
		),
		
		mxs_to_net_utils = MemUtilsStruct(),
	
		
		fn as_vec3 p = dotnetobject vec3_class p.x p.y p.z,

		fn create_generic_list class = 
		(
			local genericType = dotnet.GetType "System.Collections.Generic.List`1"
			if iskindof (local elementType = dotnet.GetType class) dotnetobject do
			(
				(dotnetclass "System.Activator").CreateInstance (genericType.MakeGenericType #(elementType))
			)
		),

		fn iarray_create_method type:#array = 
		(
			local typename = if type == #list then "List`1" else "T[]"
				
			local _method = undefined
			for method in iarray_type.GetMethods() while _method == undefined where method.Name == "ToIArray" do 
			(
				local params = method.GetParameters()
				if (params.count > 0 and params[1].ParameterType.Name == typename) do _method = method.MakeGenericMethod #(vec3_type)
			)
			_method
		),

		vec3_iarray_method = iarray_create_method(),
		
		fn create_from_vectors vecs =
		(
			local vec3_arr = dotnet.valuetodotnetobject vecs vec3_arr_class

			local method = iarray_create_method type:#array
			local vec3_iarray = method.invoke 0 #(vec3_arr)

			dotnetobject octree_class vec3_iarray
		),
		
		fn create_from_node node =	
		(
			if (vec3_arr = mxs_to_net_utils.get_mesh_verts node) != undefined do
			(
				vec3_iarray = vec3_iarray_method.invoke 0 #(vec3_arr)
				dotnetobject octree_class vec3_iarray
			)
		),

		fn create_from_object obj =	
		(
			vecs = for k=1 to numpoints obj collect as_vec3 (getpointpos obj k)
			create_from_vectors vecs
		),
		
		fn find_nearest_index p =
		(
			octree.FindClosestPoint (as_vec3 p) + 1
		),
		fn find_nearest_point pt =
		(
			if (i = find_nearest_index p) > 0 do points[i]
		),
		
		on create do
		(
		)	
	)
	global _oc = OctreeClass = AutodeskOctreeClassStruct()
	ok
)


delete objects
gc()

s = geosphere segs:100 
addmodifier s (Edit_Poly())
pp = for k=1 to numpoints s collect (getpointpos s k)	
	
(
	format ">>>>>>>>\n"

	t0 = timestamp()
	h0 = heapfree

	if (oc_tree = _oc.create_from_node s) != undefined do 
	(
		_oc.octree = oc_tree
	)
	
	format "\t octree:(%) time:% heap:%\n" (numpoints s) (timestamp() - t0) (h0 - heapfree)
)	

(
	num = 100
	v = -1
	seed 2
	index = random 1 pp.count
	
	t0 = timestamp()
	h0 = heapfree

	oc_find_nearest_index = _oc.find_nearest_index
	for k=1 to num do
	(
		v = oc_find_nearest_index pp[index]
	)

	format "\t closest:(% >> %) time:% heap:%\n" index v (timestamp() - t0) (h0 - heapfree)
)
	

Am I missing anything?

I haven’t been practicing MAX c# lately, so you can probably clean up some things there.

Nope, all is great except only a few little things

1. EvalWorldState should use current scene time or we could pass it in optional argument
2. Very first run is approximately two times slower than the following runs. Perhaps we can do the first run on a dummy mesh to eliminate this slowdown.

1. EvalWorldState should use current scene time

it should be “current time context” time option… in c++ sdk it’s MAXScript_time()

#define MAXScript_time()
        (thread_local(use_time_context) ? thread_local(current_time) : GetCOREInterface()->GetTime())

2. First time loading probably includes assemblies loading time…