[Closed] Vertex Distances via Voxel Acceleration

Ok, yeah… I was wondering how a 2D Grid would work otherwise.

I would be interested to see how much faster it would be to do that though, vs. what I am doing now with RayMeshGridIntersect(). I suppose not having to do raycasts and just getting straight up vert positions would be alot faster? Maybe 2x the speed I am getting now, but who knows?

I used some other methods like maxOps.CloneNodes because it seems to speed things up a tiny bit, and I am attaching geo differently to try and speed it up as well. I think I’ve taken it almost as far as I can without creating a custom voxel method, which I don’t really understand yet.

I know I can change the Grid size as well, but after testing and reading a post on a good grid size vs. scene complexity, it seems having 250 is a good size.

how many verts do you want to check? what calculation time do you expect?

I’m not sure about time to expect. But after seeing Bobos method from his talk, with the custom voxel method, he was searching something like 500,000 verts I think in like 50-100 ms I want to say. But he was only getting the closest point to another point.

Right now my script time isn’t bad, but if it can be faster, that’s always better. As far as points go, the amount of verts being check is unknown. I’ve been using this tool to stitch terrain to road pieces at work, and because of how we have to use Max and their tools, often people have half the track/level loaded into the scene at once. So there might be 200k or 500K verts to check, and thats across hundreds of objects if not thousands.

When stitching, on average, I didn’t have alot of verts selected, but it was usually like 30-50 verts or so, that needed to be snapped/moved to the closest vert in the scene.

I have the option for the user to select 1 piece of geo to check against, but often the internal tools freeze/load in proxy meshes, so it’s a hassle to deal with that manually (unfreeze/convert to mesh/ try to select the right piece).

– for your task you don’t need 3D grid. 2D is enough.
– you don’t need to check against all vertices in all objects. you can simply exclude all target nodes which don’t intersect with source node by bounding box. also you have to exclude the source node itself
– if you want to stitch verts probably you are talking about verts on open edges. right?

so… my guess that finding all verts to stitch for 500,000 verts scene shouldn’t take more than 0.5 sec

Well for the bounding box part, if you were using a plane, and it was floating above geo underneath it, and the plane was perfectly horizontal, that would never find the other meshes then?

The Intersection Idea in general though is something to think about…

My script basically takes a selection of verts, and will move each one to the closest vert in the scene geometry. Ideally this is used for stitching terrain to other geom, or maybe doing things like a mass target weld/snap instead of manually snapping/welding stuff together.

I have been using this tool often at work, and its been very helpful. But like I said, making it faster is always better :).

So a 2D Grid will work fine, comparing X,Y,Z Coordinates? Comparing just a single axis won’t be enough I don’t think. Doing that in half a second like you said sounds very impressive, but also seems to good to be true… :argh:

currently my method needs 2.5 sec for 576 nodes with 590K verts to find ALL vertices to stitch…
i hope to make it at least two times faster.
but probably it will not be 0.5 sec. as i promised

last update: 1.6 sec

You’re always teasing… just like Bobo with his script… which he says can work just as fast. .5 seconds or something.

What do you mean if you knew?

My current script, I just updated it, but. Right now it takes a vert selection u have, then finds the closest vert in the scene geo, that is visible to the camera (Not hidden or Visible in isolation), and moves each vert based on that.

Changing some things around, I made my script faster. I went from moving 64 verts checking against a 130K mesh in 9 seconds, to moving them in around 5.0 – 5.5 seconds.

Not as fast as yours, but are you taking a selection of verts and moving them to their closest spot? Are you also filtering the scene geo based on what’s visible and so no, or are you using whats close by?

Edit: I get what you mean now. Snap 1 set of verts to another set of verts chosen.

here is the source to play:

 (
	struct vertdata (ID, meshID, node, nodeID, pos, cell, verts = #())
	d = 10.0
	dist = d/100
	shift = [0.5,0.5,0.5]*dist/(sqrt 3.1)
	
	setCommandPanelTaskMode mode:#create
	delete objects
	nodes = #()
	global data = #()
	size = 24
	count = 0
	
	verts = 0
	t1 = timestamp()
	for y=0 to size-1 do
		for x=0 to size-1 do
		(
			count +=1 
			name = "p_" + (formattedprint count format:"04d") 
			node = plane name:name length:d width:d pos:([d*(x+0.5),d*(y+0.5),0] + (random -shift shift)) isSelected:off \
				lengthsegs:31 widthsegs:31 wirecolor:(random red blue)
			converttomesh node
			verts += node.numverts	
			append nodes node
		)
	format "build meshes... time:% nodes:% verts:%
" ((timestamp() - t1) as string) nodes.count verts
		
	getOpenEdges = meshop.getOpenEdges
	edgesToVerts = meshop.getVertsUsingEdge
	
	t1 = timestamp()
	id = 0
	for node in nodes do
	(
		vv = edgesToVerts node (getOpenEdges node)
		for v in vv do
		(
			id += 1
			append data (vertdata ID:id meshID:v node:node nodeID:(GetHandleByAnim node) pos:(getvert node v) verts:#(id))
		)
	)
	t1 = timestamp()
	
	buffer = #()
	gsize = 400
--	buffer.count = gsize+2
	nmin = objects.min
	nmax = objects.max
	csize = (nmax - nmin)/gsize
	
	for v in data do
	(
		x = (v.pos.x - nmin.x)/csize.x + 2
		y = (v.pos.y - nmin.y)/csize.y + 2
		v.cell = [x,y]
		if buffer[x] == undefined then 
		(
			buffer[x] = #() 
			buffer[x][y] = #(v.id)
		)
		else if buffer[x][y] == undefined then buffer[x][y] = #(v.id)
		else append buffer[x][y] v.id
	)

	format "	make 2D grid... time:% count:%
" ((timestamp() - t1) as string) buffer.count

	t1 = timestamp()
	count = 0

	for x=2 to buffer.count where buffer[x] != undefined do
	(
		for y=2 to buffer[x].count where buffer[x][y] != undefined do
		(
			count += buffer[x][y].count
		
			verts = copy buffer[x][y] #nomap
			if buffer[x][y+1] != undefined do verts += buffer[x][y+1]
			if buffer[x+1] != undefined and buffer[x+1][y] != undefined do verts += buffer[x+1][y]
			
			for s in buffer[x][y] do 
			(
				for d in verts where s != d and \ --(data[s].verts != data[d].verts) and \
					(distance data[s].pos data[d].pos) < dist and data[s].nodeID != data[d].nodeID do
					(
						targets = makeUniqueArray (data[s].verts + data[d].verts)
						for v in targets do data[v].verts = targets
					)
			)
--			format "x:% y:% verts:%
" x y verts
		)
	)
	format "		search verts... time:% count:%
" ((timestamp() - t1) as string) count

	mapped fn updatemesh mesh = (update mesh)
	t1 = timestamp()
	count = 0
	for v in data where v != undefined and v.verts.count > 1 do
	(
		count += v.verts.count

		pos = [0,0,0]
		for d in v.verts do pos += data[d].pos
		pos /= v.verts.count
		for d in v.verts do 
		(
			setvert data[d].node data[d].meshid pos
			data[d].pos = pos
			if data[d].verts == v.verts do data[d] = undefined
		)
	)
	updatemesh nodes
	
	format "			snap verts... time:% count:%
" ((timestamp() - t1) as string) count
	
	free buffer
	free data
	gc()
)
 

output:

 build meshes... time:783 nodes:576 verts:589824
	make 2D grid... time:387 count:402
		search verts... time:1509 count:71424
			snap verts... time:878 count:68335
 

my snapping algorithm has to be improved. It seems like I’m missing some verts trying to make the snapping faster. but i promised just a searching algorithm. so you free do make it better.
also anyone who likes the challenge can post your solution…