# Fast attach algorithm

 09 September 2010 #1 ivanisavich Some kind of robot   Tyson Ibele Animator MAKE LLC. Toronto, Canada   Join Date: Nov 2002 Posts: 3,096 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: Code: ``` ---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: Code: ``` ---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. Code: ``` 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. share quote
 09 September 2010 #2 3rd Dimentia Expert   Chris Gray TD/DeluxePaint3 Veteran Melbourne, Australia   Join Date: Aug 2002 Posts: 671 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. Code: ``` 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. share quote
09 September 2010   #3
Quote:
 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

 09 September 2010 #4 ArtOfSoulburn Artist   portfolio Neil Blevins San%2BFrancisco, United%2BStates   Join Date: Apr 2002 Posts: 4,360 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 share quote
 09 September 2010 #5 denisT MAX Doctor   portfolio Denis Trofimov CA, USA   Join Date: Jul 2009 Posts: 9,923 ... 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? share quote
 09 September 2010 #6 3rd Dimentia Expert   Chris Gray TD/DeluxePaint3 Veteran Melbourne, Australia   Join Date: Aug 2002 Posts: 671 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. share quote
09 September 2010   #7
Quote:
 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.

 09 September 2010 #8 3rd Dimentia Expert   Chris Gray TD/DeluxePaint3 Veteran Melbourne, Australia   Join Date: Aug 2002 Posts: 671 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. share quote
09 September 2010   #9
Quote:
 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.

 09 September 2010 #10 3rd Dimentia Expert   Chris Gray TD/DeluxePaint3 Veteran Melbourne, Australia   Join Date: Aug 2002 Posts: 671 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. share quote
08 August 2011   #11
Quote:
 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

 10 October 2011 #12 Vapourise Veteran portfolio k Glasgow, United Kingdom   Join Date: Oct 2011 Posts: 36 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 share quote
 10 October 2011 #13 3rd Dimentia Expert   Chris Gray TD/DeluxePaint3 Veteran Melbourne, Australia   Join Date: Aug 2002 Posts: 671 turns off the undo as attaching many objects could fill your memory with all the undo data causing max to crash. Code: ` undo off` starts and continues a loop if there are more than 1 object selected Code: `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. Code: `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. Code: `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) Code: ` polyop.attach selection[i] selection[i-1]` and finally, a function to update the single object left over Code: ` update selection[1]` But if all you were looking for was the code to attach one object to another, this is it: Code: `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. share quote
 10 October 2011 #14 Vapourise Veteran portfolio k Glasgow, United Kingdom   Join Date: Oct 2011 Posts: 36 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 share quote
 10 October 2011 #15 Kameleon Expert   portfolio Artur Leao Co-Founder / Project Manager You can do it! VFX Porto, Portugal   Join Date: Sep 2004 Posts: 1,030 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 share quote

 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 vBulletinCopyright ©2000 - 2006, Jelsoft Enterprises Ltd.