[maxscript] KDTree. Can we make it faster?


this is what i would do …
I would make an assembly to convert IMesh or system.single[] to IArray . Everything else will be slow anyway I guess


Kinda works, but I hate the fact that I have to compile here and there for every little thing

Time: 0.02sec. Mem: 3688L – for converting 9167 point3 to vec3 array

global MemUtils =
	source = "using System;\n"
	source += "using System.Runtime.InteropServices;\n"
	source += "class MemUtils\n"
	source += "{\n"
	source += "
	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;
	source += "}\n"

	csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
	compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
	compilerParams.GenerateInMemory = on
	compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(source)
	compilerResults.CompiledAssembly.CreateInstance "MemUtils"

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

tri = (createInstance Teapot).mesh
v   = g.executescript (g.stringstream.create "::tri") true
vts = v.ToMesh.Verts
base   = (vts.item 0).INativeObject__Handle

teapot_vec3 = UnmananagedArray2Struct base tri.numverts (dotNetClass "microsoft.xna.framework.vector3")


This is not for a little thing. It can be a part of MXS_Octree (or some Quick_Verts) structure with another helpful methods


You make make IArray at once…

It would also be better to pass an MXS point3 array instead of a mesh. In case you want to have a special list of points, not just all vertices.


Yes, it definitely should be created inside same function

btw. Geometry3D library also contains a wrapper for Embree, but it uses old embree version so it doesn’t support node transform. All ray intersections happen in local space which is sad


Yeah, it would be great to support lots of various point sources. With trimeshes you can use getHandleByAnim which is pretty convenient to get the IMesh on c# side.
Wish someone could show me how to get access to raw Point3 values of mxs array. I did a lot of attempts, but never succeed.


not a big deal… you can easily convert rays in coodsys you need


we can convert point3 array to flat array of floats… this might be easier


hmm… doesn’t work for me:
– Unknown property: “INativeObject__Handle” in dotNetObject:Autodesk.Max.Wrappers.Point3


It must be NativePointer, it was renamed after 2014 version

Available in 3ds Max 2018.2 Update and higher: Some native MAXScript types are converted into .NET arrays, as some .NET libraries do not support these types natively. Point2, Point3, Point4, Quat, EulerAngles, and Matrix3 types are all converted into float[] or double[] arrays.

Newer versions already can do it out of the box. This is great, but I’d still prefer a method that would fit most max versions, 2014+.
Can’t think of a way how to convert mxs point3 array to flat float array efficiently.

Just realized that Point3 arrays could be passed like this.

	arr = #([1,2,3],[4,5,6],[7,8,9])
	v   = g.executescript (g.stringstream.create "::arr") true
	fp  = g.fpvalue.create()
	v.tofpvalue fp

	for i=0 to 2 do
		pt = fp.PTab.Item (dotNetObject "System.IntPtr" i)
		format "[%,%,%]\n" pt.x pt.y pt.z



it might be slow


Yes. Unfortunately, points aren’t located next to each other in memory so UnmananagedArray2Struct returns garbage.


i’m thinking about the passing a “single[]”

	delete objects
	s = geosphere segs:100
	addmodifier s (Edit_Poly())

	ii = #()
	for k=1 to numpoints s do 
		p = getpointpos s k
		for i=1 to 3 do append ii p[i]  
	vv = dotnet.valuetodotnetobject ii (dotnetclass "single[]")

looks pretty reasonable by performance …

we can do array of doubles if it’s better

			list = createGenericList "microsoft.xna.framework.vector3"
			vv = for p in pp collect (as_vec3 p)
			vec3_arr = dotnet.valuetodotnetobject vv (dotnetclass "microsoft.xna.framework.vector3[]")
			list.addrange vec3_arr

this is not bad …


One nitpick so far:

 ia_methods = ia_type.getmethods() -- [ 67 ] >> .create that takes list<t> as a parameter

Relying on the index number is not stable. I’m using max 2020 (I saw you were using 2016) and apparently the index is 75 in the associated .NET version.

Came up with this instead

	fn findEnumerableCreateMethod methods = (
	for i = 1 to ia_methods.count do (
		if methods[i].name != "Create" then continue
		local methodParams = methods[i].GetParameters()
		if (methodParams.count == 1 and 
			methodParams[1].ParameterType.ToString() == "System.Collections.Generic.IEnumerable`1[T]") then
			return methods[i]	
	return undefined


As for this, I was involved in a discussion on the Autodesk forum about a similar thing - actually the same problem that brought me to this thread. I did not get the example code provided by the answerer to work, but it may help you to look: https://forums.autodesk.com/t5/3ds-max-programming/when-communicating-between-maxscript-and-net-how-can-i-detect-a/m-p/10226106/highlight/true#M27258

Unfortunately, points aren’t located next to each other in memory so UnmananagedArray2Struct returns garbage.

Considering this - could it be because the array in this case is generated being grown iteratively? What if you allocate the whole array at once, then fill it in instead? I.e., instead of pts = for i=1 to txt.numverts collect getvert txt i try

pts = #()
pts[txt.numverts] = [0.0,0.0,0.0]
for i = 1 to txt.numverts do pts[i] = getvert txt i

Not familiar enough with the internals to know whether these are equivalent, sorry.

global AutodeskOctree
	struct AutodeskOctreeStruct
		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",
		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

delete objects

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 …


Great refactoring, Denis.
Thousand of queries for a quarter of a second is quite impressive result compared to the mxs kd-tree :wink:

closest:(19164 >> 19164) time:242 heap:-6982468L

Had to move dotnet.loadassembly to the top of the struct to make it work in 2014.

struct AutodeskOctreeStruct
		used_assemblies = #( dotnet.loadassembly @"C:\Program Files\Autodesk\3ds Max 2016\geometry3d.dll",
				     dotnet.loadassembly @"C:\Program Files\Autodesk\3ds Max 2016\immutablearray.dll",
				     dotnet.loadassembly @"C:\Program Files\Autodesk\3ds Max 2016\monogame.framework.dll"
		object_class = dotnetobject "system.object",
                vec3_class   = dotnetclass "microsoft.xna.framework.vector3",

btw there’re some other useful methods available in octree class


… 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


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