I’ve been recently working on a script in 3DS Max to stitch vertices in a selection to nearby verts in the scene geometry. I initially was doing the brute force distance checks, but soon realized I needed a much faster/better way of doing it. Mainly because of highpoly/complex scenes.
So I just implemented a Voxel method, using the built in RayMeshGridIntersect() function of max. Using this, I made my script 50% faster, so great! But then a fella on cgTalk that helps me out often, named Dennis said he could do it 2-3x faster than what I had.
He had this post about using 2D Grids, so I’m assuming this is what he meant when he said 2-3x faster.
Does anyone have any ideas/thoughts on this? I’m not sure how to go about doing the 2D Grid… It confuses me somewhat. But it does make sense that it could be faster than a 3D Approach like a Voxel method, but then again it depends how the voxel method is created/used.
DenisT is quite amazing at anything related to scripting :D. Funny enough, I just went through that whole exercise to implement a voxel algorithm in my commercially released Ant Stitcher script (http://75ive.com/tools.html) that does exactly what you are looking for I am still polishing the new version with the 3d voxel algorithm and it’s way way faster.
Basically all you have to do is divide your 2d or 3d space in a grid of boxes (voxels) and build a two dimensional array of those voxels and the verts contained in them. Example: #(#(voxel1,#(vert1, vert2, vert3)),#(voxel2,#(vert4, vert5, vert6))).
Once you have this, for each vert that you want to move, check the distance from that vert to the voxels and once you found the closest voxel then check the distance to all the verts in that voxel.
Now the fun begins when you realize that each scene will need a slightly different grid size for fastest calculations, and that you should check adjacent voxels for closest verts as you can have unique situations where the closest vert might be in a voxel that is a little further away than the closest voxel
Good luck with it and let us know how it turns out!
I just need to wrap my head around how to do this sort of thing. It makes sense how you just explained it, but I just need to learn how to build the grid, and add data into the addresses and read it back/compare properly…
Using the RayMeshGridIntersect() function though, I’m not sure how much faster making my own voxel grid would be. Right now I use the RayMeshGridIntersect to find the closet face in the scene geo - my selection, and do distance checks on only those 3-4 verts (on average).
So this method is pretty quick. Moving 64 verts, calculating against 1 object with 120K + verts, it takes around 9 seconds. So it’s not bad… but Dennis says it could be faster… So that has been bothering me. I’m getting obsessed with wanting to reach that goal
I have used this script in the past. It took a bit of tweaking to get it behaving as I wanted but it does skirt around the issue of guessing the best voxel size.
hmmm… I will have to look through this. I don’t know Python though, so it might be sort of confusing. DennisT, that guy I mentioned from CGTalk posted his code for his method, although I don’t really understand his method either, haha.
KD-Trees are worth having a look. One of the guys here wrote a pretty nifty flocking system that was affected by the mouse pointer. Using this method the search and comparision of several hundread points in relation to the mouse pointer position was greatly improved: http://en.wikipedia.org/wiki/Kd-tree
Yeah, a guy at work just said I could look for a C# Octree method or something, since max can use C#. So if I can get a sln or .dll to use, I could maybe feed that my data set and achieve what I’m looking for.
I am still polishing the new version with the 3d voxel algorithm and it’s way way faster.
