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

just kd-tree needs to be written right …

Let’s look at these numbers … We have a model size that is quite normal for current tasks (~ 100K vert). To find the 20 closest neighbors, you need to spend ~1 s. Where 20 verts is a normal amount for soft-selection, for example. Can we live with this? Probably not.

Agreed. Did you spot a bug in the k-D tree implementation, @denisT? With the bottleneck, so far, being mostly due to the environment I am not sure where to start with finding or writing a better option.

this one works better

(
	
struct AutodeskOctree
(
	Points,
	IArray,
	Octree,
	
	fn MakeListOfType type_name = 
	(
		local genericType = dotnet.GetType "System.Collections.Generic.List`1"
		local innerType   = dotnet.GetType type_name
		local specificType = genericType.MakeGenericType #(innerType)

		(dotnetclass "System.Activator").CreateInstance specificType
	),
	
	vec3_class,
	
	fn AsVec3 vec = dotNetObject vec3_class vec.x vec.y vec.z,
		
	fn OctreeFromPoints pts =
	(
		local lst = MakeListOfType "microsoft.xna.framework.vector3"
		local ListAdd = lst.add
		for p in pts do ListAdd (dotNetObject vec3_class p.x p.y p.z)

		local ia = dotnet.GetType (dotNetClass "autodesk.sequences.immutablearray")
		local method = (ia.GetMethods())[ 67 ] -- .Create that takes List<T> as a parameter
		local vec_type = dotNet.getType vec3_class
		local meth = method.makegenericmethod (dotNet.ValueToDotNetObject #( vec_type ) (dotNetClass "system.type[]"))
		
		-- 'IArray<Vector3>'
		IArray = meth.invoke (dotNetObject "system.object") (dotNet.ValueToDotNetObject #(lst) (dotNetClass "system.object[]"))

		Octree = dotNetObject "autodesk.geometry3d.vertexoctree" IArray

		if Octree != undefined do 
		(
			Points = pts
			Octree
		)
		
	),
	
	fn FindClosest pt =
	(
		index = Octree.FindClosestPoint (dotNetObject vec3_class pt.x pt.y pt.z)
		if index < 0 then undefined else Points[ index + 1 ]
	),
	
	on create do
	(
		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"

		vec3_class = dotnetclass "microsoft.xna.framework.vector3"
	)	
)



delete objects
gc()

txt = Text text:"MAXS\r\ncript"
addModifier txt (subdivide())
txt.modifiers[1].size = (distance txt.max txt.min) / 250.0

pts = for i=1 to txt.numverts collect getvert txt i

t1=timestamp();hf = heapfree

oc = AutodeskOctree()
format "1 Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)

oc.OctreeFromPoints pts

format "2 Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)

delete helpers
::h1 = point centermarker:on cross:off wirecolor:red
::h2 = point pos:txt.center centermarker:off cross:true wirecolor:green isSelected:true

deleteAllChangeHandlers id:#xxx
when transform h2 changes id:#xxx val do
(
	t1=timestamp();hf = heapfree

	n = oc.FindClosest ::h2.pos
	
	format "Lookup: Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)
	::h1.pos = n
)

)

--dotNetObject "microsoft.xna.framework.vector3" 1 2 3

--  make it in advance and put to the struct:
vec3_class = dotnetclass "microsoft.xna.framework.vector3" 

dotnetobject vec3_class x y z

Nice, thanks!
8x faster with no effort.

updated the code in previous post

Wonder if it is possible to skip maxscript loop over points at all and somehow cast mesh verts array (from c# IMesh) to Xna.Vector3 array. It should be way faster.

As we can see the only problem is the casting mxs point3 to Vector3 and add the value to List.

And it’s the only problem. All other looks good enough to play with.

For some unknown reason max doesn’t allow to make a IntPtr to the first mesh vert from maxscript.
When I do it from compiled c# dll it works nicely, but I’d love not to compile a thing if it is possible.
ImmutableArray can be created from arrays as well, so probably we can copy whole IPoint3 memory block and use it to make Vec3 array. But how do we add the first point?

g   = (dotNetClass "Autodesk.Max.GlobalInterface").Instance
tri = (createInstance box).mesh
v   = g.executescript (g.stringstream.create "::tri") true
vts = v.ToMesh.Verts

base   = (vts.item 0).INativeObject__Handle  -- max 2014
offset = 12 -- 3 * 4 bytes to skip first Point3 entirely
floats = dotNetObject "system.single[]" (vts.Count * 3)
m = (dotNetClass "System.Runtime.InteropServices.Marshal")
m.copy (dotNetObject "System.IntPtr" (base + offset)) floats 0 (vts.Count * 3) 

for i = 0 to 20 by 3 do format "%: [%,%,%] - %\n" (1 + ((i+3)/3)) (floats.get i) (floats.get (i+1)) (floats.get (i+2)) (getvert tri (1 + (i+3)/3))

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.ReferencedAssemblies.Add("System.dll");
	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")