PDA

View Full Version : Mini-Challenge #3


denisT
05-26-2011, 09:43 PM
http://forums.cgsociety.org/showthread.php?f=98&t=244321&highlight=fast+attach
http://forums.cgsociety.org/showthread.php?f=98&t=635477&highlight=fast+attach
and finally
http://forums.cgsociety.org/showthread.php?f=98&t=922140&highlight=fast+attach

it's all about how to attach nodes faster.
the last link shows absolutely GREAT solution by ivanisavich (http://forums.cgsociety.org/member.php?u=19108) (http://forums.cgsociety.org/member.php?u=19108)

the question is: can you do it faster?

so, try to attach multiple poly-nodes (~100+) to a poly-node as fast as possible. (memory is not an issue this time). it must be new algorithm, not just smart optimization of ivanisavich (http://forums.cgsociety.org/member.php?u=19108)'s.

Let's get ready to rumble!

unified attach layout:

denisT
05-26-2011, 10:30 PM
please show all your ideas even if they are slower. it might be a bright idea but with wrong implementation. also it will be very interesting to discuss why one or another solution doesn't really work, or doesn't work as expected.
mxs has some specific problems working with arrays, pointers to node, etc.
show your idea and we will try to optimize it.

j83
05-26-2011, 10:51 PM
Ok, I gotta jump in on this one. I'll try to have something posted before Saturday morning. :)

Kickflipkid687
05-27-2011, 01:01 AM
Oooh, I will def. be watching this one. I was searching for a faster method, and found some, but it would be cool if it can be faster yet.

I am using cloneops now and also attaching somewhat randomly instead of linierly. I took part of the code from soulburn though, so I don't take credit for it.

j83
05-27-2011, 01:22 AM
How does this look for the layout?

I'm guessing we're creating/convert the teapots before we calculate any time, correct?
(the script below doesn't perform any fast methods, just an example of the layout i'll be using)


(
fn createTeapots howManyTeapots: 1000 =
(
/*
===============
Here we delete all objects, create the teapots, select them, and zoom extents, the function returns the teapot array
===============
*/
delete objects
local arrayToReturn = #()

for j = 1 to 1000 do
append arrayToReturn (teapot pos:[random -100 100, random -100 100, random 0 100])
select geometry
actionMan.executeAction 0 "311" -- Tools: Zoom Extents All Selected

clearSelection()

arrayToReturn
)

rollout roAttachSpeedTest "1000 Teapot Speed Test" width: 220
(
button btnRunSpeedTest "Run Speed Test"
group ""
(
radioButtons rbSpeedTest "Choose Test:" labels:#("Test 1", "Test 2", "Test 3") columns:1 default: 3 align:#center
)
group ""
(
radioButtons rbMeshOrPoly "Pre-Convert Teapots to" labels:#("Editable Mesh", "Editable Poly") columns:1 default:1 align:#center
)
label labSpeedTestCaption ""

on roAttachSpeedTest open do
(
if (queryBox "Reset Max scene before continuing?" beep:false) then
resetMaxFile #noprompt

actionMan.executeAction 0 "50026" -- Tools: Maximize Viewport Toggle

if objects.count != 0 then
delete objects

)
on btnRunSpeedTest pressed do
(
with undo off
(
if rbMeshOrPoly.state == 1 then
(
convertToMesh(createTeapots())
convertToPoly geometry[1]
)
else
(
convertToPoly(createTeapots())
)

gc()

if rbSpeedTest.state == 1 then
(
local theCurrTime = timeStamp()
(
messageBox "Test 1 hasn't been implimented yet." beep:false
)
local endTime = timeStamp()
labSpeedTestCaption.text = ("Test Attach 1 process took " + ((endTime - theCurrTime) as string) + "ms." )

)

if rbSpeedTest.state == 2 then
(
local theCurrTime = timeStamp()
messageBox "Test 2 hasn't been implimented yet." beep:false
local endTime = timeStamp()
labSpeedTestCaption.text = ("Test Attach 1 process took " + ((endTime - theCurrTime) as string) + "ms." )
)
if rbSpeedTest.state == 3 then
(
local theCurrTime = timeStamp()
messageBox "Test 3 hasn't been implimented yet." beep:false
local endTime = timeStamp()
labSpeedTestCaption.text = ("Test Attach 1 process took " + ((endTime - theCurrTime) as string) + "ms." )
)
)
)
)

CreateDialog roAttachSpeedTest style:#(#style_toolwindow, #style_resizing, #style_sysmenu) fgcolor:([0,255,64]) bitmap:
undefined

)

lo
05-27-2011, 04:55 AM
I had a feeling this challenge would be coming. :)
I think we need a specific test case (1000 teapots as j83 suggested is fine by me), as different algorithms are better for different cases.

denisT
05-27-2011, 05:02 AM
I had a feeling this challenge would be coming. :)

are you ready? i'm cheating as usually. honestly i spent days to beat the vanisavich (http://forums.cgsociety.org/member.php?u=19108)'s algorithm.

denisT
05-27-2011, 05:27 AM
... I think we need a specific test case...
different algorithms are better for different cases.

tomorrow i will provide the standard test for fastest poly attach algorithm. all players will have the same field.

JHN
05-27-2011, 09:58 AM
I don't know if I have time to join, but spent at least an half our in bed thinking of new ways to do this :)

Great challenge!
-Johan

lo
05-27-2011, 10:04 AM
My first attempt... cluster attach with a twist.
From my tests it seems to be 25 times faster than cluster attach. Can anyone confirm?


fn megaClusterAttach objs =
(
gc()
local ts = timestamp()
with undo off with redraw off
(
local att = meshop.Attach
local snap = snapShotAsMesh
local del = deleteItem
local j = 1
local meshes = for o in objs collect snap o
while meshes.count > 1 do
(
att meshes[j] meshes[j+1]
del meshes (j+1)
j += 1
if (j + 1) > meshes.count then j = 1
)
delete objs
local result = editable_mesh name:"Result"
result.mesh = meshes[1]
print (timeStamp()-ts)
)
)

edit: didn't notice the output must be editablepoly. Adding a convertTo command to the result adds considerable time, though still 4 times faster than cluster attach.

jonadb
05-27-2011, 11:14 AM
This works fine for small collections, but explodes with 100 teapots.. I was hoping that proboolean's merge would be fast since no geometry calculations are done.. And you can pass it an array of nodes to merge so no need for iterating over a selection in maxscript..


objs=$selection as array

main=objs[1]
deleteitem objs 1

ProBoolean.CreateBooleanObjects main objs 3 2 1

denisT
05-27-2011, 12:50 PM
My first attempt... cluster attach with a twist.
From my tests it seems to be 25 times faster than cluster attach. Can anyone confirm?


the final object has to be an EDITABLE POLY.

denisT
05-27-2011, 12:59 PM
This works fine for small collections, but explodes with 100 teapots.. I was hoping that proboolean's merge would be fast since no geometry calculations are done.. And you can pass it an array of nodes to merge so no need for iterating over a selection in maxscript..


objs=$selection as array

main=objs[1]
deleteitem objs 1

ProBoolean.CreateBooleanObjects main objs 3 2 1

create proboolean object, add attaching nodes with merge operation and move method, and convert to poly.
right?

could you provide a time result?

jonadb
05-27-2011, 01:43 PM
create proboolean object, add attaching nodes with merge operation and move method, and convert to poly.
right?

could you provide a time result?

Yeah that was the plan, the convert to poly is missing from the script but that's trivial.

When I use it on a 100 teapots max freezes so I can't produce a time for a 1000 teapots. I didn't look for a solution jet since I have actual work to do :)

denisT
05-27-2011, 02:32 PM
i've posted unified test with ivanisavich (cluster) and 3dsmax (linear) methods. the test generates defined amount of boxes in different range and order. small boxes has to be attach to big box. my method is caster. it's hidden temporarily.

see the code and use custom slot for your algorithm following the template. let me know if need any assistance.

the code is http://forums.cgsociety.org/attachment.php?attachmentid=162171

next time when you want to show your method please just post the customAttach function:

fn customAttach source nodes pb:pb1 =
(
count = nodes.count
<loop> while not keyboard.escpressed do
(
pb.value = nodes.count*100./count
/*
your attach method with counting number of attached vertices
*/
)
source
)

denisT
05-27-2011, 02:39 PM
Yeah that was the plan, the convert to poly is missing from the script but that's trivial.

When I use it on a 100 teapots max freezes so I can't produce a time for a 1000 teapots. I didn't look for a solution jet since I have actual work to do :)

i've double-checked. ProBoolean Merge is not the same as Attach.

jonadb
05-27-2011, 02:48 PM
i've double-checked. ProBoolean Merge is not the same as Attach.

The result is the same ( N nodes > 1 node ) or I'm I missing something?

Edit: btw.. I've looked at the mesher object as wel, there seems to be an 'extranodes' exposed to maxscript.. but I can't seem to feed it multiple nodes?

lo
05-27-2011, 02:49 PM
with your test case my method is a bit slower than regular cluster attach because the test objects are already editable_polys. I was testing with teapot primitives earlier, in which case converting each object to a poly (cluster attach method) is much slower.
I will look for a method which is more optimized for this test case.

denisT
05-27-2011, 02:53 PM
The result is the same ( N nodes > 1 node ) or I'm I missing something?


boolean merge is some kind of union with keeping all source and target vertices. the method generates the intersection border.

denisT
05-27-2011, 02:57 PM
there is a myth that attaching or some other extensive operations are faster with UNDO OFF. check the test. it's not TRUE. but it's a subject of another discussion.

jonadb
05-27-2011, 03:04 PM
boolean merge is some kind of union with keeping all source and target vertices. the method generates the intersection border.

edit: you're right.. I messed that one up :)

objs=$selection as array

main=objs[1]
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

jonadb
05-27-2011, 03:32 PM
cluster:
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 :)

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


------------------ template ----------------
fn customAttach source nodes pb:pb1 =
(
objs=nodes
main=source

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

main

)

lo
05-27-2011, 03:47 PM
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


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

denisT
05-27-2011, 03:50 PM
cluster:
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 :)

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


------------------ template ----------------
fn customAttach source nodes pb:pb1 =
(
objs=nodes
main=source

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
converttopoly main
main

)


you have to convert to POLY. it changes everything

Kameleon
05-27-2011, 05:45 PM
sorry but what does the pb:pb1 means in the function definition?

denisT
05-27-2011, 05:57 PM
sorry but what does the pb:pb1 means in the function definition?

pointer to UI progress bar

lo
05-27-2011, 08:02 PM
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
)
nodes[1]
)

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

denisT
05-27-2011, 08:32 PM
lo,
how many nodes are used for this test? what method of distribution?
but your solution is exactly same as I started from :) qsort is very slow... :(

lo
05-27-2011, 08:38 PM
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...

denisT
05-27-2011, 08:43 PM
Will try to continue optimizing...
good ... never stop.

lo
05-27-2011, 08:57 PM
qsort is very slow... :(

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

denisT
05-27-2011, 09:00 PM
For 1000 nodes the qsort takes me 4ms ....
if do it only one time? ;)

jonadb
05-27-2011, 09:01 PM
I just wanted to say that even while I'm getting my a** kicked here I really enjoy these challenges :) Very informative and i'm learning a lot here!

lo
05-27-2011, 09:07 PM
if do it only one time? ;)

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.

denisT
05-27-2011, 10:07 PM
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.

lo
05-27-2011, 10:54 PM
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.

j83
05-28-2011, 02:36 AM
Haven't had much time (E3 almost here :D ), but here are some things I've tried,



tried to hijack the Mesher compound object, to no avail
been musing over possible Max systems that could attach things faster than any Maxscript, haven't figured that one out yet,
traditional method of attaching with different structures/code layout, nothing from that, all way slow
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
Haven't tried much clustering, since that is what has already been done a lot,
More to try! :)

lo
05-28-2011, 02:42 PM
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]
vertArr[a]=-1
local b = findItem vertArr sortedVertArr[2]
local nA = nodes[a]
att nA nodes[b]
sortedVertArr[1]=vertArr[a]=nA.numVerts
deleteItem vertArr b
deleteItem sortedVertArr 2
deleteItem nodes b
verts += nA.numverts
)
nodes[1]
)

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

denisT
05-28-2011, 04:15 PM
@Denis: Out of curiosity... by how much, in percentage, is your algorithm faster than cluster attach?

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

jonlauf
05-28-2011, 04:55 PM
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
)

arr[1]
)

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.

lo
05-28-2011, 05:17 PM
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:

How about this? I've written a c# assembly that calculates the optimal order of attachment, but while getting the optimal order is very fast, the attach loop which is now very short is still slower! I can't really explain the reason for this, can anyone else?

The total update count shows the minimal amount of updates are being used.
c# assembly:

fn createAssembly =
(
source = ""
source += "using System;\n"
source += "using System.Collections;\n"
source += "namespace MegaAttach\n"
source += "{\n"
source += " public class OptimalOrder\n"
source += " {\n"
source += " public static Int32[] FindOrder(Int32[] verts)\n"
source += " {\n"
source += " Int32[] SortedVerts = (Int32[])(verts.Clone());\n"
source += " Int32[] result = new Int32[verts.Length*2];\n"
source += " for (int i = 0; i < result.Length; i+=2)\n"
source += " {\n"
source += " Array.Sort(SortedVerts);\n"
source += " int a = Array.FindIndex(verts, delegate(Int32 v) {return v ==SortedVerts[0];});\n"
source += " int vA = verts[a];\n"
source += " verts[a] = -1;\n"
source += " int b = Array.FindIndex(verts, delegate(Int32 v) {return v ==SortedVerts[1];});\n"
source += " result[i] = a+1;\n"
source += " result[i + 1] = b+1;\n"
source += " SortedVerts[0] = verts[a] = vA + verts[b];\n"
source += " SortedVerts[1] = verts[b] = Int32.MaxValue;\n"
source += " }\n"
source += " return result;\n"
source += " }\n"
source += " }\n"
source += "}\n"

csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"

compilerParams.ReferencedAssemblies.AddRange #("System.dll")

compilerParams.GenerateInMemory = on
compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(source)

if (compilerResults.Errors.Count > 0 ) then
(
errs = stringstream ""
for i = 0 to (compilerResults.Errors.Count-1) do
(
err = compilerResults.Errors.Item[i]
format "Error:% Line:% Column:% %\n" err.ErrorNumber err.Line \
err.Column err.ErrorText to:errs
)
MessageBox (errs as string) title: "Errors encountered while compiling C# code"
format "%\n" errs
return undefined
)

assembly = compilerResults.CompiledAssembly
assembly.CreateInstance "MegaAttach.OptimalOrder"
)

global attachClass = createAssembly()

usage:
fn customAttach source nodes pb:pb1 =
(
insertitem source nodes 1
local att = polyop.attach
local optimalOrder = attachClass.FindOrder (for o in nodes collect o.numVerts)
local count = optimalOrder.count-2
for i = 1 to count by 2 do if not keyboard.escpressed do
(
pb.value = i*100./count
local nA = nodes[optimalOrder[i]]
att nA nodes[optimalOrder[i+1]]
verts += nA.numverts
)
nodes[1]
)

j83
05-28-2011, 06:33 PM
Not sure if it'd be of any help to anyone for this contest, but for a learning experiment, I implimented a shell sort function to test against Maxscript sort, and as you could guess, sort was way faster. :)

Of course, I could have just written it wrong, though it seems to sort things correctly, just slowly. :)


(
rollout roSortingTests "Sorting Tests"
(
button btnSortTest "ShellSort vs Qsort"
group""
(
radioButtons rbSortMethod "Choose Test:" labels:#("Sort", "Shell Sort") columns:2 default:1 align:#center
)
spinner spnNumberArraySize "Array Size:" width:100 height:16 range:[1,50000,5000] type:#integer align:#center
label lbSortResult ""
fn shellSort whatArr =
(
local val = 1
local temp = undefined
local outer = undefined
local inner = undefined

while (val <= whatArr.count / 3) do
val = val * 3 + 1

while (val > 1) do
(
for outer = val to (whatArr.count - 1) do
(
temp = whatArr[outer]
inner = outer
while ((inner > val ) and whatArr[inner-val] >= temp) do
(
whatArr[inner] = whatArr[inner - val]
inner -= val
)
whatArr[inner] = temp
)
val = (val - 1) / 3
)
)

on btnSortTest pressed do
(
gc()
local myIntArray = #()
for i = 1 to spnNumberArraySize.value do
append myIntArray (random 1 spnNumberArraySize.value)

local theCurrTime = timeStamp()

if (rbSortMethod.state == 1) then
sort myIntArray
else
shellSort myIntArray

local endTime = timeStamp()

if (rbSortMethod.state == 1) then
lbSortResult.text = ("Sort sort took " + ((endTime - theCurrTime) as string) + "ms." )
else
lbSortResult.text = ("Shell sort took " + ((endTime - theCurrTime) as string) + "ms." )

--for j = 1 to myIntArray.count by 100 do
--print j

OK
)
)

CreateDialog roSortingTests style:#(#style_toolwindow, #style_resizing, #style_sysmenu) fgcolor:([0,255,64]) bitmap:
undefined

)

denisT
05-28-2011, 06:59 PM
How about this? I've written a c# assembly that calculates the optimal order of attachment, but while getting the optimal order is very fast, the attach loop which is now very short is still slower! I can't really explain the reason for this, can anyone else?


i really like your idea to use pre-ordered node list! why is it slow? check the count of pre-ordered list, check how much takes to convert c# array to mxs array, check how much time the system needs to take a pointer to node from array, don't make local copy of pointer inside loop...
i can just guess. i'll be out of max for a week.

denisT
05-28-2011, 07:16 PM
all that we doing now is trying to find optimal attach order. which is helpful for performance but it can't change the timing dramatically. keep going. but.. if we found the way to disable poly rebuilding on time of attach that would change everything.
most time of the rebuilding is taken by building normals and creating edge data (it's why trimesh attach much faster than poly).
the best scenario will be to attach all node without rebuilding normals and edges, and finally do only one update for source node.
that's a theory. but i don't know how to do it, and not sure it's possible at all.

Panayot
05-28-2011, 07:18 PM
How about this? I've written a c# assembly that calculates the optimal order of attachment, but while getting the optimal order is very fast, the attach loop which is now very short is still slower! I can't really explain the reason for this, can anyone else?
I envy to you guys that you have the free time to join this cool challenges last week. I don't even find a time to read them carefully :)

I think you hit the base 'stone' that limit the benefit of .net in Max. While the 1st challenge shows the power of .net in Max, it still a speculative proof. Don't take me wrong, am too a .net lover, but there all was 'greet' because was sended single value to .net but here sending huge amount of values (array of 1000 elements), that's slow.

Ah, even while typing, Denis allready answer :)

denisT
05-28-2011, 07:26 PM
but here sending huge amount of values (array of 1000 elements), that's slow.

sending from .net to max is slow. so we can stay with .net array
but who said it must be array list? it might be generic list or some other collection. i will not tell you what is faster. :) but try to check it yourself... for the learning purpose ;)

Panayot
05-28-2011, 07:29 PM
sending from .net to max is slow. so we can stay with .net array
but who said it must be array list? it might be generic list or some other collection. i will not tell you what is faster. :) but try to check it yourself... for the learning purpose ;)
Hmm, i was mean sending from max to .net is more slower, or am wrong?

lo
05-28-2011, 07:29 PM
check the count of pre-ordered list
What do you mean exactly? It is exactly twice as long as the number of nodes to attach.
check how much takes to convert c# array to mxs array
For 1000 nodes, the whole part before entering the attach loop takes 22ms, which is not likely to be the bottleneck.
check how much time the system needs to take a pointer to node from array
Less than 1ms for 1000 iterations.
don't make local copy of pointer inside loop...
You're right, Ive checked, and making a local copy is slower, though the difference is less than 1ms for 1000 iterations.

:shrug:

lo
05-28-2011, 07:32 PM
the best scenario will be to attach all node without rebuilding normals and edges, and finally do only one update for source node.


I agree, the best result we can get from polyop.attach is what we already have due to optimal attach order.
But ironically, the algorithm I posted which does not use the most optimal order is faster than the one that does, so I am quite puzzled...

denisT
05-28-2011, 07:34 PM
Hmm, i was mean sending from max to .net is more slower, or am wrong?
it's fast enough.

denisT
05-28-2011, 10:00 PM
could anyone try to attach poly nodes with editable_poly property update set to manual? does it effect performance?

Kickflipkid687
05-28-2011, 10:04 PM
I wish you could SnapShotAsMesh a group of objects, and get that as TriMesh, then assign that to a EMesh or EPoly.....

j83
05-28-2011, 10:11 PM
I wish you could SnapShotAsMesh a group of objects, and get that as TriMesh, then assign that to a EMesh or EPoly.....

Yeah, I tried that in about 5 different ways, no go. :(

Kickflipkid687
05-28-2011, 10:43 PM
You might be able to get all vert positions in the objects and create a new mesh from that, but then you won't get UVs and Textures, and Smoothing, ect.... So prob. not worth it, heh. :banghead:

Panayot
05-28-2011, 11:35 PM
could anyone try to attach poly nodes with editable_poly property update set to manual? does it effect performance? i tested, not help

denisT
05-29-2011, 12:58 AM
i tested, not help
too bad...

MatanH
05-29-2011, 11:38 AM
I tried to go multithreded but ran into some problems..
If I run it with more then 1 thread max crashes and it's very unstable as it is with 1.
I saw some discussions about the backgroundworker where it was mentioned that some mxs functions won't work with it, I guess attach is one of them.
here is my attempt:

struct progUpdater (
count,
current = 0,
pb,

fn increment =
(
current += 1
pb.value = 100 * current / count
)
)

global pbManager

struct hcNode (
val = 0,
left,
right,
obj,
count = 1,
verts = 0,

fn init =
(
if obj != undefined then
val = obj.numVerts
else (
if left != undefined then (
val += left.val
val += right.val
verts = left.verts + right.verts + left.val + right.val
count = left.count + right.count
)
)
),

fn mergeChildren =
(
local att = polyop.attach

if left != undefined then (
local a = left.mergeChildren()
local b = right.mergeChildren()
left = undefined
right = undefined
att a b
obj = a
verts += val
) else
pbManager.increment()

obj
),

start = init()
)

fn sortByVertNum a b =
(
a.val - b.val
)

fn insertInPlace arr new start: end: =
(
if end - start < 0 then
append arr new
else if end - start == 0 then (
if arr[start].val > new.val then
insertItem new arr start
else
insertItem new arr (start + 1)
) else (
local i = amin (start + (end - start) / 2) (end - 1)

if arr[i].val > new.val then
insertInPlace arr new start:start end:i
else if arr[i].val < new.val then
insertInPlace arr new start:(i + 1) end:end
else
insertItem new arr i
)
)

struct treeMonitor (
roots,
next = 0,
count = 0,
source,
occupied = false,

fn getRoot =
(
next += 1
occupied = false
roots[next]
),

fn mergeRoots =
(
local att = polyop.attach

for o in roots do
att source o.obj
),

fn done =
(
count += 1
if count == roots.count then
mergeRoots()
redrawViews()
)
)

global hcMergeTreeFN
fn hcMergeTreeFN =
(
global hcTreeMonitor
if hcTreeMonitor != undefined then (
hcTreeMonitor.occupied = true
local root = hcTreeMonitor.getRoot()
root.mergeChildren()
hcTreeMonitor.done()
)
)

fn foo source nodes pb:pb1 =
(
local numThreads = 1 --sysInfo.cpuCount
local nodeArr = for o in nodes collect hcNode obj:o
qsort nodeArr sortByVertNum

while nodeArr.count > numThreads do (
local left = nodeArr[1]
local right = nodeArr[2]
deleteItem nodeArr 2
deleteItem nodeArr 1
local new = hcNode left:left right:right
insertInPlace nodeArr new start:1 end:nodeArr.count
)

local count = 0
for o in nodeArr do (
count += o.count
verts += o.verts
)
pbManager = progUpdater count:count pb:pb1

/*
local att = polyop.attach
for o in nodeArr do (
o.mergeChildren()
att source o.obj
)
*/

global hcTreeMonitor = treeMonitor roots:nodeArr source:source

global hcMergeWorkers = #()
for i = 1 to numThreads do (
local newWorker = dotnetObject "System.ComponentModel.BackGroundWorker"
dotNet.addEventHandler newWorker "DoWork" hcMergeTreeFN
append hcMergeWorkers newWorker
while hcTreeMonitor.occupied do ()
newWorker.RunWorkerAsync()
)
)


fn customAttach source nodes pb:pb1 =
(
count = nodes.count

foo source nodes pb:pb1

source
)

plastic
05-29-2011, 01:05 PM
I found that every operation that affects scene nodes crashes max, when used in a backgoundworker.

I tried to go multithreded but ran into some problems..
If I run it with more then 1 thread max crashes and it's very unstable as it is with 1.
I saw some discussions about the backgroundworker where it was mentioned that some mxs functions won't work with it, I guess attach is one of them.
here is my attempt:

struct progUpdater (
count,
current = 0,
pb,

fn increment =
(
current += 1
pb.value = 100 * current / count
)
)

global pbManager

struct hcNode (
val = 0,
left,
right,
obj,
count = 1,
verts = 0,

fn init =
(
if obj != undefined then
val = obj.numVerts
else (
if left != undefined then (
val += left.val
val += right.val
verts = left.verts + right.verts + left.val + right.val
count = left.count + right.count
)
)
),

fn mergeChildren =
(
local att = polyop.attach

if left != undefined then (
local a = left.mergeChildren()
local b = right.mergeChildren()
left = undefined
right = undefined
att a b
obj = a
verts += val
) else
pbManager.increment()

obj
),

start = init()
)

fn sortByVertNum a b =
(
a.val - b.val
)

fn insertInPlace arr new start: end: =
(
if end - start < 0 then
append arr new
else if end - start == 0 then (
if arr[start].val > new.val then
insertItem new arr start
else
insertItem new arr (start + 1)
) else (
local i = amin (start + (end - start) / 2) (end - 1)

if arr[i].val > new.val then
insertInPlace arr new start:start end:i
else if arr[i].val < new.val then
insertInPlace arr new start:(i + 1) end:end
else
insertItem new arr i
)
)

struct treeMonitor (
roots,
next = 0,
count = 0,
source,
occupied = false,

fn getRoot =
(
next += 1
occupied = false
roots[next]
),

fn mergeRoots =
(
local att = polyop.attach

for o in roots do
att source o.obj
),

fn done =
(
count += 1
if count == roots.count then
mergeRoots()
redrawViews()
)
)

global hcMergeTreeFN
fn hcMergeTreeFN =
(
global hcTreeMonitor
if hcTreeMonitor != undefined then (
hcTreeMonitor.occupied = true
local root = hcTreeMonitor.getRoot()
root.mergeChildren()
hcTreeMonitor.done()
)
)

fn foo source nodes pb:pb1 =
(
local numThreads = 1 --sysInfo.cpuCount
local nodeArr = for o in nodes collect hcNode obj:o
qsort nodeArr sortByVertNum

while nodeArr.count > numThreads do (
local left = nodeArr[1]
local right = nodeArr[2]
deleteItem nodeArr 2
deleteItem nodeArr 1
local new = hcNode left:left right:right
insertInPlace nodeArr new start:1 end:nodeArr.count
)

local count = 0
for o in nodeArr do (
count += o.count
verts += o.verts
)
pbManager = progUpdater count:count pb:pb1

/*
local att = polyop.attach
for o in nodeArr do (
o.mergeChildren()
att source o.obj
)
*/

global hcTreeMonitor = treeMonitor roots:nodeArr source:source

global hcMergeWorkers = #()
for i = 1 to numThreads do (
local newWorker = dotnetObject "System.ComponentModel.BackGroundWorker"
dotNet.addEventHandler newWorker "DoWork" hcMergeTreeFN
append hcMergeWorkers newWorker
while hcTreeMonitor.occupied do ()
newWorker.RunWorkerAsync()
)
)


fn customAttach source nodes pb:pb1 =
(
count = nodes.count

foo source nodes pb:pb1

source
)

MatanH
05-29-2011, 01:18 PM
what if we could attach the trimesh values of the objects in a backgroundworker and when they are done create a new poly from that trimesh value?

lo
05-29-2011, 01:30 PM
what if we could attach the trimesh values of the objects in a backgroundworker and when they are done create a new poly from that trimesh value?

I've tried going down this route, but I could not get meshop.attach to successfully attach two trimeshes without one of them being a node. Is it possible?

edit: scratch that, I was operating on the mesh itself and not a copy of it.

MatanH
05-29-2011, 01:57 PM
found a way! (but still not so stable)

struct progUpdater (
count,
current = 0,
pb,

fn increment =
(
current += 1
pb.value = 100 * current / count
)
)

global pbManager

struct hcNode (
val = 0,
left,
right,
obj,
count = 1,
verts = 0,

fn init =
(
if obj != undefined then
val = obj.numVerts
else (
if left != undefined then (
val += left.val
val += right.val
verts = left.verts + right.verts + left.val + right.val
count = left.count + right.count
)
)
),

fn mergeChildren =
(
local att = meshop.attach

if left != undefined then (
local a = left.mergeChildren()
local b = right.mergeChildren()
left = undefined
right = undefined
att a b
obj = a
verts += val
) else
pbManager.increment()

obj
),

start = init()
)

fn sortByVertNum a b =
(
a.val - b.val
)

fn insertInPlace arr new start: end: =
(
if end - start < 0 then
append arr new
else if end - start == 0 then (
if arr[start].val > new.val then
insertItem new arr start
else
insertItem new arr (start + 1)
) else (
local i = amin (start + (end - start) / 2) (end - 1)

if arr[i].val > new.val then
insertInPlace arr new start:start end:i
else if arr[i].val < new.val then
insertInPlace arr new start:(i + 1) end:end
else
insertItem new arr i
)
)

struct treeMonitor (
roots,
next = 0,
count = 0,
source,
occupied = false,

fn getRoot =
(
next += 1
occupied = false
roots[next]
),

fn mergeRoots =
(
local att = meshop.attach

for o in roots do
att source o.obj

source = mesh mesh:source
convertTo source Editable_Poly
),

fn done =
(
count += 1
if count == roots.count then
mergeRoots()
redrawViews()
)
)

global hcMergeTreeFN
fn hcMergeTreeFN =
(
global hcTreeMonitor
if hcTreeMonitor != undefined then (
hcTreeMonitor.occupied = true
local root = hcTreeMonitor.getRoot()
root.mergeChildren()
hcTreeMonitor.done()
)
)

fn foo source nodes pb:pb1 =
(
local numThreads = 10 --sysInfo.cpuCount
local nodeArr = #()
for o in nodes do (
append nodeArr (hcNode obj:(snapshotAsMesh o))
delete o
)
qsort nodeArr sortByVertNum

while nodeArr.count > numThreads do (
local left = nodeArr[1]
local right = nodeArr[2]
deleteItem nodeArr 2
deleteItem nodeArr 1
local new = hcNode left:left right:right
insertInPlace nodeArr new start:1 end:nodeArr.count
)

local count = 0
for o in nodeArr do (
count += o.count
verts += o.verts
)
pbManager = progUpdater count:count pb:pb1

global hcTreeMonitor = treeMonitor roots:nodeArr source:(snapshotAsMesh source)
delete source

for i = 1 to numThreads do (
local newWorker = dotnetObject "System.ComponentModel.BackGroundWorker"
dotNet.addEventHandler newWorker "DoWork" hcMergeTreeFN
while hcTreeMonitor.occupied do ()
newWorker.RunWorkerAsync()
)

hcTreeMonitor.source
)

fn customAttach source nodes pb:pb1 =
(
count = nodes.count

foo source nodes pb:pb1
)

lo
05-29-2011, 02:01 PM
Interestingly enough, about 60% of the execution time when doing the whole thing with meshes, is the conversion back to poly in the end.

lo
05-29-2011, 07:36 PM
I've managed to get some scene interaction with background worker, by disabling ref messages.
Perhaps this could be used towards the attach algorithm.

Example:

workers = #()

fn createBox = box()

fn complete s e =
(
deleteItem workers (findItem workers s)
if workers.count==0 do enablerefmsgs()
)

disablerefmsgs()

for i = 1 to 8 do
(
local worker = dotnetObject "System.ComponentModel.BackGroundWorker"
dotNet.addEventHandler worker "DoWork" createBox
dotnet.addeventhandler worker "RunWorkerCompleted" complete
append workers worker
worker.RunWorkerAsync()
)
result: 8 boxes created, max doesn't crash :)

plastic
05-29-2011, 07:46 PM
very cool, I will test this with modifier operations...

I've managed to get some scene interaction with background worker, by disabling ref messages.
Perhaps this could be used towards the attach algorithm.

Example:

workers = #()

fn createBox = box()

fn complete s e =
(
deleteItem workers (findItem workers s)
if workers.count==0 do enablerefmsgs()
)

disablerefmsgs()

for i = 1 to 8 do
(
local worker = dotnetObject "System.ComponentModel.BackGroundWorker"
dotNet.addEventHandler worker "DoWork" createBox
dotnet.addeventhandler worker "RunWorkerCompleted" complete
append workers worker
worker.RunWorkerAsync()
)
result: 8 boxes created, max doesn't crash :)

lo
05-29-2011, 10:23 PM
Seems this is still quite unstable and doesn't work for all commands.

denisT
05-30-2011, 07:39 AM
i think that any max scene change or max UI change can be done in the same as application thread only. that means there is no way to do these operations using multithreading.

denisT
06-07-2011, 04:54 PM
Here is a time to show my variant of fast attach. I call it "Caster" (don't ask me why).
My idea is to have as less as possible number of updates. The ideal algorithm has to attach every time the nodes with minimum number of vertices. So we have to sort the node array every time before attach.
QSORT is very slow if we do it for every iteration of the loop. I'm using .net Sort (sorting second array using first as keys).
Also I don't use deleteItem (which is also slow for big arrays).
I'm using GetHandleByAnim (to make .net array) and GetAnimByHandle (to speed up access to node's pointer in an array).

As you can see my algorithm works much faster in situation where we have to attach small boxes to one high-poly box. Without sorting the cluster method has the similar problem as the max Linear method.

check the code and play with parameters...

MatanH
06-09-2011, 10:30 AM
Here is an optimized version of my version without the multithreading stuff.
It does the same thing Denis's casterAttach method do but without the need of sorting the array (with or without dotnet's help) every time and it looks like it works at the same speed if not a bit faster then the caster method.

The idea is taken from the Huffman code algorithm. At first I sort the objects once by vertex count, then I take the first 2 objects in the sorted array, attach them and delete them from the array. Now I use the insertInPlace function to insert a new object created from the 2 attached objects in it's correct place in the array using a binary search technique. I repeat these steps until the array holds only 1 object. I also make sure I remember which object was originally the source to make sure it doesn't get deleted.

Anyhow Denis's method is still very cool and I learned some new stuff from it, tanks for that!

fn sortByVertNum a b =
(
a.val - b.val
)

struct s_Node (
obj,
val,
isSource = false,

fn init =
(
val = obj.numVerts
),

start = init()
)

fn insertInPlace arr new start: end: =
(
if end - start < 0 then
append arr new
else if end - start == 0 then (
if arr[start].val > new.val then
insertItem new arr start
else
insertItem new arr (start + 1)
) else (
local i = amin (start + (end - start) / 2) (end - 1)

if arr[i].val > new.val then
insertInPlace arr new start:start end:i
else if arr[i].val < new.val then
insertInPlace arr new start:(i + 1) end:end
else
insertItem new arr i
)
)

fn huffmanAttach source nodes pb:pb1 =
(
nodes = for o in nodes collect s_Node obj:o
append nodes (s_Node obj:source isSource:true)
qsort nodes sortByVertNum
local att = polyop.attach
local n = nodes.count

while nodes.count > 1 do (
if nodes[2].isSource then
swap nodes[1] nodes[2]
att nodes[1].obj nodes[2].obj
local newNode = s_Node obj:nodes[1].obj isSource:nodes[1].isSource
deleteItem nodes 2
deleteItem nodes 1
insertInPlace nodes newNode start:1 end:nodes.count

pb.value = 100.0 * (1.0 - 1.0 * nodes.count / n)
verts += newNode.val
)
)

fn customAttach source nodes pb:pb1 =
(
count = nodes.count

huffmanAttach source nodes pb:pb1

source
)

denisT
06-09-2011, 04:38 PM
well... the Party Of Math Lovers won. :)
http://forums.cgsociety.org/showthread.php?f=98&t=985724

denisT
06-09-2011, 04:40 PM
wrong place for the post

CGTalk Moderation
06-09-2011, 04:40 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.