Fast attach algorithm

Become a member of the CGSociety

Connect, Share, and Learn with our Large Growing CG Art Community. It's Free!

THREAD CLOSED
 
Thread Tools Search this Thread Display Modes
Old 09 September 2010   #1
Fast attach algorithm

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 119.7 seconds to complete.

However, using the cluster attach method, the operation took only 5.7 seconds 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.

Linear Attach (slow) Algorithm:


         ---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]
  	)
  


Cluster Attach (fast) Algorithm:


         ---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 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!
__________________
http://www.tysonibele.com

Last edited by ivanisavich : 09 September 2010 at 12:05 PM.
 
Old 09 September 2010   #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]
  	)
__________________
Not bad. For a hughman.
 
Old 09 September 2010   #3
Originally Posted by 3rd Dimentia: 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.


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....
__________________
http://www.tysonibele.com
 
Old 09 September 2010   #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...burnscripts.htm

- Neil
 
Old 09 September 2010   #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?
 
Old 09 September 2010   #6
Neil: Nice to know I'm in such esteemed company.

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.
__________________
Not bad. For a hughman.
 
Old 09 September 2010   #7
Originally Posted by 3rd Dimentia: Neil: Nice to know I'm in such esteemed company.

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
...


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

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.
 
Old 09 September 2010   #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

Cg.
__________________
Not bad. For a hughman.
 
Old 09 September 2010   #9
Originally Posted by 3rd Dimentia: 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

Cg.


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.
 
Old 09 September 2010   #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.
__________________
Not bad. For a hughman.
 
Old 08 August 2011   #11
Originally Posted by ivanisavich: 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"...

...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!


You may have just saved a mans life with this script. The waiting was driving me mad. Thank you.
__________________
www.davetyner.com
 
Old 10 October 2011   #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 If not no worries.

Cheers, K
 
Old 10 October 2011   #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.
__________________
Not bad. For a hughman.
 
Old 10 October 2011   #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

Cheers
 
Old 10 October 2011   #15
I wonder if the array could be splitted and then threaded to two separate threads.... hmmmm xD
__________________
Artur Leao | Co-Founder / Project Manager
You can do it! VFX
Porto/Lisbon - Portugal
http://www.ycdivfx.com
 
Thread Closed share thread



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
CGSociety
Society of Digital Artists
www.cgsociety.org

Powered by vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

All times are GMT. The time now is 09:33 PM.


Powered by vBulletin
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.