[Closed] Break and Weld UV's on 100k tris meshes

actually it’s for pros only tenth maxscript developer knows how bsearch works and how to use it.

Of course it is a pro searching algorithm, I was kidding.

But to use bsearch you would need to modify much more than 1 line of code in your original script. What I posted was a quick easy improvement with a huge impact for what it is.

So, and to keep just those few developers in the “bsearch elite”, I am supposing you won’t either publish the code nor will you teach us on how to use bsearch right?

Or are you feeling generous today?

i’m pretty kind today

and i show the bsearch version… as you can see i didn’t add too much to basic algorithm, but i reorganized the data

fn hashSorter d1 d2 = (if d1[1] < d2[1] then -1 else if d1[1] > d2[1] then 1 else 0)
 
 fn breakTVerts node:selection[1] =
 (
 	converttomesh node
 	mesh = snapshotasmesh node
 	meshop.breakverts mesh #all
 
 	setnumtverts node mesh.numtverts
 	buildtvfaces node
 
 	tverts = for v=1 to mesh.numtverts collect
 	(
 		settvert node v (p = gettvert mesh v)
 		p
 	)
 	tfaces = for f=1 to mesh.numfaces collect 
 	(
 		vv = getface node f
 		tt = gettvface mesh f
 		
 		for k=1 to 3 where not iskindof tverts[tt[k]] array do tverts[tt[k]] = #(gethashvalue tverts[tt[k]] vv[k], tt[k])
 		settvface node f tt
 		tt
 	)
 	qsort tverts hashSorter
 	#(tfaces, tverts)
 )
 fn weldTVVerts node:selection[1] data: = 
 (
 	dd = data[2]
 	vv = #()
 	for d in dd do
 	(
 		v = bsearch d dd hashSorter
 		vv[d[2]] = v[2]
 	)
 	for f=1 to node.numfaces do
 	(
 		d = data[1][f]
 		settvface node f [vv[d[1]],vv[d[2]],vv[d[3]]]
 	)
 	meshop.deleteisomapvertsall node
 	node.numfaces
 )
 gc()
 (
 	t1 = timestamp()
 	data = breakTVerts node:objects[1]
 	t2 = timestamp()
 	num = weldTVVerts node:objects[1] data:data
 	t3 = timestamp()
 	format "faces:% time:%
" num #(t2-t1, t3-t2, t3-t1)
 ) 

BTW… i’ve made this algorithm with c++ sdk. it takes ~0.7 sec for ~80K faces mesh.

Thank you Denis!

ha! i still see another way for optimization
let me think a little…

EDITED! yes! 10934 instead of 14523.

only one small change:

	local hash, index
	for d in dd do
	(
		if d[1] == hash then vv[d[2]] = index
		else
		(
			v = bsearch d dd hashSorter
			hash = d[1]
			index = vv[d[2]] = v[2]
		)
	)

the next step is to try save some memory.

Here is my Algorithm:

faces:99380 time:1325 ram:43134792L

(
    	
    fn BreakAndWeldAllUvwVerts obj =
    (
    	mesh = snapshotasmesh obj
    	meshop.breakverts mesh #all
    
    	setnumtverts obj mesh.numtverts
    	buildtvfaces obj
    
    	for j = 1 to mesh.numtverts do settvert obj j (gettvert mesh j)
    
    	verts = for j = 1 to obj.numverts collect #()
    	idx = deepcopy verts
    	
    	for j = 1 to mesh.numfaces do
    	(
    		f1 = getface obj j
    		f2 = gettvface mesh j
    		
    		v1 = gettvert mesh f2[1]
    		v2 = gettvert mesh f2[2]
    		v3 = gettvert mesh f2[3]
    		
    		k1 = finditem verts[f1[1]] v1
    		k2 = finditem verts[f1[2]] v2
    		k3 = finditem verts[f1[3]] v3
    
    		append verts[f1[1]] v1
    		append verts[f1[2]] v2
    		append verts[f1[3]] v3
    		
    		for i = 1 to 3 do append idx[f1[i]] f2[i]
    		
    		if k1 > 0 do f2[1] = idx[f1[1]][k1]
    		if k2 > 0 do f2[2] = idx[f1[2]][k2]
    		if k3 > 0 do f2[3] = idx[f1[3]][k3]
    		
    		settvface obj j f2
    	)
    )
    
    gc()
    st = timestamp(); sh = heapfree
    BreakAndWeldAllUvwVerts $
    format "faces:% time:% ram:%
" $.numfaces (timestamp()-st) (sh-heapfree)
    
    )

PD: @Clanker, I wonder if you could upload a larger model for testing so the tests would be more real than using duplicated parts.

Very Nice!

w00t w00t ! You guys are sick and i like it.
Yeah, i’ll see to upload a more complex model, but i’m affraid i can’t share a real piece or i’ll do by pm tomorrow.
Thanks !

Improved Speed and Memory ussage:

faces:99380 time:1325 ram:43134792L
faces:99380 time:1111 ram:16968240L

(
   
   fn BreakAndWeldAllUvwVerts obj =
   (
   	mesh = snapshotasmesh obj
   	meshop.breakverts mesh #all
   
   	setnumtverts obj mesh.numtverts
   	buildtvfaces obj
   
   	for j = 1 to mesh.numtverts do settvert obj j (gettvert mesh j)
   
   	verts = for j = 1 to obj.numverts collect #()
   	idx = deepcopy verts
   	
   	for j = 1 to mesh.numfaces do
   	(
   		f1 = getface obj j
   		f2 = gettvface mesh j
   		
   		v1 = gettvert mesh f2[1]
   		v2 = gettvert mesh f2[2]
   		v3 = gettvert mesh f2[3]
   		
   		k1 = finditem verts[f1[1]] v1
   		k2 = finditem verts[f1[2]] v2
   		k3 = finditem verts[f1[3]] v3
   
   		if k1 == 0 then
   		(
   			append verts[f1[1]] v1
   			append idx[f1[1]] f2[1]
   		)else(
   			f2[1] = idx[f1[1]][k1]
   		)
   		if k2 == 0 then
   		(
   			append verts[f1[2]] v2
   			append idx[f1[2]] f2[2]
   		)else(
   			f2[2] = idx[f1[2]][k2]
   		)
   		if k3 == 0 then
   		(
   			append verts[f1[3]] v3
   			append idx[f1[3]] f2[3]
   		)else(
   			f2[3] = idx[f1[3]][k3]
   		)
   		
   		settvface obj j f2
   	)
   )
   
   gc()
   st = timestamp(); sh = heapfree
   BreakAndWeldAllUvwVerts $
   format "faces:% time:% ram:%
" $.numfaces (timestamp()-st) (sh-heapfree)
   
   )