Fast attach algorithm


#1

Hey guys,

     So I've created a really fast attach algorithm for attaching large arrays of objects together. I searched the forum and didn't find any other threads mentioning this method so I'm assuming it's unique.
     
     I call it "Cluster Attach". Basically, instead of just attaching one object to the previous object over and over until all objects are attached, it progressively attaches and clusters objects into smaller and smaller groups of remaining objects until only the final object remains. It's extremely simple, and for some reason it reduces the amount of time it takes to attach large groups of objects together by a huge amount.
     
     For example, I did some tests where I attach 1000 teapots together. A typical linear approach (where you just cumulatively attach objects together one after the other) took [b]119.7 seconds[/b] to complete.
     
     However, using the cluster attach method, the operation took only[b] 5.7 seconds[/b] to complete. Also, if you simply pass the cluster function an array of editable_poly meshes, and take out the line that converts non-editable_polys to editable_polys on the fly, the time can be nearly halved.
 
 (For those wondering, undo was disabled with "undo off" for both of these tests. Usually the answer to "how can I speed up large attach operations" is to disable undo, but as you can see, the cluster approach offers even further speed improvements)
     
     I was so surprised by the results that I decided to come here and post the generalized functions for people to use, as well as a little script with a rollout that demonstrates the two algorithms side by side, and prints out the amount of time each one takes to complete.
     
     [b]Linear Attach (slow) Algorithm:[/b]

         ---pass an array of geometry nodes to this function and it will return the combined result
         
         function linearAttach objArr =
  	(
  		converttopoly objArr[1]
  		undo off
  		(
  			for q in 2 to objArr.count do
  			(
   				polyop.attach objArr[1] objArr[q]				
  			)
  		)
  		return objArr[1]
  	)
  
     [b]Cluster Attach (fast) Algorithm:[/b]

         ---pass an array of geometry nodes to this function and it will return the combined result
         
         function clusterAttach objArr =
  	(
  		
  		j = 1
  		count = objArr.count
  			
  		undo off
  		(
  			while objArr.count > 1 do
  			(				
  				if classof objArr[j] != Editable_Poly then converttopoly objArr[j]
  					
  				polyop.attach objArr[j] objArr[j+1]
  				deleteItem objArr (j+1)
  					
  				j += 1
  					
  				if (j + 1) > objArr.count then j = 1
  				
  			)
  		)
  		return objArr[1]
  	)
  
     Here is a sample script you can run to test the two algorithms side by side. You can manually enter the number of teapots to be generated (they'll be generated in a grid-like pattern so you can see them individually), and the total attach time gets printed to the listener after the algorithm completes.

  try(destroydialog teaRoll)catch()
  
  rollout teaRoll "Roll" 
  (
  	spinner numPots "# Teapots: " type:#integer range:[1,5000,250]
  	button pressMe "Cluster Attach"
  	button pressMe2 "Linear Attach"
  	
  	progressbar prog1 "" value:0
  	
  	function makeTeapots total= 
  	(
  		teaArr = #()
  		
  		posX = 0
  			posY = 0
  
  			for q in 1 to total do
  			(
  				posX += 10
  				
  				if posX > 1000 then
  				(
  					posY += 50
  					posX = 0
  				)
  				teaArr[q] = teapot()
  				teaArr[q].pos.x = posX
  				teaArr[q].pos.y = posY
  			)		
  		
  		return teaArr
  	)
  	
  	function clusterAttach objArr =
  	(
  		
  		j = 1
  		count = objArr.count
  			
  		undo off
  		(
  			while objArr.count > 1 do
  			(
  					
  				prog1.value = (1 - ([objArr.count/count](http://objArr.count/count) as float))*100
  				
  				if classof objArr[j] != Editable_Poly then converttopoly objArr[j]
  					
  				polyop.attach objArr[j] objArr[j+1]
  				deleteItem objArr (j+1)
  					
  				j += 1
  					
  				if (j + 1) > objArr.count then j = 1
  				
  			)
  		)
  		return objArr[1]
  	)
  	
  	function linearAttach objArr =
  	(
  		converttopoly objArr[1]
  		undo off
  		(
  			for q in 2 to objArr.count do
  			(
  					
  				prog1.value = (q/objArr.count as float)*100
  					
  				polyop.attach objArr[1] objArr[q]
  				
  			)
  		)
  		return objArr[1]
  	)
  	
  	on pressMe pressed do
  	(
  
  			delete $*
  
  			teaArr = makeTeapots numPots.value
  			
  
  			tStart = timestamp()
  
  			clusterAttach teaArr
  
  			prog1.value = 0
  			tEnd = timestamp ()
  
  			print ("Attach finished. Total time: " +  ((tEnd-tStart)/1000.0) as string + "s")
  	
  		
  	)
  	
  	on pressMe2 pressed do
  	(
  
  			delete $*
  			
  			teaArr = makeTeapots numPots.value
  
  			tStart = timestamp()			
  			
  			linearAttach teaArr
  
  			prog1.value = 0
  			tEnd = timestamp ()
  
  			print ("Attach finished. Total time: " +  ((tEnd-tStart)/1000.0) as string + "s")
  			
  		
  		
  	)
  	
  )
  
  createdialog teaRoll
         
  Anyways, I've often been frustrated by how slow it can be to attach huge numbers of objects together with maxscript, and I imagine other people have been too since I found a good number of threads asking how to speed things up....so hopefully people will find the cluster method helpful!

#2

Nice one, I had the same problem a few months ago where it would take 18 minutes to attach 2040 objects. That was for 3.1mill polys. I wrote this little bit of script which seems fairly similar to yours, and the same attach took 24 seconds. Mine just attaches every odd to every even selected object until there’s only one object selected.

	undo off
  	(
  		while selection.count > 1 do
  		(
  			selcount = selection.count
  			for i = selcount to 2 by -2 do
  			(
  				polyop.attach selection[i] selection[i-1]
  			)
  		)
  		update selection[1]
  	)

#3

Yep, that’s the ticket. The only difference between our two algorithms is that yours modifies the current selection and mine modifies an array…cool to know I wasn’t the only one who thought of it! Although I wonder why the speed difference is so big…


#4

My buddy Zeboxx also figured this out awhile ago, and I added his code to my attachSelectedObjects script. Looks again pretty similar to what you guys are doing…

http://www.neilblevins.com/cg_tools/soulburnscripts/soulburnscripts.htm

  • Neil

#5

… but what if you have an array of 6 objects in order of 1 face, 10 faces, 100, 1000, 10000, and 100000 faces? What algorithm will be faster? Is it “cluster”, or “linear”, or something else? :wink:


#6

Neil: Nice to know I’m in such esteemed company. :slight_smile:

Denis: at a guess I’d say for a group of objects ordered like that, I’d say cluster, but for best results the order of the first cycle should be:

first attached to last
second attached to second last
third attached to third last

The problem with the normal attach is that when maxscript is building polys, it gets increasingly slower. I found this out while writing a poly rebuild script. It took 22 times longer to build 40k polys as it did to build 10k polys. So that means when you do a linear attach, every single time you attach something to something else is has to rebuild the entire attach-to object from scratch with the new object included. Which will get pretty slow if your attach-to object his getting up there in polycount. If you break it down and cycle over the objects attaching each to it’s second neighbour it has less to rebuild again and again. So I’d say that attaching the highest polycounts to the lowest to keep the polycounts of the objects as low as possible would be the best way to optimize it further. It then all depends on the overhead of the sorting as to whether you’d gain anything by doing it this way. I’m guessing that few objects with high polycounts would gain more than lots of objects with less polys in this case.

Cheers,

Cg.


#7

are you trying to explain me how poly-attachment works? :wink:

I could show the faster algorithm but I don’t want to take your chance to find it yourself. There is no another one. It’s mathematically proved and used it such things as database for example.


#8

Oh I do apologize Dennis, I didn’t realize you were just evoking discussion to say there were further known methods. I was just answering your question. Cheers for the tip. Off to do some research :slight_smile:

Cg.


#9

I didn’t say that you are wrong with your vision of the reason of slowing down the multiple attachment. You are almost right. But your answer for my question is not.
for the sample 1,10,100,1000,10000,100000 faces node array the linear algorithm works much faster the cluster. But it’s only for this case because the list is specifically sorted.


#10

And I’m guessing that the massive size difference from the smallest to the largest has something to do with it and there’d be some way to estimate the point where the speed crossover between cluster and linear would happen. Since you seem to be in the know with the maths background for this, can I ask if you know if “linear” and “cluster” are the proper names used for these techniques? I have no schooling background with this stuff and just figured a way to make something happen faster that was taking too long. I really want to look into the maths and/or theory behind this stuff and am unsure as to what to search for.

Cheers,

Cg.


#11

You may have just saved a mans life with this script. The waiting was driving me mad. Thank you.


#12

Wow, thanks guys for sharing this, I am really new to Maxscript and was looking for the code needed to attach poly objects. I find it difficult finding the exact thing I need within the help documentation.

If either of you could take 5 minutes to explain briefly what the symbols in your scripts mean it would help me a lot in furthering my understanding :slight_smile: If not no worries.

Cheers, K


#13

turns off the undo as attaching many objects could fill your memory with all the undo data causing max to crash.

	undo off
   starts and continues a loop if there are more than 1 object selected  
while selection.count > 1 do
create a variable to hold the initial number of objects selected in this iteration of the while loop. I made this to use instead of using the selection count 'live' cause the selection count changes as objects are attached ot each other.
selcount = selection.count
   makes a 'for' loop to iterate backwards thru the selected objects attaching every second object to every other second object.
   so with 10 objects, 10 would be attached to 9, 8 to 7, 7 to 6 etc. I did it this way cause if you count up, when you attach 1 to 2, all objects shift down 1 spot and it gets a bit less neat and not quite as easy to manage.
for i = selcount to 2 by -2 do
   This is the line that does the attaching. For example, when i  is 10 it will attach object 10 to object i-1  (which is 9)
 polyop.attach selection[i] selection[i-1]
   and finally, a function to update the single object left over 
 update selection[1]

But if all you were looking for was the code to attach one object to another, this is it:

polyop.attach object1 object2

where object2 will be attached to object1 leaving you with just object1 with the geo of object2 included.

Hope some of this helps,

Cg.


#14

Thank you very much for taking the time to explain, It is extremely useful. Sometimes the scripts can seem overwhelming but it helps when they are broken down :slight_smile:

Cheers


#15

I wonder if the array could be splitted and then threaded to two separate threads… hmmmm xD


#16

As far as I know, maxscript is not multithreaded.


#17

Well, I was actually able to do it… kind of, the problem is something related to viewport updates, I’ve tried alot of different aproaches but none was flawless on a large number of objects, worked well in small numbers though.


#18

Care to share any of your experience?


#19

There is really nothing special about it, I just ran the attach code in a different thread and then tried using disableRedraw enableRedraw and completeRedraw in different places but none worked 100%


#20

Care to share any of your experiences in a way that might help people write multithreaded code?
Like maybe a code snippet? A function name? A place in the help to read?
I’ve searched the help file for this kind of thing and didn’t manage to find anything related.