[maxscript] KDTree. Can we make it faster?


#61

I agree if it was just a single raycast, but it is loop.
And If I remember correctly someone from AD claimed that consecutive ray intersections now should be much faster since new kd-tree was implemented. Why they decided not to give any control over it to third-party developers remains unknown. Or maybe it’s just not documented yet.
Another test. Now it’s also using RayMeshGridIntersect on teapot with 100 segments. Clean 2020 max with no updates installed.

Time: 0.058sec. Mem: 264612L – Embree
Time: 1.598sec. Mem: 212L – RayMeshGridIntersect
Time: 76.975sec. Mem: 28104L – IntersectRay

another test
g = (dotNetClass "Autodesk.Max.GlobalInterface").Instance
obj = g.animatable.getanimbyhandle (getHandleByAnim tri)

-- .<System.Boolean> IntersectRay  <System.Int32>t <Autodesk.Max.IRay>r <System.Single&>at <Autodesk.Max.IPoint3>norm
objIntersectRay = obj.IntersectRay
hit_normal = g.point3.create()
dist = 0.0
fn MakeRayNative pos dir tm =
(
	_pos = pos * tm
	_dir = dir * tm
	
	g.ray.create (g.point3.create _pos.x _pos.y _pos.z) (g.point3.create _dir.x _dir.y _dir.z)
)

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 = objIntersectRay 0 (MakeRayNative ray_pos -z_axis tea_itm) dist hit_normal		
)
format "Time: %sec. Mem: %\n" ((timestamp()-t1)/1000 as float) (hf-heapfree)

Time: 78.969sec. Mem: 600312L – same as mxs IntersectRay. No surprise

For poly it is 5-6x times slower than Embree in a loop of 1000 iterations.
But in general it is actually faster than before for both mesh and poly. For objects it is slower than before

1000 iterations of IntersectRay
x2020
Time: 76.043sec. Mem: 28104L as object
Time: 0.299sec. Mem: 28104L as poly
Time: 0.182sec. Mem: 28104L as mesh

x2014
Time: 9.39sec. Mem: 26624L as object
Time: 36.487sec. Mem: 26624L as poly
Time: 4.432sec. Mem: 26624L as mesh


#62

Serejah -

Your results are very different than mine.

If I add/modify the following in your code:

teapoly = converttomesh (copy tea)

intersection = intersectRay teapoly (ray ray_pos -z_axis) // pass in mesh rather than primitive

and change the loop count to 100000 I get these results:

Time: 2.483sec. Mem: 8595480L - ray_opsRayTraceFaceIntersection
Time: 2.202sec. Mem: -13642243L - intersectray


#63

I don’t really know how to test it properly, but it is great that intesectRay doing its job quite well on so many iterations.
Performance differences could be hardware dependent since embree uses simd intensively and definitely it is also max version dependent.


#64
-- Runtime error: Cannot resolve type: Autodesk.ViperGeometry3D.ViperGeometryOps+FaceRayIntersectionOps

for which version is this code?
what assemblies do we need to load?


#65

And how would you know!? Reading what’s new in Max!
Either they don’t know or don’t want to tell us. Or both, chose!

I have always glorify Max documentation but some day started discovering most interesting thing in Max, UVW mapping on primitives.
That is uvW mapping! All coordinate spaces, all mappings, all transforms from basic starting mapping…
And very interactive!
Although loosing some interactivity with newer versions…

You could probably get some info from that, there are differences in mapping when turning between those 3.


#66

Works in 2020, but not in 2017.
It requires ViperGeometry3D.dll and I don’t know when it was first added to max.


#67

That’s why I have “cannot resolve…” for 2016.