[maxscript] KDTree. Can we make it faster?


#41

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


#42

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!


#43

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.


#44

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 :slight_smile:


#45
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.


#46

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.

#47
  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())
  1. First time loading probably includes assemblies loading time…

#48

I do convert to TriMesh Object, but for GeomObject I should be able just simply cast. But I don’t know how to do it in MXS dotnet


#49

After a few restarts I see no slowdowns on the first start and it is strange. I remember it was and issue long ago and is probably related to JIT

Can you give an example of GeomObject? I’ll try to find a way to convert it
Ok, nevermind.

g.animatable.getanimbyhandle (asuptr (gethandlebyanim (createInstance teapot)))
–> dotNetObject:Autodesk.Max.Wrappers.GeomObject


#50

I just thought, if you write c# assembly anyway, wouldn’t it be easier to write everything from mxs mesh to vertexoctree?


#51

Well, yes, it makes more sense to implement this whole struct as a c# class and compile it on demand. This way we won’t need to use reflection at all and it should make things work a little bit faster.
I already did this kind of thing for geometry3sharp library. It has a lot more useful things inside.


#52
fn make_mxs_wrappers_assembly = 
(	
	source = @"
		using System;
		using System.Collections.Generic;
		using System.Runtime.InteropServices;
		using Autodesk.Geometry3D;
		using Microsoft.Xna.Framework;
		using Autodesk.Max;
		using Autodesk.Max.Wrappers;
		using Autodesk.Sequences;

		namespace MxsWrappers
		{
			public class Methods
			{
				private static readonly IGlobal Global = Autodesk.Max.GlobalInterface.Instance;

				public static object GetIMesh(IntPtr mesh_pointer) 
				{ 
					var mesh = (Mesh)CustomMarshalerMesh.GetInstance(string.Empty).MarshalNativeToManaged(mesh_pointer);
					return mesh;
				}
				public static object GetIPoint3(IntPtr point3_pointer) 
				{ 
					var p = (Point3)CustomMarshalerPoint3.GetInstance(string.Empty).MarshalNativeToManaged(point3_pointer);
					return p;
				}
				public static object GetVector3(IntPtr point3_pointer) 
				{ 
					var p = (Point3)CustomMarshalerPoint3.GetInstance(string.Empty).MarshalNativeToManaged(point3_pointer);
					return new Vector3(p.X, p.Y, p.Z);
				}
				public static Octree BuildOctree(Mesh mesh)
				{
					var vecs = new List<Vector3>();
					foreach (var p in mesh.Verts) vecs.Add(new Vector3(p.X, p.Y, p.Z));

					var data = ImmutableArray.ToIArray(vecs);
					return new VertexOctree(data);
				}
				public static Octree BuildOctree(IntPtr mesh_pointer)
				{
					var mesh = (Mesh)CustomMarshalerMesh.GetInstance(null).MarshalNativeToManaged(mesh_pointer);
					return BuildOctree(mesh);
				}
			}
		}"
		
	csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
	compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
	
	compilerParams.ReferencedAssemblies.AddRange \
		#(
			"System.dll",
			getdir #maxroot 	+ @"\Autodesk.Max.dll", 
			getdir #assemblies 	+ @"\Autodesk.Max.Wrappers.dll",
			getdir #maxroot 	+ @"\Geometry3D.dll",
			getdir #maxroot 	+ @"\ImmutableArray.dll",
			getdir #maxroot 	+ @"\Monogame.Framework.dll"			
		)
		
	compilerParams.GenerateInMemory = on
	compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(source)
	
	dotnetclass (compilerResults.CompiledAssembly.GetType "MxsWrappers.Methods")
)

c = make_mxs_wrappers_assembly()
oc = c.BuildOctree $.mesh

/*
c.GetIMesh $.mesh
c.GetIPoint3 [1,1,1]
c.GetVector3 [1,1,1]

pt = oc.FindClosestPoint (c.GetVector3 (getvert $.mesh 100))
pts = oc.FindNClosestPoints (c.GetVector3 (getvert $.mesh 100)) 20
*/

#53

Wow, now it is so mush less code :slight_smile:
I see that you found that post of Swordslayer about passing mxs values by their names. Do you know in which max version it was first added? Code works in 2016 max, but I don’t have 2015 to test

It isn’t very convenient to pass several args of the same type but it is doable.

public static object[] GetVector3Array(IntPtr[] point3_pointer) 
{ 	
	object[] vectors = new object[ point3_pointer.Length ];
	for(int i=0; i < point3_pointer.Length; i++ )
	{
		var p = (Point3)CustomMarshalerPoint3.GetInstance(string.Empty).MarshalNativeToManaged(point3_pointer[i]);
		vectors[i] = new Vector3(p.X, p.Y, p.Z);
	}
	return vectors;	
}

upd.
No matter what I do it leaks memory. Passing large arrays of mxs values to c# is probably not an option

Mem leaks
fn make_mxs_wrappers_assembly = 
(	
	source = @"
		using System;
		using System.Collections.Generic;
		using System.Runtime.InteropServices;
		using Autodesk.Geometry3D;
		using Microsoft.Xna.Framework;
		using Autodesk.Max;
		using Autodesk.Max.Wrappers;
		using Autodesk.Sequences;

		namespace MxsWrappers
		{
			public class Methods
			{
				private static readonly IGlobal Global = Autodesk.Max.GlobalInterface.Instance;
				private static readonly ICustomMarshaler Point3Marshaler = CustomMarshalerPoint3.GetInstance(string.Empty);
	
				public static object GetIMesh(IntPtr mesh_pointer) 
				{ 
					var mesh = (Mesh)CustomMarshalerMesh.GetInstance(string.Empty).MarshalNativeToManaged(mesh_pointer);
					return mesh;
				}
				public static object GetIPoint3(IntPtr point3_pointer) 
				{ 
					var p = (Point3)CustomMarshalerPoint3.GetInstance(string.Empty).MarshalNativeToManaged(point3_pointer);
					return p;
				}
				public static object GetVector3(IntPtr point3_pointer) 
				{ 
					using ( Point3 p = (Point3)Point3Marshaler.MarshalNativeToManaged(point3_pointer) )
					{
						return new Vector3(p.X, p.Y, p.Z);
					}
				}
				public static void GetVector3Array(IntPtr[] point3_pointer, ref Vector3[] vectors) 
				{ 	
					// nothing happens here, but leak still exists
					point3_pointer = null;
					vectors = null;
				}
				public static void SetNull( object val ) 
				{ 	
					val = null;
				}
				public static Octree BuildOctree(Mesh mesh)
				{
					var vecs = new List<Vector3>();
					foreach (var p in mesh.Verts) vecs.Add(new Vector3(p.X, p.Y, p.Z));

					var data = ImmutableArray.ToIArray(vecs);
					return new VertexOctree(data);
				}
				public static Octree BuildOctree(IntPtr mesh_pointer)
				{
					var mesh = (Mesh)CustomMarshalerMesh.GetInstance(null).MarshalNativeToManaged(mesh_pointer);
					return BuildOctree(mesh);
				}
			}
		}"
		
	csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
	compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
	
	compilerParams.ReferencedAssemblies.AddRange \
		#(
			"System.dll",
			getdir #maxroot 	+ @"\Autodesk.Max.dll", 
			getdir #assemblies 	+ @"\Autodesk.Max.Wrappers.dll",
			getdir #maxroot 	+ @"\Geometry3D.dll",
			getdir #maxroot 	+ @"\ImmutableArray.dll",
			getdir #maxroot 	+ @"\Monogame.Framework.dll"			
		)
		
	compilerParams.GenerateInMemory = on
	compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(source)
	
	if (compilerResults.Errors.Count > 0 ) then
	(
		local errs = stringstream ""
		for i = 0 to (compilerResults.Errors.Count-1) do
		(
			local err = compilerResults.Errors.Item[i]
			format "Error:% Line:% Column:% %\n" err.ErrorNumber err.Line err.Column err.ErrorText to:errs
		)
		format "%\n" errs
		
		return undefined
	)
				
	dotnetclass (compilerResults.CompiledAssembly.GetType "MxsWrappers.Methods")
)

if ::c == undefined do
(
	c = make_mxs_wrappers_assembly()
-- 	oc = c.BuildOctree $.mesh
	s = GeoSphere segments:100
	tri = snapshotAsMesh s
	::pts = for i=1 to tri.numverts collect getvert tri i
)
(
	t1=timestamp();hf = heapfree
	
	format "Passing % points to c#\n" pts.count
	vecs = dotNetObject "microsoft.xna.framework.vector3[]" pts.count
	c.GetVector3Array pts vecs -- comment this line to eliminate mem leak. Each run it eats about 7Mb ram
	c.SetNull vecs	
	(dotnetclass "system.gc").collect()
	vecs = undefined
	gc()
	
	format "Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)
)

#54

look what I found :slight_smile:


delete objects
gc()

tea = Teapot()
s   = sphere radius:2 wirecolor:red pos:(2 * tea.radius * normalize [random 0.0 1.0,random 0.0 1.0,random 0.0 1.0])
rotate tea (EulerAngles (random 0 360) (random 0 360) (random 0 360))
tri = tea.mesh
wrapper = (dotNetClass "Autodesk.Max.MaxPlus.Mesh")._createwrapper tri
p3_wrapper = (dotNetClass "Autodesk.Max.MaxPlus.Point3")._createwrapper (s.pos * inverse tea.objecttransform)
Geometry3D_TriMesh = (dotNetClass "Viper3dsMaxBridge.Converters").ConvertToViperValue wrapper
Geometry3D_Vector3 = (dotNetClass "Viper3dsMaxBridge.Converters").ConvertToViperValue p3_wrapper

octree_ops = dotNetClass "Autodesk.ViperGeometry3D.ViperGeometryOps+OctreeOps"

closest_pt = octree_ops.ClosestPointOnSurface Geometry3D_TriMesh Geometry3D_Vector3
MaxPlus_Point3 = (dotNetClass "Viper3dsMaxBridge.Converters").VectorToPoint closest_pt


pt = [MaxPlus_Point3.x,MaxPlus_Point3.y,MaxPlus_Point3.z]
pt *= tea.objecttransform 
point pos:pt centermarker:on cross:off wirecolor:yellow

#55

what is Viper?


#56

it is the MCG engine


#57

In fact, MCG has a lot of useful things … unlike MCG itself. I have long thought to steal them from there.


#58

Time has come, but AD said that they will abandon MaxPlus, but I hope they won’t remove these mxs to mcg converters

Little embree offtop

1.000 mesh ray intersections time:
Time: 0.052sec. Mem: 345048L – embree
Time: 13.88sec. Mem: 107884L – intersectRay

(
delete objects
gc()

tea = Teapot segments:10
rotate tea (EulerAngles (random 0 33) (random 0 33) (random 0 360))	
tea_itm = inverse tea.objecttransform
tea_tm  = tea.objecttransform
tri = tea.mesh

wrapper = (dotNetClass "Autodesk.Max.MaxPlus.Mesh")._createwrapper tri
Geometry3D_TriMesh = (dotNetClass "Viper3dsMaxBridge.Converters").ConvertToViperValue wrapper

ray_ops = dotNetObject "Autodesk.ViperGeometry3D.ViperGeometryOps+FaceRayIntersectionOps"
ray_scene = ray_ops.RayTraceScene false	
tuple = ray_ops.RayTraceAddGeometry ray_scene Geometry3D_TriMesh


ConvertToViperValue = (dotNetClass "Viper3dsMaxBridge.Converters").ConvertToViperValue
GetRayWrapper = (dotNetClass "Autodesk.Max.MaxPlus.Ray")._createwrapper
	
fn MakeRay pos dir tm =
(
	ConvertToViperValue (GetRayWrapper (ray (pos * tm) (dir * tm)))
)	

t1=timestamp();hf = heapfree

ray_opsRayTraceFaceIntersection = ray_ops.RayTraceFaceIntersection

seed 321321
pts = for i = 1 to 1000 collect
(
	ray_pos = (random tea.min tea.max) * 0.75
	ray_pos.z = 150

	intersection = ray_opsRayTraceFaceIntersection ray_scene (MakeRay ray_pos -z_axis tea_itm)	
	
-- 	if intersection.IsValidHit then [ intersection.HitCoordinates.x, intersection.HitCoordinates.y, intersection.HitCoordinates.z ] * tea_tm else dontCollect
	
)

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

t1=timestamp();hf = heapfree
seed 321321
pts = for i = 1 to 1000 collect
(
	ray_pos = (random tea.min tea.max) * 0.75
	ray_pos.z = 150

	intersection = intersectRay tea (ray ray_pos -z_axis)
	
-- 	if intersection.IsValidHit then [ intersection.HitCoordinates.x, intersection.HitCoordinates.y, intersection.HitCoordinates.z ] * tea_tm else dontCollect
	
)
format "Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)

)

RayIntersect without an actual mesh
#59

MaxPlus Python is deprecated… C# stays as I know


#60

Isn’t this much slower because it has to convert the teapot primitive to a mesh every time? If I do that conversion once using converttomesh and pass that in, it’s 2x slower. Still impressive, but not 17sec vs. 0.05.