Mini-Challenge #3


edit: you’re right… I messed that one up :slight_smile:

objs=$selection as array

deleteitem objs 1
ProBoolean.CreateBooleanObjects  main objs  4 2 1

Using option ‘attach (no intersections)’ ( option 4 instead of a 3) solves that… I’ll try to get a timing1


Create. Time: 0.266 Memory: 133912L First: p0 Last: p99
Create. Time: 0.262 Memory: 132792L First: p0 Last: p99
#cluster: with undo:on Time:0.438 Memory:5880L Updates:329002

My method:
Create. Time: 0.263 Memory: 133304L First: p0 Last: p99
Create. Time: 0.261 Memory: 133280L First: p0 Last: p99
#custom: with undo:on Time:0.235 Memory:2312L Updates:0

Here’s the code, I could optimize it a bit further :slight_smile:

edit: A thing that might disqualify me is that the timings appear before the actual mesh does :slight_smile:

  	------------------ template ----------------
  	fn customAttach source nodes pb:pb1 = 
  		ProBoolean.SetOperandA main
  		ProBoolean.SetPlanarEdgeRemoval main 2
  		ProBoolean.SetUpdateMode main 3
  		for i=1 to objs.count do
  		ProBoolean.SetOperandB main  objs[i]  4 2 
  		ProBoolean.SetUpdateMode main 0


Am I missing something? When I run it, I am left with only the source object…


you have to convert to POLY. it changes everything


sorry but what does the pb:pb1 means in the function definition?


pointer to UI progress bar


Ok, I finally have something that beats cluster attach performance, if only by ~5%:

fn customAttach source nodes pb:pb1 = 
		fn qsfn v1 v2 = v1.numVerts - v2.numVerts		
		insertitem source nodes 1
		qSort nodes qsFn
		local k = 1
		local count = nodes.count
		local att = polyop.attach		
		while nodes.count > 1 and not keyboard.escpressed do
			local nk = nodes[k]
			pb.value = 100 - nodes.count*100./count
			att nk nodes[k+1]
			verts += nk.numverts
			deleteItem nodes (k+1)
			if nodes[k+2]!=undefined and nk.numVerts >= nodes[k+2].numVerts do k += 1
			if k >= nodes.count do k = 1			

#cluster:	with undo:on	Time:2.297	Memory:72168L	Updates:5567158
#custom:	with undo:on	Time:2.209	Memory:72192L	Updates:5297612


how many nodes are used for this test? what method of distribution?
but your solution is exactly same as I started from :slight_smile: qsort is very slow… :frowning:


the test I posted is with 1000 nodes and random distribution but I’ve gotten similar results on different amounts (tested max 5000) and all distribution options.

Will try to continue optimizing…


good … never stop.


For 1000 nodes the qsort takes me 4ms … doesn’t sound like it is the bottleneck.


if do it only one time? :wink:


I just wanted to say that even while I’m getting my a** kicked here I really enjoy these challenges :slight_smile: Very informative and i’m learning a lot here!


Yes, my check of

if nodes[k+2]!=undefined and nk.numVerts >= nodes[k+2].numVerts do k += 1

makes it redundant to sort the array more than once…
Running the qsort every cycle actually results in more total updates, not less.


it shouldn’t be. but the idea is right. we have to minimize number of updates. Updates == Poly rebuild.
it’s why linear max method works so slow.
lets say we have 100 verts node for attach to, and 2 one vert nodes to attach.

max attaches first node: 100+1 updates
after that it attaches second: 101+1 updates… all together 202 updates…

we can do it:
attach first to second: 1+1
attach result:100+2… together 104 updates.


the way I see it the goal is basically to always be attaching the two objects in the array with the lowest vertex count.
I believe my algorithm maintains that goal, but will have to check again tomorrow.


Haven’t had much time (E3 almost here :smiley: ), but here are some things I’ve tried,

[li]tried to hijack the Mesher compound object, to no avail[/li][li]been musing over possible Max systems that could attach things faster than any Maxscript, haven’t figured that one out yet,[/li][li]traditional method of attaching with different structures/code layout, nothing from that, all way slow[/li][li]had an “Unknown System Exception” a few times, but it was just how I was collecting/attaching the arrays, so that one was my fault :D[/li][/ul]Haven’t tried much clustering, since that is what has already been done a lot,
More to try! :slight_smile:


So further testing has shown my previous algorithm does not always attach the two lightest objects.

I’ve come up with this algorithm, which does always attach the two lightest, resulting in the minimal possible amount of updates.

Unfortunately, due to its added complexity it is a bit slower than my previous algorithm and just about the same speed as cluster attach. Perhaps I am overlooking a place where it can be optimized further.

@Denis: Out of curiosity… by how much, in percentage, is your algorithm faster than cluster attach?

fn customAttach source nodes pb:pb1 = 
		insertitem source nodes 1
		local count = nodes.count
		local att = polyop.attach			
		local vertArr = for o in nodes collect o.numVerts
		local sortedVertArr = deepcopy vertArr
		for i = 1 to nodes.count-1 do if not keyboard.escpressed do
			pb.value = 100 - nodes.count*100./count								
			sort sortedVertArr
			local a = findItem vertArr sortedVertArr[1]
			local b = findItem vertArr sortedVertArr[2]
			local nA = nodes[a]
			att nA nodes[b]
			deleteItem vertArr b
			deleteItem sortedVertArr 2
			deleteItem nodes b
			verts += nA.numverts								
Create.	Time: 1.181	Memory: 1240104L	First: p0 Last: p999 Random Range Dist.
#cluster:	        with undo:on	Time:2.172	Memory:72192L	Updates:5567158
#this algorithm:	with undo:on	Time:2.14	Memory:252192L	Updates:5256184
#prev. algorithm:       with undo:on 	Time:2.099	Memory:72128L	Updates:5297612


5-20%… my algorithm works better for large amount of nodes with big difference in vertex amount.


Lo, if I understand Denis correctly I believe he is saying that there is a sort method that can be included in the while loop that is faster than the logic you require in your algorithm. Although I can’t figure out what sort method other then qsort should be used, here is a simple example:

fn attachObjs arr = 
		fn qsortFn obj1 obj2 = obj1.numVerts - obj2.numVerts		
		qSort arr qsortFn
		local att = polyop.attach	
		while arr.count > 1 do
			att arr[1] arr[2]
			deleteItem arr 2
			qsort arr qsortFn


In my tests it is faster than Lo’s methods when dealing with object counts < 200 with varying vertex amounts. Once the object count goes over 200 then Lo’s method wins out because the qsort becomes a liability.